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.

Informatyka MIMUW