Chapter 3

Consider a sequence of theories \(T_{i}\) such that \(T_{i} \neq T_{i+1}\) and \(T_{i} \subseteq T_{i+1}\). Show that \(\cup\left\\{T_{i} \mid i \in \mathcal{N}\right\\}\) is not finitely axiomatisable.

If \(T_{1}\) and \(T_{2}\) are theories such that \(\operatorname{Mod}\left(T_{1} \cup T_{2}\right)=\emptyset\), then there is a \(\sigma\) such that \(T_{1} \models \sigma\) and \(T_{2} \models \neg \sigma\).

Show that each countable, ordered set can be embedded in the rationals.

Show that the class of trees cannot be axiomatised. Here we define a tree as a structure \(\langle T, \leq, t\rangle\), where \(\leq\) is a partial order, such that for each \(a\) the predecessors form a finite chain \(a=a_{n}

Consider the class \(\mathcal{K}\) of all structures of type \(\langle 1 ;-; 0\rangle\) with a denumerable unary relation. Show that any \(\mathfrak{A}\) and \(\mathfrak{B}\) in \(\mathcal{K}\) of the same cardinality \(\kappa>\aleph_{0}\) are isomorphic. Show that \(T=T h(\mathcal{K})\) is not \(\kappa\)-categorical for any \(\kappa \geq N_{0}\).

Consider the structure \(\mathfrak{A}=\langle\mathbb{R},\langle, f\rangle\), where \(<\) is the natural order, and where \(f\) is a unary function. Let \(L\) be the corresponding language. Show that there is no sentence \(\sigma\) in \(L\) such that \(\mathfrak{A} \models \sigma \Leftrightarrow f(r)>0\) for all \(r \in R\). (hint: consider isomorphisms \(x \mapsto x+k\) ).

Let \(L\) be a language with one unary function symbol \(f\). Find a sentence \(\tau_{n}\), which says that " \(f\) has a loop of length \(n\) ", i.e. \(\mathfrak{A} \vDash \tau_{n} \Leftrightarrow\) there are \(a_{1}, \ldots, a_{n} \in|\mathfrak{Q}|\) such that \(f^{\mathfrak{2}}\left(a_{i}\right)=a_{i+1}(i\aleph_{0}\). (hint: consider the partition \(\left\\{\left(f^{2}\right)^{i}(a) \mid i \in \omega\right\\}\) in a model \(\left.\mathfrak{A}\right)\). Is \(T \aleph_{0}\)-categorical? Show that \(T\) is complete and decidable. Is \(T\) finitely axiomatisable?

Show that the ordening \(<\), defined by \(x

Show (i) PA \(\vdash \forall x(0 \leq x)\) (use induction on \(\mathrm{x}\) ), (ii) \(\quad \mathbf{P A} \vdash \forall x(x=0 \vee \exists y(x=S y)\) ) (use induction on \(\mathrm{x}\) ), (iii) \(\quad \mathbf{P A} \vdash \forall x y(x+y=y+x)\), (iv) \(\quad \mathbf{P A} \vdash \forall y(x