Il testo che segue intende solo conservare una traccia
estremamente schematica di quanto viene utilizzato
nel corso di Logica Matematica: in particolare, non si assicura
compiutezza, come pure sono del tutto escluse discussioni ed
esempi. E' possibile che manchino intere parti, così come non
sia sufficientemente aggiornato. Le definizioni sono quelle usate nel
corso: dato che molte di esse fissano concetti molto importanti,
è chiaramente possibile che non coincidano esattamente con altre
riportate, magari con lo stesso nome, su testi o in altri
corsi. Inoltre, si utilizzano, a volte, adattamenti tipografici dovuti
al mezzo usato.
Definizioni
Sia S una segnatura.
Una S-algebra è una coppia ordinata (A,I) dove
In altre parole, I associa ad ogni operatore
n-ario un'operazione n-aria su A.
Siano A e B insiemi. Si dice che f è
una funzione da A a B, e si scrive f:A --> B, se
(i)
f è un sottoinsieme di A×B, o, come si dice solitamente,
una corrispondenza da A a B
(ii)
per ogni a in A esiste uno ed un solo b in B tale che (a,b) sia in f.
In questo caso si è soliti scrivere f(a) per quell'unico b che
corrisponde all'elemento a attraverso f; altre notazioni comuni sono
fa, fa, o semplicemente fa, tralasciando le
parentesi in f(a).
Si indica spesso con BA l'insieme di tutte le
funzioni da A a B.
Una successione
è una funzione dall'insieme dei numeri naturali.
Un'operazione su A è una funzione da un
insieme prodotto A×...×A in A.
Principio di induzione: sia X un insieme. Se 0 è un elemento di
X, e per ogni x in X si ha che anche x+1 appartiene a X, allora
tutti i numeri naturali stanno in X.
Una segnatura è una successione
S di insiemi (Sn). Per comodità, gli insiemi
della famiglia si assumono a due a due disgiunti. Gli elementi di
Sn si dicono operatori di arietà n,
o n-ari. Gli operatori di
arietà 0 (gli elementi di S0) vengono anche detti
costanti.
Le segnature sono indicate solitamente con lettere greche
maiuscole; le denoteremo qui con lettere romane maiuscole.