Model theory for first order logic: compactness theorem, Skolem-Loewenheim theorem

Ex. 1

Show a set \(\Delta\) of first-order sentences such that every two countable models of \(\Delta\) are isomorphic, but there exist two uncountable, nonisomorphic models of \(\Delta.\)

Ex. 2

Let \(\Sigma\) be a finite signature. Prove that for every set \(\Delta\) of sentences over \(\Sigma,\) the following conditions are equivalent:

\(\Delta\) has only finite models.
\(\Delta\) has, up to isomorphims, only finitely many models.

Ex. 3

Prove that if a class \(\mathcal{A}\) of structures over a signature \(\Sigma\) is axiomatizable by a set of first-order sentences, and if its complement
\(Mod(\Sigma)\setminus\mathcal{A}\) is also axiomatizable by a set of first-order sentences, then both classes are definable by single first-order sentences.

Hint

Assume that one class is axiomatizable by \(\Delta\) and the other by \(\Delta',\), but no finite subset of \(\Delta\) axiomatizes
\(\mathcal{A}.\) Prove that \(\Delta\cup\Delta'\) satisfies the conditions of the compactess theorem.

Ex. 4

Prove the following Robinson theorem:
If \(\Delta,\Delta'\) are satisfiable sets of sentences over some signature \(\Sigma,\) but \(\Delta\cup\Delta'\) is not satisfiable, then there exists a sentence
\(\varphi\) such that \(\Delta\models\varphi\) and \(\Delta'\models\lnot\varphi.\)

Hint

Prove that if the above consequence does not hold then \(\Delta\cup\Delta'\) satisfies the conditions of the compactess theorem.

Ex. 5

Let \(Spec(\varphi)\) denote the set of cardinalities of all finite models of a formula \(\varphi.\)
Prove that if \(\Delta\) is a set of sentences such that for each \(\varphi\in\Delta\) the set \(Spec(\lnot\varphi)\) is finite,
and if \(\Delta\models\psi,\) then \(Spec(\lnot\psi)\) is also finite.

Ex. 6

Prove that the class of all equivalence relations that have finitely many equivalence classes, is not axiomatizable.

Solution

Assume that a set of sentences \(\Delta\) axiomatizes the class. Add to \(\Delta\) the set
\(\{\exists x_1\ldots\exists x_n \bigwedge_{i\neq j}\lnot E(x_i,x_j)~|~n\in\mathbb{N}\}\).
The new set satisfies the conditions of the compactness theorem: its every finite subset is satisfiable, since the added sentence
\(\exists x_1\ldots\exists x_n \bigwedge_{i\neq j}\lnot E(x_i,x_j)\) says thay the equivalence relation \(E\) has at least \(n\) equivalence classes,
so finitely many such sentences can be satisfied in a structure with sufficiently many equivalence classes.

As a result, the entire set has a model, which obviously has infinitely many equivalence classes - contradiction.

Ex. 7

Prove that the class of al structures \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) over a signature with a single binary relation symbol \(E\) such that \(E^{\mathbb{A}}\) is finite, is not axiomatizable.

Ex. 8

Prove that the class of all algebras \(\mathbb{A}=\langle A,f^{\mathbb{A}}\rangle,\) where \(f\) is a unary function symbol, such that \(|\vec{f}(A)|< |A|\), is not axiomatizable.

Solution

Assume that a set of sentences \(\Delta\) axiomatizes the class. Add to \(\Delta\) the set
\(\{\exists x_1\exists x_2\ldots\exists x_{n-1}\exists x_n \bigwedge_{i\neq j}f(x_i)\neq f(x_j)~|~n\in\mathbb{N}\}\).
The new set satisfies the conditions of the compactness theorem: its every finite subset is satisfiable, since finitely many added sentences mean that the image of \(f\) has at least some fixed finite number of elements.

As a result, the entire set has a model, which obviously is infinite. Looking at the signature, the set has also a countable model \(\mathfrak{A}\), by the Skolema-Loewenheim Theorem. In \(\mathfrak{A}\) the image \(f^{\mathfrak{A}}\) is countable too, so \(\mathfrak{A}\) does not belong to the class in question - contradiction.

Ex. 9

Prove that the class of all structures \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) over a signature with a single binary relation symbol \(E\) such that \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) is not axiomatizable.

Ex. 10

Prove that the class of all structures \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) where \(r\in\Sigma^{R}_{1}\) such that \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) is not axiomatizable.

Zad. 11

Prove the following Hessenberg Theorem:
For each infinite cardinality \(\mathfrak{m}\), there is \(\mathfrak{m}^2=\mathfrak{m}.\)

Hint

Write a first-order sentence that will imply that the carrier of a structure has cardinality not smaller than the cardinality of its Cartesian square. Show that the sentence has an infinite model and use the Skolema-Loewenheim theorem.

Ex. 12

Prove that the class of all structures \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) where \(r\in\Sigma^{R}_{1}\) such that \(|r^{\mathbb{A}}|=2^{{|A\setminus r^{\mathbb{A}}|}}\) is not axiomatizable.

Ex. 13

Prove that the class of all structures isomorphic to a structure of the form \(\mathbb{A}=\langle\mathcal{P}(A),\cup^{\mathbb{A}},\cap^{\mathbb{A}},\subseteq^{\mathbb{A}}\rangle,\) where \(\cup^{\mathbb{A}},\cap^{\mathbb{A}}\) and \(\subseteq^{\mathbb{A}}\) are, respectively, the union, intersection and containment relations on sets, is not axiomatizable.

Solution

The class contains infinite structures, and the signature is finite. If the class were axiomatizable with a set of first-order sentences, then by the
Skolema-Loewenheima theorem is should also contain a countable structure. But such a structure does not exist.

Zad. 14

Consider a signature with a binary function symbol \(\circ\), unary function symbol \(inv\) and a constant symbol \(id\). A model \(\mathfrak{F}\) (this is the gothic F, you may write ordinary F in the solution) over this signature is called a bijection group if its carrier is the set of all bijections \(f:A\to A\) on some set \(A,\) and the operations are interpreted as follows: \(\circ^{\mathfrak{F}}\) is function composition, \(inv^{\mathfrak{F}}\) is function inversion and \(id^{\mathfrak{F}}\) is the identity function on \(A\).

Prove that ther is no set \(\Gamma\) of first order sentences such that \(\mathfrak{B}\models\Gamma\) iff \(\mathfrak{B}\) is isomorphic to a bijection group.

Solution

Ex. 15

Prove that there is no first order sentence \(\varphi\) with the property that for each undirected (finite of not) graph \(\mathfrak{G}\) there is
\(\mathfrak{G}\models\varphi\) iff evert vertex of \(\mathfrak{G}\) belongs to a (finite) cycle in the graph.

Solution

Assume that such a set \(\Delta\) of sentences exists. Extend the signature with a new constant \(c\) and extend \(\Delta\) with the set
\(\{\lnot\exists x_1\exists x_2\ldots\exists x_{n-1}\exists x_n E(c,x_1)\land E(x_1,x_2)\land E(x_2,x_3)\land\ldots\land E(x_{n-1},x_n)\land E(x_n,c)~|~n\in\mathbb{N}\}\).
The extended set satisfies the conditions of the compactnes theorem: its every finite subset is satisfiable, since a finite number of added sentences
prevent \(c\) from being on a cycle of a few finite sizes, so as a model one may take a finite cycle of sufficiently many vertices.

As a result, the entire set has a model: a contradiction, as \(c\) does not belong to any cycle in it.

Ex. 16

Does every set of sentences \(\Delta\) contain a minimal, wrt. inclusion, subset \(\Delta'\subseteq\Delta\) such that \(\Delta'\models\Delta\)?

Solution

For example, consider \(\Delta\) jest \(\{\exists x_1\dots x_n \bigwedge_{1\leq i < j \leq n}x_i\neq x_j~:~n\in\mathbb{N}\}.\)

Ex. 17

Prove that every finite set of sentences \(\Delta\) contains a subset \(\Delta'\subseteq\Delta\) such that \(\Delta'\models\Delta\) and that is independent, i.e., such that for each \(\varphi\in\Delta'\) there is \(\Delta'\setminus\{\varphi\}\not\models\varphi\).

Ex. 18

Let \(f\) be a unary function symbol, and let \(\mathcal{A}=\bigcup_{n\in\mathbb{N}}Mod(\forall x\underbrace{f\ldots
f}_n(x)=x).\)

Prove that \(\mathcal{A}\) cannot be axiomatized with any set of first order sentences, and the complement of \(\mathcal{A}\) cannot be defined with a single first-order sentence.