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:

  1. \(\Delta\) has only finite models.
  2. \(\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.

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.\)

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.

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.

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}.\)

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.

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.

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.

Ex. 16

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

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.