Set numerabile

L'insieme N × N di coppie di interi naturali è numerabile; si possono enumerare le coppie di interi naturali diagonale per diagonale, come indicato nel diagramma allegato: seguendolo si definisce facilmente per induzione una serie di coppie che enumera biettivamente tutte le coppie di interi naturali. Il reciproco di questa funzione, sia f , che è quindi una biiezione da N × N a N , chiamata funzione di accoppiamento di Cantore, è un polinomio di grado 2:

f(p,q)=q+∑0≤K<p+q(K+1)=q+(p+q)(p+q+1)2=(p+q)2+p+3q2{\ Displaystyle f (p, q) = q + \ sum _ {0 \ leq k <p + q} (k + 1) = q + {(p + q) (p + q + 1) \ over 2} = {\ frac {(p + q) ^ {2} + p + 3q} {2}}}

L'insieme Q di numeri razionali è numerabile. Infatti, un razionale è rappresentato da una frazione, cioè una coppia composta da un intero relativo e da un intero naturale diverso da zero. Componendo correttamente le biiezioni stabilite in precedenza, otteniamo una biiezione da N in Z × N ∗ . La rappresentazione di un razionale per frazione non è unica, ma, sapendo che Q è infinito, possiamo facilmente dedurre una definizione per induzione di una biiezione da N a Q (prendiamo come immagine di n il quoziente della prima coppia in l'enumerazione di Z × N ∗ che fornisce un razionale non ancora enumerato). È anche una conseguenza del teorema di Cantor-Bernstein , semplice però da dimostrare in questo caso particolare.

I primi due esempi, numerabilità di Z , ma soprattutto numerabilità di N × N , utilizzano un argomento abbastanza generico per dimostrazioni di numerabilità: enumeriamo gli elementi dell'insieme considerato in blocchi successivi, di dimensione costante nel caso di Z - due elementi dello stesso valore assoluto, di dimensione crescente nel caso di N × N - le diagonali, cioè le coppie della stessa somma. Abbiamo anche un modo uniforme di ordinare, e quindi di enumerare, ogni blocco finito.

• Ad esempio, l'insieme di parole su un alfabeto finito, cioè di sequenze finite (di lunghezza arbitrariamente grande) di elementi di un insieme finito, è numerabile. È enumerato da blocchi di parole di dimensione fissa, prima la parola vuota, poi le parole di dimensione 1, poi quelle di dimensione 2, ecc. Ogni blocco può essere ordinato lessicograficamente , da un ordine arbitrario sull'alfabeto di partenza.
• Allo stesso modo l'insieme di sequenze finite di interi (questo equivale a prendere parole su un alfabeto numerabile), è numerabile. Si possono usare per blocco le sequenze di lunghezza minore o uguale an di interi minori o uguali a n dove n appare necessariamente se la sequenza è di lunghezza strettamente minore di n-1 . Ogni blocco è ordinato lessicograficamente.
• L'insieme dei polinomi con coefficienti interi naturali può essere visto come l'insieme delle successioni (finite) di questi coefficienti. Queste sono tutte le sequenze finite di interi il cui ultimo termine è diverso da zero. In modo strettamente analogo al caso precedente, questo insieme è numerabile. Poiché l'insieme di interi relativi Z è numerabile, per composizione, si deduce che è numerabile anche l'insieme di polinomi con coefficienti interi relativi.

• L'insieme dei numeri algebrici (reali o complessi) è quindi anche numerabile: poiché possiamo enumerare i polinomi con coefficienti interi, e ciascuno di questi polinomi ha un numero finito di radici, possiamo enumerare i numeri algebrici, polinomio per polinomio, considerando solo le radici del polinomio che non sono già apparse nell'enumerazione. Poiché né l'insieme dei reali né l'insieme dei complessi sono numerabili, deduciamo l'esistenza di numeri trascendenti (reali o complessi) .

I teoremi generali che vedremo di seguito possono essere utilizzati anche per questi ultimi esempi.

Insiemi finiti e infiniti

Un set è terminata se, per qualche intero N , c'è in biiezione con il set di N primo intero o {0, 1, ..., N -1}, integer rigorosamente più piccolo N . Ad esempio, l'insieme vuoto (caso N = 0) è (come previsto) finito. Tutto finito è subpotent a N , vale a dire che v'è un'iniezione di questo insieme a N .

Una proprietà essenziale degli insiemi finiti è che un'iniezione di un insieme finito in se stesso è necessariamente biiettiva (vedi gli articoli insieme finito e principio dei cassetti ), cioè un insieme finito non può essere in biiezione con una parte propria di sé. Un insieme infinito è semplicemente un insieme che non è finito. L'insieme N , che è in biiezione ad esempio con N * , è quindi infinito, e allo stesso modo qualsiasi insieme numerabile è infinito. Abbiamo anche:

Proposta - Un insieme che contiene un insieme numerabile è in biiezione con una delle sue parti proprie (in particolare è infinito).

Anzi, lasciate E un tale insieme e A un sottoinsieme numerabile di E . E 'stata una corrispondenza biunivoca su una parte pulita di E prendendo l'identità di E - A , e una biiezione da A ad una parte pulita di A .

Con l' assioma della scelta possiamo mostrare che se un insieme è infinito allora contiene una parte numerabile (vedi la sezione # Teoria assiomatica sotto).

Parti di un set numerabile

Numeri naturali

Useremo la relazione d'ordine su N . Un segmento iniziale dell'insieme di numeri naturali N è lo stesso N o l'insieme di numeri naturali strettamente inferiore a un dato numero naturale. In particolare, l'insieme vuoto è un segmento iniziale di N . Possiamo dimostrare che:

Lemme - per la parte A di N , c'è una corrispondenza biunivoca strettamente crescente un segmento iniziale di N in A .

Il caso in cui A è vuoto essendo ovvio, supponiamo che questo insieme A non sia vuoto. Useremo il fatto che N è ben ordinato , vale a dire che ogni sottoinsieme non vuoto di N ha un elemento più piccolo. Infatti, possiamo definire per induzione una sequenza ( a n ) come segue:

• uno 0 è l'elemento più piccolo di A (che necessariamente esiste perché A non è vuoto);
• a n +1 è l'elemento più piccolo di A maggiore di a n se ce n'è uno, altrimenti è indefinito o se a n è indefinito.

Questa suite prevede una strettamente crescente biiezione di un periodo iniziale di interi segmenti in A .

Per costruzione, o questa sequenza è definita su tutti gli interi naturali, oppure esiste un intero p tale da essere definito per i primi numeri p +1 (gli interi da 0 a p ) e solo questi. Pure in costruzione è strettamente crescente, che assicura che è iniettiva sul suo insieme di definizione, e, per induzione , che se un n è definita, un n ≥ n . Si deduce quindi che se la successione è limitata, allora è definita solo su interi fino a una certa p .

Mostriamo ora che l'immagine di questa sequenza è A . O b un elemento di A . Esiste un intero p tale che a p sia definito e a p ≥ b . Infatti, o la sequenza non è limitata, oppure esiste un intero p tale che la sequenza è definita solo per gli interi fino ae incluso p , il che significa che a p è definito e che nessun elemento di A è è strettamente superiore a esso. Possiamo quindi definire, dalla proprietà di buon ordine, il più piccolo intero n tale che a n ≥ b . Dimostriamo che b = a n . Per definizione della suite, se n = 0 è che b = a 0 , l'elemento più piccolo di A . Se n ≠ 0 significa che n = m +1, e che a n è l'elemento più piccolo tra gli elementi di A strettamente maggiore di a m , di cui b appartiene appunto, per definizione di n . Quindi, per definizione di a n , a n ≤ b , quindi b = a n .

La successione ( a n ) definisce quindi una biiezione o tra N e A , nel qual caso per definizione A è numerabile, o tra l'insieme di p +1 numeri interi e A , nel qual caso A è per definizione finito.

1. un 0 è un numero intero naturale, quindi un 0 ≥ 0; se un n + 1 è definito e se un n ≥ n , si ha (dalla crescita rigoroso) un n 1> n quindi un n + 1 ≥ n + 1.

Per definizione da un lato di insiemi finiti, dall'altro di insiemi numerabili, deduciamo dal lemma la prima parte della proposizione seguente.

Proposizione - Qualsiasi parte A di N è finita o numerabile. Inoltre questa parte A è finita se è limitata, numerabile altrimenti.

Per la seconda parte (escludendo nuovamente il caso ovvio dove A è vuoto e quindi delimitato da un qualsiasi intero), abbiamo già visto durante la dimostrazione del lemma che se A è limitato allora il segmento iniziale S con cui è in biiezione è della forma {0,1,…, p } per un certo numero intero p (in altre parole: A è finito) e che viceversa, se S è della forma {0,1,…, p } allora A è limitato ( da una p ).

Una caratterizzazione corrente è quindi un sottoinsieme infinito (cioè numerabile) di N . Ad esempio, una variante della dimostrazione di Euclide dell'esistenza di un'infinità di numeri primi consiste nel mostrare che per ogni intero n , n ! + 1 ha almeno un divisore primo, e questi sono necessariamente maggiori di n .

Una conseguenza diretta della proposta è:

Corollario - Se A è subpotente a N , cioè se c'è un'iniezione da A a N , allora A è finito o numerabile.

Possiamo quindi parlare di un insieme più numerabile per un insieme finito o numerabile. Inoltre deduciamo che:

Proposizione - Se c'è una suriezione da N in A, allora A è finito o numerabile.

Infatti, se s è una suriezione da N in A , possiamo definire un'iniezione i che è un giusto reciproco di s , senza ricorrere all'assioma della scelta , poiché N , l'insieme iniziale della suriezione, è effettivamente ordinato  : prendiamo per i ( y ), dove y in A , il più piccolo antecedente di y per s .

Il contrario del corollario è ovvio per definizione di insiemi finiti e insiemi numerabili. Il contrario della proposizione è ovvio nel caso numerabile, per definizione. Se esiste una biiezione da un insieme finito F in un insieme A , e A è non vuoto, sia a ∈ A , allora possiamo completare questa biiezione da una suriezione da N in A , associando a con qualsiasi elemento di N che non sia in F . Questi risultati saranno raccolti nel teorema del paragrafo seguente.

Insiemi finiti o numerabili

Generalizziamo direttamente quanto sopra da N a qualsiasi insieme numerabile, componendo con la biiezione che garantisce l'equipotenza.

Teorema - Qualsiasi parte di un insieme numerabile è finita o numerabile. Abbiamo l'equivalenza tra le seguenti tre proposizioni:

• l'insieme A è finito o numerabile;
• c'è un'iniezione dell'insieme A in un insieme numerabile;
• A è vuoto o c'è una suriezione di un insieme numerabile nell'insieme A.

Poiché ogni insieme che contiene un insieme numerabile è infinito (vedi sopra), deduciamo:

Corollario - Le seguenti tre proposizioni sono equivalenti:

• l'insieme A è numerabile;
• c'è un'iniezione dell'insieme A in un insieme numerabile e un'iniezione di un insieme numerabile in A;
• c'è un surjection un insieme numerabile nel set A e un'iniezione di un insieme numerabile in A .

Questo corollario afferma essenzialmente il teorema di Cantor-Bernstein nel caso particolare del numerabile, la cui dimostrazione è stata facilitata dal fatto che N è ben ordinato.

Usiamo queste caratterizzazioni nel seguito, ma come un primo esempio di applicazione è possibile dimostrare che per ogni diverso da zero intero n , l'insieme N × {0, ..., n } è numerabile. Infatti questo insieme viene iniettato per inclusione in N × N , che abbiamo mostrato essere numerabile, e abbiamo un'iniezione di N in questo insieme associando ad un intero p la coppia ( p , 0) (non lo fa però non sarebbe molto difficile dare una biiezione esplicita usando la divisione euclidea ).

Imposta operazioni e contabilità

Prodotto finito di serie numerabili

Abbiamo visto che N × N è numerabile (funzione di accoppiamento di Cantore). Possiamo facilmente dedurre che:

Proposizione - Il prodotto cartesiano di una famiglia finita non vuota di insiemi numerabili è numerabile .

Per prima cosa mostriamo il risultato per A e B due set numerabili. V'è una biiezione di A su N e una biiezione di B su N . Definiamo: φ{\ displaystyle \ varphi}ψ{\ displaystyle \ psi}

λ:A×B⟶NON×NON(X,y)⟼(φ(X),ψ(y)){\ displaystyle \ lambda: {\ begin {array} {rcl} A \ times B & \ longrightarrow & \ mathbf {N} \ times \ mathbf {N} \\ (x, y) & \ longmapsto & (\ varphi ( x), \ psi (y)) \ end {array}}}

Questa mappa è biiettiva da A × B a N × N , che è numerabile. Quindi A × B è numerabile.

Si può assumere che una famiglia finita non vuota sia indicizzata da numeri interi da 0 a n per alcuni n , per definizione di un insieme finito. Il risultato si generalizza quindi a qualsiasi famiglia finita non vuota per induzione, utilizzando, per la fase di induzione, il risultato che abbiamo appena dimostrato per due serie.

Corollario - Il prodotto cartesiano di una famiglia finita di insiemi al massimo numerabili è al massimo numerabile .

Usiamo le caratterizzazioni della sezione precedente. Se la famiglia ha per cardinale finito n , definiamo come sopra un'iniezione del prodotto cartesiano in N n . Ora questo insieme è numerabile secondo la proposizione precedente (se la famiglia è vuota, il prodotto è ridotto a un elemento).

Possiamo usare queste proprietà per dare una rapida giustificazione della numerabilità dell'insieme Q di razionali . Infatti Z , insieme di interi relativi, è numerabile così come N * , insieme di interi strettamente positivi, e quindi il loro prodotto cartesiano Z × N * . Ogni razionale è scritto in almeno un modo come frazione p / q dove p ∈ Z e q ∈ N * . Ciò permette di definire una sovrastima da Z × N * in Q , che è quindi al massimo numerabile; essendo infinito, è numerabile.

Unione finita di insiemi numerabili

Proposta - La riunione di una famiglia finita di insiemi al massimo numerabili è al massimo numerabile. Se uno degli insiemi della famiglia finita è numerabile, l'unione è numerabile.

Supponiamo infatti la famiglia del cardinale n + 1 (se la famiglia è vuota anche l'unione, da cui il risultato), si può sempre ridurre ad un'indicizzazione per interi da 0 a n . Si tratta quindi di mostrare che se gli insiemi A 0 ,…, A n sono al massimo numerabili, allora è numerabile anche la loro unione. Per ogni A i è un f i un'iniezione di A i in N . Definiamo un'iniezione di A 0 ∪… ∪ A n nell'insieme numerabile N × {0,…, n }, associando a a la coppia ( f ( i ), i ), dove i è il più piccolo intero tale che a ∈ A i . Se inoltre uno di A i è numerabile, A 0 ∪… ∪ A n contiene un insieme numerabile, quindi è numerabile.

Unione numerabile di insiemi numerabili

Sfruttiamo ancora la numerabilità di N × N , ma i risultati di questa sezione utilizzano l' assioma della scelta numerabile. Quindi mostriamo che:

Proposta - La riunione di una famiglia numerabile di insiemi numerabili è numerabile.

Da composizione, è sempre possibile ridurre al caso in cui la famiglia è indicizzato da N . Si tratta quindi di mostrare che se ( A i ) i ∈ N è una famiglia di insiemi numerabili, allora l'unione di questi insiemi, A = ∪ i ∈ N A i , è un insieme numerabile. La AI essendo numerabile, esiste per ogni intero i , una biiezione da N su A i . Applicando l'assioma della scelta (numerabile) alla successione ( F i ) i ∈ N , dove F i è l'insieme delle biiezioni da N ad A i , otteniamo una successione di funzioni ( f i ) i ∈ N , dove f i è una biiezione da N ad A i . Possiamo quindi definire la seguente mappa di N 2 in A  :

f:NON×NON⟶A(io,non)⟼fio(non){\ displaystyle f: {\ begin {array} {rcl} \ mathbf {N} \ times \ mathbf {N} & \ longrightarrow & A \\ (i, n) & \ longmapsto & f_ {i} (n) \ end {array}}}

La mappa f è suriettiva, perché ciascuna delle mappe f i è, e ogni elemento di A è un elemento di almeno un A i .

Pertanto, l'insieme A è al massimo numerabile, poiché contiene un insieme numerabile, è numerabile.

Proposta - Un'unione numerabile al massimo di insiemi numerabili è al massimo numerabile.

Nel caso in cui alcuni A i siano finiti, è sufficiente ripetere la dimostrazione precedente, ma con i surettivi f i da N ad A i .

Alcuni dei primi esempi possono essere riesaminati alla luce di questi risultati. Ad esempio l'insieme di successioni finite di interi, che è l'unione di N n per n ∈ N , un'unione numerabile di insiemi numerabili, è quindi numerabile secondo la prima di queste due proposizioni. La dimostrazione è quindi diventata molto semplice. Tuttavia, la prima dimostrazione (abbozzata) non utilizzava l'assioma della scelta. Infatti ci siamo ridotti a un'unione numerabile di insiemi finiti, e abbiamo usato l'ordine lessicografico per costruire direttamente una funzione di scelta. Non possiamo nemmeno preoccuparci se fare appello o meno all'assioma della scelta, soprattutto perché qui è dopo tutto solo l'assioma della scelta numerabile.

Abbiamo una dimostrazione che utilizza gli stessi argomenti per l'insieme dei numeri algebrici. Questo insieme è infinito poiché gli interi sono ovviamente algebrici. L'insieme dei polinomi a coefficienti interi è ovviamente infinito, ed è iniettato nell'insieme delle successioni finite di interi (prendendo la successione dei suoi coefficienti), quindi è numerabile. Un polinomio ha solo un numero finito di radici. L'insieme dei numeri algebrici, che è l'unione degli insiemi delle radici di tutti i polinomi a coefficienti interi, è quindi al massimo numerabile usando la proposizione precedente; è numerabile.

Set infiniti e numerabilità

Esempi di innumerevoli insiemi infiniti

La classe degli insiemi numerabili ovviamente non è chiusa in tutte le operazioni sugli insiemi. Il teorema di Cantor mostra, per l' argomento diagonale , che tutte le parti di un insieme numerabile sono innumerevoli. Deduciamo da questo teorema, o usando l'argomento diagonale, che nemmeno l'insieme di sequenze con valori interi indicizzati da numeri interi (le funzioni da N a N ) non è numerabile, il che significa che un prodotto numerabile di insiemi numerabili non è numerabile.

Come l'insieme di parti di N , o anche l'insieme di sequenze di 0 e 1, che indichiamo con {0, 1} N , questo insieme ha la potenza del continuo  : il cardinale dell'insieme dei numeri reali. Le proprietà degli insiemi numerabili possono essere sfruttate per dimostrare che alcuni insiemi hanno il potere del continuo. Ad esempio dall'equipotenza tra il prodotto cartesiano N × N e N , deduciamo ( A B × C è equipotente a ( A B ) C ), quello tra ({0.1} N ) N e {0.1} N e quindi che il insieme di sequenze reali indicizzate dagli interi ha la potenza del continuo.

Secondo il teorema di Cantor , ci sono ovviamente insiemi che non sono né numerabili né hanno la potenza del continuum. Possiamo anche mostrare l'esistenza di innumerevoli insiemi senza usare il teorema di Cantor, usando sempre un argomento diagonale e la nozione di buon ordine , che porta al cardinale aleph-un e più in generale alla gerarchia degli alephs .

Caratterizzazioni di innumerevoli insiemi infiniti

Un insieme infinito non numerabile è per definizione un insieme che non è equipotente a un insieme finito, né a N , o altrimenti detto il cui cardinale non è né finito né numerabile. È quindi un insieme che non è equipotente una parte di N (vedere la sezione parti di un insieme numerabile ), cioè tale che non v'è iniezione di questo insieme a N . È ancora un insieme non vuoto che non è l'immagine di N da una suriezione ( stessa sezione ).

Nessuna di queste caratterizzazioni è però molto conveniente, e per ottenerne di più operative occorre l' assioma della scelta (che non era il caso delle precedenti caratterizzazioni), che permette di dimostrare che gli insiemi infiniti sono gli insiemi che contengono un insieme numerabile,

Fatto - In presenza dell'assioma della scelta, un insieme infinito non numerabile è un insieme la cui cardinalità è strettamente maggiore di quella di N , cioè è un insieme che contiene una parte numerabile, e tale che non c'è iniezione di questo insieme in N .

Tuttavia, va notato che per molte applicazioni (vedere un esempio nel paragrafo successivo) il richiamo all'assioma della scelta non è necessario. Infatti l'esistenza di insiemi che non sono equipotenti a una parte di N , ma che non contengono un insieme numerabile, non può essere dimostrata nella teoria degli insiemi ZF, poiché ciò contraddice l'assioma della scelta, o Kurt Gödel ha mostrato la compatibilità di questo uno con gli assiomi di ZF.

Incontro

Possiamo anche sfruttare le proprietà degli insiemi numerabili, per dedurne le proprietà degli insiemi che contengono un insieme numerabile, cioè in presenza dell'assioma di scelta (AC in breve), insiemi infiniti in generale. Dal fatto che l'unione di due insiemi numerabili è numerabile, si deduce immediatamente che:

Proposizione - Se E è un insieme infinito (che contiene un insieme numerabile se non abbiamo assunto AC), allora l'unione di E e un insieme numerabile è equipotente a E.

Infatti, sia A una parte numerabile di E e B un insieme numerabile. C'è una corrispondenza biunivoca tra la A e A ∪ ( B \ E ) (l'unione di A e la differenza set B \ E ) che si estende dalla identità del complementare di A a E .

Ne deduciamo (assumendo l'assioma della scelta):

Corollario (AC) - Supponiamo che E sia un insieme infinito e non numerabile e che A sia una parte numerabile di E, quindi E \ A, il complemento di A in E, è equipotente a E.

Il corollario usa l'assioma della scelta solo per mostrare che E \ A contiene un insieme numerabile. Facciamo un esempio da dove lo deduciamo direttamente. L'insieme di sequenze di 0 e 1, E = {0,1} N , non è numerabile per argomento diagonale . L'insieme A di sequenze di 0 e 1 che usano 1 solo un numero finito di volte, cioè terminano con un infinito di 0, è numerabile: abbiamo un'ovvia iniezione di questo insieme in quella di sequenze finite di interi, ed è anche ovviamente infinito (ad esempio l'insieme di sequenze che usano 1 solo una volta è numerabile). L'insieme E \ A delle sequenze di 0 e 1 che usano 1 un numero infinito di volte contiene un insieme numerabile: ad esempio quello delle sequenze che usano 0 una sola volta. Possiamo quindi applicare il corollario senza aver bisogno dell'assioma di scelta: E = {0,1} N è equipotente all'insieme E \ A di sequenze finite di 0 e 1 che non terminano in un infinito di 0. Queste sequenze forniscono un espansione unica in base 2 per i reali di] 0,1]. Deduciamo che {0,1} N e quindi l'insieme di parti di N ha la potenza del continuo .

Teoria assiomatica

Le definizioni e gli sviluppi intorno al numerabile sono stati eseguiti senza fare riferimento a una precisa assiomatizzazione della teoria degli insiemi , ma è facile verificare che tutto sia formalizzato nella teoria di Zermelo-Fraenkel , e anche nella teoria di Zermelo, con possibilmente l'assioma della scelta : piuttosto che lo schema degli assiomi di sostituzione , lo schema degli assiomi di comprensione è sufficiente. In particolare, l' assioma dell'infinito permette di mostrare l'esistenza di un insieme infinito che ha le proprietà attese dall'insieme N di interi naturali, e che assumiamo come sua definizione.

Avevamo bisogno dell'assioma della scelta, da un lato per mostrare che la riunione di una famiglia numerabile di insiemi numerabili è numerabile, dall'altra per mostrare che se un insieme non è finito, contiene un insieme numerabile. In entrambi i casi possiamo dimostrare che l'assioma della scelta numerabile è sufficiente. Questo è ovvio per la prima affermazione (vedi sopra).

Per il secondo, sia E un insieme infinito (cioè che non è in biiezione con alcun insieme {0,…, n - 1}, n intero). È naturale costruire una sequenza iniettiva per induzione usando una funzione di scelta sui sottoinsiemi cofinanziati di E (tutti non vuoti altrimenti E sarebbe finito). Modifichiamo leggermente questa dimostrazione per utilizzare solo l'assioma della scelta numerabile. Per ogni intero n l'insieme di ( n + 1) -tuple di elementi di E distinti a due a due (le iniezioni di {0, ..., n } in E ) non è vuoto. Secondo l'assioma della scelta numerabile, esiste una funzione f definita su N tale che f ( n ) è una ( n + 1) -tupla di elementi di E distinti a due a due. Possiamo quindi definire g su N per induzione come segue. A 0, g (0) è l'unico elemento di 1-tupla f (0). In n + 1, g ( n + 1) è l'elemento di indice più piccolo della ( n + 2) -tupla f ( n + 1) che non appare in { g (0),…, g ( n )} (di cardinalità al massimo n + 1, quindi tale elemento esiste). Per costruzione la funzione g iniettiva, e la sua immagine è un sottoinsieme numerabile di E .

Possiamo dimostrare che l'assioma della scelta è molto necessario per questi due risultati. Esistono modelli della teoria di Zermelo-Fraenkel, ZF, (senza l'assioma di scelta, ovviamente), in cui per esempio l'insieme di numeri reali R è un'unione numerabile di insiemi numerabili. Allo stesso modo, ci sono modelli di ZF in cui ci sono infiniti insiemi che non contengono un sottoinsieme numerabile. Le dimostrazioni utilizzano metodi avanzati di teoria degli insiemi, combinano la forzatura di Cohen e il metodo di permutazione Fraenkel - Mostowski .

Alcuni esempi di intervento del numerabile

Il numerabile è una nozione così elementare che si trova in quasi tutte le aree della matematica. Ad esempio, si preferisce parlare di una famiglia numerabile (matematica) piuttosto che di una sequenza indicizzata da numeri naturali, quando si vuole sottolineare il fatto che l'ordine non è importante (si veda ad esempio famiglia sommabile ).

Topologia

L'insieme Q di numeri razionali è una parte numerabile densa dello spazio R dei numeri reali . Questa proprietà si generalizza a R n e porta alla nozione di spazio topologico separabile . Ne consegue che un insieme di aperture di R non vuote disgiunte a due a due è al massimo numerabile. In effetti, l'intersezione con Q dell'unione (supponiamo che non sia vuota) di queste aperture è un insieme numerabile, e la mappa che a un elemento di questo insieme associa l'apertura unica a cui appartiene è suriettiva. Possiamo mostrare che ogni apertura di R è un'unione di intervalli aperti non vuoti disgiunti a due a due (le sue componenti connesse), un'unione quindi al massimo numerabile (si veda la scomposizione delle aperture di ℝ ). Un'altra proprietà di R , quella di avere una base numerabile di aperture (intervalli aperti i cui limiti sono razionali) porta alla nozione di spazio con una base numerabile .

Un'applicazione fondamentale della numerabilità è la teoria di Baire .

Logica matematica

In algebra è una banalità notare che ad esempio un gruppo avente un numero finito di generatori è al massimo numerabile. Ad esempio due riflessioni del piano generano un gruppo finito (gruppo diedro ) o infinito ma numerabile, a seconda che l'angolo tra i due assi della riflessione sia o meno un multiplo razionale di π .

Qualsiasi elemento di questo gruppo è infatti rappresentato da una sequenza finita dei generatori del gruppo. Questo è un caso speciale di un fenomeno più generale. Abbiamo visto che l'insieme di parole in un linguaggio finito o numerabile è numerabile. Questa proprietà ha importanti conseguenze nella logica . È sempre possibile dimostrare che una teoria del primo ordine espressa in un linguaggio finito o numerabile (come l'aritmetica di Peano o la teoria degli insiemi ) ha un modello numerabile. È una forma debole del teorema di Löwenheim-Skolem , che si deduce direttamente dalla dimostrazione del teorema di completezza . Nel caso della teoria degli insiemi è il cosiddetto paradosso di Skolem , ma questa è una proprietà utile, che è stata utilizzata da Paul Cohen per la sua prova indipendente per l' ipotesi continua e l' assioma della scelta .

Calcolabilità

Il computer gestisce solo il numerabile. Ma una proprietà più esigente è utile. Un insieme è finito o numerabile quando è vuoto o è l'immagine di una funzione definita su N , quindi in un certo modo “enumerabile” da una funzione definita su interi. Affinché un insieme sia enumerabile in modo ricorsivo, è anche necessario che questa funzione sia calcolabile (nel senso calcolabile da una macchina). Esistono insiemi numerabili che non sono enumerabili ricorsivamente. Un esempio è l'insieme di interi che codificano una macchina di Turing che non si ferma per una data entry, questo insieme non può essere enumerabile ricorsivamente a seconda dell'indecidibilità del problema di stop . Un altro esempio è dato dall'insieme di teoremi di teorie assiomatizzabili ricorsivamente che non è decidibile , come l'aritmetica di Peano . È un insieme di parole su un alfabeto finito (o numerabile), quindi numerabile, ma non enumerabile ricorsivamente.

Appunti

1. Cori-Lascar volume II, cap 7 .
2. André Delessert, Gödel: A Revolution in Mathematics: Essay on the Scientific and Philosophical Consequences of Gödelian Theorems , PPUR ,2000( leggi in linea ) , p.  121.
3. La nozione nell'articolo del 1874 dove compare per la prima volta (cfr. Parte storica), non porta un nome. Troviamo la definizione di numerabile ( (de) abzählbar ) come equipotente all'insieme dei numeri naturali nell'articolo pubblicato nel 1883, Über unendliche lineare Punktmannigfaltigkeiten, 3 , p.  152 della edizione delle opere complete del 1932 da Ernst Zermelo , traduzione in francese del 1889 in Sulle insiemi infiniti e lineari di punti , pag.  365 , accessibile sulla Gallica . La stessa definizione è ripetuta in Émile Borel , Lessons on the theory of functions , Gautier-Villars,1898, p.  6, un lavoro pionieristico sulla teoria degli insiemi in Francia.
4. Halmos , p.  112 ( 2 di edizione, Francese trans.).
5. Jean-Louis Krivine , Teoria degli insiemi [ dettaglio delle edizioni ], p.  36 .
6. Pierre Colmez , Elementi di analisi e algebra (e teoria dei numeri) , Éditions École Polytechnique,2009( leggi in linea ) , p.  9.
7. Vedere la sezione "  Insiemi finiti o numerabili  " che segue.
8. (de) Cantor, "Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen", Journal für die Reine und angewandte Mathematik , vol. 77, 1874, p.  258-262 (vedere sul centro di digitalizzazione di Gottinga [1] e una traduzione in francese, "Su una proprietà del sistema di tutti i numeri algebrici reali", Acta Math. , Vol. 2, 1883, p.  305-310 , su Gallica , [2] ).
9. (in) Thomas Jech , "  Set Theory  " Stanford Encyclopedia of Philosophy (Winter Edition 2011), Edward N. Zalta (a cura di).
10. Lettere tradotte in Jean Cavaillès , Filosofia matematica , appendice “Corrispondenza Cantor-Dedekind”, ed. Hermann, Parigi. p.  189-251 dell'edizione del 1962.
11. Dimostrazione dovuta a Dedekind, secondo la loro corrispondenza.
12. Ad esempio, vedere (in) William Kneale  (en) e Martha Kneale, The Development of Logic , Clarendon Press ,1962, p.  673.
13. Ad esempio Scienza e metodo , Capitolo III Matematica e logica , disponibile online [3]
14. Brouwer Intuitionism and Formalism , discorso inaugurale all'Università di Amsterdam 1912, tradotto in inglese in " The Bulletin of the American Mathematical Society , vol XX 1913 p.  81-96 , dopo Kneale e Kneale 1962 , p.  673-674.
15. Richard Dedekind, Notes on Letters of 1873 La mia opinione che la prima domanda [l'incontenibilità dei reali] [...] non avesse alcun interesse pratico particolare è stata palesemente confutata con la dimostrazione che Cantor diede dell'esistenza dei numeri trascendenti , nota tradotta nell'appendice di Filosofia matematica , opera citata, p.  194 .
16. Vedi Kneale e Kneale 1962 , p.  440.
17. Secondo un teorema di Rudolf Fueter e George Pólya , è, con la funzione simmetrica, l'unica biiezione quadratica da N × N a N  : vedi articolo dettagliato.
18. (in) Neil Calkin e Herbert Wilf (2000), "raccontare i razionali" American Mathematical Monthly , vol. 107, n .  4, 2000, pag.  360–363 [4] .
19. Caratterizzazione della ricorrenza dovuta a Moshe Newman secondo Recounting the Rationals, Continued 2003, Donald E. Knuth, CP Rupert, Alex Smith, Richard Stong, The American Mathematical Monthly , vol. 110, n .  7, 2003, pag.  642-643 DOI : 10.2307 / 3647762 .
20. Anche: Martin Aigner e Günter M. Ziegler (2004) Proofs from THE BOOK , 3 e ed Springer. P.  94-97 .
21. L'esistenza e l'unicità di una sequenza definita dall'induzione su interi naturali è dimostrata nella teoria degli insiemi .
22. (in) Kurt Gödel , La coerenza dell'assioma della scelta e dell'ipotesi del continuo generalizzato con gli assiomi della teoria degli insiemi , Princeton, Londra, Princeton University PressH. Milford, Oxford University Press, coll.  "Annali di studi di matematica" ( n °  3),1940, 66  p. ( ISBN  978-0-691-07927-1 e 0-691-07927-7 , OCLC  3316304 , leggi online ).
23. Vedi ad esempio il lavoro citato di Halmos , dove vengono fatti i primi sviluppi sulla cardinalità prima di introdurre la sostituzione.
24. In realtà utilizziamo un'altra versione debole dell'assioma della scelta, l'assioma della scelta dipendente, che è però più forte dell'assioma della scelta numerabile, vedi i lavori citati nelle note seguenti.
25. Tale modello è dovuto ad Azriel Lévy e Solomon Feferman , menzionati in (en) Horst Herrlich , Axiom of Choice , Springer-Verlag , coll.  "Appunti di matematica" ( n o  1876)2006, Edizione cartacea ISSN 0075-8434, edizione elettronica ISSN: 1617-9692 p.  23 .
26. Vedi Herrlich 2006  ; Thomas J. Jech, The Axiom of Choice , Elsevier Science 1973 e l'opera citata in bibliografia.
27. Cfr. Primo teorema della sezione Insiemi finiti o numerabili .
28. Vedi Jean-Louis Krivine , Theory of sets [ detail of editions ], cap. 10.
29. Vedi il teorema di Church

Vedi anche

Articoli Correlati

• Condizione stringa numerabile
• Spazio Lindelöf
• Spazio generato in modo conveniente
• Assiomi di numerabilità  (en)

Link esterno

Traduzione in francese dell'articolo di Cantor del 1874 sulla non numerabilità dei numeri reali, Su una proprietà del sistema di tutti i numeri algebrici reali , introduzione e analisi di Patrick Dehornoy , sul sito BibNum .

Bibliografia

• Paul Halmos , Introduzione alla teoria degli insiemi [ dettaglio delle edizioni ].Questo lavoro introduttivo copre, ad eccezione di riferimenti specifici, quasi tutto il contenuto dell'articolo.
• René Cori e Daniel Lascar , Logica matematica II . Funzioni ricorsive, teorema di Gödel, teoria degli insiemi, teoria dei modelli [ dettaglio delle edizioni ], capitolo 7.Questo lavoro introduttivo utilizza gli ordinali dai primi sviluppi sulla cardinalità.
• (en) Thomas Jech , Set Theory: The Third Millennium Edition, Revised and Expanded , 2003, Springer ( ISBN  3-540-44085-2 )