śr., 10/03/2012 - 12:30 — fmurlak
### Ex. 1

### Ex. 2

### Ex. 3

Hint

### Ex. 4

Hint

### Ex. 5

### Ex. 6

Solution

### Ex. 7

### Ex. 8

Solution

### Ex. 9

### Ex. 10

### Zad. 11

Hint

### Ex. 12

### Ex. 13

Solution

### Zad. 14

Solution

### Ex. 15

Solution

### Ex. 16

Solution

**NO**
### Ex. 17

### Ex. 18

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

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.

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.

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.

\(\mathcal{A}.\) Prove that \(\Delta\cup\Delta'\) satisfies the conditions of the compactess theorem.

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

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

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.

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

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.

\(\{\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.

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.

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.

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.

\(\{\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.

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.

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

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.

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.

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.

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.

Skolema-Loewenheima theorem is should also contain a countable structure. But such a structure does not exist.

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.

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.

Skolema-Loewenheima theorem is should also contain a countable structure. But such a structure does not exist.

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.

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.

\(\{\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.

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

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

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

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.