Successor function paradox for $\mathfrak{C}$ such that $\mathfrak{B}=(\omega;\lt,S)\preccurlyeq\mathfrak{C}$

Question

I am studying on my own "The Foundation of Mathematics" of Kunen. The exercise II.16.8 starts with:

Let $\mathcal{L}=\{\lt,S\}$ where $S$ is a unary function symbol, and let $\mathfrak{B}=(\omega;\lt,S)$, where $S$ is the successor function.

1. If $\mathfrak{B}\preccurlyeq\mathfrak{C}$ then $\omega$ is an initial segment of $C$ (where $C$ is intended to be the universe of $\mathfrak{C}$)
2. If $\mathfrak{B}\preccurlyeq\mathfrak{C}$, define $\Phi: C \to C$ so that $\Phi(c)$ is $c$ if $c \in \omega$ and $S(c)$ if $c \notin \omega$. Then $\Phi$ is automorphism of $\mathfrak{C}$ (that is, an isomorphism from $\mathfrak{C}$ onto $\mathfrak{C}$)

Hint. For (2), note that every element other than 0 has an immediate predecessor .

What I did:

1. This was quite simple: in fact an initial segment of a set $X$ need not to be an element of $X$, so if $B=C=\omega$ then $\omega$ is an initial segment of $C$, and if $C$ contain $B$, every element of $C$ is an ordinal so $\omega$ is again an initial segment.
2. The Hint makes you understand that $\omega$ cannot be an element of $C$. To verify, I used the Tarski-Vaught criterion (II.16.5):

   Let $\mathfrak{B}$ and $\mathfrak{C}$ be structures for $\mathcal{L}$ with $\mathfrak{B} \subseteq \mathfrak{C}$. Then the following are equivalent:

   • $\mathfrak{B}\preccurlyeq\mathfrak{C}$
   • For all existential formulas $\phi(\overrightarrow{x})$ of $\mathcal{L}$ (so $\phi(\overrightarrow{x}$ is of the form $\exists y \psi(\overrightarrow{x} , y))$ and all $\overrightarrow{a} \in B$ : if $\mathfrak{C} \models \phi[\overrightarrow{a}]$, then there is some $b \in B$ such that $\mathfrak{C} \models \psi [\overrightarrow{a},b]$

using as $\psi(x,y)$ the formula $(y \neq 0 \wedge x \lt y \rightarrow \urcorner(y = S(x)))$

Now if $y= \omega$, for every $a \in \mathfrak{B}$ the $\psi$ is true, but that $y$ is not in $B$ and this is a contradiction for Tarski-Vaugh criterion.

Thus $\omega \notin C$.

And in the end the paradox:

At this point, I must to verify that $\Phi$ is a bijection in $C$, but the inverse of $\Phi$ applied to $\omega + 1$ gives $\omega$ that is not in our universe C! But $\omega + 1$ is an ordinal, so $\omega \in \omega + 1$, that is the paradox, assuming that there really is an automorphism.

Where is the mistake? I can't find it

Answer 1

I'll give you some hints, by way of critiquing what you've written.

This was quite simple: in fact an initial segment of a set $X$ need not to be an element of $X$...

True, but irrelevant, as far as I can see.

...so if $B = C = \omega$ then $\omega$ is an initial segment of $C$, and if $C$ contain $B$, every element of $C$ is an ordinal so $\omega$ is again an initial segment.

No. $\mathfrak{C}$ consists of an arbitrary set $C$ equipped with an arbitrary binary relation $<$ and an arbitrary unary function $S$. We have $\omega\subseteq C$, and we know that $<$ is a linear order on $C$, since $(\omega;<,S)$ is an elementary substructure of $\mathfrak{C}$, but the other elements of $C$ need not be ordinals, and even if they are, the order $<$ on $C$ need not agree with the ordinary ordering of ordinals. For example, a priori we might have $C = \omega\cup \{\mathbb{R},\aleph_7\}$, with $0 < 1 < \mathbb{R} < \aleph_7 < 2 < 3 < \dots$ (in which case $\omega$ would not be an initial segment).

Instead, to prove $\omega$ is an initial segment of $C$, you need to use the fact that $\mathfrak{B}$ is an elementary substructure of $\mathfrak{C}$. For example, we have $\mathfrak{B}\models \lnot \exists x\, (1 < x \land x < 2)$, also $\mathfrak{C}\models \lnot \exists x\, (1 < x \land x < 2)$, so the above picture (with elements of $C\setminus \omega$ wedged between $1$ and $2$) can't happen.

The Hint makes you understand that $\omega$ cannot be an element of $C$.

Actually, there's nothing to stop $\omega$ being an element of $C$! Remember, the ordering $<$ is an arbitrary linear order on $C$. But really, the actual identity of the elements of $C\setminus \omega$ is irrelevant for solving this problem. All that matters is their order type, i.e. how they're related under $<$ (and also $S$).

To verify, I used the Tarski-Vaught criterion (II.16.5).

Why are you using Tarski-Vaught? The Tarski-Vaught criterion is useful for proving that $\mathfrak{B}\preceq \mathfrak{C}$. In this problem, you're given the assumption that $\mathfrak{B}\preceq \mathfrak{C}$.

...using as $\psi(x,y)$ the formula $(y\neq 0\land x < y \rightarrow \lnot (y = S(x)))$.

Now if $y = \omega$, for every $a\in \mathfrak{B}$ the $\psi$ is true, but that $y$ is not in $B$ and this is a contradiction for Tarski-Vaugh criterion. Thus $\omega\notin C$.

This is all quite confused. It looks like you think that Tarski-Vaught says that if there is some $c\in C$ such that for all $b\in B$, $\mathfrak{C}\models \psi(b,c)$, then there is some $b'\in B$ such that for all $b\in B$, $\mathfrak{B}\models \psi(b,b')$. If so, you have not parsed Tarski-Vaught correctly. In the correct statement, a particular $b\in B$ is fixed in advance, and then we get that if $\mathfrak{C}\models \exists y\, \psi(b,y)$, then you can find a witness $b'\in B$ which works for that fixed $b$, in the sense that $\mathfrak{B}\models \psi(b,b')$.

In any case, I think the idea behind what you wrote is this: Suppose $\mathfrak{C}\models \exists y\, (y\neq 0 \land \forall x\, \lnot (S(x) = y))$. Since $\mathfrak{B}\preceq \mathfrak{C}$, also $\mathfrak{B}\models \exists y\, (y\neq 0 \land \forall x\, \lnot (S(x) = y))$ [note that we can use the definition of elementary substructure directly here, rather than appealing to Tarski-Vaught]. But that's a contradiction, since every non-zero natural number is a successor.

The above argument is correct, and it shows that every element of $C\setminus \omega$ is a successor (which is an important step in solving (2)). But it does not show that $\omega\notin C$. Remember, the elements of $C$ don't have to be ordinals, and the ordering $<$ doesn't have to have anything to do with the ordinary ordering of the ordinals! $\omega$ can be a successor in $\mathfrak{C}$. For this reason, it's really better to forget altogether about the question of whether $\omega$ is in $\mathfrak{C}$ or not, and just think of the elements of $C\setminus \omega$ as arbitrary "stuff" ("points", as Andrés says in his comment).