Università Roma Tre

Towards model theory: some consequences of the compactness theorem

Proof of the compactness theorem for languages of any cardinality. Languages with equality. The compactness theorem for languages with equality. Correctness and completeness for languages with equality. L"owenheim-Skolem's theorem for (denumerable) languages with equality. The limits of the expressive power of first order languages. Elementary equivalence, substructures, elementary substructures. Isomorphsims and elementary equivalence. The notion of substructure. Elementary substructures and diagrams. The preservation theorems. Generalisations of the L"owenheim-Skolem's theorem. Completeness of a theory.

Logic and Arithmetic: incompleteness

Decidability and fundamental results of recursion theory: primitive recursive functions and elementary functions, Ackermann's function and the (partial) recursive functions, arithmetical hierarchy and representation (in N) of recursive functions, arithmetization of syntax, fundamental theorems of recursion theory, decidability, semi-decidability, undecidability.

Peano arithemtic

Peano arithmetic: Peano's axioms, the models of (first order) Peano arithmetic, the representable functions in (first order) Peano arithmetic, incompleteness and undecidability.

V.M. Abrusci, L. Tortora de Falco, Logica Volume 1- Dimostrazioni e modelli al primo
ordine. Springer, (2014).

V.M. Abrusci, L. Tortora de Falco, L'Incompletezza. Dispense fornite dal docente.