Appunti di Logica e Fondamenti di matematica

Francesco Lucibello 19 marzo 2022

Sommario

Insieme di appunti ordinati per una facile rilettura del corso di Logica e Fondamenti di Matematica dell’anno 2021/22.

1 Teoria ZF

Esistono vari sistemi di assiomi che permettono di descrivere la matematica, uno di questi è la Teoria degli insiemi di Zermelo-Fraenkel ed è quello utilizzato in questo corso.

1.1 Linguaggio di ZF

Il linguaggio utilizzato nella teoria ZF è un linguaggio del prim’ordine.

• Infinità numerabile di variabili proposizionali p, p, . . . 1 2
• Connettivi logici ¬, ∧, ∨, →, ←→
• Quantificatori ∀, ∃
• Parentesi (, ) servono ad evitare ambiguità
• Simboli di relazioni binarie ∈, =

1.2 Assiomi di ZF

Il seguente è l’elenco completo degli assiomi della teoria ZF (non sono tutti indipendenti fra loro, infatti per costruire la teoria non sono tutti necessari).

• Assioma di estensionalità
• Assioma dell’insieme vuoto
• Assioma della coppia non ordinata
• Assioma dell’unione
• Assioma dell’insieme delle parti
• Assioma di separazione
• Assioma dell’infinito
• Assioma di rimpiazzamento
• Assioma di fondazione

1

Ci sono altri due assiomi "aggiuntivi", che non fanno parte della teoria ZF, sono l’assioma della scelta e l’ipotesi del continuo. Se oltre agli assiomi di ZF si assume anche l’assioma della scelta, la teoria costruita si dice teoria ZFC.

Descriviamo tali assiomi singolarmente (alcuni verranno introdotti in seguito).

Assioma di estensionalità

Assioma 1.1 Se due insiemi hanno gli stessi elementi, allora coincidono.

∀x∀y(∀t(t ∈ ←→ ∈ →x t y) x = y)

Assioma dell’insieme vuoto

Assioma 1.2 Esiste un insieme privo di elementi.

∃x(∀y(y 6∈ x))

Osservazione 1.1. L’assioma dell’insieme vuoto garantisce l’esistenza di un insieme vuoto (cioè privo di elementi), mentre l’unicità è garantita dall’assioma di estensionalità, quindi è possibile definire l’insieme vuoto e denotarlo col simbolo ∅.

Assioma della coppia non ordinata

Assioma 1.3 Dati due insiemi x e y esiste un insieme i cui elementi sono x e y.

∀x∀y∃z(∀t(t ∈ ←→ ∨z (t = x t = y)))

Osservazione 1.2. Dati due insiemi x e y, l’esistenza di un insieme che abbia per elementi x e y è garantita da questo assioma, mentre l’unicità è garantita dall’assioma di estensionalità, quindi è possibile definire l’insieme della coppia non ordinata e denotarlo col simbolo {x, y}.

Assioma dell’unione - Forma provvisoria

Assioma 1.4 Dati due insiemi x e y esiste un insieme i cui elementi sono gli elementi di x e di y.

∀x∀y∃z(∀t(t ∈ ←→ ∈ ∨ ∈z (t x t y)))

Osservazione 1.3. Puoi definire l’unione ecc col simbolo ∪ x y.

Definizione 1.1 (Inclusione fra insiemi). Siano x e y, si dice che x è incluso in y e si scrive x ⊆ y se ∀t(t ∈ → ∈x t y)

Assioma dell’insieme delle parti

Assioma 1.5 Per ogni insieme x esiste un insieme i cui elementi sono i sottoinsiemi di x.

∀x∃y(∀t(t ∈ ←→ ⊆y t x))

Osservazione 1.4. Puoi definire l’insieme delle parti ... P(x)

Schema di assiomi di separazione

Assioma 1.6 Sia P una proprietà, allora per ogni insieme x esiste un insieme i cui elementi sono gli elementi di x che soddisfano P¹.

∀x∃y(∀t(t ∈ ←→ ∈ ∧y (t x P (t))))

o equivalentemente

Osservazione 1.5. Questo non è realmente un assioma ma uno schema di assiomi (perché abbiamo infinite proprietà P), grazie ad esso, possiamo definire l’insieme {t ∈ x : P (t)}

Osservazione 1.6. "L’insieme" del paradosso di Russell non è realmente un insieme secondo questa definizione (infatti nella teoria naive di Cantor era possibile ottenere un insieme data una qualsiasi proprietà, mentre per come abbiamo scritto l’assioma di separazione abbiamo bisogno sia di una proprietà che di un insieme e quindi l’insieme "naive" del paradosso non lo possiamo definire).

{x 6∈: x X}

Inesistenza dell’insieme degli insiemi

Teorema 1.1 Non esiste l’insieme degli insiemi.

6 ∃x(∀y(y ∈ x))

1 Una "proprietà" in ZF è un modo diverso per dire "formula", il concetto di "formula soddisfacibile", verrà introdotto molto più avanti, quindi per adesso pensala intuitivamente, però sappi che c’è una giustificazione formale di tutto questo.

2

Dimostrazione. Prendiamo un qualsiasi insieme A e dimostriamo che esiste un insieme B che non vi appartiene, di conseguenza non può esistere l’insieme degli insiemi. Sia A un insieme e sia per assurdo che allora se se {x ∈ 6∈ ∈ ∈ 6∈B = A : x x}, B A, B B =⇒ B B, un assurdo in entrambi i casi, quindi 6∈ ∈ 6∈B B =⇒ B B, B B.

Definizione 1.2 (Intersezione fra insiemi). Siano x e y insiemi, si definisce ∩ {t ∈ ∪ ∈ ∧ ∈ {t ∈ ∈ {t ∈ ∈:=x y x y : t x t y} = x : t y} = y : t x}

Definizione 1.3 (Sottrazione tra insiemi). Siano x e y insiemi, si definisce \ {t ∈ 6∈:=x y x : t y}

Assioma dell’unione - Forma definitiva

Assioma 1.7 Dato un insieme x, y esiste un insieme i cui elementi sono gli elementi degli elementi di x.

∀x∃y(∀t(t ∈ ←→ ∃z(z ∈ ∧ ∈y x t z)))

Definizione 1.4 (Unione di un insieme). Sia a un insieme, si definisce la sua unione l’insieme i cui elementi sono gli elementi degli elementi di a e si denota ∪a.

Osservazione 1.7. Informalmente puoi scrivere che [ {x ∃t(t ∈ ∧ ∈a = : a x t)} ma per come scritto non è un insieme, quello che garantisce l’esistenza e unicità sono gli assiomi dell’unione e di estensionalità (si potrebbe anche esplicitare, sul libro ci sta ma non è difficile).

Definizione 1.5 (Intersezione di un insieme). Sia a un insieme, si definisce la sua intersezione n o\ [∈ ∀t(t ∈ → ∈:=a x a : a x t)

Definizione 1.6 (Coppia ordinata). Siano a e b insiemi, si definisce la coppia ordinata ha, {{a}, {a,:=bi b}}

Osservazione 1.8. Si potrebbe pensare ad una definizione più intuitiva del tipo ma {a, {a, b}} questa fallisce per eh∅, {∅}i h{{∅}}, ∅i

Teorema 1.2 (Uguaglianza fra coppie ordinate). Siano u, v, x, y insiemi, si hahu, hx, ⇐⇒ ∧vi = yi u = x v = y

Definizione 1.7 (Prodotto cartesiano). Siano A e B insiemi, si definisce il prodotto cartesiano di A e B {w ∈ P(P(A∪B)) ∃x∃y(x ∈ ∧ ∈ ∧ hx, {hx, ∈ P(P(A∪B)) ∈ ∧ ∈:=A×B : A y B w = yi)} = yi : x A y B}

La seconda scrittura è leggermente meno formale della prima, ma è di più semplice lettura.

1.3 Relazioni

Definizione 1.8 (Relazione). Un insieme di coppie ordinate si dice relazione.

La prof definisce così una relazione binaria (il libro invece fa una distinzione [End77, p. 40,42]).

Osservazione 1.9. Uno si può chiedere (e si deve chiedere, altrimenti la definizione non è ben posta), se dato un insieme so dire se è una relazione o no, in altre parole, so dire se i suoi elementi sono coppie ordinate? Io credo che un insieme può essere sempre considerato una relazione, infatti se ho un insieme puoi dimostrare (Credo) che questo significa che ogni S S⊆ P(P(x, x x)), elemento di è una coppia ordinata dell’insieme Forse mi sto sbagliando perché dopo c’è S S x x. (Teorema 1.4), pensaci.

Definizione 1.9 (Elementi in relazione). Sia R una relazione e siano x, y insiemi tali che hx, ∈R x, y yi R, allora si dice che x è in relazione con y e si scrive xRy.

Lemma 1.3. Siano A, x, y insiemi tali che S S hx, ∈ ∈A, x, y yi A, x, y A.

3

Definizione 1.10 (Dominio di un insieme). Sia R un insieme, si dice dominio di R l’insieme n o[[∈ ∃y(hx, ∈:=dom R x R : yi R)

Definizione 1.11 (Rango di un insieme). Sia R un insieme, si dice rango di R l’insieme n o[[∈ ∃y(hy, ∈:=ran R x R : xi R)

Definizione 1.12 (Campo di un insieme). Sia R un insieme, si dice campo di R l’insieme ∪:=fld R dom R ran R

Definizione 1.13 (n-upla). Definiamo per ricorrenza hx i hhx i, i, . . . , x = , . . . , x x1 n 1 n−1 n

Proprietà 1.4 (Caratterizzazione relazione). Sia A un insieme, allora A è una relazione sse ⊆ ×A dom A ran A

8/10/2021

Definizione 1.14 (Relazione binaria su un insieme). Sia A un insieme, un sottoinsieme di A × A si dice relazione binaria su A.

Definizione 1.15 (Funzione). Sia F una relazione tale che per ogni x ∈ dom F esiste un unico y tale che hx, ∈yi F, allora si dice F funzione.

0 0 0∀x∀y∀y ∈ ∧ hx, i ∈ →((hx, yi F y F ) y = y )

Definizione 1.16 (Funzione da un insieme ad un altro). Sia F una funzione e siano A, B insiemi tali che dom F = A e ran F ⊆ B, allora si dice che F va da A in B e si scrive F : A → B.

Definizione 1.17 (Immagine di un elemento mediante una funzione). Sia F una funzione e sia x ∈ dom F, allora l’unico elemento y tale che xF y, si dice immagine di x mediante F e si denota F (x).

Definizione 1.18 (Funzione iniettiva). Sia F una funzione, se per ogni x ∈ ran F esiste un unico y tale che F (y) = x, allora la funzione F si dice iniettiva.

0 0 0∀x∀y∀y ∧ →((yF x y F x) y = y )

Definizione 1.19 (Funzione suriettiva). Siano A e B insiemi e F : A → B una funzione, se per ogni x ∈ B esiste y tale che yF x, allora la funzione F si dice suriettiva.

∀x(x ∈ → ∃y(yFB x))

Equivalentemente ran F = B.

Definizione 1.20 (Funzione biettiva). Siano A e B insiemi e F : A → B una funzione, se F è sia iniettiva che biettiva, allora si dice F biettiva.

Le seguenti definizioni vengono date per un qualsiasi insieme ma solitamente vengono utilizzate per le funzioni.

Definizione 1.21 (Inverso di un insieme). Sia F un insieme, si dice inverso di F, l’insieme n [ o[−1 hy, ∈ P P {hy, ∈ × hx, ∈ }:=F xi F : xF y = xi ran A dom A : yi F

Osservazione 1.10. L’esistenza ed unicità sono garantite rispettivamente dagli assiomi di separazione e di estensionalità.

Osservazione 1.11. Nota che se F è una relazione, allora F−1 è la relazione inversa e che se F è una funzione iniettiva allora F−1 è una funzione iniettiva.

Definizione 1.22 (Composizione di insiemi). Siano F e G insiemi, si definisce la composizione di F e G come l’insieme F G ◦ {hx, ∈ × ∃y(xGy ∧:=F G zi dom G ran F : yF z)}

4

Definizione 1.23 (Restrizione di insieme ad un altro). Siano F e A insiemi, si definisce la restrizione di F ad A l’insieme | {hx, ∈ × ∧ ∈ {hx, ∈ ×:=F yi dom F ran F : xF y x A} = yi A ran F : xF y}A

Osservazione 1.12. Nel caso in cui F è una relazione puoi scrivere più brevemente | {hx, ∈ ∈F = yi F : x A}A

Definizione 1.24 (Immagine di un insieme mediante un altro). Siano F e A insiemi, si definisce l’immagine di A mediante F l’insieme [[ [[| {x ∈ | ∃y(yF {x ∈ ∈ ∧ ∃y(yF:=F [A] ran F = F : x)} = F : x A x)}A A

Definizione 1.25 (Relazione riflessiva). Sia R una relazione, si dice che R è riflessiva se ∀x(x ∈ →fld R xRx), cioè ⊆diag A R

Definizione 1.26 (Relazione riflessiva su un insieme). Siano A un insieme e R una relazione, si dice che R è riflessiva su A se ∀x(x ∈ →A xRx), cioè ⊆diag A R

Definizione 1.27 (Relazione simmetrica). Sia R una relazione, se per ogni x, y tali che xRy si ha che yRx, allora si dice R simmetrica.

∀x∀y(xRy → yRx)

Definizione 1.28 (Relazione transitiva). Sia R una relazione, se per ogni x, y, z tali che xRy e yRz si ha che xRz, allora si dice R transitiva.

∀x∀y∀z((xRy ∧ →yRz) xRz)

Definizione 1.29 (Relazione di equivalenza). Sia R una relazione, se R è riflessiva, simmetrica e transitiva, allora si dice R relazione di equivalenza.

Definizione 1.30 (Relazione di equivalenza su un insieme). Sia A un insieme e sia R una relazione binaria su A, se R è riflessiva su A, simmetrica e transitiva, allora si dice R relazione di equivalenza su A.

Esempio 1.1 (Esempio di relazione di equivalenza che non è una relazione di equivalenza su un insieme). L’insieme vuoto è una relazione di equivalenza ma non è una relazione di equivalenza su qualsiasi insieme non vuoto.

Lemma 1.5. Sia R una relazione, allora R è una relazione binaria su fld R.

⊆ × ⊆ ×R R dom R ran R fld R fld R.

Proprietà 1.6. Sia R una relazione, allora ⊆A R A, fld R A.

Proprietà 1.7. Siano A un insieme e sia R una relazione binaria su A, allora fld R ⊆ A.

Teorema 1.8. Sia R una relazione simmetrica e transitiva, allora R è una relazione di equivalenza su fld R.

Osservazione 1.13. Nota che se hai che R è una relazione binaria su A tale che R è simmetrica e transitiva, non è detto che R sia una relazione di equivalenza su A, perché abbiamo osservato (Teorema 1.7) che in generale 6fld R = A.

Proprietà 1.9. Sia R una relazione simmetrica, allora R dom R = ran R = fld R.

Dimostrazione. Sia x ∈ dom R, allora esiste y tale che xRy, ma per la simmetria si ha yRx, allora x ∈ ran R, quindi dom R ⊆ ran R. Analogamente si vede che ran R ⊆ dom R, per cui dom R = ran R = fld R.

Proprietà 1.10. Siano A un insieme e sia R una relazione riflessiva su A, allora A = fld R.

5

Dimostrazione. Per (Teorema 1.7), si ha che fld R ⊆ A. Sia a ∈ A, allora aRa e quindi a ∈ dom R ∩ ran R ⊆ fld R, quindi A ⊆ fld R.

Proprietà 1.11. Sia R una relazione, allora R = ∅ ⇐⇒ dom R = ∅ ⇐⇒ ran R = ∅

Dimostrazione. Sia R = ∅, se per assurdo dom R 6= ∅, allora esiste x ∈ dom R e y tali che hx, yi ∈ R = ∅.

Sia dom R = ∅, se fosse per assurdo R 6= ∅, allora esiste hx, yi ∈ R e x ∈ dom R = ∅.

Corollario 1.11.1. Siano A un insieme e sia R una relazione riflessiva su A, allora A = ∅ ⇐⇒ R = ∅

Dimostrazione. Se A = ∅, allora, per le proprietà precedenti, dom R ⊆ fld R ⊆ A = ∅, allora R = ∅.

Sia R = ∅, allora dom R = ∅ e ran R = ∅, ma per (Teorema 1.10) fld R = A, quindi A = fld R = ∅.

Definizione 1.31 (Classe di equivalenza). Sia R una relazione di equivalenza, per ogni x ∈ fld R si dice l’insieme classe di equivalenza di x modulo R

{y ∈:=[x] fld R : xRy}R

Osservazione 1.14. Nota che vale anche {y ∈ {y ∈[x] = dom R : yRx} = ran R : xRy}R

Osservazione 1.15. Nota che se A è non vuoto, per ogni a ∈ A si ha aRa, quindi a ∈ [a]R 6= ∅.

Lemma 1.12. Siano A un insieme e R una relazione di equivalenza su A, siano x, y ∈ A, allora xRy ⇐⇒ [x]R = [y]R

Definizione 1.32 (Partizione di un insieme). Sia A un insieme e sia Π un insieme di insiemi non vuoti tale che l’unione dei suoi elementi sia A e che suoi elementi distinti siano disgiunti.

[∀x(x ∈ → 6 ∅) ∧ ∧ ∀x∀y((x ∈ ∧ ∈ → ∨ ∩ ∅))Π x = Π = A Π y Π) (x = y x y =

Osservazione 1.16. Nota che l’unica partizione del vuoto è il vuoto.

Definizione 1.33 (Insieme quoziente). Siano A un insieme e R una relazione di equivalenza su A, allora si dice insieme quoziente di A modulo R l’insieme {[x] ∈ P(A) ∈:=A/R : x A}R

Lemma 1.13. Siano A un insieme e R una relazione di equivalenza su A, allora l’insieme quoziente A/R è una partizione di A.

Definizione 1.34 (Applicazione canonica). Siano A un insieme e R una relazione di equivalenza su A, l’applicazione tale che → 7→A, ϕ : A A/R a [a] è una funzione chiamata applicazione canonica.

Osservazione 1.17. Puoi scrivere anche {hx, ∈ × P(A) }ϕ = yi A : y = [x] R

Definizione 1.35 (Relazione antiriflessiva su un insieme). Siano un insieme e sia