Conjunto de potencia

En matemáticas , el conjunto potencia (o powerset ) de un conjunto S es el conjunto de todos los subconjuntos de S , incluyendo el conjunto vacío y el propio S. ^{[ 1 ]} En la teoría axiomática de conjuntos (como se desarrolla, por ejemplo, en los axiomas ZFC ), la existencia del conjunto potencia de cualquier conjunto se postula mediante el axioma de conjunto potencia . ^{[ 2 ]} El conjunto potencia de S se denota de diversas maneras como P ( S ) , 𝒫 ( S ) , P ( S ) ,${\displaystyle \mathbb {P} (S)}$, o 2 ^S . ^{[ a ]} ​​Cualquier subconjunto de P ( S ) se llama familia de conjuntos sobre S .

Si S es el conjunto { x , y , z } , entonces todos los subconjuntos de S son

• {} (el conjunto vacío , también denotado${\displaystyle \varnothing }$o${\displaystyle \emptyset }$)
• { x }
• { y }
• { z }
• { x , y }
• { x , z }
• { y , z }
• { x , y , z }

y por lo tanto el conjunto potencia de S es {{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }} . ^{[ 3 ]}

Si S es un conjunto finito con cardinalidad | S | = n (es decir, el número de todos los elementos del conjunto S es n ), entonces el número de todos los subconjuntos de S es | P ( S ) | = 2n ^. Este hecho, así como la razón de la notación 2S que denota el conjunto potencia P ( ^S ) , se demuestran a continuación.

Una función indicadora o una función característica de un subconjunto A de un conjunto S con cardinalidad | S | = n es una función de S al conjunto de dos elementos {0, 1} , denotada como I _A  : S → {0, 1} , e indica si un elemento de S pertenece a A o no; si x en S pertenece a A , entonces I _A ( x ) = 1 , y 0 en caso contrario. Cada subconjunto A de S se identifica por o es equivalente a la función indicadora I _A , y {0,1} ^S como el conjunto de todas las funciones de S a {0, 1} consta de todas las funciones indicadoras de todos los subconjuntos de S. En otras palabras, {0, 1} ^S es equivalente o biyectivo al conjunto potencia P ( S ) . Dado que cada elemento en S corresponde a 0 o 1 bajo cualquier función en {0, 1} ^S , el número de todas las funciones en {0, 1} ^S es 2 ⁿ . Dado que el número 2 puede definirse como {0, 1} (véase, por ejemplo, los ordinales de von Neumann ), P ( S ) ^también se denota como 2S . Obviamente , | 2S | = 2 ^{| S |} se cumple. En términos generales, XY es el conjunto de todas las ^{funciones de} Y a X y | XY | = | X | ^{| Y | .}

El argumento diagonal de Cantor demuestra que el conjunto potencia de un conjunto (sea infinito o no) siempre tiene una cardinalidad estrictamente mayor que la del conjunto original (o, dicho de otro modo, el conjunto potencia debe ser mayor que el conjunto original). En particular, el teorema de Cantor demuestra que el conjunto potencia de un conjunto infinito numerable es infinito no numerable . El conjunto potencia del conjunto de los números naturales puede establecerse en correspondencia biunívoca con el conjunto de los números reales (véase Cardinalidad del continuo ).

El conjunto potencia de un conjunto S , junto con las operaciones de unión , intersección y complemento , es un σ-álgebra sobre S y puede considerarse el ejemplo prototípico de un álgebra booleana . De hecho, se puede demostrar que cualquier álgebra booleana finita es isomorfa al álgebra booleana del conjunto potencia de un conjunto finito. Para álgebras booleanas infinitas , esto ya no es cierto, pero toda álgebra booleana infinita puede representarse como una subálgebra de un álgebra booleana de conjunto potencia (véase el teorema de representación de Stone ).

El conjunto potencia de un conjunto S forma un grupo abeliano cuando se considera con la operación de diferencia simétrica (con el conjunto vacío como elemento neutro y cada conjunto como su propio inverso), y un monoide conmutativo cuando se considera con la operación de intersección (con todo el conjunto S como elemento neutro). Por lo tanto, se puede demostrar, probando las leyes distributivas , que el conjunto potencia considerado junto con ambas operaciones forma un anillo booleano .

En teoría de conjuntos , X ^Y es la notación que representa el conjunto de todas las funciones de Y a X. Como " 2 " puede definirse como {0, 1} (véase, por ejemplo, los ordinales de von Neumann ), 2 ^S (es decir, {0, 1} ^S ) es el conjunto de todas las funciones de S a {0, 1} . Como se muestra arriba , 2 ^S y el conjunto potencia de S , P ( S ) , se consideran idénticos desde el punto de vista de la teoría de conjuntos.

Esta equivalencia se puede aplicar al ejemplo anterior , en el que S = { x , y , z } , para obtener el isomorfismo con las representaciones binarias de los números de 0 a 2 ⁿ − 1 , donde n es el número de elementos en el conjunto S o | S | = n . Primero, se define el conjunto enumerado { ( x , 1), ( y , 2), ( z , 3) ​​} en el que el número en cada par ordenado representa la posición del elemento emparejado de S en una secuencia de dígitos binarios como { x , y } = 011 ₍₂₎ ; x de S está ubicado en el primero desde la derecha de esta secuencia e y está en el segundo desde la derecha, y 1 en la secuencia significa que el elemento de S correspondiente a su posición en la secuencia existe en el subconjunto de S para la secuencia mientras que 0 significa que no existe.

Para todo el conjunto potencia de S , obtenemos:

Dicha aplicación inyectiva de P ( S ) a los enteros es arbitraria, por lo que esta representación de todos los subconjuntos de S no es única, pero el orden de clasificación del conjunto enumerado no cambia su cardinalidad. (Por ejemplo, {( y , 1), ( z , 2), ( x , 3)} se puede usar para construir otra aplicación inyectiva de P ( S ) a los enteros sin cambiar el número de correspondencias biyectivas).

Sin embargo, dicha representación binaria finita solo es posible si S puede enumerarse. (En este ejemplo, x , y y z se enumeran con 1 , 2 y 3 respectivamente como la posición de las secuencias de dígitos binarios). La enumeración es posible incluso si S tiene una cardinalidad infinita (es decir, el número de elementos en S es infinito), como el conjunto de los números enteros o racionales, pero no es posible, por ejemplo, si S es el conjunto de los números reales, en cuyo caso no podemos enumerar todos los números irracionales.

El teorema del binomio está estrechamente relacionado con el conjunto potencia. Una combinación de k elementos de un conjunto es sinónimo de subconjunto de k elementos, por lo que el número de combinaciones , denotado como C( n , k ) (también llamado coeficiente binomial ), es el número de subconjuntos con k elementos en un conjunto con n elementos; en otras palabras, es el número de conjuntos con k elementos que son elementos del conjunto potencia de un conjunto con n elementos.

Por ejemplo, el conjunto potencia de un conjunto con tres elementos tiene:

• C(3, 0) = 1 subconjunto con 0 elementos (el subconjunto vacío),
• C(3, 1) = 3 subconjuntos con 1 elemento (los subconjuntos unitarios),
• C(3, 2) = 3 subconjuntos con 2 elementos (los complementos de los subconjuntos unitarios),
• C(3, 3) = 1 subconjunto con 3 elementos (el conjunto original mismo).

Utilizando esta relación, podemos calcular | 2 ^S | usando la fórmula: $${\displaystyle \left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}}$$

Por lo tanto, se puede deducir la siguiente identidad, suponiendo | S | = n : $${\displaystyle \left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}}$$

Si S es un conjunto finito , entonces la definición recursiva de P ( S ) procede de la siguiente manera:

• Si S = {} , entonces P ( S ) = { {} } .
• De lo contrario, sea e ∈ S y T = S ∖ { e } ; entonces P ( S ) = P ( T ) ∪ { t ∪ { e }  : t ∈ P ( T )} .

En palabras:

• El conjunto potencia del conjunto vacío es un conjunto unitario cuyo único elemento es el conjunto vacío.
• Para un conjunto no vacío S , sea${\displaystyle e}$Sea cualquier elemento del conjunto y T su complemento relativo ; entonces el conjunto potencia de S es una unión de un conjunto potencia de T y un conjunto potencia de T cuyos elementos se expanden con el elemento e .

El conjunto de subconjuntos de S con cardinalidad menor o igual a κ se denota a veces por P _κ ( S ) o [ S ] ^κ , y el conjunto de subconjuntos con cardinalidad estrictamente menor que κ se denota a veces por P _{< κ} ( S ) o [ S ] ^{< κ} . De manera similar, el conjunto de subconjuntos no vacíos de S podría denotarse por P _≥1 ( S ) o P ⁺ ( S ) .

Un conjunto puede considerarse como un álgebra sin operaciones no triviales ni ecuaciones definitorias. Desde esta perspectiva, el concepto de conjunto potencia de X como el conjunto de todos los subconjuntos de X se generaliza naturalmente al conjunto de todas las subálgebras de una estructura algebraica o álgebra. ^{[ 4 ] [ 5 ]}

El conjunto potencia de un conjunto, cuando se ordena por inclusión, es siempre un álgebra booleana atómica completa, y toda álgebra booleana atómica completa surge como el retículo de todos los subconjuntos de algún conjunto. La generalización a álgebras arbitrarias es que el conjunto de subálgebras de un álgebra, ordenado nuevamente por inclusión, es siempre un retículo algebraico , y todo retículo algebraico surge como el retículo de subálgebras de alguna álgebra. ^{[ 6 ]} Así pues, en ese sentido, las subálgebras se comportan de forma análoga a los subconjuntos.

Sin embargo, existen dos propiedades importantes de los subconjuntos que no se aplican a las subálgebras en general. Primero, aunque los subconjuntos de un conjunto forman un conjunto (así como un retículo), en algunas clases puede que no sea posible organizar las subálgebras de un álgebra como un álgebra en sí misma dentro de esa clase, aunque siempre se pueden organizar como un retículo. Segundo, mientras que los subconjuntos de un conjunto están en biyección con las funciones de ese conjunto al conjunto {0, 1} = 2 , no hay garantía de que una clase de álgebras contenga un álgebra que pueda desempeñar el papel de 2 de esta manera.

Ciertas clases de álgebras poseen ambas propiedades. La primera es más común; el caso de tener ambas es relativamente raro. Una clase que sí las tiene es la de los multigrafos . Dados dos multigrafos G y H , un homomorfismo h  : G → H consta de dos funciones, una que mapea vértices a vértices y otra que mapea aristas a aristas. El conjunto H ^G de homomorfismos de G a H se puede organizar como el grafo cuyos vértices y aristas son, respectivamente, las funciones de vértice y arista que aparecen en ese conjunto. Además, los subgrafos de un multigrafo G están en biyección con los homomorfismos de grafos de G al multigrafo Ω definible como el grafo dirigido completo en dos vértices (por lo tanto, cuatro aristas, a saber, dos bucles y dos aristas más que forman un ciclo) aumentado con una quinta arista, a saber, un segundo bucle en uno de los vértices. Por lo tanto , podemos organizar los subgrafos de G como el multigrafo Ω ^G , llamado objeto potencia de G.

Lo especial de un multigrafo como álgebra es que sus operaciones son unarias. Un multigrafo tiene dos tipos de elementos que forman un conjunto V de vértices y E de aristas, y tiene dos operaciones unarias s , t  : E → V que dan los vértices origen (inicio) y destino (fin) de cada arista. Un álgebra cuyas operaciones son todas unarias se llama prehaz . Cada clase de prehaces contiene un prehaz Ω que desempeña para las subálgebras el papel que 2 desempeña para los subconjuntos. Dicha clase es un caso especial de la noción más general de topos elemental como una categoría cerrada (y además cartesiana cerrada ) que tiene un objeto Ω , llamado clasificador de subobjetos . Aunque el término "objeto potencia" se usa a veces como sinónimo de objeto exponencial Y ^X , en la teoría de topos se requiere que Y sea Ω . ^{[ 7 ]}

There is both a covariant and contravariant power set functor, P: Set → Set and P: Set ^op → Set. The covariant functor is defined more simply as the functor which sends a set S to P(S) and a morphism f: S → T (here, a function between sets) to the image morphism. That is, for A = {x₁, x₂, ...} ∈ P(S), Pf (A) = {f (x₁), f (x₂), ...} ∈ P(T). Elsewhere in this article, the power set was defined as the set of functions of S into the set with 2 elements. Formally, this defines a natural isomorphism P ≅ Set(-,2). The contravariant power set functor is different from the covariant version in that it sends f to the preimage morphism, so that if f (A) = B ⊆ T, Pf (B) = A. This is because a general functor C(-,c) takes a morphism h: a → b to precomposition by h, so a function h*: C(b,c) → C(a,c), which takes morphisms from b to c and takes them to morphisms from a to c, through b via h.^[8]

In category theory and the theory of elementary topoi, the universal quantifier can be understood as the right adjoint of a functor between power sets, the inverse image functor of a function between sets; likewise, the existential quantifier is the left adjoint.^[9]

• Cantor's theorem
• Family of sets
• Field of sets
• Combination
• Kleene star

• Devlin, Keith J. (1979). Fundamentos de la teoría de conjuntos contemporánea . Universitext. Springer-Verlag . ISBN 0-387-90441-7. Zbl 0407.04003 . 
• Halmos, Paul R. (1960). Teoría ingenua de conjuntos . The University Series in Undergraduate Mathematics. van Nostrand Company. Zbl 0087.04403 . 
• Mac Lane, Saunders ; Moerdijk, Ieke (1992), Haz en geometría y lógica , Springer-Verlag, ISBN 0-387-97710-4
• Puntambekar, AA (2007). Teoría de autómatas y lenguajes formales . Publicaciones técnicas. ISBN 978-81-8431-193-8.
• Weisstein, Eric W. "Conjunto de potencias" . mathworld.wolfram.com . Archivado del original el 6 de abril de 2023. Consultado el 5 de septiembre de 2020 .

• Conjunto de potencias en PlanetMath .
• Potencia establecida en el laboratorio n
• Objeto de energía en el laboratorio n
• Algoritmo del conjunto potencia en C++