Teoria degli insiemi - calvino.polito.itcalvino.polito.it/~camerlo/gargnan2014-1.pdf · Cos’ e la...

Teoria degli insiemi

Cos’e la teoria degli insiemi

La teoria degli insiemi e il fondamento della matematica.

Questa affermazione e singolare: la teoria degli insiemi ha cominciato aessere svilupata a partire dalla fine del XIX secolo; la matematica esistevagia da qualche millenio.

Il significato e:

Tutti i concetti matematici possono essere definiti in termini delle nozioniprimitive di insieme e appartenenza da cui tutti i risultati matematici

possono essere dedotti.

Da questa osservazione nasce la teoria degli insiemi.

La teoria degli insiemi e il fondamento della matematica.Questa affermazione e singolare: la teoria degli insiemi ha cominciato aessere svilupata a partire dalla fine del XIX secolo; la matematica esistevagia da qualche millenio.

Il significato e:

Tutti i concetti matematici possono essere definiti in termini delle nozioniprimitive di insieme e appartenenza da cui tutti i risultati matematici

possono essere dedotti.

Da questa osservazione nasce la teoria degli insiemi.

Si potrebbe quindi anche dare la definizione

matematica = teoria degli insiemi

L’identificaziona appare sensata, ma non si puo escludere che in futurodebba essere soggetta a revisione.

Si potrebbe quindi anche dare la definizione

matematica = teoria degli insiemi

L’identificaziona appare sensata, ma non si puo escludere che in futurodebba essere soggetta a revisione.

Quale teoria degli insiemi?

Ci sono varie teorie degli insiemi, non tutte equivalenti fra loro —sebbene con larghe sovrapposizioni: hanno tutte l’ambizione di contenerela matematica ordinaria!

La teoria chiamata usualmente teoria degli insiemi e la teoria ZFC:Zermelo-Fraenkel con assioma della scelta.

Quale teoria degli insiemi?

Ci sono varie teorie degli insiemi, non tutte equivalenti fra loro —sebbene con larghe sovrapposizioni: hanno tutte l’ambizione di contenerela matematica ordinaria!

La teoria chiamata usualmente teoria degli insiemi e la teoria ZFC:Zermelo-Fraenkel con assioma della scelta.

Il linguaggio della teoria degli insiemi

Una teoria matematica e espressa attraverso formule in un linguaggio.

Illinguaggio della teoria degli insiemi consiste di

1. Simboli logici:I Simbolo di uguaglianza =I Connettivi ¬ (negazione), ∨ (disgiunzione), ∧ (congiunzione), ⇒

(implicazione), ⇔ (biimplicazione)I Quantificatori ∃ (quantificatore esistenziale), ∀ (quantificatore

universale)I Variabili v0, v1, v2, . . .

2. Simbolo non logico:I Relazione binaria di appartenenza ∈

Una teoria matematica e espressa attraverso formule in un linguaggio. Illinguaggio della teoria degli insiemi consiste di

Dato il linguaggio, si possono definire le formule:

Definizione. Siano x , y delle variabili.

I x = y , x ∈ y sono formule

I Se ϕ,ψ sono formule, anche ¬ϕ,ϕ ∨ ψ,ϕ ∧ ψ,ϕ⇒ ψ,ϕ⇔ ψ sonoformule

I Se ϕ e una formula, anche ∃xϕ,∀xϕ sono formule

Gli assiomi di ZFC (primo blocco)

1. Estensionalita: ∀z(z ∈ x ⇔ z ∈ y)⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y(y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y))

3. Schema di separazione: Per ogni formula ϕ:∃y∀x(x ∈ y ⇔ x ∈ z ∧ ϕ)

4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x(x ∈ Y ∧ Y ∈ F ⇒ x ∈ A)

6. Schema di rimpiazzamento: Per ogni formula ϕ:∀x ∈ A ∃!yϕ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le proprieta elementari dellateoria degli insiemi. Questo facilita anche l’enunciazione degli assiomirestanti.

4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

Primi sviluppi della teoria

Definizione.

I Insieme vuoto: y = ∅ ⇔ ∀x x /∈ y

I Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y)

I Coppia ordinata: (x , y) = {{x}, {x , y}I Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I Unione:⋃F =

⋃Y∈F Y = {x | ∃Y ∈ F x ∈ Y }

I Prodotto cartesiano: A× B = {(x , y) | x ∈ A, y ∈ B}

Definizione.

I Unione:⋃F =

⋃Y∈F Y = {x | ∃Y ∈ F x ∈ Y }

Definizione.

I Coppia ordinata: (x , y) = {{x}, {x , y}

I Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I Unione:⋃F =

⋃Y∈F Y = {x | ∃Y ∈ F x ∈ Y }

Definizione.

I Unione:⋃F =

⋃Y∈F Y = {x | ∃Y ∈ F x ∈ Y }

Definizione.

I Unione:⋃F =

⋃Y∈F Y = {x | ∃Y ∈ F x ∈ Y }

Definizione.

I Unione:⋃F =

⋃Y∈F Y = {x | ∃Y ∈ F x ∈ Y }

Relazioni e funzioni

Definizione.

I R e una relazione se e un insieme di coppie ordinate

I domR = {x | ∃y(x , y) ∈ R}I f e una funzione se e una relazione e ∀x ∈ domf ∃!y(x , y) ∈ f . Tale

y e denotato f (x). Se domf = A e f ⊆ A× B, si scrive f : A→ B.Una tale f e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x) 6= f (y)) e∀z ∈ B ∃x ∈ A f (x) = z .

I Se R,S sono relazioni, A,B sono insiemi ed f : A→ B, allora f e unisomorfismo tra (A,R) e (B,S) se f e biiettiva e∀x , y ∈ A (xRy ⇔ f (x)Sf (y))

I R e un ordine totale (stretto) su A se e irriflessiva (∀x ∈ A¬xRx),transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale(∀x , y ∈ A (x = y ∨ xRy ∨ yRx))

I . . .

Si puo dunque in questo frammento di ZFC cominciare a sviluppare lamatematica ordinaria (per garantire l’esistenza di altri enti importanti inmatematica c’e bisogno degli altri assiomi). Ma la teoria risultaabbastanza interessante da studiare per interesse indipendente.

Definizione.

I domR = {x | ∃y(x , y) ∈ R}

I f e una funzione se e una relazione e ∀x ∈ domf ∃!y(x , y) ∈ f . Taley e denotato f (x). Se domf = A e f ⊆ A× B, si scrive f : A→ B.Una tale f e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x) 6= f (y)) e∀z ∈ B ∃x ∈ A f (x) = z .

I . . .

Definizione.

I . . .

Definizione.

I . . .

Definizione.

I . . .

Definizione.

I . . .

Definizione.

I . . .

Buoni ordini

Un concetto importante in molte aree della matematica e fondamentalein teoria degli insiemi e quello di buon ordine.

Definizione. Una relazione d’ordine (A,R) e un buon ordine se ognisottoinsieme non vuoto B ⊆ A ha un elemento minimo rispetto a R.

Lemma. Se (A,R) e un buon ordine e a ∈ A, allora (A,R) non eisomorfo al suo segmento iniziale ({x ∈ A | xRa},R).

Dimostrazione. Se f : A→ {x ∈ A | xRa} e un isomorfismo, l’elementomin{y ∈ A | f (y) 6= y} produce una contraddizione.

Lemma. Se (A,R), (B,S) sono buoni ordini isomorfi, l’isomorfismo traloro e unico.

Dimostrazione. Se f , g : A→ B sono isomorfismi, l’esistenza dimin{y ∈ A | f (y) 6= g(y)} fornisce una contraddizione.

Buoni ordini

Teorema. Se (A,R), (B,S) sono buoni ordini, vale esattamente unadelle alternative seguenti:

1. (A,R), (B,S) sono isomorfi

2. (A,R), ({y ∈ B | ySb},S) sono isomorfi, per qualche b ∈ B

3. ({x ∈ A | xRa},R), (B,S) sono isomorfi, per qualche a ∈ A

Dimostrazione. Sia

f = {(a, b) ∈ A× B | {x ∈ A | xRa} ' {y ∈ B | ySb}}.

Allora f e un isomorfismo tra un segmento iniziale di A e un segmentoiniziale di B, e non possono essere entrambi propri.

Buoni ordini

Teorema. Se (A,R), (B,S) sono buoni ordini, vale esattamente unadelle alternative seguenti:

1. (A,R), (B,S) sono isomorfi

2. (A,R), ({y ∈ B | ySb},S) sono isomorfi, per qualche b ∈ B

3. ({x ∈ A | xRa},R), (B,S) sono isomorfi, per qualche a ∈ A

Dimostrazione. Sia

f = {(a, b) ∈ A× B | {x ∈ A | xRa} ' {y ∈ B | ySb}}.

Allora f e un isomorfismo tra un segmento iniziale di A e un segmentoiniziale di B, e non possono essere entrambi propri.

Ordinali

Definizione.

I Un insieme x e transitivo se ogni elemento di x e sottoinsieme di x :∀y ∈ x y ⊆ x

I x e un numero ordinale se e transitivo e la relazione ∈ e un buonordine su x

Esempi d’ordinali (i numeri naturali)

I 0 = ∅I 1 = {0}I 2 = {0, 1} = {∅, {∅}}I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}I . . .

Con gli assiomi introdotti finora non si puo dimostrare l’esistenza di altriordinali.

Ordinali

Definizione.

I 0 = ∅I 1 = {0}I 2 = {0, 1} = {∅, {∅}}I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}I . . .

Ordinali

Definizione.

I 0 = ∅

I 1 = {0}I 2 = {0, 1} = {∅, {∅}}I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}I . . .

Ordinali

Definizione.

I 0 = ∅I 1 = {0}

I 2 = {0, 1} = {∅, {∅}}I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}I . . .

Ordinali

Definizione.

I 0 = ∅I 1 = {0}I 2 = {0, 1} = {∅, {∅}}

I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}I . . .

Ordinali

Definizione.

I 0 = ∅I 1 = {0}I 2 = {0, 1} = {∅, {∅}}I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I . . .

Ordinali

Definizione.

I 0 = ∅I 1 = {0}I 2 = {0, 1} = {∅, {∅}}I 3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}I . . .

Ordinali

Teorema.

1. Se x e un ordinale e y ∈ x , allora y e un ordinale e y e l’insieme dei∈-predecessori di se stesso in x

2. Se x , y sono ordinali e x ' y , allora x = y

3. Se x , y sono ordinali, esattamente una delle seguenti alternativevale: x ∈ y , x = y , y ∈ x

4. Se x , y , z sono ordinali e x ∈ y , y ∈ z , allora x ∈ z

5. Se C e un insieme non vuoto di ordinali, allora∃x ∈ C ∀y ∈ C (x = y ∨ x ∈ y)

6. Se ϕ e una formula soddisfatta da almeno un ordinale, allora c’e unminimo ordinale che la soddisfa

Dimostrazione. (5) Sia x ∈ C . Se x ∩ C = ∅, allora x e ∈-minimo in C .Altrimenti min(x ∩ C ) = min C .(6) Simile a (5). Si esprime anche dicendo che ogni classe non vuota diordinali ha un minimo.

Ordinali

Teorema.

Ordinali

Teorema.

Ordinali

Teorema.

Ordinali

Teorema.

Ordinali

Lemma. Se A e un insieme transitivo di ordinali, allora A e un ordinale.

Teorema. Se (A,R) e un buon ordine, allora c’e un unico ordinale Cisomorfo a (A,R).

Dimostrazione. (Esistenza) Siano

B = {a ∈ A | ∃x (x e un ordinale e {b ∈ A | bRa} ' x)}f (a) = l’unico x tale che {b ∈ A | bRa} ' x .

Se C = imf e l’immagine di f , per il lemma precedente C e un ordinale ef : B → C e un isomorfismo. Se fosse B 6= A, sia m = min(A \ B).Allora B = {a ∈ A | aRm}, da cui m ∈ B, contraddizione.

Gli ordinali sono dunque rappresentanti dei tipi d’ordine dei buoni ordini.

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α e Sα = α ∪ {α}.

Lemma. Per ogni ordinale α:

I S(α) e un ordinale

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Inoltre, se X e un insieme non vuoto di ordinali, sup X =⋃

Ordinali

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Ordinali

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Ordinali

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Ordinali

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Ordinali

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Ordinali

I α < Sα

I ∀β(β < Sα⇔ β ≤ α)

Ordinali

Definizione. Un ordinale α e

I un ordinale successore se α = Sβ per qualche β

I un ordinale limite se non e 0 ne un ordinale sucessore

Definizione. α e un numero naturale se∀β ≤ α (β = 0 ∨ β e successore).

I naturali formano quindi un segmento iniziale degli ordinali.

Ordinali

Operazioni sugli ordinali

Si definiscono, per induzione transfinita, alcune operazioni sugli ordinali(che coincidono sui naturali con le corrispondenti operazioni aritmetiche):

Addizione.

I α + 0 = α

I α + Sβ = S(α + β)

I Se λ e un ordinale limite, α + λ = sup{α + β | β < λ}α + β e il tipo d’ordine di un’unione disgiunta di un tipo d’ordine α conin coda un tipo d’ordine β.

Per esempio, α + 1 = Sα.

Addizione.

I α + 0 = α

I α + Sβ = S(α + β)

I Se λ e un ordinale limite, α + λ = sup{α + β | β < λ}

α + β e il tipo d’ordine di un’unione disgiunta di un tipo d’ordine α conin coda un tipo d’ordine β.

Addizione.

I α + 0 = α

I α + Sβ = S(α + β)

I Se λ e un ordinale limite, α + λ = sup{α + β | β < λ}α + β e il tipo d’ordine di un’unione disgiunta di un tipo d’ordine α conin coda un tipo d’ordine β.

Moltiplicazione

I α0 = 0

I αSβ = αβ + α

I Se λ e un ordinale limite, αλ = sup{αβ | β < λ}

αβ e il tipo d’ordine di α× β ordinato antilessicograficamente.

Esponenziazione.

I α0 = 1

I αβ+1 = αβα

Moltiplicazione

I α0 = 0

I αSβ = αβ + α

I Se λ e un ordinale limite, αλ = sup{αβ | β < λ}αβ e il tipo d’ordine di α× β ordinato antilessicograficamente.

Esponenziazione.

I α0 = 1

I αβ+1 = αβα

Moltiplicazione

I α0 = 0

I αSβ = αβ + α

I Se λ e un ordinale limite, αλ = sup{αβ | β < λ}αβ e il tipo d’ordine di α× β ordinato antilessicograficamente.

Esponenziazione.

I α0 = 1

I αβ+1 = αβα

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x(0 ∈ x | ∀y ∈ x Sy ∈ x)

8. Potenza: ∃y∀z(z ⊆ x ⇒ z ∈ y)

9. Scelta: ∃f : F →⋃F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X )

L’assioma della scelta e equivalente alPrincipio del buon ordinamento. Ogni insieme e bene ordinabile.Lemma di Zorn. Se A e un insieme (parzialmente) ordinato tale cheogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora Aha un elemento massimale.

(Un ordine parziale ≤ e una relazione riflessiva: ∀x x ≤ x ; transitiva:∀x , y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:∀x , y (x ≤ y ∧ y ≤ x ⇒ x = y). E totale se ∀x , y (x ≤ y ∨ y ≤ x).)

Definizione. L’insieme dei numeri naturali, che esiste per gli assiomadell’infinito e di separazione, e indicato con ω.

Teorema. ω e un ordinale. E il minimo degli ordinali infiniti (cioe non inbiiezione con un numero naturale).

Definizione. P(x) = {z | x ⊆ x} e l’insieme potenza di x .

L’assioma della scelta e equivalente alPrincipio del buon ordinamento. Ogni insieme e bene ordinabile.

Lemma di Zorn. Se A e un insieme (parzialmente) ordinato tale cheogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora Aha un elemento massimale.

Numeri cardinali

Definizione. Dato un insieme A, la cardinalita di A, denotata |A|, e ilminimo ordinale α in biiezione con A (l’esistenza di α e l’enunciatodell’assioma della scelta).Se α e tale che |A| = α per qualche α (equivalentemente, α = |α|),allora α e un numero cardinale.L’insieme A e finito se |A| e un numero naturale.L’insieme A e numerabile se |A| ≤ ω.

Teorema. Se κ, λ sono cardinali

I κ = λ sseesiste una bijezione κ→ λ sseesistono iniezioni κ→ λ, λ→ κ

I κ ≤ λ sseesiste una iniezione κ→ λ sseesiste una suriezione λ→ κ

Numeri cardinali

Definizione. Dato un insieme A, la cardinalita di A, denotata |A|, e ilminimo ordinale α in biiezione con A (l’esistenza di α e l’enunciatodell’assioma della scelta).Se α e tale che |A| = α per qualche α (equivalentemente, α = |α|),allora α e un numero cardinale.L’insieme A e finito se |A| e un numero naturale.L’insieme A e numerabile se |A| ≤ ω.

Teorema. Se κ, λ sono cardinali

I κ = λ sseesiste una bijezione κ→ λ sseesistono iniezioni κ→ λ, λ→ κ

I κ ≤ λ sseesiste una iniezione κ→ λ sseesiste una suriezione λ→ κ

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.Viceversa, si mostra che non c’e alcuna suriezione A→ P(A). Siag : A→ P(A) una funzione. Allora I = {x ∈ A | x /∈ g(x)} /∈ img .

Definizione.

I α+ e il minimo cardinale piu grande di α.

I κ e un cardinale successore se κ = α+ per qualche α.

I Un cardinale κ e un cardinale limite se κ > ω e κ non e un cardinalesuccessore.

Teorema. |A| < |P(A)|.Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’e alcuna suriezione A→ P(A). Siag : A→ P(A) una funzione. Allora I = {x ∈ A | x /∈ g(x)} /∈ img .

Definizione.

Teorema. |A| < |P(A)|.Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.Viceversa, si mostra che non c’e alcuna suriezione A→ P(A). Siag : A→ P(A) una funzione. Allora I = {x ∈ A | x /∈ g(x)} /∈ img .

Definizione.

La sequenza degli ℵ

Si definisce la sequenza dei cardinali ℵα = ωα:

Definizione.

I ω0 = ω

I ωα+1 = ω+α

I Se λ e un ordinale limite, ωλ = sup{ωα | α < λ}

Teorema.

1. La sequenza degli ℵα contiene tutti e soli i numeri cardinali

2. α < β ⇒ ℵα < ℵβ3. ℵα e un cardinale successore sse α e un ordinale successore; ℵα e un

cardinale limite sse α e un ordinale limite

Definizione.

I ω0 = ω

I ωα+1 = ω+α

Teorema.

Definizione.

I ω0 = ω

I ωα+1 = ω+α

Teorema.

Definizione.

I ω0 = ω

I ωα+1 = ω+α

Teorema.

Definizione.

I ω0 = ω

I ωα+1 = ω+α

Teorema.

Operazioni sui cardinali

Si possono definire operazioni di somma, prodotto e esponenziazionecardinale. Estendono le corrispondenti operazioni sui naturali, ma noncoincidono con le operazioni definite sugli ordinali infiniti.

Addizione. κ+ λ e la cardinalita di un’unione disgiunta di un insieme dicardinalita κ e uno di cardinalita λ:κ+ λ = |(κ× {0}) ∪ (λ× {1})|.

Moltiplicazione. κ+ λ e la cardinalita di un prodotto cartesiano di uninsieme di cardinalita κ e uno di cardinalita λ:κλ = |κ× λ|.

Tuttavia queste operazioni non sono interessanti: se almeno uno tra κ eλ e infinito,κ+ λ = κλ = max(κ, λ).

Si possono definire operazioni di somma, prodotto e esponenziazionecardinale. Estendono le corrispondenti operazioni sui naturali, ma noncoincidono con le operazioni definite sugli ordinali infiniti.

Addizione. κ+ λ e la cardinalita di un’unione disgiunta di un insieme dicardinalita κ e uno di cardinalita λ:κ+ λ = |(κ× {0}) ∪ (λ× {1})|.

Moltiplicazione. κ+ λ e la cardinalita di un prodotto cartesiano di uninsieme di cardinalita κ e uno di cardinalita λ:κλ = |κ× λ|.

Tuttavia queste operazioni non sono interessanti: se almeno uno tra κ eλ e infinito,κ+ λ = κλ = max(κ, λ).

Definizione. Per A,B insiemi, AB = BA = {f : B → A}.

Se κ, λ sono ordinali, e di solito preferibile usare la notazione λκ perquesto insieme di funzioni, per evitare confusione col numero cardinaleκλ.

Esponenziazione. Se κ, λ sono cardinali, κλ = |λκ|.

Esempi.2λ = |P(λ)|2ℵ0 = |R| e la cardinalita del continuo

Teorema. Se 2 ≤ κ ≤ λ e λ e infinito, λ < 2λ = κλ.

Dimostrazione. 2λ ≤ κλ ≤ λλ ≤ |P(λ× λ)| = |P(λ)| = 2λ.

Definizione. Per A,B insiemi, AB = BA = {f : B → A}.Se κ, λ sono ordinali, e di solito preferibile usare la notazione λκ perquesto insieme di funzioni, per evitare confusione col numero cardinaleκλ.

Esempi.2λ = |P(λ)|

2ℵ0 = |R| e la cardinalita del continuo

Dimostrazione. 2λ ≤ κλ

≤ λλ ≤ |P(λ× λ)| = |P(λ)| = 2λ.

Dimostrazione. 2λ ≤ κλ ≤ λλ

≤ |P(λ× λ)| = |P(λ)| = 2λ.

Dimostrazione. 2λ ≤ κλ ≤ λλ ≤ |P(λ× λ)|

= |P(λ)| = 2λ.

Dimostrazione. 2λ ≤ κλ ≤ λλ ≤ |P(λ× λ)| = |P(λ)|

= 2λ.

L’ipotesi del continuo

Il teorema di Cantor asserisce che ∀α 2ℵα ≥ ℵα+1.

Definizione.

I CH e l’enunciato: 2ℵ0 = ℵ1I GCH e l’enunciato ∀α 2ℵα = ℵα+1

Si tratta dei piu famosi enunciati indipendenti in ZFC , cioe tali che (seZFC e consistente) ne essi ne le loro negazioni sono dimostrabili.

Definizione.

La cofinalita

Definizione. Sia L = (L,≤) un ordine totale senza massimo elemento.La cofinalita cof (L) di L e il minimo ordinale α tale che esiste unafunzione illimitata (cofinale) f : α→ L.

La funzione f puo essere presastrettamente crescente.In particolare, cof (L) ≤ |L|.

Lemma.

1. cof (L) e un cardinale

2. Se α, β sono ordinali limiti e f : α→ β e strettamente crescente ecofinale, allora cof (α) = cof (β)

3. cof (cof (β)) = cof (β)

Dimostrazione (2) cof (β) ≤ cof (α) per l’esistenza della funzione cofinalecof (α)→ α→ β. Viceversa, sia g : cof (β)→ β cofinale eh : cof (β)→ α definita da h(ξ) = min{η | f (η) > g(ξ)}.

La cofinalita

Definizione. Sia L = (L,≤) un ordine totale senza massimo elemento.La cofinalita cof (L) di L e il minimo ordinale α tale che esiste unafunzione illimitata (cofinale) f : α→ L. La funzione f puo essere presastrettamente crescente.

In particolare, cof (L) ≤ |L|.

Lemma.

La cofinalita

Definizione. Sia L = (L,≤) un ordine totale senza massimo elemento.La cofinalita cof (L) di L e il minimo ordinale α tale che esiste unafunzione illimitata (cofinale) f : α→ L. La funzione f puo essere presastrettamente crescente.In particolare, cof (L) ≤ |L|.

Lemma.

La cofinalita

Lemma.

La cofinalita

Lemma.

La cofinalita

Esempi. cof (ω) = ω.

cof (ℵ1) = ℵ1; piu in generale, ogni cardinale successore e regolare.cof (ℵω) = ω, infatti f : ω → ℵω, n 7→ ℵn e illimitata

In generale, se α e un ordinale limite, allora cof (ℵα) = cof (α). Dunquese ℵα e un cardinale limite regolare, ℵα = α. Questa condizione non epero sufficiente: sia

I α0 = ℵ0I αn+1 = ℵαn

I α = sup{αn | n ∈ ω}Allora ℵα = α, ma cof (ℵα) = cof (α) = ω.

cof (κ) = λ significa che κ e unione di λ insiemi di cardinalita minore diκ.

La cofinalita

Esempi. cof (ω) = ω.cof (ℵ1) = ℵ1; piu in generale, ogni cardinale successore e regolare.

cof (ℵω) = ω, infatti f : ω → ℵω, n 7→ ℵn e illimitata

La cofinalita

Esempi. cof (ω) = ω.cof (ℵ1) = ℵ1; piu in generale, ogni cardinale successore e regolare.cof (ℵω) = ω, infatti f : ω → ℵω, n 7→ ℵn e illimitata

La cofinalita

In generale, se α e un ordinale limite, allora cof (ℵα) = cof (α).

Dunquese ℵα e un cardinale limite regolare, ℵα = α. Questa condizione non epero sufficiente: sia

La cofinalita

In generale, se α e un ordinale limite, allora cof (ℵα) = cof (α). Dunquese ℵα e un cardinale limite regolare, ℵα = α.

Questa condizione non epero sufficiente: sia

La cofinalita

I α = sup{αn | n ∈ ω}Allora ℵα = α,

ma cof (ℵα) = cof (α) = ω.

La cofinalita

Cardinali inaccessibili

Un modo di costruire in ZFC dei cardinali via via piu grandi e di iterare leoperazioni di potenza κ 7→ 2κ e estremo superiore{κα | α < λ} 7→ sup{κα | α < λ}:

quest’ultimo ha cofinalita ≤ λ.

Definizione. Un cardinale infinito κ e regolare se cof (κ) = κ. Altrimentie singolare.

Per esempio: ℵ0 e i cardinali successori sono regolari; ℵω e singolare.

Un modo di costruire in ZFC dei cardinali via via piu grandi e di iterare leoperazioni di potenza κ 7→ 2κ e estremo superiore{κα | α < λ} 7→ sup{κα | α < λ}: quest’ultimo ha cofinalita ≤ λ.

Definizione.

I κ e debolmente inaccessibile se κ e un cardinale limite regolare

I κ e fortemente inaccessibile se κ > ℵ0, κ e regolare e ∀λ < κ 2λ < κ

Quindi: κ fortemente inaccessibile ⇒ κ debolmente inaccessibile(GCH) κ fortemente inaccessibile ⇔ κ debolmente inaccessibile

L’esistenza di cardinali debolmente inaccessibili non e dimostrabile inZFC.

E equiconsistente con l’esistenza di un debolmente inaccessibile che 2ℵ0

sia debolmente inaccessibile, o che sia piu grande che un debolmenteinaccessibile.

Definizione.

Quindi: κ fortemente inaccessibile ⇒ κ debolmente inaccessibile

(GCH) κ fortemente inaccessibile ⇔ κ debolmente inaccessibile

Definizione.

La teoria degli insiemi

I Combinatorica infinita

I Grandi cardinali

I Dimostrazioni di consistenza e indipendenza

I Modelli interni

I Forcing

I Teoria descrittiva degli insiemi

I Determinatezza

I Set theoretic topology

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Grandi cardinali

I Modelli interni

I Forcing

I Determinatezza

I Fuzzy set theory

I Combinatorica infinita (l’assioma di Martin, l’ipotesi di Suslin)

I Teoria descrittiva degli insiemi (teorema di Cantor-Bendixson)

Teoria degli insiemi - calvino.polito.itcalvino.polito.it/~camerlo/gargnan2014-1.pdf · Cos’ e la...

Documents

Transcript of Teoria degli insiemi - calvino.polito.itcalvino.polito.it/~camerlo/gargnan2014-1.pdf · Cos’ e la...

Luigi Cerlienco - Corsi · Cap. 1 Elementi di logica matematica e di teoria degli insiemi 1.1 Enunciati e predicati pag. 1 1.2 Connettivi ′′ 2 1.3 Come deﬁnire gli insiemi ′′

ECDL - Modulo 1 - Concetti base delle tecnologie ICT 1 Concetti base... · teoria degli insiemi, fisica quantistica, economia, informatica, teoria dei giochi, fluidodinamica e in

Elementi di Teoria degli Insiemi, 2010-11 - dm.unipi.itberardu/Didattica/Appunti/Insiemi/Berarducci... · Elementi di Teoria degli Insiemi, 2010-11 Alessandro Berarducci Versione

La Matematica tra le mani dei giovani - Ivano Coccorullo · 2013. 12. 27. · Battipaglia 05/02/13 La Matematica tra le mani dei giovani Gli Insiemi La teoria degli insiemi svolge

Cantor e la teoria degli insiemi - Parlando di storia e ... · che si interessó alla musica imparando a suonare il violino. ... Da quel momento, ... teoria degli insiemi sono attualmente

TEORIA Introduzione alla probabilità · 4 TEORIA CAPITOLO . INTRODUZIONE ALLA PROBABILITÀ Gli eventi e gli insiemi Consideriamo il lancio di un dado e l’evento «esce un numero

Teoria degli Insiemi - unipa.itmath.unipa.it/~fbenanti/InsiemiAlgebra1201516.pdf · 2015. 10. 9. · Definizione: Dati due insiemi Ae B, si de nisce prodotto cartesiano di Ae B, e

C. Gaibisso Programmazione di calcolatori Lezione III Cenni di teoria ingenua degli insiemi Programmazione di calcolatori: Cenni di teoria ingenua degli.

Algebra 1 - Teoria degli insiemi e delle funzioni · Web viewGeneralità sulla teoria degli insiemi e delle funzioni. Parte I - Insiemi. Prendiamo le mosse, nel nostro itinerario

Cenni Di Logica e Teoria Degli Insiemi

Insiemi Lezione 1: Probabilità e Teoria degli InsiemiInsiemi Operazioni sugli insiemi La Probabilità Gli Insiemi Se Sè l’insieme di tutti gli scalari x2[0;1], può essere scritto

I Insiemi e funzioni - Syllogismos · Insiemi e funzioni 1. TEORIA DEGLI INSIEMI 1.1. Insiemi ... Tra tutti i sottoinsiemi di un insieme dato A troviamo sempre l’insieme A ... Il

Cenni di logica e teoria degli insiemi - pagine.dm.unipi.itpagine.dm.unipi.it/paolini/didattica/appunti/logica.pdf · Cenni di logica e teoria degli insiemi E. Paolini 2 novembre

Embedding di uno spazio metrizzabile e compatto nello ... · gico, di insiemi aperti, chiusi, e alcuni concetti elementari della teoria degli insiemi. Nel secondo capitolo verranno

Teoria della Normalizzazione - · no riferimento a due insiemi, ma possono essere estese in maniera ovvia ad un numero n arbitrario di insiemi. Il numero n delle componenti del prodotto

Teoria della misura - Dipartimento di Matematica - UniPDvargiolu/CalPro/TeoriaDellaMisura.pdf · la teoria della misura `e nata proprio per estendere la misura di Riemann ad insiemi

A. Berarducci - Elementi Di Teoria Degli Insiemi

Teoria degli insiemi - polito.itcalvino.polito.it/~camerlo/gargnan2014-1.pdf · La teoria degli insiemi e il fondamento della matematica. Questa a ermazione e singolare: la teoria

GLI INSIEMI - dp · 2006. 8. 15. · Nella teoria ingenua degli insiemi, e per i ﬁni tutti dell’educazione matematica nella scuola secondaria, deﬁniamo Insieme un aggregato

Categoricità, dalla teoria dei modelli alla teoria degli insiemi? · 2019. 4. 14. · Categoricità, dalla teoria dei modelli alla teoria degli insiemi? Andrés Villaveces Univ.