# Section 3.1: Problem 6 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Show that $\mbox{Th}\mathfrak{N}_{S}$ is not finitely axiomatizable. Suggestion: Show that no finite subset of $A_{S}$ suffices, and then apply Section 2.6.
According to Theorem 26H, if $\mbox{Th}\mathfrak{N}_{S}=\mbox{Cn}A_{S}$ were finitely axiomatizable, there would be a finite subset $A$ of $A_{S}$ such that $\mbox{Cn}A=\mbox{Cn}A_{S}=\mbox{Th}\mathfrak{N}_{S}$ . We show that this is not the case.
If a finite $A\subset A_{S}$ , then $\mbox{Cn}A\subseteq\mbox{Cn}A_{S}$ , and we need to show that $\mbox{Cn}A\subsetneq\mbox{Cn}A_{S}$ . That is, there is a sentence $\sigma$ true in $\mbox{Cn}A_{S}$ that is not true in $\mbox{Cn}A$ . At the same time, every model of $A_{S}$ is a model of $A$ , and every sentence true in $A_{S}$ will be true in such a model. Therefore, we need to find a model of $A$ that is not a model of $A_{S}$ , and a sentence $\sigma$ true in $\mbox{Cn}A_{S}$ that is not true in this particular model of $A$ .
Let us call each axioms S1-S4 as $\sigma_{1}$ , $\sigma_{2}$ , $\sigma_{3}$ and $\sigma_{4,n}$ for $n\ge1$ . Let $A_{n}=\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4,1},\ldots,\sigma_{4,n}\}$ , $n\in\mathbb{N}$ . Then, for a finite $A\subset A_{S}$ , there is some $n$ such that $A\subseteq A_{n}\subset A_{S}$ , and $\mbox{Cn}A\subseteq\mbox{Cn}A_{n}\subseteq\mbox{Cn}A_{S}$ . If we show that for every $n$ , $\mbox{Cn}A_{n}\subsetneq\mbox{Cn}A_{S}$ , then we will show the strict inclusion for every finite $A$ .
For $n\in\mathbb{N}$ , as the sentence that is true in $A_{S}$ but not in $A_{n}$ , consider $\sigma=\sigma_{4,n+1}$ . Then, obviously, $\sigma$ is true in $\mbox{Cn}A_{S}$ . We need to provide a model of $A_{n}$ such that $\sigma$ is not true in the model. The axioms of group 4 ensure that there is no loop of any finite length. In $A_{n}$ we excluded all such axioms for the lengths of the loop greater than $n$ . In particular, $\sigma$ says that there is no loop of length $n+1$ . So, our model of $A_{n}$ may have loops of any length greater than $n$ , and to ensure that $\sigma$ is false, it has to have a loop of length $n+1$ . At the same time, we still need to satisfy all axioms S1-S3: $0$ has no predecessor, $\mathbb{S}^{\mathfrak{A}}$ is one-to-one, and every element except $0$ has a predecessor. So, consider the set $N=\{1,\ldots,n+1\}$ , and let $S:\mathbb{N}\cup N\rightarrow\mathbb{N}\cup N$ be $S(k)=k+1\in\mathbb{N}$ for $k\in\mathbb{N}$ , and $S(k)=1+(k\mbox{ mod }(n+1))\in N$ for $k\in N$ . Then, let $\mathfrak{A}=(\mathbb{N}\cup N;0,S)$ . We check that all axioms S1-S4n hold for $\mathfrak{A}$ .
1. S1: $\forall x\mathbb{S}x\neq0$ . Indeed, $s(0)=0\in\mathbb{N}$ , and for every $d\in\mathbb{N}$ , $S(d)\ge1$ , while for every $d\in N$ , $S(d)\notin\mathbb{N}$ .
2. S2: $\forall x\forall y(\mathbb{S}x=\mathbb{S}y\rightarrow x=y)$ . Indeed, if for $d,d'\in\mathbb{N}\cup N$ , $S(d)=S(d')$ , then either $d,d'\in\mathbb{N}$ , and $d+1=d'+1$ implies $d=d'$ , or $d,d'\in N$ , and $1+d\mbox{ mod }(n+1)=1+d'\mbox{ mod }(n+1)$ implies $d\mbox{ mod }(n+1)=d'\mbox{ mod }(n+1)$ and $d=d'$ (all numbers in $N$ have different residuals).
3. S3: $\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ . Indeed, if $d\in\mathbb{N}$ , $d>0$ , then $d-1\in\mathbb{N}$ , and $S(d-1)=d$ , and if $d\in N$ , then if $d=1$ , $d=S(n+1)$ , otherwise $d=S(d-1)$ .
4. S41-S4n: for every $k\in\mathbb{N}$ , $1\le k\le n$ , $\forall x\mathbb{S}^{k}x\neq x$ . Indeed, there are no loops in $\mathbb{N}$ , and $|N|=n+1$ , where each element except $n+1$ is mapped by $S$ to the next one, while $n+1$ is mapped to $1$ (since $N$ is finite, one can even check the finite number of axioms S41-S4n for each element in $N$ ).
Therefore, $\mathfrak{A}$ is indeed a model of $A_{n}$ . At the same time, $\sigma=\sigma_{n+1}$ is not true in $\mathfrak{A}$ , as there is a loop of length $n+1$ in $N$ (actually, for every $d\in N$ , $\vDash_{\mathfrak{A}}\mathbb{S}^{n+1}x=x[s(x|d)]$ , i.e. $\not\vDash_{\mathfrak{A}}\mathbb{S}^{n+1}x\neq x[s(x|d)]$ ).