En matemáticas , el conjunto potencia (o conjunto potencia ) de un conjunto S es el conjunto de todos los subconjuntos de S , incluido el conjunto vacío y el propio S. [1] En la teoría de conjuntos axiomática (tal como se desarrolla, por ejemplo, en los axiomas de ZFC ), la existencia del conjunto potencia de cualquier conjunto se postula mediante el axioma del conjunto potencia . [2] El conjunto de potencias de S se denota de diversas formas como P ( S ) , 𝒫 ( S ) , P ( S ) , , o 2 S . La notación 2 S , que significa el conjunto de todas las funciones desde S hasta un conjunto dado de dos elementos (por ejemplo, {0, 1} ), se utiliza porque el conjunto potencia de S puede identificarse con el conjunto potencia de S, es equivalente o biyectivo. conjunto de todas las funciones desde S hasta el conjunto de dos elementos dado. [1]
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
y por 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 ) | = 2 norte . Este hecho, así como el motivo de la notación 2 S que denota el conjunto de potencias P ( S ) , se demuestran a continuación.
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 mismo (o informalmente, el conjunto de potencias debe ser mayor que el conjunto original). En particular, el teorema de Cantor muestra que el conjunto potencia de un conjunto contablemente infinito es incontablemente infinito. El conjunto potencia del conjunto de números naturales se puede poner en correspondencia uno a uno con el conjunto de números reales (ver Cardinalidad del continuo ).
El conjunto potencia de un conjunto S , junto con las operaciones de unión , intersección y complemento , puede verse como el ejemplo prototípico de á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 cada álgebra booleana infinita se puede representar como una subálgebra de un álgebra booleana de conjunto de potencias (consulte 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 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, demostrando las leyes distributivas , que el conjunto de potencias 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 " se puede definir 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 desde S hasta {0, 1} . Como se muestra arriba, 2 S y el conjunto potencia de S , P ( S ) , se consideran conjuntos idénticos en teoría.
Esta equivalencia se puede aplicar al ejemplo anterior, en el que S = { x , y , z } , para obtener el isomorfismo con las representaciones binarias de números del 0 al 2 n − 1 , siendo n el número de elementos del conjunto S o | S | = norte . 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 tal como { x , y } = 011 (2) ; 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.
Para todo el conjunto de potencias de S , obtenemos:
Tal mapeo inyectivo de P ( S ) a números enteros es arbitrario, por lo que esta representación de todos los subconjuntos de S no es única, pero el orden del conjunto enumerado no cambia su cardinalidad. (Por ejemplo, {( y , 1), ( z , 2), ( x , 3) } se puede utilizar para construir otra aplicación inyectiva de P ( S ) a los números enteros sin cambiar el número de correspondencias uno a uno. )
Sin embargo, dicha representación binaria finita sólo 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 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 números enteros o racionales, pero no es posible, por ejemplo, si S es el conjunto de números reales, en cuyo caso no podemos enumerar todos los números irracionales.
El teorema del binomio está estrechamente relacionado con el conjunto de potencias. Una combinación de k elementos de algún conjunto es otro nombre para un subconjunto de k elementos, por lo que el número de combinaciones , denotado como C( n , k ) (también llamado coeficiente binomial ) es un número de subconjuntos con k elementos en un conjunto con norte 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 de tres elementos, tiene:
Usando esta relación, podemos calcular | 2 S | usando la fórmula:
Por lo tanto, se puede deducir la siguiente identidad, suponiendo | S | = norte :
Si S es un conjunto finito , entonces una definición recursiva de P ( S ) procede de la siguiente manera:
En palabras:
El conjunto de subconjuntos de S de cardinalidad menor o igual a κ a veces se denota por P κ ( S ) o [ S ] κ , y el conjunto de subconjuntos con cardinalidad estrictamente menor que κ a veces se denota 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 que no tiene operaciones no triviales ni ecuaciones definitorias. Desde esta perspectiva, la idea del conjunto potencia de X como el conjunto de subconjuntos de X se generaliza naturalmente a las subálgebras de una estructura algebraica o álgebra.
El conjunto potencia de un conjunto, cuando se ordena por inclusión, es siempre un álgebra booleana atómica completa, y cada álgebra booleana atómica completa surge como la red de todos los subconjuntos de algún conjunto. La generalización a álgebras arbitrarias es que el conjunto de subálgebras de un álgebra, nuevamente ordenadas por inclusión, es siempre una red algebraica , y cada red algebraica surge como la red de subálgebras de alguna álgebra. 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 trasladan a las subálgebras en general. Primero, aunque los subconjuntos de un conjunto forman un conjunto (así como una red), en algunas clases puede no ser posible organizar las subálgebras de un álgebra como un álgebra en esa clase, aunque siempre se pueden organizar como un conjunto. 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 ambas propiedades. La primera propiedad es más común; el caso de tener ambos es relativamente raro. Una clase que tiene ambas cosas es la de multigrafos . Dados dos multigrafos G y H , un homomorfismo h : G → H consta de dos funciones, una que asigna vértices a vértices y la otra que asigna aristas a aristas. 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 multigrafo G están en biyección con los homomorfismos de grafos de G al multigrafo Ω definible como el gráfico dirigido completo en dos vértices (por lo tanto, cuatro aristas, es decir, dos bucles propios y dos aristas más que forman un ciclo) aumentadas con un quinto borde, es decir, un segundo bucle automático en uno de los vértices. Por lo tanto , podemos organizar los subgrafos de G como el multigrafo Ω G , llamado objeto de 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 de origen (inicio) y destino (final) de cada arista. Un álgebra cuyas operaciones son todas unarias se llama presheaf . Cada clase de prehaz contiene un prehaz Ω que desempeña el papel para las subálgebras que 2 desempeña para los subconjuntos. Tal 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 ) y que tiene un objeto Ω , llamado clasificador de subobjetos . Aunque el término "objeto de potencia" se utiliza a veces como sinónimo de objeto exponencial Y X , en la teoría del topos Y se requiere que sea Ω .
Hay un functor de conjunto de potencias covariante y contravariante , P : Conjunto → Conjunto y P : Conjunto op → Conjunto . El functor covariante se define de forma más sencilla. como el functor que envía un conjunto S a P ( S ) y un morfismo f : S → T (aquí, una función entre conjuntos) al morfismo de la imagen. Es decir, para . En otra parte de este artículo, el conjunto potencia se definió como el conjunto de funciones de S en el conjunto con 2 elementos. Formalmente, esto define un isomorfismo natural . El functor de conjunto de potencias contravariante es diferente de la versión covariante en que envía f al morfismo previo a la imagen, de modo que if . Esto se debe a que un funtor general toma un morfismo para precomponer por h , por lo que es una función que toma morfismos de b a c y los lleva a morfismos de a a c , pasando por b vía h . [4]
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 funtor de imagen inversa de una función entre conjuntos; Asimismo, el cuantificador existencial es el adjunto izquierdo . [5]
