Modelli simulativi
per le Scienze Cognitive
Paolo Bouquet
(Università di Trento)
Marco Casarotti
(Università di Padova)
Insiemi, numeri cardinali
e calcolabilità
Modulo 3
Scopo del modulo 3
Tenteremo di rispondere a domande come:
1.
Quante sono le funzioni aritmetiche?
2.
Quante sono le funzioni calcolabili?
3.
Quali conseguenze hanno le risposte alle due
domande?
Confronto tra insiemi
Intuitivamente, per confrontare due insiemi A e
B, si possono applicare due metodi
principali:
1.
2.
Contare gli elementi dei due insiemi e verificare
quindi se i due numeri sono uguali, o uno è
maggiore dell’altro
Appaiare gli elementi dei due insiemi e
verificare se è possibile mettere gli elementi di
un insieme in corrispondenza biunivoca con gli
elementi dell’altro
Vantaggio del secondo metodo: si può
applicare anche a insiemi infiniti!
Equipotenza di insiemi
Definizione. L’insieme A è equipotente
all’insieme B (e si scrive A  B) sse esiste
una funzione biiettiva φ : A  B.
La relazione di equipotenza è:
–
–
–
riflessiva (per ogni A, A  A)
simmetrica (per ogni A e B, se A  B allora B 
A)
transitiva (per ogni A, B e C, se A  B e B  C,
allora A  C)
Equipotenza e numeri cardinali
Definizione. Se due insiemi A e B sono equipotenti,
allora si dice che hanno la stessa cardinalità, o lo
stesso numero cardinale (Card(A) = Card(B))
Definizione. Se l’insieme A è equipotente a un
sottoinsieme di B, allora di dice che la cardinalità di
A è minore o uguale della cardinalità di B (Card(A)
 Card(B))
Se A ha n elementi, Card(A) = n
… e ancora …
●
●
L’esistenza di una funzione biiettiva tra due
insiemi A e B è condizione necessaria e
sufficiente affinchè i due insiemi abbiano lo
stesso numero di elementi.
Dato un insieme finito A, non può esistere
alcuna funzione biiettiva tra A e una sua
parte propria.
Ma questo non vale per insiemi infiniti!!
Insiemi infiniti
Un sottoinsieme è infinito quando può essere
messo in corrispondenza biunivoca con una
sua parte propria, finito altrimenti.
Esempio: sia N l’insieme dei numeri naturali e
Q quello dei quadrati perfetti. La funzione φ :
N  Q tale che φ(x) = x2 è biiettiva
Insiemi numerabili
Definizione. Un insieme A è numerabile sse esiste
una funzione biiettiva φ : N  A
Cioè, se A è numerabile, allora Card(A) = Card(N)
Se A è numerabile, i suoi elementi possono essere
disposti in una sequenza infinita senza ripetizioni, e
viceversa.
Esempi: numeri pari, potenze di 2, numeri primi, …
Esempi importanti di insiemi
numerabili
●
E’ numerabile l’insieme Z dei numeri interi
relativi (interi positivi e negativi)
0, +1, -1, +2, -2, +3, -3, …, +n, -n, …
f(n) =

 - (n/2)
se n è pari
 (n+1)/2 se n è dispari
Esempi importanti di insiemi
numerabili
●
E’ numerabile una successione infinita A0, A1,
A2, …, An, … senza ripetizioni di insiemi
numerabili
Idee?
[Cfr. Figura 3.1, pag. 93]
Esempi importanti di insiemi
numerabili
●
E’ numerabile il prodotto cartesiano A×B di
due insiemi numerabili A e B
Idee?
Esempi importanti di insiemi
numerabili
●
E’ numerabile l’insieme Q dei numeri
razionali (le “frazioni”)
Idee?
Esempi importanti di insiemi
numerabili
●
E’ numerabile l’insieme S di tutte le sequenze
infinite di 0 e 1 che da un certo punto in poi
sono costituiti solo da 0
Dimostrazione. Sfruttare la trasformazione in
base 2 del numero come codifica iniettiva e
suriettiva degli elementi di S
Esempi importanti di insiemi
numerabili
●
E’ numerabile l’insieme F di tutte le n-ple di
numeri naturali [per es. (1,3), (5,2,6),
(1,45,12,13), …]
Dimostrazione. Associamo a ogni numero
naturale n una sequenza di n+1 “1”. Ogni npla è codificata inserendo uno 0 tra ogni
elemento della n-pla codificato come sopra.
Questo ci riporta al caso di S.
Cardinalità di un linguaggio L
●
●
Un linguaggio L è definito da un alfabeto
finito o numerabile A e da un insieme E di
espressioni (successioni finite di elementi di
A).
Da quanto detto, segue che Card(E) 
Card(F). Infatti:
–
–
essendo A al più numerabile, esiste sempre una
corrispondenza biunivoca φ con N
a ogni elemento di E del tipo (e1, e2, …, en)
possiamo far corrispondere la n-pla di numeri
(φ(e1), φ(e2),…, φ(en)), che è un elemento di F
Insiemi più che numerabili
●
Consideriamo l’insieme G di tutte le
successioni di 0 e 1.
Teorema. L’insieme G è più che numerabile.
Dimostrazione: mediante il metodo diagonale
descritto nella Figura 3.2 (pag. 97)
Card(P(N)) = Card(G)
Teorema. L’insieme G è equipotente
all’insieme potenza di N.
Dimostrazione: basta associare a ogni
sottoinsieme M di N una successione s0, s1,
…, sn, … di 0 e 1 tale che:
–
se n  M, allora sn = 1
–
altrimenti sn = 0
Siccome tale corrispondenza è biunivoca, se ne
conclude che Card(P(N)) = Card(G)
Altri insiemi più che numerabili
●
L’insieme dei punti di una retta
●
L’insieme dei punti di un segmento
●
L’insieme dei numeri reali
●
L’insieme potenza di qualsiasi insieme numerabile
Tutti questi insiemi hanno la
cardinalità dei continuo.
Gerarchia degli “infiniti”
Esistono insiemi più grandi degli insiemi con la
cardinalità del continuo?
Teorema 3.4. Per ogni insieme A, non può esistere
alcuna corrispondenza biunivoca tra A e l’insieme
potenza P(A) di A stesso.
Dimostrazione: vedi riquadro 3.1 pag 101.
Conclusione: esiste una gerarchia crescente di
insiemi infiniti di cardinalità sempre più elevata!!
Quante proprietà dei numeri
esistono?
Come abbiamo visto, ogni proprietà in N può essere
identificata con il sottoinsieme di N che ne gode.
Da questo segue un’ovvia conseguenza:
L’insieme delle proprietà è più che numerabile
Infatti, l’insieme dei sottoinsiemi di N (cioè P(N)) ha la
cardinalità del continuo.
L’insieme delle relazioni n-arie ha cardinalità
Card(P(NN)) = Card(P(N)) = Card(G)
Quante funzioni N × N ci sono?
●
●
●
●
●
Le funzioni di tipo N × N sono insiemi di coppie
ordinate
Segue che l’insieme  delle funzioni di tipo N × N è
un sottoinsieme delle relazioni binarie in N
Perciò Card()  Card(G)
Ma l’insieme delle funzioni caratteristiche è in
corrispondenza biunivoca le proprietà di N
Per cui Card(P(N))  Card(), e quindi, siccome
Card(P(N)) = Card(G), ne consegue che Card() =
Card(G)
Riduzione a funzioni a 1
argomento
●
Possiamo limitarci a studiare le funzioni a un
solo argomento, dato che l’input di una
funzione a n argomenti può essere codificato
sempre in maniera effettiva come un numero
naturale!
Esistenza di funzioni non
calcolabili
Teorema. L’insieme delle funzioni calcolabili è
numerabile.
Dimostrazione intuitiva: una funzione è
calcolabile sse esiste un algoritmo che la
calcola. Ma un algoritmo è una sequenza
finita di istruzioni scritta in un linguaggio L.
Pertanto la cardinalità dell’insieme di tutti i
possibili algoritmi è al più quella delle
espressioni E di L, vale a dire quella di N.
Le funzioni calcolabili sono
“poche”
●
●
●
L’insieme  delle funzioni di tipo N × N ha la
cardinalità del continuo
Ne segue che le funzioni calcolabili sono un
sottoinsieme numerabile dell’ insieme  che ha la
cardinalità del continuo
Di conseguenza, l’insieme delle funzioni non
calcolabili ha la cardinalità del continuo!
[Nota: la dimostrazione precedente è “non costruttiva”: dice che esistono
finzioni non calcolabili, ma non ne esibisce alcuna.]
Perché le funzioni parziali?
La nozione di calcolabilità data non equivale a:
Otteniamo un risultato in un numero finito di passi
ma a:
Otteniamo un risultato in un numero finito di passi se
il risultato esiste
Perché non restringerci alla prima nozione
(eliminando le funzioni parziali)?
Problema: gli algoritmi
Se rinunciassimo alle funzioni parziali, rinunceremmo
a poter decidere se un insieme finito di istruzioni sia
effettivamente un algoritmo …
Infatti:
●
●
Sappiamo che l’insieme  di tutti gli algoritmi è
numerabile (esiste cioè una funzione biiettiva :N
 )
Allora è possibile rappresentare l’insieme  come
una sequenza infinita A0, A1, A2, …, An, … che li
contiene tutti
Teorema. Non si può assumere che  sia una
funzione calcolabile e che al tempo stesso
tutti gli algoritmi di  terminino per ogni input
Dimostrazione. Associamo ad A0, A1, A2, …, An, … la
sequenza di tutte le funzioni totali a un argomento
(vedi par. 3.3.1 del libro)
0,  1,  2, …,  n, …
Definiamo poi la funzione (calcolabile!) f : N × N tale
che
f(x) = x(x) + 1
Con il metodo della diagonale si ottiene
immediatamente una contraddizione (cfr. libro, pag.
105-106)
Quindi:
1.
2.
o si ammette che  non sia computabile
o si accetta che le funzioni calcolate dagli
algoritmi possano essere parziali.
Siccome (1) non è sostenibile (gli algoritmi si
possono enumerare in modo effettivo),
allora deve essere il caso che (2).
Se vale (2), allora la contraddizione generata
con la diagonalizzazione non è più tale
(semplicemente k (k) = , cioè k diverge
per l’argomemento k).
Alcune considerazioni
●
Esistono funzioni calcolabili di cui però non
sappiamo calcolare i valori! Per esempio:
g(x) =
●

0
se esistono numeri perfetti dispari
1
se non esistono
Nella cosiddetta “matematica costruttiva”, una
funzione è detta calcolabile sse si possono
effettivamente determinare i suoi valori [ma a prezzo
del rifiuto del principio del terzo escluso …]