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 S en sí. [1] En la teoría de conjuntos axiomáticos (como se desarrolla, por ejemplo, en los axiomas ZFC ), la existencia del conjunto de potencias de cualquier conjunto es postulada por el axioma de conjunto de potencias . [2] El conjunto de potencias de S se denota de diversas formas como P ( S ), 𝒫 ( S ), [3] P ( S ) , ℙ ( S ) , ℘ ( S ) (utilizando el " Weierstrass p "), o 2 S . Seutiliza lanotación 2 S porque dado cualquier conjunto con exactamente dos elementos, el conjunto de potencias de S se puede identificar con el conjunto de todas las funciones de S en ese conjunto. [1]
Cualquier subconjunto de P ( S ) se llama una familia de conjuntos más de S .
Ejemplo
Si S es el conjunto { x , y , z } , entonces los subconjuntos de S son
- {} (también denotado o , el conjunto vacío o el conjunto nulo) [3]
- { x }
- { y }
- { z }
- { x , y }
- { x , z }
- { y , z }
- { x , y , z }
y por lo tanto, el conjunto de potencias de S es {{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }} . [4]
Propiedades
Si S es un conjunto finito con | S | = n elementos, entonces el número de subconjuntos de S es | P ( S ) | = 2 n . Este hecho, que es el motivo de la notación 2 S , puede demostrarse simplemente de la siguiente manera,
- Primero, ordene los elementos de S de cualquier manera. Escribimos cualquier subconjunto de S en el formato {γ 1 , γ 2 , ..., γ n } donde γ i , 1 ≤ i ≤ n , puede tomar el valor de 0 o 1 . Si γ i = 1 , el i -ésimo elemento de S está en el subconjunto; de lo contrario, el i -ésimo elemento no está en el subconjunto. Claramente, el número de subconjuntos distintos que se pueden construir de esta manera es 2 n como γ i ∈ {0, 1} .
El argumento diagonal de Cantor muestra que el conjunto de potencias de un conjunto (ya sea infinito o no) siempre tiene una cardinalidad estrictamente más alta que el conjunto en sí (o informalmente, el conjunto de potencias debe ser mayor que el conjunto original). En particular, el teorema de Cantor muestra que el conjunto de potencias de un conjunto infinito numerable es infinito incontable . El conjunto de potencias del conjunto de números naturales se puede poner en una correspondencia uno a uno con el conjunto de números reales (ver Cardinalidad del continuo ).
El conjunto de potencias de un conjunto S , junto con las operaciones de unión , intersección y complemento , puede verse como el ejemplo prototípico de un álgebra booleana . De hecho, se puede demostrar que cualquier finita álgebra de Boole es isomorfo al álgebra de Boole del conjunto potencia de un conjunto finito. Para álgebras booleanas infinitas , esto ya no es cierto, pero cada álgebra booleana infinita se puede representar como una subálgebra de un álgebra booleana de conjuntos de potencias (ver teorema de representación de Stone ).
El conjunto de potencias 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 de identidad y cada conjunto es su propio inverso), y un monoide conmutativo cuando se considera con la operación de intersección. Por tanto, se puede demostrar, al probar las leyes distributivas , que el conjunto de potencias considerado junto con ambas operaciones forma un anillo booleano .
Representar subconjuntos como funciones
En la teoría de conjuntos , X Y es el conjunto de todas las funciones de Y a X . Como "2" puede definirse como {0,1} (ver, 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} . Al identificar una función en 2 S con la correspondiente preimagen de 1 , vemos que hay una biyección entre 2 S y P ( S ), donde cada función es la función característica del subconjunto en P ( S ) con el que se identifica. . Por tanto, 2 S y P ( S ) podrían considerarse conjuntos idénticos en teoría. (Por tanto, hay dos motivaciones notacionales distintas para denotar el conjunto de potencias por 2 S : el hecho de que esta función-representación de subconjuntos lo convierte en un caso especial de la notación X Y y la propiedad, mencionada anteriormente , de que | 2 S | = 2 | S | .)
Esta noción se puede aplicar al ejemplo anterior , en el que S = { x , y , z } , para obtener el isomorfismo con los números binarios de 0 a 2 n - 1 , siendo n el número de elementos del conjunto. En S , un "1" en la posición correspondiente a la ubicación en el conjunto enumerado {( x , 0), ( y , 1), ( z , 2)} indica la presencia del elemento. Entonces { x , y } = 011 (2) .
Para todo el conjunto de potencias de S , obtenemos:
Subconjunto | Secuencia de dígitos | Interpretación binaria | Equivalente decimal |
---|---|---|---|
{} | 0, 0, 0 | 000 (2) | 0 (10) |
{ x } | 0, 0, 1 | 001 (2) | 1 (10) |
{ y } | 0, 1, 0 | 010 (2) | 2 (10) |
{ x , y } | 0, 1, 1 | 011 (2) | 3 (10) |
{ z } | 1, 0, 0 | 100 (2) | 4 (10) |
{ x , z } | 1, 0, 1 | 101 (2) | 5 (10) |
{ y , z } | 1, 1, 0 | 110 (2) | 6 (10) |
{ x , y , z } | 1, 1, 1 | 111 (2) | 7 (10) |
Tal mapeo biyectivo de S a enteros es arbitrario, por lo que esta representación de subconjuntos de S no es única, pero el orden de clasificación del conjunto enumerado no cambia su cardinalidad.
Sin embargo, tal representación binaria finita solo es posible si S se puede enumerar. Esto es posible incluso si S tiene una cardinalidad infinita, como el conjunto de números enteros o racionales, pero no, por ejemplo, si S es el conjunto de números reales, en cuyo caso no podemos enumerar todos los números irracionales para asignarles una ubicación finita definida en un conjunto ordenado.
Relación con el teorema del binomio
El conjunto de potencias está estrechamente relacionado con el teorema del binomio . El número de subconjuntos con k elementos en el conjunto de potencias de un conjunto con n elementos viene dado por el número de combinaciones , C ( n , k ) , también llamados coeficientes binomiales .
Por ejemplo, el conjunto de 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 singleton),
- C (3, 2) = 3 subconjuntos con 2 elementos (los complementos de los subconjuntos singleton),
- C (3, 3) = 1 subconjunto con 3 elementos (el conjunto original en sí).
Usando esta relación, podemos calcular usando la fórmula:
Por tanto, se puede deducir la siguiente identidad, asumiendo :
Definición recursiva
Si es un conjunto finito , luego una definición recursiva de procede de la siguiente manera:
- Si , luego .
- De lo contrario, deja y ; luego.
En palabras:
- El conjunto de potencia del conjunto vacío es un singleton cuyo único elemento es el conjunto vacío.
- Para un conjunto no vacío , dejar ser cualquier elemento del conjunto y su complemento relativo ; entonces el conjunto de poder dees una unión de un conjunto de poder de y un conjunto de poder de cuyo cada elemento se expande con el elemento.
Subconjuntos de cardinalidad limitada
El conjunto de subconjuntos de S de cardinalidad menor o igual que κ se denota a veces por P κ ( S ) o [ S ] κ , y el conjunto de subconjuntos con cardinalidad estrictamente menor que κ se denota a veces 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 ) .
Objeto de poder
Un conjunto puede considerarse como un álgebra que no tiene operaciones no triviales ni ecuaciones definitorias. Desde esta perspectiva, la idea del conjunto de poder de X como el conjunto de subconjuntos de X se generaliza naturalmente a las subálgebras de una estructura algebraica o álgebra.
El conjunto de potencias de un conjunto, cuando se ordena por inclusión, es siempre un álgebra atómica booleana completa, y cada álgebra atómica booleana completa surge como la red de todos los subconjuntos de algún conjunto. La generalización a las álgebras arbitrarias es que el conjunto de subálgebras de un álgebra, nuevamente ordenadas por inclusión, es siempre una retícula algebraica , y toda retícula algebraica surge como la retícula de subálgebras de alguna álgebra. Entonces, en ese sentido, las subálgebras se comportan de manera análoga a los subconjuntos.
Sin embargo, hay dos propiedades importantes de los subconjuntos que no se transfieren 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í mismo en esa clase, aunque siempre se pueden organizar como un enrejado. En segundo lugar, 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 disfrutan de estas dos propiedades. La primera propiedad es más común, el caso de tener ambos es relativamente raro. Una clase que tiene ambos es la de multigraphs . Dados dos multigrafos G y H , un homomorfismo h : G → H consta de dos funciones, una mapeando vértices a vértices y la otra mapeando bordes a bordes. El conjunto H G de homomorfismos de G a H puede entonces organizarse como el gráfico 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 multigraph G están en biyección con los homomorfismos del grafo de G al multigraph Ω definible como el grafo dirigido completo en dos vértices (por lo tanto, cuatro bordes, es decir, dos auto-bucles y dos bordes más que forman un ciclo) aumentados con un quinto borde, es decir, un segundo bucle automático en uno de los vértices. Por tanto, podemos organizar los subgrafos de G como el multigrafo Ω G , llamado el objeto de poder del G .
Lo que tiene de especial un multigraph 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 de origen (inicio) y destino (final) de cada arista. Un álgebra cuyas operaciones son unarias se llama presheaf . Cada clase de pre-ondas contiene una pre-gavilla Ω que desempeña el papel de subálgebras que desempeña 2 para los subconjuntos. Tal clase es un caso especial de la noción más general de topos elemental como una categoría que es cerrada (y además cartesiana cerrada ) y tiene un objeto Ω , llamado clasificador de subobjetos . Aunque el término "objeto de poder" a veces se usa como sinónimo de objeto exponencial Y X , en la teoría topográfica Y se requiere que sea Ω .
Functores y cuantificadores
En la teoría de categorías y la teoría de los topoi elementales , el cuantificador universal puede entenderse como el adjunto derecho de un funtor entre conjuntos de potencias, el functor de imagen inverso de una función entre conjuntos; asimismo, el cuantificador existencial es el adjunto izquierdo . [5]
Ver también
- Teorema de cantor
- Familia de conjuntos
- Campo de conjuntos
- Combinación
Referencias
- ^ a b Weisstein, Eric W. "Power Set" . mathworld.wolfram.com . Consultado el 5 de septiembre de 2020 .
- ^ Devlin 1979 , p. 50
- ^ a b "Lista completa de símbolos de la teoría de conjuntos" . Bóveda de matemáticas . 2020-04-11 . Consultado el 5 de septiembre de 2020 .
- ^ Puntambekar 2007 , págs. 1-2
- ^ Saunders Mac Lane , Ieke Moerdijk , (1992) Gavillas en geometría y lógica Springer-Verlag. ISBN 0-387-97710-4 Consulte la página 58
Bibliografía
- 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 de conjuntos ingenua . La Serie Universitaria en Matemáticas de Pregrado. van Nostrand Company. Zbl 0087.04403 .
- Puntambekar, AA (2007). Teoría de los autómatas y lenguajes formales . Publicaciones técnicas. ISBN 978-81-8431-193-8.
enlaces externos
- Energía establecida en PlanetMath .
- Potencia establecida en nLab
- Objeto de poder en nLab
- Algoritmo de conjunto de energía en C ++