Conjunto de partes
Keywords: Conjunto de partes, Bit, Cardinal, Complemento de un conjunto, Conjunto, Conjunto infinito, Conjunto vacío, Función biyectiva, Función matemática
En matemáticas, dado un conjunto S, el conjunto de partes de S, escrito P(S) o 2S, es el conjunto de todos los subconjuntos de S. En el lenguaje formal, la existencia del conjunto de partes de un conjunto es presupuesta por el axioma del conjunto de partes. Por ejemplo, si S es el conjunto {A, B, C} entonces la lista completa de subconjuntos de S es como sigue:
- { } (conjunto vacío);
- {A};
- {B};
- {C};
- {A, B};
- {A, C};
- {B, C};
- {A, B, C};
y por lo tanto el conjunto de partes de S es
- P(S) = {{ }, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}}.
Si n = |S| es el número de elementos de S, entonces el respectivo conjunto de partes contiene |P(S)| = 2n elementos. Se puede —y las computadoras lo hacen realmente— representar los elementos P(S) como números de n-bits; el n-ésimo bit se refiere a la presencia o ausencia del n-ésimo elemento de S. Hay 2n tales números.
Uno puede también considerar el conjunto de partes de los conjuntos infinitos. El argumento diagonal de Cantor demuestra que el conjunto de partes de un conjunto (infinito o no) tiene siempre cardinal más alto estrictamente que el conjunto mismo, el conjunto de partes es siempre "mayor" que el conjunto original. El conjunto de partes de los números naturales, por ejemplo, se puede poner en correspondencia uno a uno con el conjunto de números reales (identificando una secuencia infinita de 0-1 con el conjunto de los índices donde ocurren los 1).
El conjunto de partes de un conjunto S, junto con las operaciones de la unión, de la intersección y del complemento forman el ejemplo prototípico de álgebra de Boole. De hecho, uno puede demostrar que cualquier álgebra de Boole finita es isomorfa al álgebra booleana del conjunto de partes de un conjunto finito. Para las álgebras booleanas infinitas esto no es verdad, pero cada álgebra booleana infinita es subálgebra de una álgebra booleana de partes.
La notación 2S
En teoría de conjuntos, XY es el conjunto de todas las funciones de Y a X. Como 2 puede ser definido como {0, 1} (véase número natural), 2S es el conjunto de todas las funciones de S a {0, 1}. Identificando una función en 2S con la antiimagen de 0 correspondiente, vemos que hay biyección entre 2S y P(S), entonces 2S y P(S) se podrían considerar iguales en teoría de conjuntos.