Insieme numerabile

In matematica , un insieme numerabile è un insieme finito o se c'è una corrispondenza con i numeri naturali . Più specificamente, un insieme si dice numerabile (o numerabile) quando è finito o quando c'è una biiezione tra questo insieme e l'insieme dei numeri naturali.

Nel 1874 Georg Cantor introdusse il termine insieme numerabile , contrapponendo gli insiemi numerabili a quelli non numerabili . Oggi gli insiemi numerabili costituiscono la base di una branca della matematica chiamata matematica discreta.

Definizione

Un insieme è numerabile se esiste una funzione iniettiva da numeri naturali poiché c'è un'ovvia biiezione tra e , non c'è differenza se 0 è considerato naturale o meno; In ogni caso, questo articolo prende la convenzione standard della logica matematica, dove si prende a , cioè ogni n dei naturali (dominio o insieme iniziale) corrisponde a un elemento di S (immagine o insieme di arrivo) usando una funzione . $sì$ $F$ $\mathbb {N} =\{0,1,2,3,...\}$ ${\ displaystyle -}$${\ displaystyle \ mathbb {N}}$$\mathbb {N} 0}=\{1,2,3,...\}$${\ displaystyle 0 \ in \ mathbb {N}}$ $-$$sì$$F$

${\begin{array}{rccl}f:&S&\longrightarrow &N\end{array}}$

Se la funzione è anche suriettiva (e quindi biiettiva ), allora è chiamata infinito numerabile. $F$$sì$

In altre parole, un insieme è numerabile infinito se ha corrispondenza biunivoca con l'insieme dei numeri naturali . ${\ displaystyle \ mathbb {N}}$

Come notato sopra, questa terminologia non è universale. Alcuni autori usano numerabile nel senso di ciò che qui viene chiamato numerabile infinito e non includono insiemi finiti.

Possono essere fornite anche formulazioni alternative (equivalenti) della definizione in termini di funzione biiettiva o suriettiva. Vedi sotto.

Storia

Nel 1874, nel suo primo articolo sulla teoria degli insiemi , Cantor dimostrò che l'insieme dei numeri reali non è numerabile, dimostrando così che non tutti gli insiemi infiniti sono numerabili. Nel 1878 utilizzò le corrispondenze uno-a-uno per definire e confrontare le cardinalità. Nel 1883 estese i numeri naturali con i loro ordinali infiniti e usò insiemi di ordinali per produrre un'infinità di insiemi aventi diverse cardinalità infinite. ]

Origine del termine

La nozione di numerabilità fu introdotta da Georg Cantor in un articolo del 1874, ​Su una proprietà del sistema di tutti i numeri algebrici reali ​ dove afferma da un lato che l'insieme dei numeri algebrici reali (cioè il insieme di numeri reali che sono la soluzione di qualche equazione polinomiale a coefficienti razionali) è numerabile, ​ e d'altra parte che l'insieme di tutti i numeri reali non lo è, da cui si deduce immediatamente l'esistenza di numeri trascendenti o non -algebrico, riscoprendo così un risultato di Liouville .

La sua origine è legata alla concezione dell'infinito in matematica. Fino alla scoperta di Cantor, l'infinito era l'infinito potenziale , la possibilità di continuare un processo senza mai fermarsi. Il confronto di insiemi infiniti porta con sé la nozione di infinito raggiunto , attuale o completato: un insieme infinito visto nel suo insieme, un concetto che è stato rifiutato da numerosi matematici ( Gauss , o, al tempo di Cantor, Kronecker , ecc.) . Per loro il fatto di considerare un'infinità di oggetti nel suo insieme, cioè il concetto di insieme infinito , non ha senso, ma anzi l'infinito può nascere solo dal processo di enumerazione senza ripetizione che non si ferma mai . Solo l'infinito numerabile può avere rigorosamente un significato.

Introduzione

Un insieme è un insieme di elementi e può essere descritto in molti modi. Un modulo è semplicemente un elenco di tutti i suoi elementi; Ad esempio, l'insieme costituito dagli interi 3, 4 e 5 può essere indicato con {3, 4, 5}. Tuttavia, questo è efficace solo per piccoli set; per set più grandi questo potrebbe richiedere molto tempo e soggetto a errori. Invece di elencare ogni elemento, a volte viene utilizzata un'ellissi ("...") se lo scrittore ritiene che il lettore possa facilmente indovinare cosa manca; ad esempio, {1, 2, 3, ..., 100} denota presumibilmente l'insieme di interi da 1 a 100. Anche in questo caso è ancora possibile elencare tutti gli elementi, poiché l'insieme è finito .

Alcuni insiemi sono infiniti ; questi insiemi hanno più di n elementi per ogni intero n . Ad esempio, l'insieme dei numeri naturali, scritto come {0, 1, 2, 3, 4, 5, ...}, ha un numero infinito di elementi e non possiamo usare nessun numero normale per dare la sua dimensione. Tuttavia, si scopre che gli insiemi infiniti hanno un'idea ben definita di dimensione (o meglio, di cardinalità , che è il termine tecnico per indicare il numero di elementi in un insieme), e non tutti gli insiemi infiniti hanno la stessa cardinalità.

Rappresentazione biiettiva di interi a numeri uguali.

Per capire cosa significa, esaminiamo prima cosa non significa . Ad esempio, esistono un numero infinito di interi dispari, un numero infinito di interi pari e (quindi) un numero infinito di interi in generale. Tuttavia, risulta che il numero di interi pari, che è lo stesso del numero di interi dispari, è anche lo stesso del numero di interi in generale. Questo perché per ogni intero dispari c'è una controparte, anche intero: ... -2 → -4, -1 → -2, 0 → 0, 1 → 2, 2 → 4, ... Nella figura Interi e i numeri pari sono disposti in una corrispondenza uno a uno (o biiezione ), che è una funzione che rappresenta due insiemi in modo tale che ogni elemento di ciascun insieme corrisponda a un singolo elemento nell'altro insieme.

Tuttavia, non tutti gli insiemi infiniti hanno la stessa cardinalità. Ad esempio, Georg Cantor (che ha introdotto questo concetto) ha mostrato che i numeri reali non possono essere in corrispondenza biunivoca con i numeri naturali (interi non negativi), e quindi l'insieme dei numeri reali ha una cardinalità maggiore dell'insieme di numeri naturali.

Un insieme è numerabile se: (1) è finito, oppure (2) se ha la stessa cardinalità (dimensione) dell'insieme dei numeri naturali. In modo equivalente, un insieme è numerabile se ha la stessa cardinalità di un sottoinsieme dell'insieme dei numeri naturali. In caso contrario, non è numerabile .

Formulazione generale senza dettagli

Per definizione, un insieme S è numerabile se esiste una funzione iniettiva f  : S → N da S all'insieme dei numeri naturali N = {0, 1, 2, 3, ...}.

Potrebbe sembrare normale dividere gli insiemi in classi diverse: mettere insieme tutti gli insiemi contenenti un elemento; tutti gli insiemi che contengono due elementi insieme; ...; infine, metti insieme tutti gli infiniti insiemi e considerali della stessa dimensione. Questo punto di vista non è sostenibile all'interno della definizione naturale di dimensione.

Per elaborare questo abbiamo bisogno del concetto di biiezione . Sebbene una biiezione sembri un concetto più avanzato di un numero, il consueto sviluppo della matematica in termini di teoria degli insiemi definisce le funzioni prima dei numeri, poiché si basano su insiemi molto più semplici. È qui che entra in gioco il concetto di biiezione: definisce la corrispondenza

a ↔ 1, b ↔ 2, c ↔ 3

Questo definisce una biiezione, poiché ogni elemento di { a , b, c } corrisponde a un preciso elemento di {1, 2, 3} e viceversa.

Generalizziamo ora questa situazione e definiamo due insiemi della stessa dimensione se (e solo se) c'è una biiezione tra di loro. Per tutti gli insiemi finiti questo ci dà la consueta definizione di dimensione equivalente . Cosa ci dice sulla dimensione degli insiemi infiniti?

Considera gli insiemi A = {1, 2, 3, ...}, l'insieme degli interi positivi , e B = {2, 4, 6, ...}, l'insieme degli interi positivi pari. Affermiamo che, secondo la nostra definizione, questi insiemi hanno la stessa dimensione e che quindi B è numerabilmente infinito. Ricordiamo che per dimostrarlo dobbiamo provare una biiezione tra loro. Ma questo è facile, usando n ↔ 2 n , quindi

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....

Come nell'esempio precedente, ogni elemento di A è stato accoppiato con un elemento di B e viceversa. Quindi hanno le stesse dimensioni. Questo è un esempio di un insieme della stessa dimensione di uno dei suoi sottoinsiemi propri (cosa impossibile per gli insiemi finiti).

Allo stesso modo, l'insieme di tutte le coppie ordinate di numeri naturali è numerabilmente infinito, come si può vedere seguendo un percorso come quello nell'immagine:

La funzione di corrispondenza Cantor assegna un numero naturale a ciascuna coppia di numeri naturali.

La rappresentazione risultante è:

0 ↔ (0.0), 1 ↔ (1.0), 2 ↔ (0.1), 3 ↔ (2.0), 4 ↔ (1.1), 5 ↔ (0.2), 6 ↔ (3.0) ....

Questa rappresentazione comprende tutte le coppie ordinate.

È interessante notare che se tratti ogni coppia come numeratore e denominatore di una frazione volgare , allora per ogni frazione positiva, possiamo arrivare a una quantità diversa che le corrisponderà. Questa rappresentazione include anche i numeri naturali, poiché ogni numero naturale è anche una frazione N /1. Pertanto possiamo concludere che ci sono esattamente tanti numeri razionali positivi quanti sono gli interi positivi. Questo vale anche per tutti i numeri razionali, come si può vedere di seguito.

Teorema: Il prodotto cartesiano di un numero finito di insiemi numerabili è numerabile.

A volte è utile più di una rappresentazione. Qui è dove rappresenti che l'insieme che vuoi mostrare è numerabilmente infinito in un altro insieme, e quindi rappresenta quest'altro insieme di numeri naturali. Ad esempio, i numeri razionali positivi possono essere facilmente assegnati a (un sottoinsieme di) le coppie di numeri naturali perché p / q rappresenta ( p , q ).

E che dire degli infiniti sottoinsiemi degli infiniti insiemi numerabili? Questi hanno meno elementi di N ?

Teorema: ogni sottoinsieme di un insieme numerabile è numerabile. In particolare, ogni sottoinsieme infinito di un insieme numerabile infinito è numerabile infinito.

Ad esempio, l'insieme dei numeri primi è numerabile, assegnando l' n- esimo numero primo a n :

• 2 rappresenta 1
• 3 rappresenta 2
• 5 rappresenta 3
• 7 rappresenta 4
• 11 rappresenta 5
• 13 rappresenta 6
• 17 rappresenta 7
• 19 rappresenta 8
• 23 rappresenta 9
• ...

Che dire degli insiemi che sono naturalmente "maggiori di" N ? Ad esempio, l'insieme degli interi , Z , o l'insieme dei numeri razionali , Q , che intuitivamente possono sembrare molto più grandi di N. Ma le apparenze ingannano, poiché affermiamo che:

Teorema: Z (l'insieme di tutti i numeri interi) e Q (l'insieme di tutti i numeri razionali) sono numerabili.

Allo stesso modo, l'insieme dei numeri algebrici è numerabile. ]

Teorema: qualsiasi unione finita di insiemi numerabili è numerabile. Q può essere definito come l'insieme di tutte le frazioni del tipo a'/ b dove a e b sono interi, con b > 0. Questo può essere mappato al sottoinsieme delle triple ordinate di numeri naturali ( a , b , c ) di tale che se a ≥ 0 e b > 0, a e b sono coprimi, e c ∈ {0, 1} allora c = 0 se a / b ≥ 0, e c = 1 altrimenti.

• Lo 0 rappresenta (0,1,0)
• L'1 rappresenta (1,1,0)
• Il −1 rappresenta (1,1,1)
• La 1/2 rappresenta (1,2,0)
• Il −1/2 rappresenta (1,2,1)
• Il 2 rappresenta (2,1,0)
• Il −2 rappresenta (2,1,1)
• 1/3 rappresenta (1,3,0)
• Il −1/3 rappresenta (1,3,1)
• Il 3 rappresenta (3,1,0)
• Il −3 rappresenta (3,1,1)
• Il 1/4 rappresenta (1,4,0)
• Il −1/4 rappresenta (1,4,1)
• Il 2/3 rappresenta (2,3,0)
• Il −2/3 rappresenta (2,3,1)
• Il 3/2 rappresenta (3,2,0)
• Il −3/2 rappresenta (3,2,1)
• Il 4 rappresenta (4,1,0)
• Il −4 rappresenta (4,1,1)
• ...

Con la previdenza di sapere che ci sono insiemi numerabili, ci si può chiedere se quest'ultimo risultato possa essere esteso. La risposta è "sì" e "no", possiamo estenderla, ma dobbiamo assumere un nuovo assioma per farlo.

Teorema: (assumendo l' assioma della scelta numerabile ) L'unione di un numero numerabile di insiemi numerabili è numerabile.

Ad esempio, dato l'insieme numerabile a , b , c , ...

Enumerazione di numeri numerabili di insiemi numerabili.

Utilizzando una variante dell'enumerazione triangolare vista sopra:

• uno ₀ rappresenta 0
• un ₁ rappresenta 1
• b ₀ rappresenta 2
• un ₂ rappresenta 3
• b ₁ rappresenta 4
• c ₀ rappresenta 5
• un ₃ rappresenta 6
• b ₂ rappresenta 7
• c ₁ rappresenta 8
• d ₀ rappresenta 9
• un ₄ rappresenta 10
• ...

Nota che questo funziona solo se gli insiemi a , b , c , ... sono insiemi disgiunti . In caso contrario, l'unione è ancora più piccola e quindi anche enumerabile da uno dei teoremi precedenti.

Si noti inoltre che abbiamo bisogno dell'assioma della scelta numerabile per indicizzare tutti gli insiemi a , b , c , ... contemporaneamente.

Teorema: L'insieme di tutte le successioni finite di numeri naturali è numerabile.

Questo insieme è l'unione di successioni di lunghezza 1, lunghezza 2, lunghezza 3, che sono insiemi numerabili (prodotto cartesiano finito). Quindi stiamo parlando di un'unione numerabile di insiemi numerabili, che è numerabile dal teorema di cui sopra.

Teorema: L'insieme di tutti i sottoinsiemi finiti dei numeri naturali è numerabile.

Avendo un sottoinsieme finito, puoi ordinare gli elementi in una sequenza finita. C'è solo un numero numerabile di sequenze finite, quindi c'è anche solo un numero numerabile di sottoinsiemi finiti.

Il seguente teorema fornisce formulazioni equivalenti in termini di una funzione biiettiva o suriettiva . Una prova di questo risultato può essere trovata nel testo di Lang.

Teorema (di base): Sia S un insieme. Le seguenti dichiarazioni sono equivalenti:

1. S è numerabile, cioè esiste una funzione iniettiva f  : S → N .
2. Ó S è vuoto oppure esiste una funzione suriettiva g  : N → S .
3. Ó S è finito oppure c'è una biiezione h  : N → S .

Il teorema di Cantor afferma che se A è un insieme e P ( A ) è il suo insieme di potenze , cioè l'insieme di tutti i sottoinsiemi di a , allora non esiste una funzione suriettiva da A a P ( A ). Una dimostrazione è data nell'articolo Teorema di Cantor . Come immediata conseguenza di questo e del precedente teorema di base abbiamo:

Proposizione: L'insieme P ( N ) non è numerabile; cioè non è numerabile .

Per un'elaborazione di questo risultato si veda Argomento diagonale di Cantor.

L'insieme dei numeri reali non è numerabile (vedi la prima dimostrazione di non numerabilità di Cantor ), così come l'insieme di tutte le successioni infinite dei numeri naturali.

Alcuni dettagli tecnici

Le dimostrazioni delle dichiarazioni contenute nel paragrafo precedente si basano sull'esistenza di funzioni con determinate proprietà. Questa sezione introduce le funzioni più comunemente utilizzate in questo documento, ma non verifica che queste funzioni abbiano le proprietà richieste. Il teorema di base viene spesso utilizzato per semplificare le dimostrazioni. Si noti che N in questo teorema può essere sostituito da qualsiasi insieme numerabile infinito.

Proposizione: Qualsiasi insieme finito è numerabile.

Dimostrazione: per definizione, esiste una biiezione tra un insieme finito non vuoto, S , e l'insieme {1, 2, ..., n } per qualsiasi numero naturale positivo n . Questa funzione è un'iniezione di S in N .

Proposizione: Qualsiasi sottoinsieme di un insieme numerabile è numerabile. ]

Dimostrazione : la restrizione di una funzione iniettiva a un sottoinsieme del suo dominio è ancora iniettiva.

Proposizione: Se S è un insieme numerabile e x ∉ S , allora S ∪ { x } è numerabile. ]

Dimostrazione: Sia f : S → N un'iniezione, definiamo g : S ∪ { x } → N come g ( x ) = 0 e g ( y ) = f ( y ) + 1 per ogni y in S . Questa funzione g è un'iniezione.

Proposizione: Se A e B sono insiemi numerabili, allora A ∪ B sono numerabili. ]

Dimostrazione: Sia f : A → N e g : B → N iniezioni, definiamo una nuova iniezione h : A ∪ B → N come h ( x ) = 2 f ( x ) se x è in A e h ( x ) = 2 g ( x ) + 1 se x è in B ma non in A .

Proposizione: Il prodotto cartesiano di due insiemi numerabili A e B è numerabile. ]

Dimostrazione: Si noti che N × N è numerabile per definizione perché la funzione f  : N × N → N data da f ( m , n ) = 2 ^m 3 ⁿ è iniettiva. ​ Quindi segue il teorema del prodotto cartesiano di base, in cui due insiemi numerabili qualsiasi hanno un prodotto numerabile. Se A e B sono numerabili, esistono assoggettamenti f  : N → A e g  : N → B . Così

f × g  : N × N → A × B

è una soggezione di un insieme numerabile N × N all'insieme A × B e il corollario implica che A × B è numerabile. Questo risultato generalizza il prodotto cartesiano di qualsiasi raccolta finita di insiemi numerabili e la dimostrazione per induzione del numero di insiemi nella raccolta.

Proposizione: Gli interi Z sono numerabili ei numeri razionali Q sono numerabili.

Dimostrazione: Gli interi Z sono numerabili per la funzione f  : Z → N data da f ( n ) = 2 ⁿ se n non è negativo f ( n ) = 3 ^{− n} se n è negativo, è una funzione iniettiva. I numeri razionali Q sono numerabili per la funzione g  : Z × N → Q data da g ( m , n ) = m /( n + 1) è una soggezione dell'insieme numerabile Z × N ai razionali Q.

Proposizione: I numeri algebrici A sono numerabili.

Dimostrazione: poiché tutti i numeri algebrici (compresi i numeri complessi) sono radici di un polinomio. Sia un polinomio e il numero algebrico è la k- esima radice del polinomio (prima, ordinato per valore assoluto dal più piccolo al più grande, poi, ordinato per argomento dal più piccolo al più grande). Possiamo definire una funzione iniettiva (cioè uno-a-uno) f  : A → Q data da , dove è l' n- esimo primo .$a_{0}x^{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots +a_{n}x^{n}$$?$$f(\alpha )=2^{k-1}\cdot 3^{a_{0}}\cdot 5^{a_{1}}\cdot 7^{a_{2}}\cdot \dots \cdot {p_{n+2}}^{a_{n}}\cdot \dots$$p_{n}$

Proposizione: se A _n è un insieme numerabile per ogni n in N allora anche l'unione di tutto A _n è numerabile. ]

Dimostrazione: Questa è una conseguenza del fatto che per ogni n esiste una funzione soggettiva g _n  : N → A _n e quindi la funzione

${\ displaystyle G: \ mathbf {N} \ times \ mathbf {N} \ a \ bigcup {n \ in \ mathbf {N} } A_ {n},}$

dato da G ( n , m ) = g _n ( m ) è un assoggettamento. Poiché N × N è numerabile, il corollario implica che l'unione è numerabile. Usiamo l' assioma della scelta numerabile in questa dimostrazione per scegliere per ogni n in N un assoggettamento g _n dalla raccolta non vuota di assoggettamenti da N ad A _n .

Una prova topologica della non numerabilità dei numeri reali è descritta nella proprietà dell'intersezione finita .

Modello minimo di teoria degli insiemi

Se esiste un insieme che è un modello standard (vedi modello interno ) della teoria degli insiemi ZFC, allora non esiste un modello standard minimo ( vedi universo costruibile ). Il teorema di Löwenheim-Skolem può essere utilizzato per dimostrare che questo modello minimo è numerabile. Il fatto è che la nozione di "non numerabilità" ha senso in questo modello, e in particolare questo modello M contiene elementi che sono:

• Sottoinsiemi di M , quindi numerabili
• Ma innumerevoli sotto il punto di vista di M

Agli albori dell'esistenza, questa teoria era considerata un paradosso (vedi il paradosso di Skolem ).

Il modello standard minimo include tutti i numeri algebrici e tutti i numeri trascendentali effettivamente calcolabili , così come molti altri tipi di numeri.

Ordini totali

I set numerabili possono essere ordinati totalmente in vari modi, ad esempio:

• Con un buon ordine (vedi anche numero ordinale ):
  • Il solito ordine dei numeri naturali (0 , 1, 2, 3, 4, 5, ...)
  • Interi nell'ordine (0, 1, 2, 3, ...; -1, -2, -3, ...)
• Altri (in ordine sfavorevole):
  • Il solito ordine degli interi (..., -3, -2, -1, 0, 1, 2, 3, ...)
  • Il solito ordinamento dei numeri razionali (non può essere scritto esplicitamente come una lista ordinata)

Si noti che in entrambi gli esempi di buon ordinamento, ogni sottoinsieme ha un elemento minore ; e negli esempi dei misordering, alcuni sottoinsiemi non hanno un minimo elemento . Questa è la definizione chiave che determina se un ordine totale è anche un buon ordine.

Esempi

${\begin{array}{|rcr|}\hline n&\longmapsto &p\\\hline 1&\longmapsto &2\\2&\longmapsto &0\\3&\longmapsto &4\\4&\longmapsto &-2\\ 5&\longmapsto &6\\6&\longmapsto &-4\\7&\longmapsto &8\\8&\longmapsto &-6\\\cdots &\longmapsto &\cdots \\\end{array}}$

• L'insieme di tutti i numeri pari è numerabile perché la funzione:

${\begin{array}{rccl}f:&N&\longrightarrow &P\\&n&\longmapsto &p=f(n)\end{array}}$

$f(n)={\begin{cases}p=n+1&,\;if:&n{\text{ è dispari}}\\p=2-n&,\;if:&n{\text{ è pari}}\end{casi}}$

è una biiezione : ad ogni numero naturale corrisponde un solo numero pari e viceversa.

• Anche l'insieme di tutti gli interi è numerabile.$\mathbb{Z}$
• Inoltre, l'insieme di tutti i numeri razionali è numerabile. ]$\mathbb{Q}$
• Il set è numerabile.${\ displaystyle \ mathbb {N} \ volte \ mathbb {N}}$
• Dalla precedente affermazione consegue che anche l'insieme di tutti i razionali è numerabile, tenendo conto che , dove non contiene lo 0 .${\ displaystyle \ mathbb {N} \ volte \ mathbb {N'} =\ mathbb {Q}}$${\ displaystyle \ mathbb {N'}}$
• Per induzione si può dimostrare che sono numerabili per qualsiasi numero naturale k .$\mathbb {N}<k},\mathbb {Z}<k},\mathbb {Q}<k}$

Vedi anche

• Numero ordinale (teoria degli insiemi)
• Aleph (cardinali)
• Contare
• numero cardinale
• Il paradosso dell'hotel di Hilbert
• insieme finito
• insieme infinito
• spazio compatto
• insieme non numerabile
• Ipotesi del continuo

Collegamenti esterni

• Quest'opera contiene una traduzione completa derivata dal " countable set " di Wikipedia in inglese, in particolare questa versione , rilasciata dai suoi editori sotto la GNU Free Documentation License e la Creative Commons Attribution-ShareAlike 3.0 Unported License .