Potenza impostata - Power set

Gli elementi dell'insieme delle potenze di { x , y , z } ordinati rispetto all'inclusione .

In matematica , l' insieme delle potenze (o insieme delle potenze ) di un insieme $S$ è l'insieme di tutti i sottoinsiemi di $S$ , compreso l' insieme vuoto e $S$ stesso. Nella teoria degli insiemi assiomatica (come sviluppata, ad esempio, negli assiomi ZFC ), l'esistenza dell'insieme delle potenze di qualsiasi insieme è postulata dall'assioma dell'insieme delle potenze . Il powerset di $S$ è variamente indicato come $P (S)$ , $𝒫 (S)$ , $P (S)$ , , $℘ ($ $S$ $)$ (usando la " Weierstrass p "), o $2$ $S$ . La notazione $2$ $S$ , che significa l'insieme di tutte le funzioni da S a un dato insieme di due elementi (es. {0, 1}), è usata perché l'insieme delle potenze di $S$ può essere identificato con, equivalente a, o biunivoco all'insieme di tutte le funzioni da $S$ al dato insieme di due elementi. $\mathbb {P} (S)$

Qualsiasi sottoinsieme di $P (S)$ è chiamato famiglia di insiemi su $S$ .

Esempio

Se $S$ è l'insieme ${x, y, z}$ , allora tutti i sottoinsiemi di $S$ sono

${}$ (denotato anche o , l' insieme vuoto o l'insieme nullo) $\varnothing$ ${\displaystyle\emptyset}$
${x}$
${e}$
${z}$
${x, y}$
${x, z}$
${y, z}$
${x, y, z}$

e quindi l'insieme delle potenze di $S$ è ${{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}$ .

Proprietà

Se $S$ è un insieme finito con cardinalità $| S | = n$ (cioè il numero di tutti gli elementi dell'insieme $S$ è $n$ ), allora il numero di tutti i sottoinsiemi di $S$ è $| P (S)| = 2 n$ . Questo fatto così come il motivo della notazione $2 S che$ denota l'insieme di potenze $P (S)$ sono dimostrati nel seguito.

Una funzione indicatrice o una funzione caratteristica di un sottoinsieme A di un insieme S con cardinalità | S | = n è una funzione da S all'insieme dei due elementi {0, 1}, indicata come I _A : S → {0, 1}, e indica se un elemento di S appartiene ad A oppure no; Se x in S appartiene ad A , allora I _A ( x ) = 1 e 0 altrimenti. Ciascun sottoinsieme A di S è identificato da o equivalente alla funzione indicatrice I _A , e {0, 1} ^S come l'insieme di tutte le funzioni da S a {0, 1} è costituito da tutte le funzioni indicatrici di tutti i sottoinsiemi di s . In altre parole, {0, 1} ^S è equivalente o biunivoco all'insieme delle potenze

P (S)

. Poiché ogni elemento in S corrisponde a 0 o 1 sotto qualsiasi funzione in {0, 1} ^S , il numero di tutte le funzioni in {0, 1} ^S è 2 ⁿ . Poiché il numero 2 può essere definito come

{0,1}

(vedi, ad esempio, ordinali di von Neumann ), anche la

P (S)

è indicata come

2 S

. Ovviamente

| 2 S | = 2 | S |

tiene. In generale, X ^Y è l'insieme di tutte le funzioni da Y a X e | X ^Y | = | X | ^{| Y |}.

L'argomento diagonale di Cantor mostra che l'insieme delle potenze di un insieme (che sia infinito o meno) ha sempre una cardinalità strettamente maggiore dell'insieme stesso (o informalmente, l'insieme delle potenze deve essere più grande dell'insieme originale). In particolare, teorema di Cantor mostra che l'insieme potenza di un infinito numerabile insieme è numerabile infinito. L'insieme delle potenze dell'insieme dei numeri naturali può essere posto in corrispondenza biunivoca con l'insieme dei numeri reali (vedi Cardinalità del continuum ).

L'insieme delle potenze di un insieme $S$ , insieme alle operazioni di unione , intersezione e complemento , può essere visto come l'esempio prototipico di un'algebra booleana . Infatti, si può dimostrare che qualsiasi algebra booleana finita è isomorfa all'algebra booleana dell'insieme delle potenze di un insieme finito. Per infinite algebre booleane, questo non è più vero, ma ogni infinita algebra booleana può essere rappresentata come una sottoalgebra di un insieme di potenze algebra booleana (vedi teorema di rappresentazione di Stone ).

L'insieme delle potenze di un insieme $S$ forma un gruppo abeliano se considerato con l'operazione di differenza simmetrica (con l'insieme vuoto come elemento di identità e ogni insieme essendo il proprio inverso), e un monoide commutativo se considerato con l'operazione di intersezione . Si può quindi dimostrare, dimostrando le leggi distributive , che l'insieme di potenze considerato insieme ad entrambe queste operazioni forma un anello booleano .

Rappresentare sottoinsiemi come funzioni

In teoria degli insiemi , $X Y$ è la notazione che rappresenta l'insieme di tutte le funzioni da $Y$ a $X$ . Poiché "2" può essere definito come ${0,1}$ (vedi, ad esempio, ordinali di von Neumann ), $2 S$ (cioè ${0,1} S$ ) è l'insieme di tutte le funzioni da $S$ a ${0,1}$ . Come mostrato sopra , $2 S$ e l'insieme di potenza di $S$ , $P (S)$ , è considerato identico in teoria.

Questa equivalenza può essere applicata all'esempio sopra , in cui $S = {x, y, z}$ , per ottenere l' isomorfismo con le rappresentazioni binarie dei numeri da 0 a $2 n - 1$ , dove $n$ è il numero di elementi nell'insieme $S$ o $| S | = n$ . Innanzitutto, viene definito l'insieme enumerato ${ (x, 1), (y, 2), (z, 3) }$ in cui il numero in ciascuna coppia ordinata rappresenta la posizione dell'elemento accoppiato di $S$ in una sequenza di cifre binarie come come ${x, y} = 011 (2)$ ; $x$ di $S$ si trova al primo da destra di questa sequenza e $y$ è al secondo da destra, e 1 nella sequenza significa che l'elemento di $S$ corrispondente alla sua posizione nella sequenza esiste nel sottoinsieme di $S$ per la sequenza mentre 0 significa che non lo fa.

Per l'intero insieme di potenze di $S$ , otteniamo:

sottoinsieme	Sequenza di cifre binarie	Interpretazione binaria	Equivalente decimale
${ }$	$0, 0, 0$	$000 (2)$	$0 (10)$
${x}$	$0, 0, 1$	$001 (2)$	$1 (10)$
${e}$	$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)$

Tale mappatura biunivoca da $P (S)$ a interi è arbitraria, quindi questa rappresentazione di tutti i sottoinsiemi di $S$ non è unica, ma l'ordinamento dell'insieme enumerato non cambia la sua cardinalità. (Ad esempio, ${ (y, 1), (z, 2), (x, 3) }$ può essere usato per costruire un altro biunivoco da $P (S)$ agli interi senza cambiare il numero di corrispondenze uno a uno.)

Tuttavia, tale rappresentazione binaria finita è possibile solo se S può essere enumerato. (In questo esempio, $x$ , $y$ e $z$ sono enumerati rispettivamente con 1, 2 e 3 come posizione delle sequenze di cifre binarie.) L'enumerazione è possibile anche se $S$ ha una cardinalità infinita (cioè il numero di elementi in $S$ è infinito), come l'insieme degli interi o dei razionali, ma non è possibile ad esempio se S è l'insieme dei numeri reali, nel qual caso non possiamo enumerare tutti i numeri irrazionali.

Relazione con il teorema binomiale

Il teorema del binomio è strettamente correlato all'insieme delle potenze. Una combinazione di $k$ -elementi da un insieme è un altro nome per un sottoinsieme di $k$ -elementi, quindi il numero di combinazioni , indicato come $C(n, k)$ (chiamato anche coefficiente binomiale ) è un numero di sottoinsiemi con $k$ elementi in un insieme con $n$ elementi; in altre parole è il numero di insiemi con $k$ elementi che sono elementi dell'insieme delle potenze di un insieme con $n$ elementi.

Ad esempio, l'insieme di potenza di un insieme con tre elementi, ha:

C(3, 0) = 1 sottoinsieme con 0 elementi (il sottoinsieme vuoto),
C(3, 1) = 3 sottoinsiemi con 1 elemento (i sottoinsiemi singleton),
C(3, 2) = 3 sottoinsiemi con 2 elementi (i complementi dei sottoinsiemi singleton),
C(3, 3) = 1 sottoinsieme con 3 elementi (l'insieme originale stesso).

Usando questa relazione, possiamo calcolare usando la formula: ${\textstyle \left|2^{S}\right|}$

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

Pertanto, si può dedurre la seguente identità, assumendo : ${\textstyle |S|=n}$

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

Definizione ricorsiva

Se è un insieme finito , allora una definizione ricorsiva di procede come segue: $S$ $P(S)$

Se , allora . $S=\{\}$ $P(S)=\{\,\{\}\,\}$
Altrimenti, let e ; allora . $e\in S$ $T=S\setminus \{e\}$ $P(S)=P(T)\cup \{t\cup \{e\}:t\in P(T)\}$

In parole:

L'insieme di potenza dell'insieme vuoto è un singleton il cui unico elemento è l'insieme vuoto.
Per un insieme non vuoto , sia un qualsiasi elemento dell'insieme e il relativo complemento ; allora l'insieme di potenze di è un'unione di un insieme di potenze di e un insieme di potenze di cui ogni elemento è espanso con l' elemento. $S$ $e$ $T$ $S$ $T$ $T$ $e$

Sottoinsiemi di cardinalità limitata

L'insieme di sottoinsiemi di $S$ di cardinalità inferiore o uguale a $κ$ è talvolta indicato con $P κ (S)$ o $[S] κ$ , e l'insieme dei sottoinsiemi con cardinalità strettamente minore di $κ$ è talvolta denotati $P <κ (S)$ o $[S] <κ$ . Allo stesso modo, l'insieme dei sottoinsiemi non vuoti di $S$ potrebbe essere indicato con $P \geq 1 (S)$ o $P + (S)$ .

Oggetto di potere

Un insieme può essere considerato come un'algebra che non ha operazioni non banali o che definisce equazioni. Da questo punto di vista, l'idea dell'insieme delle potenze di $X$ come insieme dei sottoinsiemi di $X si$ generalizza naturalmente alle sottoalgebre di una struttura algebrica o algebra.

L'insieme delle potenze di un insieme, quando ordinato per inclusione, è sempre un'algebra booleana atomica completa, e ogni algebra booleana atomica completa nasce come reticolo di tutti i sottoinsiemi di un insieme. La generalizzazione alle algebre arbitrarie è che l'insieme delle sottoalgebre di un'algebra, sempre ordinato per inclusione, è sempre un reticolo algebrico , e ogni reticolo algebrico nasce come reticolo delle sottoalgebre di qualche algebra. Quindi, a questo proposito, le sottoalgebre si comportano in modo analogo ai sottoinsiemi.

Tuttavia, ci sono due importanti proprietà dei sottoinsiemi che non vengono trasferite alle sottoalgebre in generale. Primo, sebbene i sottoinsiemi di un insieme formino un insieme (così come un reticolo), in alcune classi potrebbe non essere possibile organizzare le sottoalgebre di un'algebra come se stesse un'algebra in quella classe, sebbene possano sempre essere organizzate come reticolo. In secondo luogo, mentre i sottoinsiemi di un insieme sono in biiezione con le funzioni da quell'insieme all'insieme {0,1} = 2, non vi è alcuna garanzia che una classe di algebre contenga un'algebra che possa svolgere il ruolo di 2 in questo modo .

Alcune classi di algebre godono di entrambe queste proprietà. La prima proprietà è più comune, il caso di avere entrambe è relativamente raro. Una classe che ha entrambi è quella dei multigrafi . Dati due multigrafi $G$ e $H$ , un omomorfismo $h : G \to H$ consiste di due funzioni, una che mappa i vertici ai vertici e l'altra che mappa gli archi agli archi. L'insieme $H G$ degli omomorfismi da $G$ ad $H$ può allora essere organizzato come il grafo i cui vertici e archi sono rispettivamente le funzioni vertice e arco che compaiono in quell'insieme. Inoltre, i sottografi di un multigrafo $G$ sono in biiezione con gli omomorfismi di grafi da $G$ al multigrafo $Ω$ definibili come il grafo orientato completo su due vertici (quindi quattro archi, cioè due self-loop e altri due archi che formano un ciclo) aumentati con un quinto spigolo, cioè un secondo self-loop in corrispondenza di uno dei vertici. Possiamo quindi organizzare i sottografi di $G$ come il multigrafo $Ω G$ , detto oggetto potenza di $G$ .

La particolarità di un multigrafo come algebra è che le sue operazioni sono unarie. Un multigrafo ha due tipi di elementi che formano un insieme $V$ di vertici ed $E$ di spigoli, e ha due operazioni unarie $s, t : E \to V che$ danno i vertici sorgente (inizio) e destinazione (fine) di ciascun bordo. Un'algebra le cui operazioni sono tutte unarie si chiama prefascio . Ogni classe di prefasci contiene un prefascio $Ω$ che svolge il ruolo per le sottoalgebre che 2 svolge per i sottoinsiemi. Tale classe è un caso particolare del concetto più generale di elementari topos come categoria che è chiusa (e inoltre cartesiano chiusi ) e ha un oggetto $Ω$ , chiamato classificatore subobject . Sebbene il termine "oggetto di potere" sia talvolta usato come sinonimo di oggetto esponenziale $Y X$ , nella teoria dei topos $Y$ è richiesto che sia $Ω$ .

Funtori e quantificatori

Nella teoria delle categorie e nella teoria dei topoi elementari , il quantificatore universale può essere inteso come il giusto aggiunto di un funtore tra insiemi di potenze, il funtore immagine inverso di una funzione tra insiemi; allo stesso modo, il quantificatore esistenziale è l' aggiunto sinistro .

Guarda anche

Riferimenti

Bibliografia

Devlin, Keith J. (1979). Fondamenti di teoria degli insiemi contemporanea . Universitesto. Springer-Verlag . ISBN 0-387-90441-7. Zbl 0407.04003 .
Halmos, Paul R. (1960). Teoria degli insiemi ingenua . La serie universitaria in matematica universitaria. van Nostrand Company. Zbl 0087.04403 .
Puntambekar, AA (2007). Teoria degli automi e dei linguaggi formali . Pubblicazioni tecniche. ISBN 978-81-8431-193-8.

Languages

In other projects