Concetti fondamentali

tutto si riconduce a questi

insieme: esempi

{1,3,5,7,9}
insieme dei numeri dispari positivi minori di dieci
{Antonio, Beatrice, Carlo, Daria}
insieme dei cugini di Gino
{{d,c}, {r}, {f,e,r,t}}
un insieme di insiemi di lettere
{2i | i=0,1,2,…}
insieme delle potenze positive di due

notare: insiemi infiniti, insiemi di insiemi

insiemi: appartenenza, sottoinsiemi

x∈S = x è un elemento dell'insieme S

esempio: Carlo ∈ {Antonio, Beatrice, Carlo, Daria}

P⊆S = S contiene tutti gli elementi di P

esempio: {1,3,5,7,9} ⊆ {1,2,3,4,5,6,7,8,9}
formale: se x∈P allora x∈S

sequenze: esempi

⟨1,2,3,4,5⟩
sequenza dei primi cinque numeri interi
⟨ ⟨0,1⟩, ⟨0,0⟩, ⟨2,1⟩ ⟩
sequenza di risultati di partite
ogni risultato è una coppia come ⟨0,1⟩,
cioè una sequenza di due numeri
⟨p,a,r,o,l,a⟩
una sequenza di lettere
forma abbreviata: 'parola'

concetti derivati

stringa
sequenza di caratteri (elementi di un certo alfabeto)
funzione
insieme di coppie con certe proprietà
relazione
insieme di coppie
...
[altro?]

concetti derivati: relazioni

esempio: relazione genitore-figlio:

{ ⟨marco,giulia⟩, ⟨giulia,luca⟩, ⟨gianni,roberto⟩, … }

due elementi a e b sono in relazione se ⟨a,b⟩ ∈ relazione

⟨a,b⟩ e ⟨b,a⟩ non sono la stessa cosa!:

⟨marco,giulia⟩ ∈ relazione
marco è un genitore di giulia
⟨giulia,marco⟩ ∈ relazione
giulia è un genitore di marco 
marco
  |            gianni
  V              |
giulia           V
  |           roberto
  V
 luca

relazioni simmetriche

esempio: relazione fratello-di

se marco è fratello di Luca
allora luca è fratello di marco

formale:

relazione simmetrica: se ⟨a,b⟩∈relazione allora ⟨b,a⟩∈relazione

viceversa: automatico

non tutte le relazioni sono simmetriche

concetti derivati: funzioni

esempio: funzione quadrato

{ ⟨0,0⟩, ⟨1,1⟩, ⟨2,4⟩, ⟨3,9⟩, ⟨4,16⟩, … }

interpretazione: f(x) è

= y
tale che ⟨x,y⟩ ∈ funzione
indefinita
se non esiste ⟨x,y⟩ ∈ funzione 
 0
()      2->4->16
    9<-3
1()

funzioni: rappresentazione grafica

per chiarezza: elementi duplicati

stesso significato

coppie rappresentate con frecce

esempio:

freccia da 2 a 4 significa: ⟨2,4⟩ ∈ funzione 
0 -> 0
1 -> 1
2 -> 4
3 -> 9
4 -> 16

condizioni sulle funzioni

tutte

non esistono ⟨x,y⟩∈funzione e ⟨x,z⟩∈funzione con y≠z

iniettive

non esistono ⟨x,y⟩∈funzione ⟨w,y⟩∈funzione con x≠w

suriettive

per ogni y esiste x tale che ⟨x,y⟩∈funzione

esempi grafici…

relazioni e funzioni

0  +---->
1 -+  +-> 0
      |
      | +-> 1
  ----+ |
2 ------+
ecc.

maggiore: relazione (non è una funzione)
{⟨1,0⟩,⟨2,0⟩,⟨2,1⟩…}

0 -> 0
1 -> 1
2 -> 4
3 -> 9
4 -> 16

quadrato: funzione
{⟨0,0⟩,⟨1,1⟩,⟨2,4⟩…}

La prima non è una funzione, come si vede dalle due coppie con lo stesso primo elemento 2.

funzioni iniettive e non

0 -> 0
1 -> 1
2 -> 4
3 -> 9
4 -> 16

quadrato: funzione iniettiva
{⟨0,0⟩,⟨1,1⟩,⟨2,4⟩…}

0 -----> 
   +---> 0
   | +->
   | |
1 ---|---+
2 -+ |   |
     |   V
3 -----> 1
4 ---+

modulo due: non iniettiva
{⟨0,0⟩,⟨1,1⟩,⟨2,0⟩…}

La seconda non è iniettiva, come si vede dalle due coppie con lo stesso secondo elemento 0.

funzioni suriettive e non

esempio con funzioni da interi a interi

0 -> 0
1 ---^
2 -> 1
3 ---^

dimezzamento intero: suriettiva
(funzione numero//2)

0 -> 0
     1
1 -> 2
     3
2 -> 4

doppio: non suriettiva
(funzione numero*2)

La seconda non è suriettiva, dato che 3 non è un valore possibile. Notare che la suriettività dipende da come si definisce il codominio delle funzione: la seconda sarebbe suriettiva sugli interi pari.

operazioni su insiemi

unione
A ∪ B contiene gli elementi di A e quelli di B
esempio: {1,3,5} ∪ {2,3,4,5,9,10} = {1,2,3,4,5,9,10}
intersezione
A ∩ B contiene solo gli elementi che sono sia in A che in B
esempio: {1,3,5} ∩ {2,3,4,5,9,10} = {3,5} 
    +-------------+
+-------+  2      |
|   | 3 |      10 |
| 1 | 5 |  4      |
+-------+     9   |
    +-------------+

insieme vuoto

quello che non contiene nessun elemento

simbolo: ∅

o anche {}

contenimento e contenimento stretto

A⊆B
contenimento: anche uguali {1,2,3} ⊆ {1,2,3}
A⊂B
contenimento stretto, come {1,3} ⊂ {1,2,3}

vale che ∅ ⊆ A per qualsiasi insieme A
ma ∅ ⊂ A solo se A non è vuoto

sottoinsieme, insieme delle parti

sottoinsieme di A = un insieme contenuto in A

i sottoinsiemi di {1,2,3}:

{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3} ∅

l'insieme di questi: insieme delle parti di A
simbolo P(A) oppure 2A

insieme delle parti: esempi
insieme insieme delle parti
S={Carlo, Luca} P(S)={∅, {Carlo}, {Luca}, {Carlo, Luca}}
T={0} P(T)={∅, {0}}
R={⟨0,1⟩, ⟨1,0⟩} P(R)={∅,{⟨0,1⟩},{⟨1,0⟩},{⟨0,1⟩, ⟨1,0⟩}}

cardinalità di un insieme

= numero dei suoi elementi

|{10,3,9,41}| = 4
|{Luca,Antonio}| = 2
|∅| = 0
|P(A)| = 2|A|

domanda: |A∪B| = |A|+|B|?

cardinalità di un'unione

|{1,2}| = 2
|{2,3}| = 2
|{1,2}∪{2,3}| = |{1,2,3}| = 3

non vale |A∪B| = |A|+|B|

però: |A∪B| ≤ |A|+|B|

per l'intersezione?

cardinalità dell'interesezione

|A∩B| può anche essere zero:

|{1,2}∩{3,4}| = |∅| = 0

vale: |A∩B| ≤ min(|A|,|B|)

confronto fra insiemi

  L  H
    T
---------
 E  A
  C

ci sono più lettere maiuscole sopra la riga o sotto?

ovviamente:

  • tre sopra
  • tre sotto

stesso numero

Non è una domanda a trabocchetto: si parla solo delle lettere (maiuscole) del disegno (HLTEAC).

insiemi più grandi

  V  K  L S
G W   F  P
  H D  T
------------
 U E M Y  X
O    I   A
 C B   J

stessa domanda: più sopra o più sotto?

questa volta ci vuole un po'...

Sicuri di aver contato anche la I sotto la linea? E la F sopra? Le lettere sono non allineate apposto per rendere il conteggio difficile.

facilitazione

 H G V W K D F L T P S
-----------------------
 B O U C E M Y I A J X

animazione

stesse lettere

versione facilitata

 H G V W K D F L T P S
-----------------------
 B O U C E M Y I A J X

spostando le lettere:
stesso numero

in generale…

contare e confrontare

per confrontare due insiemi:

contare gli elementi
facile con pochi
farli corrispondere
sempre possibile

infiniti elementi: impossibile contarli

cardinalità di insiemi infiniti

insiemi con numero infinito di elementi:
impossibile contare quanti elementi sono

però: i positivi sono quanti i negativi

 1  2  3  4  5 …
-------------------
-1 -2 -3 -4 -5 …

in generale: vedere se gli elementi corrispondono

confronto fra insiemi infiniti

 1  2  3  4  5 …
-------------------
-1 -2 -3 -4 -5 …
  • non si può dire il numero di elementi
    di un insieme infinito, ma
  • si può dire se è grande quanto un altro

|positivi| = |negativi|

altro esempio

interi positivi e sequenze di bit che iniziano con 1:

 1   2   3   4   5 …
-----------------------
 1  10  11 100 101 …

corrispondono → stessa grandezza

|interi| = |sequenze di bit che iniziano con 1|

l'albergo di Hilbert

+----+----+----+----+----+----+-
|1 0 |2 0 |3 0 |4 0 |5 0 |6 0 |
|  | |  | |  | |  | |  | |  | |
| / \| / \| / \| / \| / \| / \|
+----+----+----+----+----+----+-

è un albergo con un numero infinito di stanze numerate:
stanza 1, stanza 2, stanza 3, …

sono tutte piene

arriva un nuovo cliente

gli trovano una stanza!

  • non cacciano nessun cliente
  • sempre un cliente per stanza

come fanno?

albergo di Hilbert: non soluzione

metto il cliente nella stanza infinito+1

non esiste!

infinito non è un numero
significa solo che per ogni intero c'è una stanza

stanza n con cliente n

albergo di Hilbert: soluzione

+----+----+----+----+----+----+-
|1   |2   |3   |4   |5   |6   |
|    |    |    |    |    |    |
|    |    |    |    |    |    |
+----+----+----+----+----+----+-
   \  ^  \  ^ \  ^ \  ^ \  ^
    --    --   --   --   --
   0    0    0    0    0    0  
   |    |    |    |    |    |
  / \  / \  / \  / \  / \  / \

si spostano i clienti:

  • quello della stanza 1 va nella 2
  • quella della 2 nella 3
  • quello della 3 nella 4
  • …

albergo di Hilbert, dopo lo spostamento

+----+----+----+----+----+----+-
|1   |2 0 |3 0 |4 0 |5 0 |6 0 |
|    |  | |  | |  | |  | |  | |
|    | / \| / \| / \| / \| / \|
+----+----+----+----+----+----+-

il nuovo cliente va nella 1!

clienti precedenti: cliente n ⇒ stanza n+1

i clienti da 1 in poi entrano nelle stanze da 2 in poi

in generale…

attenzione ai sottoinsiemi

interi e interi maggiori di tre:

 1 2 3 4 5 …
---------------
 4 5 6 7 8 …

corrispondono → stessa grandezza

|interi| = |interi maggiori di tre|

ma però…

cardinalità dei sottoinsiemi

finiti:
se A⊆B allora:
B è più grande di A o uguale
infiniti:
lo stesso
se A⊆B allora |A|≤|B|

e se A⊂B?

sottoinsiemi stretti

insiemi finiti: se A⊂B allora |A|<|B|
insiemi infiniti:
interi maggiori di tre ⊂ interi
ma: corrispondono (= stessa grandezza)
|interi maggiori di tre| = |interi|

es: 1∈interi ma 1∉interi maggiori di tre

elemento che l'altro insieme non ha
ma: stessa cardinalità

interi e interi pari

sottoinsieme stretto:
ogni pari è intero
5 è intero ma non pari

ma:

 1 2 3 4 …
-------------
 2 4 6 8 …

corrispondono → stessa cardinalità

|pari| = |interi|

interi e pari

gli interi sono di più!!!
(o no?)

ragionamento (errato):

  • ogni intero pari è un intero
  • 5 è intero ma non pari

quindi gli interi sono più dei pari
(falso)

grandezza di insiemi infiniti

A⊂B non implica |A|<|B|

es pari e interi

la cardinalità di un insieme infinito indica il suo ordine di grandezza, non il numero specifico di elementi (questo numero non esiste)

se A⊂B allora |A|≤|B|

definizione formale

per ogni intero c'è un pari (il doppio)
e per ogni pari c'è un intero (la metà)

gli interi positivi pari sono quanti gli interi positivi

se esiste una funzione suriettiva f:A→B allora |A|≤|B|

suriettiva: per ogni y esiste x tale che f(x)=y

insiemi grandi come gli interi

  • interi maggiori di tre
  • interi positivi pari
  • interi negativi
  • coppie di interi
  • …

coppie di interi

   1     2     3     4     5     6   …
------------------------------------------
 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) …

può funzionare?

coppie di interi: disposizione errata

   1     2     3     4     5     6   …
------------------------------------------
 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) …

ci sono infinite coppie (1,numero)

a (2,1) non ci arrivo mai:

non si può mettere (2,1) "dopo infinito":
infinito = non ci si arriva mai

coppie di interi: soluzione

   1     2     3     4     5     6   …
------------------------------------------
 (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) …

come funziona?

ordinamento delle coppie

   1     2     3     4     5     6   …
------------------------------------------
 (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) …

prima le coppie con somma 2: (1,1)

poi quelle con somma 3: (1,2) e (2,1)

poi con somma 4, ecc.

corrispondenza coppie ↔ interi: matrice

(1,1)    (1,2)   (1,3)


(2,1)    (2,2)   (2,3)


(3,1)    (3,2)   (3,3)

visualizzando le coppie come una matrice…

corrispondenza coppie ↔ interi: grafico

(1,1)--> (1,2)   (1,3)
   +-----+ +-----^ +
   V   +---+ V-----+
(2,1)--+ (2,2)   (2,3)
   +-----+
   V
(3,1)    (3,2)   (3,3)

sequenza di coppie:
si parte da (1,1) e si seguono le frecce

grafico alternativo

 --------------+  +------...
  (1,1)  (1,2) |  | (1,3)
               |  |
    +----------+  |
    +-------------+
  (2,1)

si segue la linea

modifica

 --------------+  +------...
  (1,1)  (1,2) |  | (1,3)
               |  |
    +----------+  |
    +-------------+
  (2,1)

   ||  raddrizzando la linea
   \/

si ottiene…

linea raddrizzata

 --------------+  +------...
  (1,1)  (1,2) |  | (1,3)
               |  |
    +----------+  |
    +-------------+
  (2,1)

   ||  raddrizzando la linea
   \/

-----------------------
 (1,1) (1,2) (2,1) ...

si aggiungono 1 2 3 4 … sopra la linea
si ottiene la corrispondenza

cardinalità delle coppie di interi

linea con interi sopra e coppie sotto
⇓
|coppie| = |interi|

perchè non per linee?

(1,1) → (1,2) → (1,3) → …
(2,1) → (2,2) → (2,3) → …
(3,1) → (3,2) → (3,3) → …
…

qual è l'intero di (2,1)?
(ce ne sono infiniti prima di lui)

nell'altro modo no,
posizione di (n,m):

  • somma n+m
  • prima le diagonali a somma 2, 3, … n+m-1
  • poi n lungo questa diagonale

insiemi contabili

sono quelli con la stessa cardinalità degli interi:

  • interi negativi
  • interi pari
  • interi maggiori di tre
  • coppie di interi

definizione alternativa: si possono contare
(= si mettono sotto la linea, poi: uno, due, tre, …)

contabilità dei numeri razionali

numero razionale → coppia di interi

es: 1,25 = 5/4 → (5,4)

|razionali| ≤ |coppie di interi|

(la funzione inversa non è iniettiva, ma non ci interessa)

dimostrato prima: |coppie di interi|≤|interi|

quindi:

|razionali| ≤ |interi|

razionali e interi

|razionali| ≤ |interi|

ma interi ⊂ razionali

quindi |interi| ≤ |razionali|

quindi:

|razionali| = |interi|

non molto intuitivo…

sottoinsiemi di insiemi infiniti

"gli interi sono molti meno dei razionali"

infatti: già fra 0 e 1 ci sono infiniti razionali

su insiemi infiniti non vuol dire niente

invece: i reali sono davvero di più!

stringhe

es: ASCII

stringa=sequenza di caratteri terminata da NUL

carattere → numero a otto bit (NUL→0)

stringa → sequenza di tutti questi bit
aggiungere 1 all'inizio

|stringhe| ≤ |sequenze di bit|

(neanche tutte le sequenze:
lunghezza multipla di otto, zero solo alla fine)

già visto: |sequenze di bit|=|interi|

quindi: |stringhe| ≤ |interi|

viceversa: numero → sequenza di caratteri 0,…,9

numeri reali

non ci interessa la definizione formale
diciamo che:

numero reale ↔ sequenza (anche infinita) di cifre

quindi:

|reali| = |sequenze di cifre|

mettere i reali sotto la linea

il sistema dei razionali non funziona:
in che posizione si mette π?

si dimostra che non si può fare

contare i reali

mettiamo la linea in verticale
(è lo stesso)

1 | 0,12300000000…
2 | 0,90450123213…
3 | 0,52942343242…
4 | 0,00000028213…
5 | 0,22222222222…
6 | 0,61743817232…
…

consideriamo solo i numeri minori di 1

dimostriamo che qualche numero non c'è

cifre in diagonale

1 | 0,12300000000…
2 | 0,90450123213…
3 | 0,52942343242…
4 | 0,00000028213…
5 | 0,22222222222…
6 | 0,61743817232…
…

numero con quella cifra più uno (9 diventa 0)

      109028
      ↓↓↓↓↓↓
    0,210139…

definizione di questo numero:

sua cifra i = uno più cifra i del numero i

dove sta il numero in diagonale?

1  | 0,12300000000…
2  | 0,90450123213…
3  | 0,52942343242…
4  | 0,00000028213…
5  | 0,22222222222…
6  | 0,61743817232…
   …
   |   ↓↓↓↓↓↓
10 | 0,210139…

deve stare da qualche parte nella lista

per esempio: posizione 10

numero in posizione dieci

1  | 0,12300000000…
2  | 0,90450123213…
3  | 0,52942343242…
4  | 0,00000028213…
5  | 0,22222222222…
6  | 0,61743817232…
7  |       …x…
8  |        …y…
9  |         …z…
10 | 0,210139 …c…

la diagonale interseca il numero alla decima cifra

decima cifra

1  | 0,12300000000…
2  | 0,90450123213…
3  | 0,52942343242…
4  | 0,00000028213…
5  | 0,22222222222…
6  | 0,61743817232…
7  |       …x…
8  |        …y…
9  |         …z…
10 | 0,210139 …c…

cifra del numero = uno più la cifra sulla diagonale

per la decima cifra:

c = uno più c

conclusione: il numero non è in posizione dieci

posizione del numero

1 | 0,12300000000…
2 | 0,90450123213…
3 | 0,52942343242…
4 | 0,00000028213…
5 | 0,22222222222…
6 | 0,61743817232…
…
  | ↓↓↓↓↓↓
n | 0,210139…

indichiamo con n la sua posizione

la diagonale lo interseca sulla n-esima cifra

n-esima cifra del numero in diagonale

definizione del numero:

n | 0,210139…c…
sua cifra i = uno più cifra i del numero i

se i=n:

cifra n = uno più cifra n del numero n

contraddizione!

diagonalizzazione

si assume che l'elenco contenga tutti i reali

si costruisce un reale prendendo una cifra modificata da ognuno

si dimostra che se sta nell'elenco in posizione n
allora la sua n-esima cifra vale lei stessa più uno

i reali non sono in corrispondenza con gli interi

non sono contabili

insieme delle parti

insieme di tutti gli insiemi (anche infiniti) di interi

rappresentazione:

           1 2 3 4 5 6 7 …
--------------------------------
{1,3}      1 0 1 0 0 0 0 …
{2,4,5}    0 1 0 1 1 0 0 …
∅          0 0 0 0 0 0 0 …
tutti      1 1 1 1 1 1 1 …
pari       0 1 0 1 0 1 0 …
<4         1 1 1 0 0 0 0 …
>4         0 0 0 0 1 1 1 …

con 0, davanti = numeri reali minori di uno in binario

|insiemi di interi| = |reali|

non contabili

l'insieme delle parti dell'insieme dei numeri interi non è contabile

contabili e non contabili

contabili
negativi, pari, sequenze di bit, coppie di interi, razionali, stringhe
non contabili
reali, insiemi di interi