Set de poder

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Conjunto matemático que contiene todos los subconjuntos de un conjunto dado

En matemáticas, la power set (o powerset) de un conjunto $S$ es el conjunto de todos los subconjuntos de $S$ , incluyendo el set vacío y $S$ en sí mismo. En la teoría de conjuntos axiomáticos (como se desarrolló, por ejemplo, en los axiomas ZFC), la existencia del conjunto de poder de cualquier conjunto es postulada por el axioma del conjunto de poder. La potencia de $S$ es denotado como $P () S)$ , $P(S)$ , $P () S)$ , ${displaystyle mathbb {P} (S)}$ , ${displaystyle wp (X)}$ , o $2 S$ . La notación $2 S$ , lo que significa que el conjunto de todas las funciones de S a un conjunto dado de dos elementos (por ejemplo, {0, 1}), se utiliza porque el conjunto de potencia de $S$ se puede identificar con, equivalente o bijetivo al conjunto de todas las funciones de $S$ a los dos elementos establecidos.

Cualquier subconjunto de $P (S)$ se llama una familia de conjuntos sobre $S$ .

Ejemplo

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

${}$ (también denotado) $varnothing$ o $empty$ , el conjunto vacío o el conjunto nulo)
${} x}$
${} Sí.}$
${} z}$
${} x, Sí.}$
${} x, z}$
${} Sí., z}$
${} x, Sí., z}$

y, por lo tanto, el conjunto de potencia de $S$ es ${{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}$ .

Propiedades

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

Función indicadora o función característica de un subconjunto A de un conjunto S con la cardinalidadSSilencio n es una función S a los dos elementos establecidos {0, 1}, denotados como I_A: S → {0, 1}, e indica si un elemento de S pertenece A o no; si x dentro S pertenece A, entonces I_A()x) = 1, y 0 de lo contrario. Cada subconjunto A de S se identifica por o equivalente a la función indicadora I_A, y ${0,1} S$ como conjunto de todas las funciones de S a ${0,1}$ consiste en todas las funciones indicadoras de todos los subconjuntos de S. En otras palabras, ${0,1} S$ es equivalente o bijetivo al conjunto de potencia $P () S)$ . Desde 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$ 2ⁿ. Puesto que el número 2 se puede definir como ${0,1}$ (ver, por ejemplo, los ordinals von Neumann), los $P () S)$ es también denotado como $2 S$ . Obviamente $Silencio 2 S Silencio = 2 Silencio S Silencio$ sostiene. En términos generales, X^Y es el conjunto de todas las funciones de Y a X y $Silencio X Y Silencio X Silencio Silencio Y Silencio$ .

El argumento de la diagonal de Cantor muestra que el conjunto potencia de un conjunto (sea infinito o no) siempre tiene una cardinalidad estrictamente mayor que el propio conjunto (o, de manera informal, el conjunto potencia 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 los números naturales se puede poner en una correspondencia biunívoca con el conjunto de los 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 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 las álgebras booleanas infinitas, esto ya no es cierto, pero cada álgebra booleana infinita puede representarse 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 el operación de diferencia simétrica (con el conjunto vacío como elemento de identidad y siendo cada conjunto su propio inverso), y un monoide conmutativo cuando se considera con la operación de intersección. Por tanto, puede demostrarse, demostrando las leyes distributivas, que el conjunto de potencias considerado junto con estas dos operaciones forma un anillo booleano.

Representación de subconjuntos como funciones

En la teoría de conjuntos, $XY$ 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 de potencia de S, P (S), se considera teóricamente un conjunto idéntico.$

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 del 0 al $2 n - 1$ , siendo $n$ el número de elementos en el conjunto $S$ o $| S| = n$ . Primero, el conjunto enumerado ${ (x, 1), (y, 2), (z, 3) }$ se define 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 (2); x de S está ubicado en el primero desde la derecha de esta secuencia y y está en el segundo desde la derecha, y 1 en la secuencia significa el elemento de S correspondiente a la posición del mismo en la secuencia existe en el subconjunto de S para la secuencia, mientras que 0 significa que no existe.$

Para todo el conjunto de potencia de $S$ , obtenemos:

Subset	Secuencia de dígitos binarios	binario interpretación	Decimal equivalente
${}$	$0, 0, 0$	$000 2)$	$0 (10)$
${} x}$	$0, 0, 1$	$001 2)$	$1 (10)$
${} Sí.}$	$0, 1, 0$	$010 2)$	$2 (10)$
${} x, Sí.}$	$0, 1, 1$	$011 2)$	$3 (10)$
${} z}$	$1, 0, 0$	$100 2)$	$4 (10)$
${} x, z}$	$1, 0, 1$	$101 2)$	$5 (10)$
${} Sí., z}$	$1, 0$	$110 2)$	$6 (10)$
${} x, Sí., z}$	$1, 1, 1$	$111 2)$	$7 (10)$

Este mapeo biyectivo de $P (S)$ a enteros es arbitrario, por lo que esta representación de todos los subconjuntos de $S$ no es único, 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 otro biyectivo de $P (S)$ a los números enteros sin cambiar el número de correspondencias uno a uno).

Sin embargo, tal representación binaria finita solo es posible si se puede enumerar S. (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.

Relación con el teorema del binomio

El teorema del binomio está estrechamente relacionado con el conjunto potencia. 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, indicado 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 elementos $k$ 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 de singleton),
C(3, 2) = 3 subconjuntos con 2 elementos (los complementos de los subconjuntos de un soloton),
C(3, 3) = 1 subconjunto con 3 elementos (el conjunto original).

Usando esta relación, podemos calcular ${textstyle left|2^{S}right|}$ usando la fórmula:

{displaystyle left|2^{S}right|=sum _{k=0}^{|S|}{binom {|S|}{k}}}

Por lo tanto, uno puede deducir la siguiente identidad, asumiendo ${textstyle |S|=n}$ :

{displaystyle left|2^{S}right|=2^{n}=sum _{k=0}^{n}{binom {n}{k}}}

Definición recursiva

Si $S$ es un conjunto finito, luego una definición recursiva de $P(S)$ de la siguiente manera:

Si ${displaystyle S={}}$ , entonces ${displaystyle P(S)={,{},}}$ .
De lo contrario, déjalo ${displaystyle ein S}$ y ${displaystyle T=Ssetminus {e}}$ ; entonces ${displaystyle P(S)=P(T)cup {tcup {e}:tin P(T)}}$ .

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 $S$ , vamos $e$ ser cualquier elemento del conjunto y $T$ su complemento relativo; entonces el conjunto de poder $S$ es una unión de un conjunto de poder $T$ y un conjunto de poder $T$ cuyo elemento se expande con el $e$ elemento.

Subconjuntos de cardinalidad limitada

El conjunto de subconjuntos de $S$ de cardinalidad menor o igual que $κ$ 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 indicarse mediante P \geq 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 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, de nuevo ordenadas por inclusión, es siempre un retículo algebraico, y cada retículo algebraico surge como el retículo de subálgebras de algún á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 trasladan 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 no ser posible organizar las subálgebras de un álgebra como un álgebra en sí misma en esa clase, aunque siempre pueden organizarse como un álgebra. 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 ambas es relativamente raro. Una clase que tiene ambos es la de los multigrafos. Dados dos multigrafos $G$ y $H$ , un homomorfismo $h : G \to H$ consta de dos funciones, una mapea vértices con vértices y la otra mapea bordes con bordes. El conjunto $H G$ de homomorfismos de $G$ a $H$ se puede organizar 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 del grafo de $G$ al multigrafo $Ω$ definible como el grafo dirigido completo en dos vértices (por lo tanto, cuatro aristas, es decir, dos bucles automáticos y dos aristas más que forman un ciclo) aumentados con un quinto borde, a saber, 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 poder 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 bordes, y tiene dos operaciones unarias $s, t : E \to V$ dando los vértices de origen (inicio) y destino (final) de cada borde. Un álgebra cuyas operaciones son todas unarias se llama pregavilla. Cada clase de pregavillas contiene una pregavilla $Ω$ que desempeña el papel de 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 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 topos $Y$ debe ser $Ω$ .

Funtores 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 potencia, el funtor imagen inversa de una función entre conjuntos; asimismo, el cuantificador existencial es el adjunto izquierdo.

Contenido relacionado

Clase de isomorfismo
Grupo trivial
En matemáticas, a grupo trivial o grupo cero es un grupo compuesto por un solo elemento. Todos estos grupos son isomorfos, así que a menudo se habla de el...
August Ferdinand Möbius
Más resultados...
Te puede interesar