Conjunto de potencia

Conjunto de potencia

Los elementos del conjunto potencia de { x , y , z } ordenados con respecto a la inclusión .
Tipo	Operación establecida
Campo	Teoría de conjuntos
Declaración	El conjunto potencia es el conjunto que contiene todos los subconjuntos de un conjunto dado.
Declaración simbólica	${\displaystyle x\en P(S)\iff x\subseteq S}$

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

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

• {} (también denotado como o , el conjunto vacío o el conjunto nulo)${\displaystyle \varnothing}$${\displaystyle \conjunto vacío}$
• { x }
• { y }
• { y }
• { 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 la cardinalidad | S | = n (es decir, el número de todos los elementos en el conjunto S es n ), entonces el número de todos los subconjuntos de S es | P ( S ) | = 2 ⁿ . Este hecho, así como la razón de la notación 2 ^S 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 la 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 ⁿ . Como el número 2 se puede definir como {0, 1} (ver, por ejemplo, los ordinales de von Neumann ), P ( S ) también se denota como 2 ^S . Obviamente , | 2 ^S | = 2 ^{| S |} se cumple. En términos generales, X ^Y es el conjunto de todas las funciones desde Y hasta X y | X ^Y | = | X | ^{| Y |} .

El argumento diagonal de Cantor muestra que el conjunto potencia de un conjunto (sea infinito o no) siempre tiene una cardinalidad estrictamente mayor que la del propio conjunto (o, informalmente, el conjunto potencia debe ser mayor que el conjunto original). En particular, el teorema de Cantor muestra que el conjunto potencia de un conjunto infinito numerable es infinito incontable . El conjunto potencia del conjunto de números naturales puede ponerse en correspondencia biunívoca con el conjunto de 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 una Σ-álgebra sobre S y puede considerarse como el ejemplo prototípico de un álgebra de Boole . De hecho, se puede demostrar que cualquier álgebra de Boole finita es isomorfa al álgebra de Boole del conjunto potencia de un conjunto finito. Para las álgebras de Boole infinitas , esto ya no es cierto, pero cada álgebra de Boole infinita puede representarse como una subálgebra de un álgebra de Boole de conjuntos 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 identidad y cada conjunto siendo su propio inverso), y un monoide conmutativo cuando se considera con la operación de intersección (con todo el conjunto S como elemento identidad). Se puede demostrar, por tanto, mediante la demostración de 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 desde Y hasta X . Como " 2 " se puede definir como {0, 1} (ver, por ejemplo, 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 de potencias de S , P ( S ) , se consideran idénticos en 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 , siendo n 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 tal como { x , y } = 011 ₍₂₎ ; x de S se ubica 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 la posición de este 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:

Una aplicación inyectiva de este tipo de P ( S ) a los números 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 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 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 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 binomial está estrechamente relacionado con el conjunto potencia. Una combinación de k elementos de un 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 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 singleton),
• C(3, 2) = 3 subconjuntos con 2 elementos (los complementos de los subconjuntos singleton),
• C(3, 3) = 1 subconjunto con 3 elementos (el propio conjunto original).

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

Por 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 una 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 singleton cuyo único elemento es el conjunto vacío.
• Para un conjunto no vacío S , 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 cuyo cada elemento se expande con el elemento e .${\estilo de visualización 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 a κ 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 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 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, nuevamente ordenado por inclusión, es siempre un retículo algebraico , y todo retículo algebraico surge como el retículo de subálgebras de algún álgebra. Por lo tanto, 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. En primer lugar, 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 en esa clase, aunque siempre se pueden organizar como un retículo. 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 ambas es relativamente raro. Una clase que tiene ambas es la de los multigrafos . Dados dos multigrafos G y H , un homomorfismo h  : G → H consiste en 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 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 grafo de G al multigrafo Ω definible como el grafo dirigido completo en dos vértices (de ahí cuatro aristas, es decir, dos bucles propios y dos aristas más que forman un ciclo) aumentado con una quinta arista, es decir, un segundo bucle propio 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 de origen (inicio) y destino (fin) de cada arista. Un álgebra cuyas operaciones son 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. Una clase de este tipo es un caso especial de la noción más general de topos elementales como una categoría que es cerrada (y además cartesianamente cerrada ) y tiene un objeto Ω , llamado clasificador de subobjetos . Aunque el término "objeto de potencia" a veces se usa como sinónimo de objeto exponencial Y ^X , en la teoría de topos se requiere que Y sea Ω .

Hay un funtor de conjunto potencia covariante y contravariante , P : Set → Set y P : Set ^op → Set . El funtor covariante se define de forma más sencilla. como el funtor que envía un conjunto S a P ( S ) y un morfismo f : S → T (aquí, una función entre conjuntos) al morfismo 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 funtor de conjunto potencia contravariante es diferente de la versión covariante en que envía f al morfismo pre imagen, de modo que si . Esto se debe a que un funtor general toma un morfismo a precomposición por h , por lo que una función , que toma morfismos de b a c y los lleva a morfismos de a a c , a través de b mediante h . ^[4]${\displaystyle A=\{x_{1},x_{2},...\}\in {\mathsf {P}}(S),{\mathsf {P}}f(A)=\{f(x_{1}),f(x_{2}),...\}\in {\mathsf {P}}(T)}$${\displaystyle {\overline {\mathsf {P}}}\cong {\text{Conjunto}}(-,2)}$${\displaystyle f(A)=B\subseteq T,{\overline {\mathsf {P}}}f(B)=A}$${\displaystyle {\text{C}}(-,c)}$${\displaystyle h:a\rightarrow b}$${\displaystyle h^{*}:C(b,c)\rightarrow C(a,c)}$

En la teoría de categorías y la teoría de topos elementales , el cuantificador universal puede entenderse como el adjunto derecho de un funtor entre conjuntos potencia, el funtor imagen inversa de una función entre conjuntos; asimismo, el cuantificador existencial es el adjunto izquierdo . ^[5]

• Teorema de Cantor
• Familia de conjuntos
• Campo de conjuntos
• Combinación

• 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 . The University Series in Undergraduate Mathematics. Van Nostrand Company. Zbl  0087.04403.
• Mac Lane, Saunders ; Moerdijk, Ieke (1992), Haces 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 desde el original el 2023-04-06 . Consultado el 2020-09-05 .

Busque conjunto de potencia en Wikcionario, el diccionario libre.

• Conjunto de potencias en PlanetMath .
• Conjunto de potencias en el laboratorio n
• Objeto de potencia en el laboratorio n
• Algoritmo de conjunto de potencias en C++