Teorema di Cantor: differenze tra le versioni

Versione delle 19:16, 7 ott 2020

Versione attuale delle 22:40, 5 feb 2024

(17 versioni intermedie di 11 utenti non mostrate)

Riga 1:

{{F|matematica|luglio 2017}}

In [[matematica]], e in particolare nella [[teoria degli insiemi di Zermelo - Fraenkel]] (ZF), il '''teorema 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>.

:<math>|\mathcal P(A)| > |A|.</math>

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]].

La relazione che lega la cardinalità di <math>\mathcal P(A)</math> con quella di <math>\mathcal P(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.

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]].

IlNel verocaso ein propriocui teorema<math>A</math> disia Cantorun specificainsieme checon questacardinalità proprietànumerabile, deglisotto insiemil'[[ipotesi finitidel noncontinuo]], siil estinguesuo quandoinsieme ladelle loroparti è un insieme con cardinalità divienenon 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>, spessocioè definita comela [[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>.

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à.

La cardinalità di <math>A</math> è <math>n</math>. La cardinalità di <math>\mathcal P(A)</math> corrisponde al numero di sottoinsiemi impropri generabili a partire dagli elementi di <math>A</math>, che risulta essere <math>2^n</math>. Di conseguenza il teorema vale, dato che <math>2^n > n, \ \forall n \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> nell'insieme delle parti dia <math>\mathcal P(A)</math>:

Sia <math>f</math> una generica funzione da <math>A</math> nell'insieme delle parti di <math>A</math>:

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

Per provare il teorema si deve mostrare che <math>f</math> è necessariamente non [[Funzione suriettiva|suriettiva]]. A tal fine è sufficiente individuare un elemento di <math>\mathcal P(A)</math> che non è nell'immagine di <math>f</math>. Questo elemento è:

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

:<math>B=\left\{x\in A : x\not\in f(x)\right\} \in \mathcal P(A).</math> . (Notare che se B è vuoto la dimostrazione continua a essere valida)

Per dimostrare che <math>B</math> non è nell'immagine di <math>f</math>, si suppone per assurdo che lo sia. Per qualche <math>y\in A</math>, si ha allora <math>f(y) = B</math>. Si considerano ora i due casi possibili:

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

Se :<math>yB=\left\{x\in A : x\not\in B = f(yx)</math> allora per la definizione di <math>B</math> si ha <math>y\right\} \in B\mathcal P(A).</math>, assurdo.

Tale sottoinsieme avrà come elementi costitutivi tutti gli elementi appartenenti ad <math>A</math>, che però non appartengono al sottoinsieme di cui sono [[controimmagine]].

Se <math>y \in B = f(y)</math> allora per la definizione di <math>B</math> si ha <math>y \not\in B</math>, assurdo.

InSupponiamo entrambiper iassurdo casiquindi, siche ottieneesista una contraddizione. Quindifunzione <math>Af</math> esuriettiva il suo insieme potenza non sono equipotenti. In particolare, la cardinalità dell'insieme delle parti dida <math>A</math> è maggiore della cardinalità dia <math>\mathcal P(A)</math> perché(e lache funzionequindi ogni elemento di <math>g\colon A \to \mathcal P(A)</math> definitaabbia comecontroimmagine in <math>g(a)=\{a\}A</math> è chiaramente iniettiva).

Necessariamente ci sarà un qualche valore <math>\xi \in A</math> la cui funzione <math>f(\xi)</math> sarà uguale a <math>B</math> . Ci sono ora due casi possibili:

Per una trattazione della tecnica di dimostrazione usata da Cantor si veda la voce [[argomento diagonale di Cantor]].

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

Allora si giunge alla seguente contraddizione:

:<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</math> tale che <math>f(\xi) = B</math>.

Ossia, <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>. <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/>

== Voci correlate ==

Line 32 ⟶ 56:

* [[Georg Cantor]]

* [[Paradosso dell'ipergioco]]

== Altri progetti ==

{{interprogetto|preposizione=sul}}

== Collegamenti esterni ==

Line 39 ⟶ 66:

[[Categoria:Teoria degli insiemi]]

[[Categoria:Teoremi di matematica|Cantor]]