1 Alcuni elementi di logica

(1)

1

(2)

Prima nozione fondamentale:

1

(3)

affermazione (o proposizione o enunciato).

1

(4)

Esempi di affermazione sono i seguenti:

1

(5)

2 < 7 ,

1

(6)

2 < 7 , 2³ > 9 .

1

(7)

2 < 7 , 2³ > 9 .

Un’affermazione pu`o essere vera o falsa.

1

(8)

2 < 7 , 2³ > 9 .

Un’affermazione pu`o essere vera o falsa.

Nel seguito denoteremo le affermazioni con lettere del tipo P, Q, etc.

1

(9)

Come nel linguaggio comune, molte affermazioni si ottengono combinando opportunamente affermazioni pi`u elementari.

2

(10)

Il modo pi`u semplice `e la negazione.

2

(11)

Se P `e un’affermazione, non P `e l’affermazione che

`e vera quando P `e falsa e viceversa.

2

(12)

Se P `e un’affermazione, non P `e l’affermazione che

`e vera quando P `e falsa e viceversa.

La seguente tavola riassume questa caratterizzazio- ne:

P V F

non P F V

2

(13)

Un secondo modo `e la congiunzione.

3

(14)

Se P e Q sono due affermazioni, P e Q `e l’affermazione che `e vera quando P e Q sono entrambe vere.

3

(15)

Se P e Q sono due affermazioni, P e Q `e l’affermazione che `e vera quando P e Q sono entrambe vere.

La tavola corrispondente `e:

P V V F F Q V F V F P e Q V F F F

3

(16)

Un terzo modo `e la disgiunzione.

4

(17)

Se P e Q sono due affermazioni, P o Q è l’affermazione che è vera quando almeno una delle due affermazioni è vera. In particolare, se P e Q sono entrambe vere, P o Q è vera.

4

(18)

Se P e Q sono due affermazioni, P o Q è l’affermazione che è vera quando almeno una delle due affermazioni è vera. In particolare, se P e Q sono entrambe vere, P o Q è vera.

La tavola `e:

P V V F F Q V F V F P o Q V V V F

4

(19)

Un quarto modo, meno ovvio, `e l’implicazione.

5

(20)

Per comprendere il funzionamento di P =⇒ Q (“P implica Q” o anche “se P allora Q”),

consideriamo un’espressione del tipo

n `e un multiplo di 6

=⇒

, dove n denota un numero intero positivo.

5

(21)

Per comprendere il funzionamento di P =⇒ Q (“P implica Q” o anche “se P allora Q”),

consideriamo un’espressione del tipo

=⇒

, dove n denota un numero intero positivo.

Noi vogliamo che questa asserzione abbia carattere generale, ossia che sia vera per ogni n.

5

(22)

Per ottenere questo risultato `e anzitutto necessario fare in modo che le affermazioni

6

(23)

12 `e un multiplo di 6

=⇒

,

6

(24)

=⇒

,

=⇒

,

6

(25)

=⇒

,

=⇒

,

=⇒

, siano tutte vere.

6

(26)

Questa esigenza obbliga intanto alle seguenti scelte:

P V V F F

Q V F V F

P =⇒ Q V V V

7

(27)

Questa esigenza obbliga intanto alle seguenti scelte:

P V V F F

Q V F V F

P =⇒ Q V V V

A questo punto, affinch´e P =⇒ Q non sia sempre vera indipendentemente da P e Q, il che rendereb- be il concetto di implicazione insignificante, l’unico completamento possibile `e:

P V V F F

Q V F V F

P =⇒ Q V F V V

7

(28)

In conclusione, l’affermazione P =⇒ Q `e sempre vera, tranne il caso in cui P sia vera e Q sia falsa.

8

(29)

Infine, l’ultimo modo che consideriamo `e la doppia implicazione.

9

(30)

Date due affermazioni P e Q, l’affermazione

P ⇐⇒ Q (“P se e solo se Q”) `e vera quando P e Q sono entrambe vere o entrambe false.

9

(31)

Date due affermazioni P e Q, l’affermazione

P ⇐⇒ Q (“P se e solo se Q”) `e vera quando P e Q sono entrambe vere o entrambe false.

La tavola corrispondente `e

P V V F F

Q V F V F

P ⇐⇒ Q V F F V

9

(32)

I simboli

non e o

=⇒

⇐⇒

che abbiamo introdotto, si chiamano connettivi logici.

10

(33)

A questo punto qualche considerazione `e necessaria.

11

(34)

Anzitutto, se P e Q sono due affermazioni e se sappiamo che P e (P =⇒ Q) sono entrambe vere, possiamo concludere che Q `e vera, come risulta dall’analisi della tabella dell’implicazione.

11

(35)

Anzitutto, se P e Q sono due affermazioni e se sappiamo che P e (P =⇒ Q) sono entrambe vere, possiamo concludere che Q `e vera, come risulta dall’analisi della tabella dell’implicazione.

Questa `e la principale regola di deduzione che `e alla base del ragionamento, anche matematico.

11

(36)

In secondo luogo, vale la pena osservare che mol- to spesso le affermazioni in matematica hanno la forma P =⇒ Q (P si chiama ipotesi e Q tesi ).

12

(37)

In secondo luogo, vale la pena osservare che mol- to spesso le affermazioni in matematica hanno la forma P =⇒ Q (P si chiama ipotesi e Q tesi ).

Se P, Q e R sono tre affermazioni, si verifica con un po’ di pazienza che l’affermazione

P e ( non Q) =⇒ R e ( non R)

ha lo stesso valore di verit`a di P =⇒ Q .

12

(38)

Pertanto un modo per dimostrare P =⇒ Q con- siste nel provare che dall’ipotesi P e dalla negazione della tesi Q si ottiene una contraddizione (dimostrazione per assurdo).

13

(39)

Per chi ama la massima economia sui concetti pri- mitivi, `e possibile ricondurre tutto ad un unico connettivo, opportunamente scelto.

14

(40)

Ad esempio, si pu`o introdurre la negazione alter- nativa.

15

(41)

Se P e Q sono due affermazioni, P nand Q oppure P | Q `e l’affermazione che `e falsa quando P e Q sono entrambe vere.

15

(42)

Se P e Q sono due affermazioni, P nand Q oppure P | Q `e l’affermazione che `e falsa quando P e Q sono entrambe vere.

La tavola corrispondente `e:

P V V F F

Q V F V F

P nand Q F V V V

15

(43)

Si stabiliscono poi le seguenti abbreviazioni:

16

(44)

Si stabiliscono poi le seguenti abbreviazioni:

non P significa P nand P ,

P e Q significa non (P nand Q) ,

P o Q significa ( non P) nand ( non Q) , P =⇒ Q significa P nand ( non Q) ,

P ⇐⇒ Q significa (P =⇒ Q) e (Q =⇒ P) .

16

(45)

Seconda nozione fondamentale:

17

(46)

frase aperta (o formula aperta o predicato).

17

(47)

Generalizza quella di affermazione.

17

(48)

Generalizza quella di affermazione.

Una frase aperta è un’asserzione dipendente da una o più variabili, la cui verità dipende dai valori assunti dalle variabili stesse.

17

(49)

Ad esempio

x² > 4

`e una frase aperta in una variabile, mentre x² + y² < 25

`e una frase aperta in due variabili.

18

(50)

Ad esempio

x² > 4

Nel seguito denoteremo le frasi aperte con espres- sioni del tipo P(x), Q(x, y), etc.

18

(51)

Ad esempio

x² > 4

Nel seguito denoteremo le frasi aperte con espres- sioni del tipo P(x), Q(x, y), etc.

Le affermazioni vanno concepite come frasi aperte che non dipendono da nessuna variabile.

18

(52)

La negazione, congiunzione, disgiunzione, implicazione e doppia implicazione di frasi aperte danno per risultato una frase aperta dipendente da tutte le variabili che compaiono.

19

(53)

La negazione, congiunzione, disgiunzione, implicazione e doppia implicazione di frasi aperte danno per risultato una frase aperta dipendente da tutte le variabili che compaiono.

Ad esempio

P(x) e Q(x, y)

`e una frase aperta nelle due variabili x e y, mentre P(y) =⇒ Q(x, z)

`e una frase aperta nelle tre variabili x, y e z.

19

(54)

Di importanza fondamentale sono le procedure che consentono di ottenere un’affermazione da una frase aperta.

20

(55)

La pi`u semplice `e la sostituzione delle variabili con costanti.

20

(56)

La pi`u semplice `e la sostituzione delle variabili con costanti.

Ad esempio, se P(x) `e la frase aperta x² > 4 ,

si ha che P(1) e P(3) sono due affermazioni, la prima falsa e la seconda vera.

20

(57)

Si possono anche considerare casi intermedi.

21

(58)

Si possono anche considerare casi intermedi.

Ad esempio, se P(x, y, z) `e la frase aperta in tre variabili

x² + y² < z² ,

si ha che P(3, y, 5) `e la frase aperta in una variabile 9 + y² < 25.

21

(59)

La seconda (pi`u interessante) procedura per ottenere affermazioni a partire da frasi aperte `e l’applicazione del

quantificatore universale ∀ (per ogni) e del

quantificatore esistenziale ∃ (esiste).

22

(60)

Se P(x) `e una frase aperta in una variabile,

∀x : P(x)

`e l’affermazione che significa

“la frase aperta P(x) `e vera per ogni x”.

23

(61)

Se P(x) `e una frase aperta in una variabile,

∀x : P(x)

“la frase aperta P(x) `e vera per ogni x”.

Ad esempio,

∀x : x² + 1 > 0

`e un’affermazione vera, mentre

∀x : x > 7

`e un’affermazione falsa.

23

(62)

Anche in questo caso si possono considerare situa- zioni intermedie:

∀x : y² > 1 − x²

`e una frase aperta nella sola variabile y, ottenuta a partire dalla frase aperta in due variabili y² > 1 − x².

24

(63)

Per quel che riguarda il quantificatore esistenziale,

∃x : P(x)

“la frase aperta P(x) `e vera per almeno un x”.

25

(64)

Una particolare attenzione va posta quando si sus- seguono pi`u quantificatori di tipo diverso.

26

(65)

Ad esempio

∀x, ∃y : P(x, y) significa che

per ogni x esiste un y per cui valga P(x, y).

26

(66)

Ad esempio

∀x, ∃y : P(x, y) significa che

per ogni x esiste un y per cui valga P(x, y).

Si intende che scegliendo x diversi si trovano in generale y differenti.

26

(67)

Invece

∃y, ∀x : P(x, y) significa che

esiste un y tale che per ogni x si abbia P(x, y).

27

(68)

Invece

∃y, ∀x : P(x, y) significa che

esiste un y tale che per ogni x si abbia P(x, y).

In questo caso si intende che un medesimo y va bene per tutti gli x.

27

(69)

Consideriamo qualche esempio esplicito:

∀x, ∃y : y > x

`e un’affermazione vera (dato x, si scelga ad esempio y = x + 1).

28

(70)

Consideriamo qualche esempio esplicito:

∀x, ∃y : y > x

`e un’affermazione vera (dato x, si scelga ad esempio y = x + 1).

Viceversa

∃y, ∀x : y > x

`e un’affermazione falsa (non esiste un numero y che sia pi`u grande di tutti i numeri).

28

(71)

Infine

∃y, ∀x : x² + y > 5

`e un’affermazione vera (si scelga, ad esempio, y = 6).

29

(72)

Conviene anche riflettere sulla negazione di un’affermazione contenente dei quantificatori.

30

(73)

Conviene anche riflettere sulla negazione di un’affermazione contenente dei quantificatori.

La negazione di

∀x : P(x)

`e

∃x : non P(x) ,

30

(74)

mentre la negazione di

∃x : P(x)

`e

∀x : non P(x) .

31

(75)

Frase aperta in due variabili basilare:

x = y (frase aperta di identit`a).

32

(76)

La logica che abbiamo delineato, contenente frasi aperte, fra cui in posizione basilare quella di identit`a, e quantificatori, si chiama logica del primo ordine con identit`a.

32

(77)

La logica che abbiamo delineato, contenente frasi aperte, fra cui in posizione basilare quella di identit`a, e quantificatori, si chiama logica del primo ordine con identit`a.

Essa costituisce il linguaggio in cui `e formulata la matematica moderna.

32

(78)

2 Primi assiomi della Teoria degli insiemi

33

(79)

2 Primi assiomi della Teoria degli insiemi

Esponiamo i primi elementi della teoria degli insiemi secondo Zermelo.

33

(80)

I primi concetti di teoria degli insiemi dovrebbero essere, in forma intuitiva, familiari a tutti. Ricor- diamo che la nozione di base `e la frase aperta in due variabili x ∈ X (x appartiene a X). Va solo pre- cisato che, a livello intuitivo, x e X sembrano avere due nature diverse (x l’elemento e X l’insieme).

34

(81)

Al contrario, nella teoria formale che consideriamo esiste un solo tipo di ente: l’insieme. Questo pun- to di vista è economico e conveniente perché, ad esempio, un quadrato nel piano può essere conce- pito come insieme dei suoi punti, ma anche come elemento dell’insieme di tutti i quadrati.

35

(82)

A questo proposito `e bene chiarire che, per ragioni di eleganza e rispondenza con l’intuizione, si pre- ferisce dire “famiglia di insiemi” o “collezione di insiemi”, intendendo “insieme di insiemi”. Per lo stesso motivo gli insiemi vengono denotati, a seconda dei casi, con lettere di dimensione e tipo diverso, quali x, Y , F, anche se dal punto di vista logico si tratta di variabili tutte con la stessa dignit`a. Riassumiano.

36

(83)

Gli oggetti della teoria sono di un unico tipo e si chiamano insiemi.

37

(84)

Gli oggetti della teoria sono di un unico tipo e si chiamano insiemi.

La teoria contiene due frasi aperte (in due variabili) primitive. Esse sono la frase aperta di identit`a, proveniente dalla logica,

x = y (x `e uguale ad y)

e la frase aperta di appartenenza, tipica della teoria degli insiemi,

x ∈ X (x appartiene ad X) .

37

(85)

Ogni frase aperta della Matematica (e quindi, in particolare, della Teoria degli insiemi) `e costruita, secondo le regole della logica, a partire da queste due frasi aperte primitive.

38

(86)

Ogni frase aperta della Matematica (e quindi, in particolare, della Teoria degli insiemi) `e costruita, secondo le regole della logica, a partire da queste due frasi aperte primitive.

Per evitare di dover maneggiare frasi aperte di volta in volta sempre pi`u lunghe, stabiliremo all’oc- correnza delle abbreviazioni.

38

(87)

Le prime due, x 6= y (x `e diverso da y) e x 6∈ X (x non appartiene a X), sono ovvie:

39

(88)

Le prime due, x 6= y (x `e diverso da y) e x 6∈ X (x non appartiene a X), sono ovvie:

x 6= y significa non (x = y) ; x 6∈ X significa non (x ∈ X) .

39

(89)

Introduciamo anche delle abbreviazioni nella scrittura delle frasi aperte:

40

(90)

Introduciamo anche delle abbreviazioni nella scrittura delle frasi aperte:

∀x ∈ X : P(x) significa

∀x : (x ∈ X) =⇒ P(x) ;

∃x ∈ X : P(x) significa

∃x : (x ∈ X) e P(x) .

40

(91)

Un’ulteriore notazione `e collegata con la nozione fondamentale di sottoinsieme.

41

(92)

Se X ed Y sono due insiemi, diciamo che X è sottoinsieme di Y e scriviamo X ⊆ Y (X è incluso in Y o X è una parte di Y ), se ogni elemento di X è anche elemento di Y .

41

(93)

Se X ed Y sono due insiemi, diciamo che X è sottoinsieme di Y e scriviamo X ⊆ Y (X è incluso in Y o X è una parte di Y ), se ogni elemento di X è anche elemento di Y .

Pi`u formalmente,

X ⊆ Y significa ∀x : x ∈ X =⇒ x ∈ Y .

41

(94)

Le due propriet`a seguenti sono di immediata verifica.

42

(95)

(2.1) Teorema Per ogni X, Y e Z si ha

X ⊆ X ; (2.2)

(X ⊆ Y e Y ⊆ Z) =⇒ X ⊆ Z . (2.3)

42

(96)

(2.1) Teorema Per ogni X, Y e Z si ha

X ⊆ X ; (2.2)

(X ⊆ Y e Y ⊆ Z) =⇒ X ⊆ Z . (2.3) Il primo assioma, che ora introduciamo, stabilisce una terza naturale propriet`a dell’inclusione.

42

(97)

(2.4) Assioma (di estensionalit`a) Per ogni X ed Y si ha

(X ⊆ Y e Y ⊆ X) =⇒ X = Y .

43

(98)

(X ⊆ Y e Y ⊆ X) =⇒ X = Y .

L’assioma di estensionalit`a fornisce lo strumen- to principale per dimostrare che due insiemi sono uguali.

43

(99)

(X ⊆ Y e Y ⊆ X) =⇒ X = Y .

L’assioma di estensionalit`a fornisce lo strumen- to principale per dimostrare che due insiemi sono uguali.

Se X ed Y sono due insiemi, per dimostrare che X = Y , molto spesso si prova che X ⊆ Y e che Y ⊆ X.

43

(100)

Il secondo assioma postula l’esistenza di un insieme con una particolare propriet`a.

44

(101)

(2.5) Assioma (dell’insieme vuoto) Esiste X tale che

∀x : x 6∈ X . (2.6)

44

(102)

∀x : x 6∈ X . (2.6)

Si dimostra che l’insieme di cui all’assioma precedente `e unico.

44

(103)

∀x : x 6∈ X . (2.6)

Si dimostra che l’insieme di cui all’assioma precedente `e unico.

Da ora in poi verr`a denotato col simbolo ∅ (insieme vuoto).

44

(104)

Per ogni insieme X, si ha sempre

∅ ⊆ X .

45

(105)

∅ ⊆ X .

I prossimi assiomi garantiscono la possibilit`a di costruire insiemi con particolari propriet`a a partire da dati insiemi.

45

(106)

∅ ⊆ X .

I prossimi assiomi garantiscono la possibilit`a di costruire insiemi con particolari propriet`a a partire da dati insiemi.

Il primo dei tre consente, dato un qualunque insieme X, di costruire un insieme che abbia per elementi esattamente i sottoinsiemi di X.

45

(107)

(2.7) Assioma (dell’insieme delle parti) Per ogni X esiste F tale che

∀Y : Y ∈ F ⇐⇒ Y ⊆ X . (2.8)

46

(108)

∀Y : Y ∈ F ⇐⇒ Y ⊆ X . (2.8) Assegnato X, si dimostra che l’insieme di cui al- l’assioma precedente `e unico.

46

(109)

∀Y : Y ∈ F ⇐⇒ Y ⊆ X . (2.8) Assegnato X, si dimostra che l’insieme di cui al- l’assioma precedente `e unico.

Da ora in poi verr`a denotato col simbolo P (X) (insieme delle parti di X o insieme potenza di X).

46

(110)

Siccome si ha sempre ∅ ⊆ X e X ⊆ X, si ha sempre ∅ ∈ P (X) e X ∈ P (X).

47

(111)

(2.9) Esempio

(a) Si ha ∅ ∈ P (∅), per cui P (∅) 6= ∅.

47

(112)

(2.9) Esempio

(a) Si ha ∅ ∈ P (∅), per cui P (∅) 6= ∅.

(b) Si ha

∅ ∈ P (P (∅)) , P (∅) ∈ P (P (∅)) ,

per cui ∅ e P (∅) sono due elementi distinti di P (P (∅)).

47

(113)

(2.10) Assioma (di accoppiamento) Per ogni a e per ogni b esiste X tale che

∀x : x ∈ X ⇐⇒ (x = a o x = b) .

48

(114)

∀x : x ∈ X ⇐⇒ (x = a o x = b) .

Assegnati a e b, si dimostra che l’insieme di cui all’assioma precedente `e unico.

48

(115)

∀x : x ∈ X ⇐⇒ (x = a o x = b) .

Assegnati a e b, si dimostra che l’insieme di cui all’assioma precedente `e unico.

Da ora in poi verr`a denotato col simbolo {a, b}.

48

(116)

Stabiliamo anche le seguenti notazioni:

49

(117)

{a} = {a, a} , {} = ∅ .

49

(118)

L’assioma successivo garantisce la possibilit`a di costruire un insieme come unione di pi`u insiemi. In effetti, per le esigenze della matematica moderna

`e necessario poter fare l’unione di molti insiemi.

Per non scontrarsi con le difficolt`a connesse con la nozione di infinito, `e opportuno affrontare la questione da un punto di vista appropriato. Per poter fare l’unione di certi insiemi, si richiede che esista un insieme F che abbia per elementi esattamente

50

(119)

gli insiemi che si vogliono unire (intuitivamente F sarà quindi una famiglia di insiemi). L’unione sarà allora qualcosa che dipenderà da F (che è un solo oggetto), piuttosto che dagli insiemi che si vogliono unire, ossia gli elementi di F (che possono essere tanti).

51

(120)

(2.11) Assioma (dell’insieme-unione) Per ogni F esiste X tale che

∀x : x ∈ X ⇐⇒ (∃F ∈ F : x ∈ F ) .

52

(121)

∀x : x ∈ X ⇐⇒ (∃F ∈ F : x ∈ F ) .

Assegnato F, si dimostra che l’insieme di cui all’assioma precedente `e unico.

52

(122)

∀x : x ∈ X ⇐⇒ (∃F ∈ F : x ∈ F ) .

Assegnato F, si dimostra che l’insieme di cui all’assioma precedente `e unico.

Da ora in poi verr`a denotato col simbolo S F oppure S

F ∈F

F (insieme-unione di F).

52

(123)

(2.12) Osservazione Per ogni F, valgono i seguenti fatti:

∀F : F ∈ F =⇒ F ⊆ [

F , F ⊆ P [

F

.

53

(124)

X ∪ Y = [

{X, Y } , X⁺ = {X} ∪ X .

54

(125)

X ∪ Y = [

{X, Y } , X⁺ = {X} ∪ X .

L’insieme X⁺ si chiama successore di X.

54

(126)

X ∪ Y = [

{X, Y } , X⁺ = {X} ∪ X .

L’insieme X⁺ si chiama successore di X.

Si verifica facilmente che

∀x : x ∈ X ∪ Y ⇐⇒ (x ∈ X o x ∈ Y ) ,

∀x : x ∈ X⁺ ⇐⇒ (x = X o x ∈ X) .

54

(127)

Poniamo anche

vn0 = ∅ ,

vn1 = (vn0)⁺ , vn2 = (vn1)⁺ , vn3 = (vn2)⁺ .

55

(128)

Risulta quindi

vn0 = ∅ = {} ,

vn1 = {∅} = {{}} ,

vn2 = {{∅}, ∅} = {{{}}, {}} , vn3 = {{{∅}, ∅}, {∅}, ∅}

= {{{{}}, {}}, {{}}, {}} .

56

(129)

(2.13) Assioma (di specificazione) Siano P(x) una frase aperta in una variabile e X un insieme. Allora esiste un insieme Y tale che

∀x : x ∈ Y ⇐⇒ (x ∈ X e P(x)) .

57

(130)

(2.13) Assioma (di specificazione) Siano P(x) una frase aperta in una variabile e X un insieme. Allora esiste un insieme Y tale che

∀x : x ∈ Y ⇐⇒ (x ∈ X e P(x)) .

Assegnati P(x) e X, si dimostra che l’insieme di cui all’assioma precedente `e unico.

57

(131)

Da ora in poi verr`a denotato con la scrittura {x : x ∈ X e P(x)}

o, pi`u brevemente,

{x ∈ X : P(x)} .

58

(132)

Da ora in poi verr`a denotato con la scrittura {x : x ∈ X e P(x)}

o, pi`u brevemente,

{x ∈ X : P(x)} . Notazioni alternative sono anche

{x| x ∈ X e P(x)}

e

{x ∈ X| P(x)} .

58

(133)

L’assioma di specificazione è forse la proprietà della teoria degli insiemi di uso più frequente. Se si vuo- le costruire un insieme Y costituito esattamente da certi elementi, è sufficiente costruire un insieme X contenente tali elementi. Il principio di specificazione consente poi di “ritagliare” la parte di X che interessa.

59

(134)

Osserviamo che l’assioma di specificazione consente di rispondere (negativamente) alla questione circa l’esistenza di un insieme universale.

60

(135)

Osserviamo che l’assioma di specificazione consente di rispondere (negativamente) alla questione circa l’esistenza di un insieme universale.

(2.14) Teorema (di Russell) Per ogni X esiste x tale che x 6∈ X.

60

(136)

Quando la teoria degli insiemi era ancora in una fa- se iniziale, si riteneva che dovesse esistere l’insieme di tutti gli insiemi. Questa convinzione, combina- ta col teorema precedente, portava ad una contraddizione, nota nella letteratura come paradosso di Russell.

61

(137)

Come dicevamo, il principio di specificazione consente di costruire un gran numero di insiemi, purché siano sottoinsiemi di qualche insieme a sua volta già costruito. Ad esempio, l’intersezione può essere costruita come opportuno sottoinsieme dell’unione.

62

(138)

(2.15) Teorema Per ogni F 6= ∅ esiste uno ed un solo X tale che

∀x : x ∈ X ⇐⇒ (∀F ∈ F : x ∈ F ) .

63

(139)

(2.15) Teorema Per ogni F 6= ∅ esiste uno ed un solo X tale che

∀x : x ∈ X ⇐⇒ (∀F ∈ F : x ∈ F ) .

Nel seguito l’insieme definito dal teorema precedente verr`a denotato col simbolo T F oppure T

F ∈F

F (insieme-intersezione di F).

63

(140)

Osserviamo che la condizione F 6= ∅ `e necessaria.

64

(141)

Osserviamo che la condizione F 6= ∅ `e necessaria.

Se F = ∅, la propriet`a

∀F : F ∈ F =⇒ x ∈ F

`e vera per ogni x. Pertanto T F dovrebbe essere un insieme che contiene tutti gli insiemi come elementi. Il Teorema (2.14) asserisce che un tale insieme non esiste.

64

(142)

Introduciamo le seguenti notazioni:

X ∩ Y = \

{X, Y } ,

X \ Y = {x ∈ X : x 6∈ Y } .

65

(143)

X ∩ Y = \

{X, Y } ,

X \ Y = {x ∈ X : x 6∈ Y } . Si verifica facilmente che

∀x : x ∈ X ∩ Y ⇐⇒ (x ∈ X e x ∈ Y ) ,

65

(144)

X ∩ Y = \

{X, Y } ,

X \ Y = {x ∈ X : x 6∈ Y } . Si verifica facilmente che

∀x : x ∈ X ∩ Y ⇐⇒ (x ∈ X e x ∈ Y ) ,

∀x : x ∈ X \ Y ⇐⇒ (x ∈ X e x /∈ Y ) .

65

(145)

3 Coppie ordinate, relazioni e funzioni

66

(146)

(3.1) Definizione Per ogni x ed y poniamo (x, y) = {x}, {x, y} .

66

(147)

L’insieme (x, y) si chiama coppia ordinata.

66

(148)

Per ogni F, con F 6= ∅ e F 6= {∅}, poniamo anche

66

(149)

π₁F = [ \

F ,

66

(150)

π₁F = [ \

F , π₂F = [ [

F

\ [ \ F

∪ \ [ F

.

66

(151)

La nozione di coppia ordinata `e importante a causa della seguente propriet`a fondamentale.

67

(152)

(3.2) Teorema Per ogni x, y si ha

π₁(x, y) = x , π₂(x, y) = y .

67

(153)

(3.2) Teorema Per ogni x, y si ha

π₁(x, y) = x , π₂(x, y) = y . In particolare, per ogni a, b, x, y si ha

(a, b) = (x, y) ⇐⇒ (a = x e b = y) .

67

(154)

Dati due insiemi X ed Y , vogliamo costruire un insieme che abbia per elementi tutte e sole le coppie ordinate (x, y) con x ∈ X ed y ∈ Y . In virt`u del principio di specificazione, `e sufficiente costruire un insieme che contenga tali coppie ordinate.

68

(155)

(3.3) Lemma Per ogni X, Y , x, y si ha

(x ∈ X e y ∈ Y ) =⇒ (x, y) ∈ P (P (X ∪ Y )) .

69

(156)

(x ∈ X e y ∈ Y ) =⇒ (x, y) ∈ P (P (X ∪ Y )) . (3.4) Teorema Se X ed Y sono due insiemi, esiste uno ed un solo insieme Z tale che

∀z : z ∈ Z ⇐⇒

(∃x ∈ X, ∃y ∈ Y : z = (x, y)) .

69

(157)

(x ∈ X e y ∈ Y ) =⇒ (x, y) ∈ P (P (X ∪ Y )) . (3.4) Teorema Se X ed Y sono due insiemi, esiste uno ed un solo insieme Z tale che

∀z : z ∈ Z ⇐⇒

(∃x ∈ X, ∃y ∈ Y : z = (x, y)) . Nel seguito l’insieme definito dal teorema precedente verr`a denotato col simbolo X × Y (insieme- prodotto di X ed Y ).

69

(158)

(3.5) Definizione Un insieme R si dice relazione, se tutti i suoi elementi sono coppie ordinate. Formalmente, R si dice relazione, se

∀z : z ∈ R =⇒ ∃x, ∃y : z = (x, y) .

70

(159)

∀z : z ∈ R =⇒ ∃x, ∃y : z = (x, y) .

Se R `e una relazione, la notazione xRy (x `e nella relazione R con y) significa (x, y) ∈ R.

70

(160)

∀z : z ∈ R =⇒ ∃x, ∃y : z = (x, y) .

Se R `e una relazione, la notazione xRy (x `e nella relazione R con y) significa (x, y) ∈ R.

Osserviamo che non si richiede a x ed y di appar- tenere a qualche prefissato insieme.

70

(161)

Evidentemente, se X ed Y sono due insiemi, ogni sottoinsieme R di X ×Y è una relazione. Per moti- vi tecnici è utile sapere che ogni relazione può essere ottenuta in questo modo, attraverso un’opportuna scelta di X ed Y .

71

(162)

(3.6) Lemma Per ogni relazione R si ha R ⊆

[ [ R

×

[ [ R

.

72

(163)

[ [ R

×

[ [ R

.

(3.7) Teorema Sia R una relazione. Allora esiste uno ed un solo insieme X tale che

∀x : x ∈ X ⇐⇒ (∃y : xRy)

72

(164)

[ [ R

×

[ [ R

.

(3.7) Teorema Sia R una relazione. Allora esiste uno ed un solo insieme X tale che

∀x : x ∈ X ⇐⇒ (∃y : xRy)

ed esiste uno ed un solo insieme Y tale che

∀y : y ∈ Y ⇐⇒ (∃x : xRy) .

72

(165)

Nel seguito i due insiemi definiti dal teorema precedente verranno denotati rispettivamente col simbolo dom (R) (dominio di R) e col simbolo img (R) (immagine di R).

73

(166)

(3.8) Proposizione Se R e S sono due relazioni e X `e un insieme, gli insiemi

74

(167)

S ◦ R =

(x, z) ∈ (dom (R)) × (img (S)) :

∃y : xRy e ySz

,

74

(168)

S ◦ R =

(x, z) ∈ (dom (R)) × (img (S)) :

∃y : xRy e ySz

, R⁻¹ =

(x, y) ∈ (img (R)) × (dom (R)) :

yRx

,

74

(169)

S ◦ R =

(x, z) ∈ (dom (R)) × (img (S)) :

∃y : xRy e ySz

, R⁻¹ =

(x, y) ∈ (img (R)) × (dom (R)) :

yRx

, R_|X = {(x, y) ∈ R : x ∈ X}

sono delle relazioni.

74

(170)

(3.9) Definizione La relazione S ◦ R si chiama composizione di R e S. La relazione R⁻¹ si chiama relazione inversa di R. La relazione R_|X si chiama restrizione di R all’insieme X.

75

(171)

(3.9) Definizione La relazione S ◦ R si chiama composizione di R e S. La relazione R⁻¹ si chiama relazione inversa di R. La relazione R_|X si chiama restrizione di R all’insieme X.

Consideriamo ora un tipo particolare di relazione.

75

(172)

(3.10) Definizione Una funzione (o applicazione) `e una relazione f tale che

∀x, ∀y₁, ∀y₂ : (xf y₁ e xf y₂) =⇒ y₁ = y₂ .

76

(173)

(3.10) Definizione Una funzione (o applicazione) `e una relazione f tale che

∀x, ∀y₁, ∀y₂ : (xf y₁ e xf y₂) =⇒ y₁ = y₂ .

Se f `e una funzione e x ∈ dom (f ), si denota con f (x) oppure f_x l’unico y tale che xf y.

76

(174)

Intuitivamente, f pu`o essere concepita come una

“legge” che ad ogni elemento di dom (f ) associa uno ed un solo valore f (x). In omaggio a questo punto di vista, si usa spesso la notazione

{x 7→ f (x)}

per denotare la funzione f , mentre l’insieme f viene chiamato grafico della funzione.

77

(175)

Nella teoria formale degli insiemi la funzione viene identificata col suo grafico. Questo consente di trattare la funzione come un qualunque insieme, senza introdurre un’entit`a di natura diversa.

78

(176)

(3.11) Teorema Se f e g sono due funzioni e X `e un insieme, le relazioni g ◦ f e f_|X sono delle funzioni.

79

(177)

(3.12) Definizione Una funzione f si dice iniettiva, se

∀x₁, ∀x₂, ∀y : (x₁f y e x₂f y) =⇒ x₁ = x₂ .

79

(178)

(3.12) Definizione Una funzione f si dice iniettiva, se

∀x₁, ∀x₂, ∀y : (x₁f y e x₂f y) =⇒ x₁ = x₂ .

(3.13) Teorema Una funzione f `e iniettiva se e solo se la relazione f⁻¹ `e una funzione.

79

(179)

(3.14) Definizione Siano X ed Y due insiemi e sia f una funzione. Diciamo che f `e una funzione da X in Y (e scriviamo f : X → Y ), se dom (f ) = X ed img (f ) ⊆ Y . In tal caso diciamo che Y `e il codominio di f : X → Y .

80

(180)

(3.15) Definizione Una funzione f : X → Y si dice suriettiva, se img (f ) = Y . Si dice biiettiva, se f `e iniettiva e suriettiva.

81

(181)

(3.16) Proposizione Siano f : X → Y e g : Y → Z due funzioni. Valgono allora i seguenti fatti:

81

(182)

(a) se g ◦ f `e iniettiva, allora f `e iniettiva;

81

(183)

(a) se g ◦ f `e iniettiva, allora f `e iniettiva;

(b) se g ◦ f `e suriettiva, allora g `e suriettiva.

81

(184)

Se f `e una funzione da X in Y , si ha evidentemente f ⊆ X × Y . Si pu`o quindi definire l’insieme delle applicazioni da X in Y come un opportuno sottoinsieme di P (X × Y ).

82

(185)

(3.17) Teorema Se X ed Y sono due insiemi, esiste uno ed un solo insieme F tale che

∀f : f ∈ F ⇐⇒

f `e una funzione da X in Y .

83

(186)

(3.17) Teorema Se X ed Y sono due insiemi, esiste uno ed un solo insieme F tale che

∀f : f ∈ F ⇐⇒

f `e una funzione da X in Y . Nel seguito denoteremo con Y ^X l’insieme definito dal teorema precedente (insieme delle funzioni da X in Y ).

83

(187)

4 L’assioma di infinit`a

84

(188)

4 L’assioma di infinit`a

Gli assiomi finora introdotti garantiscono l’esistenza dell’insieme vuoto e ci forniscono la possibilit`a di costruire certi insiemi a partire dall’insieme vuoto.

Per poter tuttavia costruire i primi insiemi nume- rici, come ad esempio l’insieme dei numeri natura- li, `e necessario un ulteriore assioma che garantisca l’esistenza di un insieme sufficientemente grande.

84

(189)

(4.1) Assioma (di infinit`a) Esiste un insieme X tale che

85

(190)

∅ ∈ X ; (4.2)

85

(191)

∅ ∈ X ; (4.2)

∀x : x ∈ X =⇒ x⁺ ∈ X . (4.3)

85

(192)

∅ ∈ X ; (4.2)

∀x : x ∈ X =⇒ x⁺ ∈ X . (4.3) (4.4) Teorema Esiste uno ed un solo insieme ω con le seguenti propriet`a:

85

(193)

∅ ∈ X ; (4.2)

(a) ω soddisfa la (4.2) e la (4.3);

85

(194)

∅ ∈ X ; (4.2)

(a) ω soddisfa la (4.2) e la (4.3);

(b) se Y `e un insieme che soddisfa la (4.2) e la (4.3), si ha ω ⊆ Y .

85

(195)

(4.5) Definizione L’insieme ω introdotto nel teorema precedente si chiama insieme dei cardinali finiti e gli elementi di ω si chiamano cardinali finiti.

86

(196)

Definiamo una funzione σ : ω → ω ponendo σ(n) = n⁺ ossia, pi`u formalmente,

σ = (n, m) ∈ ω × ω : m = n⁺ .

87

(197)

Definiamo una funzione σ : ω → ω ponendo σ(n) = n⁺ ossia, pi`u formalmente,

σ = (n, m) ∈ ω × ω : m = n⁺ .

Vogliamo dimostrare che l’insieme ω e la funzione σ soddisfano alcune propriet`a notevoli. Per questo premettiamo un lemma.

87

(198)

(4.6) Lemma Siano m, n ∈ ω tali che m ∈ n.

Allora si ha m ⊆ n.

88

(199)

(4.6) Lemma Siano m, n ∈ ω tali che m ∈ n.

Allora si ha m ⊆ n.

Possiamo adesso dimostrare le propriet`a fondamen- tali dell’insieme ω e della funzione σ.

88

(200)

(4.7) Teorema L’insieme ω e la funzione σ soddisfano le seguenti propriet`a:

89