^^Il nr di sottoinsiemi di N elementi e' 2N.

Teo: |P(X)| = 2|X| .

nm:

Per questo motivo si indica P(X) ≡ 2X, per poter scrivere:  |2X| = 2|X|

che fa felice gli amanti della forma estetica, anche se ha un minimo di utilita' memo.

 

L'idea per la dim

funzione caratteristica di un sottoinsieme

vale 1 sul sottoinsieme e 0 fuori

A⊆X  fA:X→{0,1}

         fA(x)=1 se x∈A

         fA(x)=0 se x∉A

sottoinsieme e sua funzione caratteristica sono in corrispondenza biunivoca.

 

Teo: 

l'insieme delle parti e' in corrispondenza biunivoca con

  • lo spazio funzionale delle funzioni a valori binari.

  • i numeri binari lunghi quanto l'ordine dell'insieme
 

P(X) ↔ F(X→{0,1})
subX ↔ f:X→{0,1}

dim: Lo dico per gli elementi, siccome sono qualsiasi, vale per tutti, e quindi per lo spazio.

f:{a,b,c}→{0,1} generica funzione dello spazio funzionale F({a,b,c},{0,1})

Lg:

P(X) ↔ F(X→{0,1})   cr espressa sugli insiemi
subX ↔ f:X→{0,1}    cr espressa sugli elementi