## 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.

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.

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.