Differenze tra le versioni di "Insieme delle parti"

m (Bot: Aggiungo: pms:Ansem potensa)
 
=== Insiemi finiti ===
Se ''S'' è un insieme finito con |''S''|=''n'' elementi, allora l'insieme delle parti di ''S'' contiene <math>|\mathcal{P}(S)| = 2^n</math> elementi. (Si può - come si fa abitualmente con i computer - rappresentare gli elementi di <math>\mathcal{P}(S)</math> come numeri a ''n'' bit; l'''n''-mo bit si riferisce alla presenza o all'assenza dell' ''n''-mo elemento di ''S''. Ci sono 2<sup>''n''</sup> di tali numeri.)
 
==== Dimostrazione ====
 
Quindi i sottoinsiemi di S sono in tutto <math>2^{n-1} + 2^{n-1} = 2 \cdot 2^{n-1} = 2^{n}</math>.
 
=== Rappresentazione dei sottoinsiemi mediante funzioni ===
 
C'è una corrispondenza biunivoca fra <math>\mathcal{P}(S)</math> e l'insieme delle funzioni <math>S \to \{0, 1\}</math>, corrispondenza che spiega la notazione <math>2^S</math> per <math>\mathcal{P}(S)</math>. La corrispondenza manda il sottoinsieme <math>A</math> di <math>S</math> nella sua [[funzione indicatrice]] <math>1_A</math>. La sua inversa manda una funzione <math>f : S \to \{0, 1\}</math> in <math>\{ x \in S : f(x) = 1 \}</math>.
 
Se <math>S</math> è un insieme finito con <math>n</math> elementi, è immediato che l'insieme di queste funzioni ha <math>2^n</math> elementi. Questo fornisce una dimostrazione alternativa del risultato appena visto.
 
=== Insiemi infiniti ===
382

contributi