Problem 1
Consider the language of groups. \(T=\\{\sigma \mid \mathfrak{A} \models \sigma\\}\), where \(\mathfrak{A}\) is a fixed non-trivial group. Show that \(T\) is not a Henkin theory.
Problem 1
Let \(\mathfrak{A}=\langle A, \leq\rangle\) be a poset. Show that \(\operatorname{Diag}^{+}(\mathfrak{A}) \cup\\{\bar{a} \neq \bar{b} \mid a \neq b, a, b \in\) \(|\mathfrak{A}|\\} \cup\\{\forall x y(x \leq y \vee y \leq x)\\}\) has a model. (Hint: use compactness). Conclude that every poset can be linearly ordered by an extension of its ordering.
Problem 2
Determine the Skolem forms of
(a) \(\forall y \exists x\left(2 x^{2}+y x-1=0\right)\),
(b) \(\forall \varepsilon \exists \delta(\varepsilon>0 \rightarrow(\delta>0
\wedge \forall x(|x-\bar{a}|<\delta
\rightarrow|f(x)-f(\bar{a})|<\varepsilon)\),
(c) \(\forall x \exists y(x=f(y))\),
(d) \(\forall x y(x
Problem 3
Let \(\mathfrak{A} \subseteq \mathfrak{B} . \varphi\) is called universal (existential) if \(\varphi\) is prenex with only universal (existential) quantifiers. (i) Show that for universal sentences \(\varphi \mathfrak{B} \models \varphi \Rightarrow \mathfrak{A} \models \varphi\). (ii) Show that for existential sentences \(\varphi \mathfrak{A} \models \varphi \Rightarrow \mathfrak{B} \models \varphi\). (Application: a substructure of a group is a group. This is one reason to use the similarity type \(\langle-; 2,1 ; 1\rangle\) for groups, instead of \(\langle-; 2 ; 0\rangle\), or \(\langle-; 2 ; 1\rangle\), as some authors do).
Problem 3
Let \(\sigma^{s}\) be the Skolem form of \(\sigma\). Consider only sentences. (i) Show that \(\Gamma \cup\left\\{\sigma^{s}\right\\}\) is conservative over \(\Gamma \cup\\{\sigma\\}\). (ii) Put \(\Gamma^{s}=\left\\{\sigma^{s} \mid \sigma \in \Gamma\right\\}\). Show that for finite \(\Gamma, \Gamma^{s}\) is conservative over \(\Gamma\). (iii) Show that \(\Gamma^{s}\) is conservative over \(\Gamma\) for arbitrary \(\Gamma\).
Problem 4
Let \(\mathfrak{A}=\langle N,<\rangle, \mathfrak{B}=\langle N-\\{0\\},<\rangle .\) Show: \(\quad\) (i) \(\quad \mathbf{A} \cong \mathfrak{B}\); (ii) \(\mathfrak{a} \equiv \mathfrak{B}\); (iii) \(\mathfrak{B} \subseteq \mathfrak{A}\); (iv) \(\quad\) not\mathfrak \(\mathfrak{B} \prec \mathfrak{A}\).
Problem 4
Show that \(T=\left\\{\sigma \mid \lambda_{2} \vdash \sigma\right\\} \cup\left\\{c_{1} \neq c_{2}\right\\}\) in a language with \(=\) and two constant symbols \(c_{1}, c_{2}\), is a Henkin theory.
Problem 6
Show that well-ordering is not a first-order notion. Suppose that \(\Gamma\)
axiomatises the class of well-orderings. Add countably many constants \(c_{i}\)
and show that \(\Gamma \cup\left\\{c_{i+1}
Problem 8
Let \(L\) have the binary predicate symbol \(P, \sigma:=\forall x \neg P(x, x) \wedge \forall x y z(P(x, y) \wedge\) \(P(y, z) \rightarrow P(x, z)) \wedge \forall x \exists y P(x, y) .\) Show that Mod \((\sigma)\) contains only infinite models.
Problem 12
Let \(X \subseteq|\mathfrak{A}| .\) Define \(X_{0}=X \cup C\) where \(C\) is the set of constants of \(\mathfrak{A}, X_{n+1}=X_{n} \cup\left\\{f\left(a_{1}, \ldots, a_{m}\right) \mid f\right.\) in \(\left.\mathfrak{A}, a_{1}, \ldots, a_{m} \in X_{n}\right\\}, X_{\omega}=\) \(\bigcup\left\\{X_{n} \mid n \in \mathbb{N}\right\\}\) Show that \(\mathfrak{B}=\left\langle X_{\omega}, R_{1} \cap X_{\omega}^{r_{1}}, \ldots, R_{2} \cap X_{\omega}^{r_{1}}, f_{1}\left|X_{\omega}^{a_{1}}, \ldots, f_{m}\right| X_{\omega}^{a_{m}},\left\\{c_{1} \mid i \in\right.\right.\) \(I\\}\rangle\) is a substructure of \(\mathfrak{A}\). We say that \(\mathfrak{B}\) is the substructure generated by \(X\). Show that \(\mathfrak{B}\) is the smallest substructure of \(\mathfrak{A}\) containing \(X ; \mathfrak{B}\) can also be characterized as the intersection of all substructures containing \(X\).
