Conjunto potencia

En matemáticas, dado un conjunto S, el conjunto potencia o conjunto de partes de S, escrito P(S) o 2^S, es el conjunto de todos los subconjuntos de S. En la teoría de conjuntos basada en los Axiomas de Zermelo-Fraenkel, la existencia del conjunto potencia se establece por el axioma del conjunto potencia.

Por ejemplo, si S= {a, b, c} entonces la lista completa de subconjuntos de S es como sigue:

1. { } (conjunto vacío);
2. {a};
3. {b};
4. {c};
5. {a, b};
6. {a, c};
7. {b, c};
8. {a, b, c};

y por lo tanto el conjunto potencia de S es

P(S) = {{ }, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Otro ejemplo más complejo es el siguiente: Sea A = { 2 , Ф }, Determinar P ( P(A) ); Ф es el conjunto vacío:

Primero hacemos:

P(A) = { Ф, {2}, {Ф}, A }

y luego hacemos P ( P(A) ) :

P ( P(A) ) = { Ф ,

{ Ф } , { {2} } , { {Ф} } , { {A} },

{ Ф, {2} } , { Ф, {Ф} } , { Ф, {A} }, { {2} , {Ф} } , { {2} , {A} } , { {Ф}, A },

{ Ф, {2}, {Ф} } , { Ф, {2}, A }, { Ф, {Ф}, A }, { {2}, {Ф}, A }

y P(A) }

Cuando S es finito, si n = |S| es el número de elementos de S, en este caso 3, entonces el respectivo conjunto potencia contiene |P(S)| = 2ⁿ elementos, en este caso $2^{3}=8$. En este caso también se puede establecer una biyección entre los elementos del conjunto potencia con números de n-bits: el n-ésimo bit se refiere a la presencia o ausencia del n-ésimo elemento de S. Hay 2ⁿ tales números.

Este argumento prueba la identidad de coeficientes binomiales:

${n \choose 0}+{n \choose 1}+{n \choose 2}+\cdots +{n \choose n}=2^{n}$

La cardinalidad de un conjunto potencia siempre es mayor que la cardinalidad del conjunto base, el argumento diagonal de Cantor demuestra la afirmación para conjuntos infinitos, mientras que el hecho de que n < 2ⁿ la prueba para conjuntos finitos.

El conjunto potencia de los números naturales, por ejemplo, se puede poner en correspondencia uno a uno con el conjunto de números reales. Usualmente se establece primero una biyección entre los números reales y el intervalo cerrado [0,1], para luego, usando la expansión diádica de los números reales, identificar cada elemento de [0,1] con la sucesión infinita de ceros y unos dada por los coeficientes.

El conjunto potencia 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 potencia 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 2^S

En teoría de conjuntos, X^Y es el conjunto de todas las funciones de Y a X. Como 2 puede ser definido como {0, 1} (véase número natural), 2^S es el conjunto de todas las funciones de S a {0, 1}. Cada función en 2^S está en correspondencia biyectiva con un subconjunto de S (la antiimagen de 1) por lo que se establece una equivalencia de conjuntos entre 2^S y P(S)

Implementación en Python

Esta implementación del algoritmo para obtener un conjunto potencia de una colección dada:

def addTo(e, t):	
	for s in t:
		s += [e]
	return t
	
def powerSet(a_set):
	if not a_set: return [[]]
	e = a_set[0]
	t = a_set[1:]
	return powerSet(t) + addTo(e, powerSet(t))

La cual puede ser probada ejecutando luego:

a = [1,2,3]

print powerSet(a)

Y la respuesta será:

[[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]]

Demostración por inducción del cardinal del conjunto potencia de S cuando S es finito

Sea S un conjunto finito con n elementos (|S|=n) entonces |P(S)|=$2^{n}$

Demostración

Caso base n=0

Sea S el conjunto vacío, entonces |S| = 0 y P(S) = {$\emptyset$}

Supongamos cierto si |S|=m y m es menor o igual que n, entonces |P(S)|=$2^{m}$

Sea |S' |=n+1

S' = {$a_{0},a_{1},...,a_{n-1},a_{n}$}

Por tanto

S' = {$a_{0},a_{1},...,a_{n-1}$} U {$a_{n}$}

Sea |S|== {$a_{0},a_{1},...,a_{n-1}$}

entonces

S' = S U {$a_{n}$}

Tenemos que

P(S' ) = P(S U {$a_{n}$}) = P(S) U {P' U {$a_{n}$} / P' $\in$ P(S)}

Dado que ambos conjuntos son disjuntos tenemos que:

|P(S' )| = |P(S) U {P' U {$a_{n}$} / P' $\in$ P(S)}| = |P(S)| + |{P' U {$a_{n}$} / P' $\in$ P(S)}| = $2^{n}$ + $2^{n}$ = $2^{n+1}$