nLab Cantor's teorema

Sommario

Georg Cantor dimostra molti teoremi, ma che di solito si chiama teorema di Cantor è il primo banale teorema di Cantor nuova teoria: che alcuni infiniti sono più grandi di altri; in particolare, un infinito numero cardinale (o infinito) genera uno più grande, prendendo il set di alimentazione.

(Il teorema si applica a tutti gli insiemi, non solo a quelli infiniti, anche se è abbastanza ovvio per gli insiemi finiti.)

Il teorema di Cantor non deve essere confuso con il teorema di Bernstein di Cantor (vedi numero cardinale), che è diverso (ma correlato, in quanto è importante giustificare l’interpretazione di Cantor del suo teorema).

Storia

Prima di Cantor, le persone tendevano a pensare all’infinito (che ci credessero o meno) come un concetto assoluto: tutti gli infiniti sono equivalenti. Era stato notato (da Galileo, per esempio) che è possibile dare un insieme infinito un’autoiniezione che non è una suriezione; ad esempio, l’inclusione degli interi pari negli interi raddoppiando. Così qui ci sono due infiniti †” l’infinito EE di interi pari e l’infinito NN di tutti gli interi — che sono in realtà equivalenti, anche se a prima vista sembrerebbe che EE è più piccolo.

Cantor ha mostrato che tale equivalenza fallisce con i numeri reali RR: nessuna mappa da NN a RR può essere suriettiva (in modo che RR sia innumerevoli). Il suo primo argomento è stato ad hoc, ma ha poi generalizzato questo con l’argomento diagonale per mostrare che nessuna mappa da qualsiasi set SS al suo set di potenza 𝒔S\mathcal{P}S potrebbe essere suriettiva. In questo modo, il sistema di calcolo del valore di RR è in grado di determinare la differenza tra RR e Н’”N\mathcal{P}N, che possiamo ora considerare come un’istanza del Teorema di Bernstein di SCHRöDER di Cantor.) Poiché esiste un’ovvia mappa iniettiva (la mappa singleton) da SS a 𝒔S\mathcal{P}S, Cantor ha concluso che la cardinalità dell’uno è strettamente inferiore alla cardinalità dell’altro.

L’argomento di Cantor, come tutta la sua teoria degli insiemi, era controverso all’epoca. Coloro che, come Kronecker, credevano che tutta la matematica dovesse essere matematica finita, la consideravano priva di significato. Ancora più moderati costruttivisti primi, come Brouwer e Weyl, ha scoperto che aveva poco senso. (In particolare, non dice nulla direttamente su RR, dal momento che la bijection tra RR e 𝒔N\mathcal{P}N non è costruttivamente valida, sebbene la prova originale di Cantor che RR è incalcolabile possa essere fatta funzionare.)

Tuttavia, le versioni del teorema indicate di seguito sono costruttivamente valide, e il Teorema è anche predicativamente valido (purché si abbiano insiemi di funzioni); i costruttivisti moderni generalmente accettano questi come teoremi. (L’interpretazione, tuttavia, non è così chiara.) Sono infatti teoremi nel linguaggio interno di qualsiasi topos (e il teorema è un teorema in qualsiasi Î \Pi-pretopos).

Dichiarazioni e prove

(Questo generalizza il teorema del punto fisso di Lawvere.)

La presenza della mappa diagonale Δ S\Delta_S qui spiega perché questa dimostrazione è chiamata argomento diagonale. (Questa spiegazione è anacronistica ma moralmente corretta.) Lawvereâ € ™s prova spiega anche (in realtà generalizza)il YY‑ o combinatore a punto fisso in lambda-calcolo non tipizzato, dove Y(n) Y(n) è un punto fisso per qualsiasi termine nn.

Segue immediatamente (anche in modo costruttivo) che se VV ha un’auto-mappatura senza punto fisso, allora nessuna mappa da SS a S→VS \a V può essere una suriezione. In effetti, abbiamo qualcosa di leggermente più forte di (ma classicamente equivalente a) il fallimento di ff per essere una suriezione: esiste effettivamente un elemento gg di S→VS \to V che non è uguale a nessun valore nell’intervallo di ff. (Se VV ha una relazione di apartness, allora puoi ottenere un risultato ancora più forte per un’ipotesi corrispondentemente più forte su nn, ma ciò non si applica alle versioni seguenti.)

Si noti che sebbene la negazione non abbia tutte le sue proprietà usuali nella matematica costruttiva, p=Âpp = \neg{p} è ancora impossibile.

La versione successiva è classicamente equivalente alla versione precedente (almeno se si verifica che 𝒔S\mathcal{P}S è abitata), ma non in modo costruttivo equivalente. (Infatti, a differenza del Teorema, apparentemente non ha un analogo costruttivo quando 𝠑” S \ mathcal {P}S è sostituito da V SV ^ S.)Questo argomento proviene dalla Proposizione 2.8.8 delle Basi pratiche di Taylor (anche se non lo so se è davvero nato lì).

Se ii è un’iniezione, allora ff è una retrazione di ii e quindi una suriezione, che è impossibile per Teorema .

Naturalmente, Cantor ha anche dimostrato il Teorema , ma la sua prova non è stata costruttiva.

Possiamo combinare Teoremi e nella seguente affermazione ancora più generale, tratta da D4.1.8 dell’Elefante di Johnstone.

Interpretazione

Si noti che esiste un’iniezione da SS a 𝒔S\mathcal{P}S, data dalla mappa singleton. Quindi nell’aritmetica dei numeri cardinali, abbiamo

Ma poiché non esiste tale suriezione, non esiste certamente alcuna biiezione, e abbiamo

Quindi concludiamo che

Cioè, ogni set è strettamente più piccolo in cardinalità rispetto al suo set di potenza.

Questa interpretazione si basa su una buona relazione tra ≤\leq e == sulla classe dei numeri cardinali; in particolare, il teorema di Bernstein di Cantor–Schroeder–che ≤\leq è antisimmetrico. Nella matematica costruttiva, questa relazione è carente, ed è del tutto possibile che due serie siano strettamente più piccole l’una dell’altra nel senso sopra. Grazie al Teorema , questo non è possibile per un insieme e il suo set di potenza, ma significa che l’interpretazione di <\lt come dimensione relativa è problematica —in effetti quasi problematico come l’idea che ci sono meno interi pari di interi!

Paul Taylor ha sostenuto che il valore essenziale del Teorema di Cantor è il lemma, implicito nella dimostrazione di Cantor, che Bill Lawvere isolato come Teorema . Come l’interpretazione principale del Teorema è significativo solo in uno specifico contesto set-teorico (in particolare, quello in cui il Cantor–Schroeder–teorema di Bernstein detiene), non può sopravvivere un â€revolution’ che rovescia il primato di quel contesto. Ma il lemma di Lawvere sopravviverà, dal momento che â € fa il work’ mentre il teorema di Cantor â € prende il credit’. (Vedi Taylor 2009 qui sotto per ulteriori discussioni di â € Lemmi che fanno il lavoro e teoremi che prendono il credit’.)

In posets

Un teorema analogo al teorema di Cantor’s per gli insiemi può essere formulato per altre categorie chiuse cartesiane. In particolare, si può chiedere se è possibile avere una suriezione X↠‘ 2 XX \ a 2 ^ X tra poset, dove la base 22 non è il poset discreto {0,1}\{0, 1\} ma piuttosto l’ordine {0≤1} \ {0 \ leq 1\}.

La risposta è che non esiste una tale suriezione f: X↠‘ 2 Xf: X \ a 2 ^ X, ma questo non deriva da una semplice applicazione del teorema del punto fisso della legge, dove si cerca di escludere tale ff invocando l’esistenza di una mappa 2→22 \a 2 che non ha un punto fisso (non esiste una mappa poset 2→22 \a 2!). Né possiamo fare appello a qualche argomento di cardinalità grezzo; per esempio, se XX è l’ordinale ω\omega, allora 2 X2^X è l’ordine ⊥⊔ω op\bot \sqcup \omega^{op} (liberamente adiacente a un elemento inferiore ⊥\bot a ω op\omega^{op}), che ha la stessa cardinalità. Quindi qualche altra prova deve essere cercata.

Dimostrare che non c’è suriezione X→2 XX \a 2^X è un esercizio divertente. Una linea di attacco (che interiorizza a qualsiasi topos) può essere trovata qui.

• Teorema del punto fisso di Lawvere