Il precedente lemma ci dice che Φ `e suriettiva e quindi 2κ = |P(B)| ≤ |P(ω)| = 2ω. Ovviamente da κ≥ ω segue 2κ≥ 2ω e quindi 2κ= 2ω. ✷
Dunque anche la Questione 1 `e risolta.
Corollario 2.2.10 MA implica che 2ω`e regolare.
Dimostrazione: Se κ < 2ω, `e 2κ = 2ω per il teorema precedente. Per il Teorema di K¨onig si ha allora cf(2ω) = cf(2κ) > κ, per ogni κ < 2ω. Dunque cf(2ω) = 2ω. ✷
Si pu`o dimostrare che `e consistente con ZFC che 2ω sia un cardinale singolare comeℵω1.
2.3 Un accenno al calcolo delle partizioni
Si consideri il seguente problema da salotto. Si pensi ad un ricevimento al quale partecipano almeno sei persone. Allora o tre di queste persone gi`a si conoscevano mutuamente prima di partecipare al ricevimento o tre di queste erano mutuamente estranee. Vediamo di ragionarci un po’ su. Si supponga che non ci siano tre persone che gi`a si conoscevano in precedenza l’una l’altra. Si prenda quindi a caso uno dei partecipanti, diciamo il Sig. Rossi. Il resto dei convenuti si divide fra quelli che gi`a conoscevano Rossi (classe C) e quelli che non lo conoscevano (classe S). Se due persone di S non si conoscono, abbiamo concluso: con Rossi fanno tre che non si conoscono l’un l’altro. Supponiamo allora che le persone in S si conoscano l’una l’altra. Ma allora possono essere al pi`u due!
Rossi conosce tutte le persone in C. Se due di queste si conoscevano prima del ricevimento, allora ce ne sono tre che si conoscono l’un l’altro, contro l’ipotesi. Dunque due qualsiasi persone in C non si conoscevano in precedenza. Ma, poich´e|S| ≤ 2, allora |C| ≥ 3. Il fatto `e provato.
Questa `e una semplicissima accezione di un teorema alla Ramsey. Per enunciare teoremi di questo tipo sar`a opportuno stabilire un’opportuna notazione.
Definizione 2.3.1 (a) Diremo che{Pi: i∈ I} `e una partizione di Z se gli insiemi Pi sono a due a due disgiunti e
i∈I
Pi= Z; non
escluder-emo che qualche Pi possa essere vuoto.
(b) Sia [X]ρ = {Y ⊂ X: |Y | = ρ}. Se [X]ρ `e ripartito negli insiemi {Pi: i∈ I} diremo che Y ⊂ X `e omogeneo per la partizione se esiste qualche i∈ I tale che [Y ]ρ⊂ Pi.
Il gioco che abbiamo raccontato sopra si pu`o descrivere come segue. Se
|X| ≥ 6 e [X]2`e ripartito in due classi, allora esiste un sottoinsieme Y ⊂ X
che `e omogeneo per la partizione e tale che |Y | ≥ 3. Si usa la seguente
notazione “freccia” per esprimere concisamente il fatto appena detto: 6→ (3)2
2 .
Il numero che appare in posizione di apice dice quanti sono gli elementi contenuti in ogni sottoinsieme (qui consideriamo coppie di elementi di X); il numero che compare in posizione di pedice dice quante sono le classi della partizione.
Pi`u in generale, la notazione freccia si scrive come segue
κ→ (λ)ρ σ ,
si legge ”κ freccia λ ρ σ” e ha il seguente significato: Se si ripartisce [κ]ρ (o l’insieme dei sottoinsiemi di cardinalit`a ρ estratti da un qualsiasi insieme
A di cardinalit`a κ) in σ classi, allora esiste un sottoinsieme di cardinalit`a λ estratto da κ (da A) ch e `e omogeneo. Il Teorema di Ramsey per gli insiemi finiti afferma che comunque si prendano numeri interi j, m, k < ω esiste
n < ω tale che n→ (j)m k . Dimostreremo il seguente Teorema 2.3.1 [Ramsey, 1930]∀n, m < ω, ω → (ω)n m.
Prima di dimostrare il Teorema di Ramsey ne dedurremo alcune interessanti conseguenze
Teorema 2.3.2 Ogni insieme parzialmente ordinato e infinito possiede o
un’anticatena infinita o un sottoinsieme infinito d’elementi a due a due compatibili.
Dimostrazione: Sia A un sottoinsieme numerabilmente infinito di un insieme parzialmente ordinato, e sia [A]2= P1∪ P2, dove {x, y} ∈ P1 se e solo se x e y sono incompatibili; altrimenti{x, y} ∈ P2. Sia H un insieme infinito omogeneo, sottoinsieme di A. Se [H]2⊂ P1allora gli elementi di H formano un’anticatena. Se [H]2⊂ P2, allora∪H (cio`e gli elementi di H) `e
un insieme infinito di elementi a due a due compatibili. ✷
Proposizione 2.3.3 Siano κ, λ, ρ, σ, τ numeri cardinali. Supponiamo che
κ→ (λ)ρ
σ. Allora
(a) Se τ > κ, `e τ→ (λ)ρ σ.
2.3. CALCOLO DELLE PARTIZIONI 73 (b) Se τ < λ, `e κ→ (τ)ρ σ. (c) Se τ < σ, `e κ→ (λ)ρ τ. Dimostrazione:
(a) Data la partizione {Pα: α < σ} di [τ]ρ, si consideri{P
α: α < σ} con P
α= Pα∩ [κ]ρ. Gli insiemi omogenei per P
α lo sono per Pα.
(b) Se `e dato un insieme omogeneo di cardinalit`a λ, basta ridurlo a uno di cardinalit`a τ .
(c) Ogni partizione in τ classi `e anche una partizione in σ classi. Basta che gli insiemi aggiunti siano vuoti. ✷
Per ogni κ infinito le relazioni κ→ (κ)1
2 e κ→ (κ)2
1 sono ovvie. Perci`o la pi`u semplice relazione freccia non banale `e κ→ (κ)2
2
Proposizione 2.3.4 Se κ `e infinito e κ→ (κ)2
2, allora κ→ (κ)2
mper ogni m≥ 2.
Dimostrazione: (Per induzione su m.) Supponiamo vera κ→ (κ)2
m−1 e sia P1, P2, . . . , Pm una partizione di [κ]2. Definiamo P1 = P1∪ P2 e, per
i > 1, Pi = Pi+1. Allora i Pi sono una partizione in m− 1 classi di [κ]2
ed esiste un sottoinsieme Y omogeneo di cardinalit`a κ. Se [Y ]2 ⊂ P i, con
i > 1, abbiamo finito. Se invece [Y ]2 ⊂ P
1 = P1∪ P2, poich´e, per ipotesi
κ→ (κ)2
2, esiste un sottoinsieme omogeneo Z di Y , tale che|Z| = κ. ✷
Per giungere alla dimostrazione del teorema 2.3.1 di Ramsey, comince-remo a dimostrare il seguente
Teorema 2.3.5 [A]. ω→ (ω)2 2.
Dimostrazione: Si supponga di avere ripartito [ω]2in due classi P0e P1. Costruiramo ricorsivamente due successioni, una di numeri naturali{kj: j∈ ω} e una di insiemi infiniti {Aj: j ∈ ω} tali che Aj+1⊂ Aj, kj ∈ Aj e per ogni j esista qualche i per il quale Aj+1 ⊂ {m: {kj, m} ∈ Pi}. Vediamo
come ci`o si possa fare. Poniamo k0 = 0 e A0 = ω. Supposto di avere determinato kj e Aj per j ≤ m in modo che sia soddisfatte le richieste
precedenti, si osservi che esiste qualche indice i per il quale l’insieme A =
{k: k > km, k ∈ Am,{km, k} ∈ Pi} `e infinito. Poniamo allora Am+1= A e scegliamo km+1∈ Am+1.
Dati che siano i kn, si definisca f (n) = i se e solo se∀m ∈ An+1{kn, m} ∈ Pi. La funzione f `e cos`ı definita per ogni n; im(f ) = {0, 1} ed ha
va-lore costante i su qualche insieme infinito B. Ma se n, m ∈ B, allora {kn, km} ∈ Pi, cosicch´e{kn: n∈ B} `e omogeneo. ✷
Teorema 2.3.6 [B]. Se ω→ (ω)2
2, allora ω→ (ω)n
mper ogni n, m∈ ω.
Dimostrazione: Per la precedente Proposizione 2.3.4, basta fissare m e la-vorare per induzione su n. Si supponga ω→ (ω)n
me siaP = {P1, P2, . . . , Pm}
una partizione di [ω]n+1. Per ogni k∈ ω sia Pk
i ={s ∈ [ω]n: s∪ {k} ∈ Pi}
e sia Pk = {Pk
1, Pk
2, . . . , Pk
m}. Ogni Pk `e una partizione di [ω\ {k}]n. Come abbiamo fatto nella dimostrazione del Teorema A costruiamo ricorsi-vamente due successioni{kj}, {Aj} una crescente di numeri naturali e una
di sottoinsiemi infiniti di ω tali che Aj+1⊂ Aj, kj ∈ Aj e ogni insieme Aj sia omogeneo per ogni Pkr, con r < j. Vediamo come ci`o si possa fare. Poniamo A0 = ω e ko = 0. Supposto che siano noti Ar e kr ∈ Ar, per
r≤ j, consideriamo le partizioni Pkr, r = 0, . . . , j e sia B0j⊂ Aj omogeneo per Pk0, B1j ⊂ Bj
0 omogeneo per Pk1, e cos`ı via. Allora Bjj `e omogeneo per tutti iPkr, con r≤ j; poniamo Aj+1= Bjj e kj+1∈ Aj+1. Ripetendo l’argomento del precedente teorema, dati che siano i kn, si definisca ora
f : ω→ {0, 1, . . . , m} come segue: f(3) = i se e solo se [A&+1]n⊂ Pk i . (La funzione `e ben definita perch´e A&+1 `e omogeneo per Pk). Esiste allora qualche i per il quale l’insieme B = {3: f(3) = i} `e infinito; si riconosce
infine che{k&: 3∈ B} `e omogeneo per la partizione originale P. ✷
Poich´e la validit`a dei Teoremi A e B implica quella del teorema di Ram-sey 2.3.1, la dimostrazione del teorema stesso `e cos`ı completata. ✷
Mostriamo ora che κ → (κ)2
2 `e una propriet`a di grande cardinale; in particolare, che κ `e fortemente inaccessibile se non `e numerabile.
Teorema 2.3.7 Se κ→ (κ)2
2, allora κ `e regolare.
Dimostrazione: Sia κα, α < cf(κ), una successione crescente di cardinali cofinale in κ. Per ogni β < κ, sia f (β) = minimo α tale che β < κα e diciamo β∼ γ se f(β) = f(γ). La relazione ∼ `e una relazione d’equivalenza
che divide [κ]2 in due classi: P1 contiene tutte le coppie che stanno in relazione ∼; P2 quelle che non stanno in relazione∼. Poich´e ogni κα< κ,
nessun insieme Y di cardinalit`a κ pu`o essere tale che [Y ]2⊂ P1. Dunque un insieme omogeneo di cardinalit`a κ contiene al pi`u un elemento in ogni classe d’equivalenza di ∼, cio`e al pi`u un elemento tra κα e κα+1. Perci`o
fκ = κ. ✷
Teorema 2.3.8 L’ordine lessicografico su λ2 non possiede n´e catene cre-scenti di tipo λ+, n´e decrescenti inversamente ordinate in tipo λ+.
Dimostrazione: Per assurdo sia F = {fα: α < λ+}, fα∈ F e α < β → fα <L fβ, dove <L `e l’ordine lessicografico. Per ogni assegnato f ∈ F
2.3. CALCOLO DELLE PARTIZIONI 75
sia d(f ) il minimo γ < λ tale che per qualche g ∈ F , sia f(γ) < g(γ) e f γ = g γ. Per ogni f `e tautologicamente f(d(f)) = 0. Sia Fγ ={f ∈ F : d(f ) = γ}. Se f ∈ Fγ, g∈ F `e un “testimone” per f se f γ = g γ e f (γ) < g(γ). Si osservi che g /∈ Fγ. Notiamo ora il seguente
Fatto 2.3.1 Siano f ∈ Fγ, g testimone per f . Allora h <L g per ogni h∈ Fγ.
Dimostrazione: Si supponga di no. Allora esiste qualche h∈ Fγ tale che
h >L g e quindi h >L f . Cosa fa h(γ) ? Se h(γ) = 0, allora h <L g,
contro l’ipotesi; se h(γ) = 1, allora h /∈ Fγ, ancora una contraddizione. L’affermazione `e provata. ✷
Dal fatto precedente segue che ogni Fγ ⊂ {fα: α < δ} per qualche δ < λ+, dove fδ `e un testimone per qualche f ∈ Fγ. Dunque ogni Fγ ha cardinalit`a |Fγ| ≤ λ e poich´e F = ∪γ<λFγ, |F | = λ, ma ci`o `e una
contraddizione.
Analogamente si dimostra che non esiste {fα: α < λ+}, con fα∈λ2 e
α < β→ fα>Lfβ. ✷
Teorema 2.3.9 Per ogni cardinale infinito λ, vale 2λ→ (λ+)2 2.
Dimostrazione: Sia {fα: α < 2λ} l’elenco degli elementi di λ2 e <L l’ordine lessicografico. Si ripartisca [λ2]2 in due classi: P1 ={{α, β}: α < β e fα <L fβ} e P2 = {{α, β}: α < β e fα >L fβ}. Un insieme
omoge-neo sarebbe una catena bene ordinata crescente oppure decrescente. Ma queste catene, come abbiamo dimostrato nel precedente Teorema 2.3.8, non possono esistere.
Tuttavia si pu`o provare
Teorema 2.3.10 [Erd˝os - Rado] (2λ)+→ (λ+)2 2.
Dimostrazione: Omessa. ✷
Vale infine
Teorema 2.3.11 Se κ→ (κ)2
2, allora κ `e fortemente limite.
Dimostrazione: Per assurdo sia λ < κ tale che 2λ ≥ κ. Allora κ → (κ)2 2
implicherebbe κ→ (λ+)22, essendo λ+≤ κ, e quindi 2λ → (λ+)22, contro il risultato precedentemente dimostrato nel Teorema 2.3.9. ✷
Tenuto conto dei risultati dei Teoremi 2.3.7 e 2.3.11 si conclude che se
κ→ (κ)2
2, allora κ `e fortemente inaccessibile.
Definizione 2.3.2 Un cardinale non numerabile κ si dice debolmente com-patto se κ→ (κ)2