ULTRAFILTRI E METODI NONSTANDARD

IN TEORIA COMBINATORIA DEI NUMERI

MAURO DI NASSO

1. Filtri e ultrafiltri
Iniziamo introducendo le fondamentali nozioni di filtro e ultrafiltro.

Definizione 1.1. Un filtro F su un insieme I una famiglia di sottoinsiemi di I

tale che:
(1) ∅ ∈
/F eI ∈F;
(2) Se A ∈ F e A ⊆ B allora B ∈ F ;
(3) Se A, B ∈ F allora A ∩ B ∈ F.

Ricordiamo che una famiglia di insiemi F ha la proprietà dell’intersezione finita

(in breve FIP, cioè “finite intersection property”) se ogni intersezione finita di ele-
menti in F è non vuota:
∀ A1 , . . . , An ∈ F A1 ∩ . . . ∩ An 6= ∅.
Dunque un filtro è una famiglia non vuota di insiemi che soddisfa la FIP ed è
chiusa per soprainsieme. Se G è una famiglia (non vuota) con la FIP, allora
hGi = {B | ∃ G1 , . . . , Gn ∈ G t.c. B ⊇ G1 ∩ . . . ∩ Gn }
è un filtro, che si dice filtro generato da G.

Esempio 1.2. Per ogni sottoinsieme X ⊆ I, la famiglia

FX = {A ⊆ I | X ⊆ A}
è un filtro, detto filtro principale generato da X.

Un esempio molto importante di filtro è il seguente.

Esempio 1.3. Il filtro di Frechet su un insieme infinito I è il filtro costituito da

tutti gli insiemi cofiniti, cioè dagli insiemi con complementare finito:
Fr(I) = {A ⊆ I | Ac è finito }.

Notiamo che Fr(I) è non principale.

Intuitivamente, un filtro F potrebbe essere pensato come una famiglia di insiemi
“grandi” rispetto ad una opportuna nozione di grandezza stabile per intersezioni
finite. Per questo talvolta diremo che un insieme A è “F-grande” per intendere che
A ∈ F . Tuttavia, questa interpretazione può essere fuorviante. Infatti, dato un
qualunque insieme infinito X ⊆ I “piccolo” rispetto ad I quanto si vuole, si possono
prendere filtri non principali F su I che contengano X. Chiaramente, X sarebbe
1
2 MAURO DI NASSO

allora “F-grande” mentre il complementare X c non lo sarebbe. Per questo, sembra

più appropriato pensare agli insiemi di un filtro come agli insiemi “importanti” o
“qualificati” rispetto ad un’opportuna qualità che non corrisponde necessariamente
ad un’idea di grandezza.

Proposizione 1.4. Sia F un filtro su un insieme I. Allora sono proprietà equiva-

lenti:
/ F ⇒ Ac ∈ F.
(1) A ∈
(2) A1 ∪ . . . ∪ An ∈ F ⇒ ∃i Ai ∈ F.
(3) F è un filtro massimale rispetto all’inclusione.
Dim. (1) ⇒ (2). Supponiamo per assurdo che Ai ∈ / F per tutti gli i. Allora per
l’ipotesi (1) avremmo che i complementari Aci ∈ F per tutti gli i. Dunque, per la
FIP, anche l’intersezione
Ac1 ∩ . . . ∩ Acn = (A1 ∪ . . . ∪ An )c ∈ F .
Questo assurdo, perchè contraddice l’ipotesi A1 ∪ . . . ∪ An ∈ F .
(2) ⇒ (3). Se F non è massimale, esiste un filtro F 0 ⊃ F che lo estende
propriamente. Prendo allora X ∈ F 0 \F. In particolare, il complementare X c ∈ / F 0,
c c
e quindi anche X ∈ / F. Ma allora I = X ∪ X ∈ F sarebbe l’unione di due insiemi
che non appartengono al filtro F, contro la (2).
(3) ⇒ (1). Supponiamo per assurdo che A, Ac ∈ / F, e consideriamo la famiglia
di insiemi:
G = {F ∩ A | F ∈ F}.
Dimostriamo che G ha la FIP. Se F1 , . . . , Fn ∈ F, allora (F1 ∩ A) ∩ . . . ∩ (Fn ∩ A) =
F ∩ A dove F = F1 ∩ . . . ∩ Fn ∈ F. Chiaramente F ∩ A 6= ∅, altrimenti F ⊆ Ac
implicherebbe che Ac ∈ F, contro la nostra assunzione. Consideriamo ora il filtro
F 0 = hGi generato da G. Notiamo che F 0 è un filtro che estende propriamente F.
Infatti F = F ∩ I ∈ G ⊆ F 0 per ogni F ∈ F, e inoltre A = I ∩ A ∈ G ⇒ A ∈ F 0 \ F .
Questo contraddice la massimalità di F. ¤

Definizione 1.5. Un filtro che soddisfi una (e quindi tutte) le proprietà precedenti
è detto ultrafiltro.

Esercizio 1.6. Due ultrafiltri U 6= V sono diversi se e solo se esiste X tale che
X ∈ U e il complementare X c ∈ V.

Su ogni insieme infinito I, il filtro di Frechet Fr(I) non è un ultrafiltro. Infatti,

basta prendere un insieme infinito A ⊂ I il cui complementare Ac sia infinito, ed
abbiamo che A, Ac ∈/ Fr(I).

Esempio 1.7. Per ogni elemento i ∈ I, il filtro generato dal singoletto {i}:
Ui = F{i} = {A ⊆ I | i ∈ I}
è un ultrafiltro, detto ultrafiltro principale generato da i.

In realtà, questi sono gli unici esempi possibili di ultrafiltri principali. Infatti:
 UMN 3

Proposizione 1.8. Sia U un ultrafiltro su un insieme infinito I. Allora sono

proprietà equivalenti:
(1) U è principale.
(2) U = Ui è l’ultrafiltro principale generato da un elemento i ∈ I.
(3) Il filtro di Frechet Fr(I) 6⊆ U non è incluso in U.
(4) Esiste un insieme finito F ∈ U.
Dim. (1) ⇔ (2). Una implicazione è banale. Viceversa, sia U = FX principale e
supponiamo per assurdo che X contenga almeno due elementi. Allora, preso x ∈ X,
da {x} ∪ (X \ {x}) = X ∈ U seguirebbe per la proprietà di ultrafiltro che {x} ∈ U
o X \ {x} ∈ U. Questo contraddice l’ipotesi U = FX perché né {x} nè X \ {x}
includono X.
(2) ⇒ (3). Se fosse Fr(I) ⊆ U allora per ogni i ∈ I avremmo {i}c ∈ U, e dunque
{i} ∈
/ U per ogni i ∈ I, cioè U 6= Ui per ogni i ∈ I.
(3) ⇒ (4). Per ipotesi esiste X ∈ Fr(I) con X ∈ / U . Dalla proprietà di ultrafiltro,
segue allora che il complementare X c , che è un insieme finito, appartiene ad U .
(4) ⇒ (2). Prendiamo un insieme finito F = {i1 , . . . , ik } ∈ U. Per la proprietà
di ultrafiltro, da {i1 } ∪ . . . ∪ {ik } = F ∈ U segue che {is } ∈ U per un opportuno is .
Ma allora U = Uis . ¤

L’esistenza di ultrafiltri non principali (che sono gli ultrafiltri che estendono il
filtro di Frechet) è garantita dal Lemma di Zorn, che è una delle forme equivalenti
dell’assioma di scelta.

Teorema 1.9. Per ogni filtro F su un insieme I, esiste un ultrafiltro U ⊇ F che

lo estende.
Dim. Sia G = {G filtro su I | G ⊇ F}. La famiglia G è parzialmente ordinata per
inclusione. Per poter applicare il Lemma di Zorn, occorre dimostrare l’esistenza di
un maggiorante per ogni catena. S Sia dunque hGj | j ∈ Ji una catena di elementi
di G. Banalmente, l’unione G = j∈J Gj include tutti i Gj (e dunque anche F).
Perché sia un maggiorante, resta da dimostrare che G ∈ G, cioè che G è un filtro. Se
A, B ∈ G, allora A ∈ Gj1 e B ∈ Gj2 per opportuni j1 , j2 ∈ J. Ma hGj | j ∈ Ji è una
catena, dunque sarà Gj1 ⊆ Gj2 (o viceversa). Quindi A, B ∈ Gj2 ⇒ A∩B ∈ Gj2 ⊆ G.
La verifica che G è anche chiuso per soprainsieme è immediata. Possiamo finalmente
applicare il Lemma di Zorn, ed ottenere l’esistenza di un elemento U massimale in
G, che è l’ultrafiltro cercato. ¤

In un senso preciso, non si possono definire ultrafiltri non principali.1 In altre

parole, nonostante si possa dimostrare che esistono (e lo abbiamo appena fatto!),
nessuno di loro può essere “descritto esplicitamente”. Per quanto possa apparire
strano, un fenomeno simile si ritrova anche nella combinatoria elementare. Ad
esempio, per il cosiddetto principio dei cassetti, se abbiamo n + 1 oggetti distribuiti
in n cassetti possiamo concludere che esiste un cassetto contenente almeno due
oggetti; ma “descrivere esplicitamente” quale sia un tale cassetto non è possibile.
1 Più precisamente, non esistono formule ϕ(x) della teoria degli insiemi tali che la teoria ZFC
dimostra entrambi gli enunciati: “Se vale ϕ(x) allora x è un ultrafiltro non principale” e “Esiste
ed unico x tale che ϕ(x)”.
4 MAURO DI NASSO

Nell’esercizio seguente, vediamo che avere un ultrafiltro non principale equivale

ad avere una misura finitamente additiva a due valori, che assegni misura nulla a
tutti i punti.

Esercizio 1.10.
(1) Sia µ : P(I) → {0, 1} una misura a due valori finitamente additiva e non-
atomica.2 Allora la famiglia Uµ = {A ⊆ I | µ(A) = 1} è un ultrafiltro non
principale.
(2) Viceversa, sia U un ultrafiltro non principale su I. Allora la funzione µU :
P(I) → {0, 1} definita ponendo µU (A) = 1 ⇔ A ∈ U è una misura a due
valori finitamente additiva e non-atomica.

Dunque un ultrafiltro U su un insieme I è in realtà una misura su I, sia pure

di tipo molto speciale. Per questo, data una qualunque proprietà P (i) relativa ad
elementi i ∈ I, a volte diremo che P vale U-quasi ovunque o vale per U-quasi ogni
i per intendere che {i ∈ I | P (i)} ∈ U.
Introduciamo ora un prodotto naturale tra ultrafiltri, che useremo in seguito per
dimostrare il teorema di Ramsey.

Definizione 1.11. Il prodotto tensoriale U ⊗ V di due ultrafiltri su I è l’ultrafiltro

su I × I definito ponendo per ogni A ⊆ I × I:
A ∈ U ⊗ V ⇐⇒ {i | Ai ∈ V} ∈ U.
Con Ai = {j ∈ I | (i, j) ∈ A} abbiamo denotato la fibra verticale di A corrispon-
dente all’ascissa i.

Dunque, un sottoinsieme A del prodotto cartesiano I × I è “U ⊗ V-grande” se e

solo se per una quantità “U-grande” di indici i, la corrispondente fibra verticale Ai
è “V-grande”.

Esercizio 1.12.
(1) Verificare che U ⊗ V è in effetti un ultrafiltro.
(2) Se U e V sono non principali, allora anche U ⊗ V è non principale. Mostrare
che l’implicazione inversa non vale.
(3) Vale la proprietà associativa: U ⊗ (V ⊗ W) = (U ⊗ V) ⊗ W.
(4) Non vale la proprietà commutativa: infatti, esistono ultrafiltri non princi-
pali U, V tali che U ⊗ V 6= V ⊗ U.

Concludiamo questo paragrafo con un esempio di applicazione dei filtri e degli ul-
trafiltri in topologia. Per definizione, il limite di una successione reale limn→∞ an =
l ∈ R se e solo se per ogni ² > 0, l’insieme di indici {n ∈ N | |an − l| < ²} per i quali
la successione è “²-vicina” ad l è un insieme cofinito, cioè appartiene al filtro di
Frechet Fr(N). Generalizzando, si ottiene un’utile nozione di limite che si applica
a spazi topologici qualunque.

2 Cioè µ soddisfa le proprietà: (1) µ(I) = 1, (2) µ(A ∪ B) = µ(A) + µ(B) = µ(A ∩ B), (3)
µ({i}) = 0 per ogni i ∈ I.
 UMN 5

Definizione 1.13. Sia X uno spazio topologico, e sia F un filtro su un insieme I.

Diciamo che una I-successione hxi | i ∈ Ii di elementi di X ha come F-limite il
punto x ∈ X, e scriviamo F-lim xi = x oppure limF xi = x, se per ogni intorno U
di x si ha
{i ∈ I | xi ∈ U } ∈ F.

Esercizio 1.14. Sia X uno spazio topologico. Allora:

(1) (Chiusura) Se hxi | i ∈ Ii è una I-successione di elementi di un sottospazio
Y ⊆ X che ha F-limite, allora limF yi ∈ Y appartiene alla chiusura di Y .
(2) (Unicità) Se X è di Hausdorff, allora per ogni insieme I e per ogni filtro F
su I, ogni I-successione di elementi di X ha al più un F-limite.
(3) (Esistenza) Se X è compatto, allora per ogni insieme I e per ogni ultrafiltro
U su I, ogni I-successione di elementi di X ha un U-limite.3

Considerando insiemi I di cardinalità sufficientemente grande, valgono anche le

implicazioni inverse.

Esercizio 1.15. ∗ Sia X uno spazio topologico, e sia κ la più piccola cardinalità
di una sua base di aperti.
(1) Sia Y ⊆ X un sottospazio e sia x ∈ Y . Allora esiste una κ-sequenza
hyi | i ∈ κi di elementi di Y e un filtro F su κ tali che limF yi = x.
(2) Se X non è di Hausdorff, allora esiste un filtro F su κ ed una κ-successione
di elementi di X avente due F-limiti diversi.
(3) Se X non è compatto, allora esiste un ultrafiltro U su κ ed una κ-successione
di elementi di X che non ha alcun U-limite.

Esercizio 1.16. In base ai due esercizi precedenti, si ottiene l’equivalenza: X è

compatto se e solo se per ogni I-successione hxi | i ∈ Ii di elementi di X e per ogni
ultrafiltro U su I, esiste U-lim xi ∈ X. Usando questa caratterizzazione dimostrare
il Teorema di Tychonoff: “Un prodotto topologico di spazi compatti è compatto”.

3 Nella definizione di spazio topologico compatto non si assume la proprietà di Hausdorff.