Articles

9.3: il Teorema di Cantor e le Sue Conseguenze

sviluppo

  • Spiegare il teorema di Cantor

una Volta che Cantor ha dimostrato che c’erano due tipi di infinito (numerabili e non numerabili), la seguente domanda era naturale, “tutti numerabile di insiemi hanno la stessa cardinalità?”

Proprio come non tutti i” non-cani ” sono gatti, non c’è, fuori mano, alcun motivo per credere che tutti i set innumerevoli dovrebbero avere le stesse dimensioni. Tuttavia la costruzione di insiemi innumerevoli di diverse dimensioni non è così facile come sembra.

Ad esempio,per quanto riguarda il segmento di linea rappresentato dall’intervallo \(\) e il quadrato rappresentato dall’insieme \( × = \{(x,y)|0 ≤ x, y ≤ 1\}\). Certamente il quadrato bidimensionale deve essere un insieme infinito più grande del segmento di linea unidimensionale. Sorprendentemente, Cantor ha dimostrato che questi due set erano la stessa cardinalità. Nella sua corrispondenza del 1877 di questo risultato al suo amico e collega matematico, Richard Dedekind, anche Cantor osservò: “Lo vedo, ma non ci credo!”

figura 9.3.1.png

Figura \(\PageIndex{1}\): Richard Dedekind

Quanto segue fornisce l’idea originale della prova di Cantor. Cantor ha ideato la seguente funzione \(f:× → \). Innanzitutto, rappresentiamo le coordinate di qualsiasi punto \((x, y)××\) con le loro rappresentazioni decimali \(x = 0.a_1a_2a_3 …\ ) e \(y = 0.b_1b_2b_3….\ ) Anche i decimali terminanti possono essere scritti in questo modo come potremmo scrivere \(0.5 = 0.5000….\ ) Possiamo quindi definire\ (f (x,y)\) da

\

Questa idea relativamente semplice ha alcune difficoltà tecniche legate al seguente risultato.

Esercizio \(\PageIndex{1}\)

Considera la sequenza \((0.9,0.99,0.999,…)\). Determina che questa sequenza converge e, di fatto, converge su \(1\). Questo suggerisce che \(0.999… = 1\).

Allo stesso modo, abbiamo \(0.04999… = 0.05000…\ ), ecc. Per rendere unica la rappresentazione decimale di un numero reale in \ ( \ ), dobbiamo fare una scelta coerente di scrivere un decimale terminante come uno che termina in una stringa infinita di zeri o una stringa infinita di nove . Non importa quale scelta facciamo, non potremmo mai fare questa funzione su. Ad esempio, \(109/1100 = 0,09909090…\ ) avrebbe come pre-immagine \((0.0999…,0.9000…)\) che sarebbe un mix delle due convenzioni.

Cantor è stato in grado di superare questa tecnicità per dimostrare una corrispondenza uno a uno, ma invece noteremo che in entrambe le convenzioni, la funzione è uno-a-uno, quindi questo dice che l’insieme \(×\) è la stessa cardinalità di alcuni (innumerevoli) sottoinsiemi di \(\mathbb{R}\). Il fatto che questo abbia la stessa cardinalità di \(\mathbb{R}\) è qualcosa a cui torneremo. Ma prima proveremo a costruire un insieme non numerabile che non ha la stessa cardinalità di \(\mathbb{R}\). Per risolvere questo problema, Cantor ha dimostrato quanto segue nel 1891.

Teorema \(\PageIndex{1}\): Teorema di Cantor

Sia \(S\) qualsiasi insieme. Quindi non c’è corrispondenza uno-a-uno tra \(S\) e \(P(S)\), l’insieme di tutti i sottoinsiemi di \(S\).

Poiché \(S\) può essere messo in corrispondenza uno-a-uno con un sottoinsieme di \(P(S) (a → \{a\})\), allora questo dice che \(P(S)\) è grande almeno quanto \(S\). Nel caso finito \(/P (S)|\) è strettamente maggiore di \(|S|\) come mostra il seguente problema. Dimostra anche perché \(P (S)\) è chiamato il set di potenza di \(S\).

Esercizio \(\PageIndex{2}\)

Prova: Se \(/S / = n\), quindi \(/P (S)| = 2n\)

Suggerimento

Let \(S = a_1, a_2, …, a_n\). Considera la seguente corrispondenza tra gli elementi di \ (P (S)\) e l’insieme \(T\) di tutte le \(n\)-tuple di yes (\(Y\)) o no (\(N\)):

\

Quanti elementi sono in \(T\)?

Esercizio \(\PageIndex{3}\)

Dimostrare il teorema di Cantor.

Suggerimento

Supponiamo per contraddizione, che ci sia una corrispondenza uno-a-uno \(f : S → P(S)\). Si consideri \(A = \{x S S /x \ non {}} f (x)\}\). Poiché \(f\) è onto, allora c’è \(a\ A\) tale che\(A = f(a)\). È \(a A A\) o è \ (a\not {}} A\)?

In realtà risulta che \(\mathbb{R}\) e \(P(\mathbb{N})\) hanno la stessa cardinalità. Questo può essere visto in modo indiretto usando alcune delle idee di cui sopra dall’esercizio \(\PageIndex{2}\). In particolare, sia \ (T\) l’insieme di tutte le sequenze di zeri o uno (puoi usare \(Y\)s o \(N\)s, se preferisci). Quindi è semplice vedere che \(T\) e\(P (\mathbb{N})\) hanno la stessa cardinalità.

Se consideriamo \((0,1]\), che ha la stessa cardinalità di \(\mathbb{R}\), allora possiamo vedere che anche questo ha la stessa cardinalità di \(T\). In particolare, se pensiamo ai numeri in binario, allora ogni numero reale in \(\) può essere scritto come \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) dove \(a_j \\{0,1\}\). Dobbiamo tenere conto del fatto che rappresentazioni binarie come \(0.0111…\ ) e \(0.1000…\ ) rappresentano lo stesso numero reale (diciamo che nessuna rappresentazione finirà in una stringa infinita di zeri), quindi possiamo vedere che \(\) ha la stessa cardinalità di \(T – U\), dove \(U\) è l’insieme di tutte le sequenze che terminano in una stringa infinita di zeri. Si scopre che \(U\) stesso è un insieme numerabile.

Esercizio \(\PageIndex{4}\)

Let \(U_n = \{(a_1, a_2, a_3,…) / a_j \\ {0,1\}\) e \ (a_{n+1} = a_{n+2} = ··· = 0\}\). Mostra che per ogni \(n\), \(U_n\) è finito e usa questo per concludere che \(U\) è numerabilmente infinito.

I seguenti due problemi mostrano che l’eliminazione di un set numerabile da un set non numerabile non ne modifica la cardinalità.

Esercizio \(\PageIndex{5}\)

Sia \(S\) un insieme infinito. Dimostrare che\ (S\) contiene un sottoinsieme numerabilmente infinito.

Esercizio \(\PageIndex{6}\)

Supponiamo che \(X\) sia un insieme non numerabile e \(Y X X\) sia numerabilmente infinito. Dimostrare che \(X\) e \(Xy\) hanno la stessa cardinalità.

Suggerimento

Let \ (Y = Y_0\). Se \(X-Y_0\) è un insieme infinito, allora dal problema precedente contiene un insieme numerabilmente infinito \(Y_1\). Allo stesso modo se \(X – (Y_0 Y Y_1)\) è infinito contiene anche un insieme infinito \(Y_2\). Di nuovo, se \(X – (Y_0 Y Y_1 Y Y_2)\) è un insieme infinito, allora contiene un insieme infinito \(Y_3\), ecc. Per \(n = 1,2,3,…,\) sia\ (f_n : Y_{n-1} → Y_n\) una corrispondenza uno-a-uno e definisca\ (f : X → Xy\) per

\

Mostra che \(f\) è uno-a-uno e su.

I problemi di cui sopra dicono che \(R\), \(T – U\), \(T\) e \(P(N)\) hanno tutti la stessa cardinalità.

Come indicato in precedenza, il lavoro di Cantor sugli insiemi infiniti ha avuto un profondo impatto sulla matematica all’inizio del XX secolo. Ad esempio, esaminando la dimostrazione del teorema di Cantor, l’eminente logico Bertrand Russell ideò il suo famoso paradosso nel 1901. Prima di questo tempo, un set era ingenuamente pensato come una semplice collezione di oggetti. Attraverso il lavoro di Cantor e altri, insiemi sono stati diventando un oggetto centrale di studio in matematica come molti concetti matematici sono stati riformulati in termini di insiemi. L’idea era che la teoria degli insiemi doveva essere un tema unificante della matematica. Questo paradosso impostare il mondo matematico sul suo orecchio.

Paradosso di Russell

Considera l’insieme di tutti gli insiemi che non sono elementi di se stessi. Chiamiamo questo set \(D\) e chiediamo: “È \ (D D D\)?”Simbolicamente, questo set è

\

Se \(D D D\), quindi per definizione, \(D\non {}} D\). Se D 6 D D, quindi per definizione, \(D\D\).

Se si guarda indietro alla dimostrazione del Teorema di Cantor, questa era fondamentalmente l’idea che ci ha dato la contraddizione. Avere una tale contraddizione che si verifica al livello più elementare della matematica è stato scandaloso. Ha costretto un certo numero di matematici e logici a elaborare attentamente gli assiomi con cui gli insiemi potrebbero essere costruiti. Per essere onesti, la maggior parte dei matematici si avvicina ancora alla teoria degli insiemi da un punto di vista ingenuo poiché gli insiemi con cui di solito ci occupiamo rientrano nella categoria di quelli che chiameremmo “insiemi normali.”In realtà, un tale approccio è ufficialmente chiamato Teoria ingenua degli insiemi (al contrario della Teoria assiomatica degli insiemi). Tuttavia, i tentativi di mettere la teoria degli insiemi e la logica su basi solide hanno portato allo studio moderno della logica simbolica e, infine, alla progettazione della logica del computer (macchina).

Un altro luogo in cui il lavoro di Cantor ha avuto una profonda influenza nella logica moderna deriva da qualcosa a cui abbiamo accennato prima. Abbiamo mostrato prima che il quadrato unitario \ ( × \ ) aveva la stessa cardinalità di un sottoinsieme non numerabile di \(\mathbb{R}\). In effetti, Cantor mostrò che il quadrato unitario aveva la stessa cardinalità di \(\mathbb{R}\) stesso e fu spostato per avanzare nel 1878.

Congettura (L’ipotesi del Continuo)

Ogni sottoinsieme non numerabile di \(\mathbb{R}\) ha la stessa cardinalità di \(\mathbb{R}\).

Cantor non fu in grado di dimostrare o confutare questa congettura (insieme ad ogni altro matematico). Infatti, dimostrando o confutare questa congettura, che è stato soprannominato il Continuum Ipotesi, è stato uno dei famosi \(23\) problemi di Hilbert presentato come una sfida per i matematici al Congresso Internazionale dei matematici nel 1900.

Dato che \(\mathbb{R}\) ha la stessa cardinalità \(P(N)\), quindi il Continuum Ipotesi generalizzato per il:

Congettura (Generalizzata Continuum Ipotesi)

Dato un insieme infinito \(S\), non esiste un insieme infinito che ha una cardinalità strettamente tra di \(S\) e la sua potenza impostata \(P(S)\).

Gli sforzi per dimostrare o confutare ciò sono stati vani e con buone ragioni. Nel 1940, il logico Kurt Gödel dimostrò che l’ipotesi del Continuo non poteva essere confutata dagli assiomi di Zermelo-Fraenkel della teoria degli insiemi 1. Nel 1963, Paul Cohen dimostrò che l’ipotesi del Continuum non poteva essere dimostrata usando gli assiomi di Zermelo-Fraenkel. In altre parole, gli assiomi di Zermelo-Fraenkel non contengono informazioni sufficienti per decidere la verità dell’ipotesi.

Siamo disposti a scommettere che a questo punto la tua testa potrebbe nuotare un po ‘ con incertezza. Se è così, allora sappi che questi sono gli stessi sentimenti che la comunità matematica ha sperimentato a metà del ventesimo secolo. In passato, la matematica era vista come un modello di certezza logica. È sconcertante scoprire che ci sono affermazioni che sono “indecidibili.”In effetti, Gödel dimostrò nel 1931 che un sistema di assiomi finito coerente che conteneva gli assiomi dell’aritmetica conterrebbe sempre affermazioni indecidibili che non potevano né essere dimostrate vere né false con quegli assiomi. La conoscenza matematica sarebbe sempre incompleta.

 fig 9.3.2.png

Figura \(\PageIndex{2}\): Kurt Gödel

Quindi, cercando di mettere le basi del calcolo su un terreno solido, siamo arrivati a un punto in cui non possiamo mai ottenere la certezza matematica. Questo significa che dovremmo alzare le mani e concedere la sconfitta? Dovremmo essere paralizzati dalla paura di provare qualcosa? Certamente no! Come abbiamo accennato prima, la maggior parte dei matematici fa bene adottando un approccio pragmatico: usando la loro matematica per risolvere i problemi che incontrano. In realtà, è in genere i problemi che motivano la matematica. E ‘ vero che i matematici prendono le probabilità che non sempre pan fuori, ma ancora prendere queste possibilità, spesso con successo. Anche quando i successi portano a più domande, come fanno in genere, affrontare queste domande di solito porta a una comprensione più profonda. Per lo meno, la nostra comprensione incompleta significa che avremo sempre più domande a cui rispondere, più problemi da risolvere.

Cos’altro potrebbe chiedere un matematico?