Teoria dei modelli finiti nella logica del prim'ordine

This work is an introduction to the study of finite models (FMT) in first-order logic (FOL). The techniques involved are often quite different than those employed in standard model theory. In the first part we examine the method known as the Ehrenfeucht-Fraïssé games; thanks to this method we are able to prove that FOL is unable to express many interesting properties. In the second part we assign a probability to the event ‘The structure $A$ satisfies the sentence $\phi$’ and discuss the 0-1 law of FOL. In the third part we present nontrivial results proven with the tools of FMT: (i) the class of valid sentences with prefix $forall^2 exists^{\ast}$ is decidable; (ii) a subset of the natural numbers is a spectrum for a unary function symbol if and only if it is eventually periodic.

Questo lavoro è un’introduzione allo studio dei modelli finiti (FMT) nella logica del prim’ordine (FOL). Le tecniche usate sono spesso assai dissimili da quelle della teoria dei modelli standard. La prima parte esamina il metodo noto come i giochi di Ehrenfeucht-Fraïssé; questo metodo permette di dimostrare risultati limitativi sul potere espressivo di FOL. Nella seconda parte si assegna una probabilità all’evento ‘La struttura $A$ soddisfa l’enunciato $\phi$’ e si discute la legge 0-1 di FOL. La terza parte presenta risultati non banali provati con gli strumenti di FMT: (i) la classe degli enunciati validi con prefisso $\forall^2 exists^{\ast}$ è decidibile; (ii) un sottoinsieme dei numeri naturali è uno spettro per un simbolo di funzione unaria se e soltanto se è definitivamente periodico.