Teorema di Cantor: differenze tra le versioni

Versione delle 19:38, 21 ago 2021

Versione delle 20:06, 27 mar 2022

Riga 1:

{{F|matematica|luglio 2017}}

In [[matematica]], e in particolare nella [[teoria degli insiemi di Zermelo - Fraenkel]] (ZF), il '''teoremaTeorema di Cantor''', sviluppato dall'omonimo matematico tedesco [[Georg Cantor]], è un teorema che afferma che per ogni insieme <math>A</math>, di qualsiasi [[cardinalità]] arbitraria (finita o infinita), il suo [[insieme delle parti]] <math>\mathcal P(A)</math> ha sempre cardinalità strettamente maggiore.

:<math>\mathrm{card(|\mathcal P(A))}| > \mathrm{card(|A)}|</math>

La relazione che lega la cardinalità di <math>\mathcal P(A)</math> con quella di <math>A</math> è espressa dalla disequazione <math>|A| < 2^{\aleph_0|A|} > \aleph_0</math>. In particolare, l'insieme delle parti di un insieme numerabile (o non numerabile) è un insieme non numerabile.

Per quanto riguarda gli insiemi finiti, il teorema di Cantor si dimostra semplicemente enumerando gli elementi dei due insiemi e confrontandone la cardinalità. La cardinalità di <math>A</math> è <math>n</math>. La cardinalità di <math>\mathcal P(A)</math>, contando l'insieme vuoto <math>\varnothing</math> e <math>A</math> stesso come sottoinsiemi di <math>A</math>, vale <math>2^n</math>. Di conseguenza il teorema vale, perché <math>2^n > n</math> per ogni [[Intero positivo|intero non negativo]]. Il vero e proprio teorema di Cantor specifica che questa proprietà degli insiemi finiti non si estingue quando la loro cardinalità diviene infinita. Come conseguenza importante, si ha che l'insieme delle parti dei [[Numero naturale|numeri naturali]] <math>\mathcal P(\N)</math>, dove <math>\N</math> è un [[Insieme numerabile|infinito numerabile]] con cardinalità <math>\aleph_0 = \mathrm{card(\N)}</math>, è un infinito non numerabile, con cardinalità uguale alla cardinalità dei [[Numero reale|numeri reali]] <math>\R</math>, spesso definita come [[cardinalità del continuo]].

PerNel quantocaso riguardain gli insiemi finiti, il teorema di Cantor si dimostra semplicemente enumerando gli elementi dei due insiemi e confrontandone la cardinalità. La cardinalità dicui <math>A</math> èsia <math>n</math>.un Lainsieme con cardinalità di <math>\mathcal P(A)</math>numerabile, contandosotto l'insieme vuoto <math>\varnothing</math> e <math>A</math> stesso come sottoinsiemi di <math>A</math>, vale <math>2^n</math>. Di conseguenza il teorema vale, perché <math>2^n > n</math> per ogni [[InteroIpotesi positivo|interodel non negativocontinuo]]., Ilil verosuo el'insieme propriodelle teoremaparti diè Cantorun specificainsieme checon questa proprietà degli insiemi finiticardinalità non si estingue quando la loro cardinalità diviene infinitanumerabile. Come conseguenza importante, si ha che l'insieme delle parti dei [[Numero naturale|numeri naturali]] <math>\mathcal P(\N)</math>, dove <math>\N</math> è un [[Insieme numerabile|infinito numerabile]] con cardinalità <math>\aleph_0 = \mathrm{card(\N)}</math>, è un infinito non numerabile, con cardinalità uguale alla cardinalità dei [[Numero reale|numeri reali]] <math>\R</math>, spesso definita come [[cardinalità del continuo]].

La relazione che lega la cardinalità di <math>\mathcal P(A)</math> con quella di <math>A</math> è espressa dalla disequazione <math>2^{\aleph_0} > \aleph_0</math>. In particolare, l'insieme delle parti di un insieme numerabile (o non numerabile) è un insieme non numerabile.

Il teorema di Cantor ha avuto un impatto immediato e importante sulla [[filosofia della matematica]]. Ad esempio, nell'applicare iterativamente l'insieme delle parti di un insieme infinito e successivamente il teorema di Cantor, otteniamo una gerarchia infinita di cardinalità infinite, ognuna strettamente maggiore della precedente. Di conseguenza, il teorema implica che non esiste una cardinalità massima per un dato insieme., Dio conseguenzaequivalentemente, che i livelli gerarchici delle cardinalità infinite sono anch'esseessi infiniteinfiniti.<ref>{{Cita libro|autore=Marco Bramanti|autore2=Pagani Carlo Domenico|autore3=Sandro Salsa|titolo=Analisi Matematica 1}}</ref>

== Dimostrazione ==

Il teorema si divide in due casi, in base alla cardinalità di <math>A</math>.

Per definizione di cardinalità, abbiamo <math>\mathrm{card(X)} < \mathrm{card(\bar{X})}</math> per due insiemi generici <math>X</math> e <math>\bar{X}</math>, se e solo se ogni funzione da <math>X</math> a <math>\bar{X}</math> non è suriettiva (o equivalentemente ogni funzione iniettiva non è anche suriettiva).

Se la cardinalità di <math>A</math> è finita, il teorema di Cantor si dimostra semplicemente enumerando gli elementi dei due insiemi e confrontandone la cardinalità.

Di conseguenza, è sufficiente dimostrare che non c'è [[suriezione]] da <math>X</math> a <math>\bar{X}</math>. Questo è il cuore del teorema di Cantor: non esiste una funzione suriettiva da un insieme al suo insieme delle parti. Per dimostrarlo, basta far vedere che non è possibile per una funzione <math>f</math> mappare tutti gli elementi di un insieme qualsiasi <math>A</math> a tutti i sottoinsiemi generati dall'insieme delle parti <math>\mathcal P(A)</math>.

QuindiLa dobbiamocardinalità dimostraredi l'esistenza<math>A</math> diè un<math>n</math>. elementoLa incardinalità di <math>\mathcal P(A)</math> checorrisponde nonal ènumero contenutodi nell'immaginesottoinsiemi impropri generabili a partire dagli elementi di <math>fA</math>, (Ogniche risulta essere <math>f(x)2^n</math>. èDi sottoinsiemeconseguenza diil teorema vale, dato che <math>A2^n > n, \ \forall x \in \N</math>).

Se la cardinalità di <math>A</math> è infinita, presi due insiemi generici <math>X</math> e <math>S</math>, per definizione stessa di cardinalità abbiamo che <math>|X| < |S|</math> se e solo se tutte le funzioni da <math>X</math> a <math>S

</math> non sono suriettive (o equivalentemente ogni funzione iniettiva non è anche suriettiva).

Basta far vedere che non esiste una funzione <math>f</math> capace di mappare ''tutti'' gli elementi di un insieme qualsiasi <math>A</math> a tutti gli elementi di <math>\mathcal P(A)</math>.

Sia <math>f</math> una generica funzione da <math>A</math> a <math>\mathcal P(A)</math>:

:<math>f\colon A \to \mathcal P(A).</math>

Un sottoinsieme con le proprietà appena descritte è dato dalla seguente costruzione, chiamatoderivato dall'[[argomento diagonale di Cantor]].

:<math>B=\left\{x\in A : x\not\in f(x)\right\} \in \mathcal P(A).</math>

Supponiamo per assurdo quindi, che esista una funzione <math>f</math> suriettiva da <math>A</math> a <math>\mathcal P(A)</math> (e che quindi ogni elemento di <math>\mathcal P(A)</math> abbia controimmagine in <math>A</math>).

Per costruzione, ci sarà qualche valore particolare di <math>\xi \in A</math>, si ha allora <math>f(\xi) = B</math>. SiCi consideranosono ora i due casi possibili:

:<math>\xi \not\in B</math> oppure <math>\xi \in B.</math>

Allora si giunge alla seguente contraddizione:

Allora:

<math>\begin{aligned}
\xi \in f(\xi) &\iff \xi \in B && \text{(dall'assunzione che }f(\xi)=B\text{)}; \\

\xi\in B &\iff \xi\notin f(\xi) && \text{(per definizione di }B\text{)}.\end{aligned}</math>

Quindi non esiste un valore <math>\xi \in A : f(\xi) = B</math>.

Si ha quindi una contraddizione. Quindi non esiste un valore <math>\xi \in A : f(\xi) = B</math>. In altre parole, <math>B</math> non è nell'immagine di <math>f</math>, e <math>f</math> non mappa a tutti gli elementi di <math>\mathcal P(A)</math>, e quindi <math>f</math> non è suriettiva. Per completare il teorema non resta che trovare una funzione iniettiva <math>g\colon A \to \mathcal P(A).</math> Questa funzione è molto semplice ed è definita come la funzione che mappa <math>x</math> all'insieme contenente solamente <math>x</math>.

:<math>g(x)=\{x\}</math>

La dimostrazione è terminata, in quanto abbiamo stabilito la diseguaglianza stretta per ogni insieme <math>A</math> tale che <math>\mathrm{card(\mathcal P(A))} > \mathrm{card(A)}</math>

Si ha quindi una contraddizione. Quindi non esiste un valore <math>\xi \in A : f(\xi) = B</math>. In altre paroleOssia, <math>B</math> non è nell'immagine di <math>f</math>, e <math>f</math> non mappa a tutti gli elementi di <math>A</math> in <math>\mathcal P(A)</math>, e quindi. <math>f</math> non è suriettiva. Per completare il teorema non resta che trovare una funzione iniettiva <math>g\colon A \to \mathcal P(A).</math> Questa funzione è molto semplice ed è definita come la funzione identità che mappa <math>x</math> all'insieme contenente solamente <math>x</math> stesso.

:<math>g(x)=\{x\}</math>

== Note ==

<references/>

Riga 45 ⟶ 51:

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Portale|matematica}}