Can a countable model of arithmetic have mutually non-definable numbers?

Question

Let $M$ be a countable model of arithmetic (that satisfies PA). Can we have two numbers $c_1, c_2 \in M$ such that $c_1$ can not be defined in terms of $c_2$, and $c_2$ can not be defined in terms of $c_1$?

(When I say that $a$ can be defined in terms of $b$, I mean that we have a predicate in the language of arithmetic $\phi(x,y)$ such that only $a$ satisfies $\rho(z)=\phi(z,b)$.)

Start with $PA$, and add two symbols $c_1$, $c_2$. For each arithmetical predicate $\phi$, add the axiom $\phi(c_1,c_2) \implies (\exists c \neq c_1 \phi(c,c_2) \land \exists c \neq c_2 \phi(c_1,c))$. My question is equivalent then becomes equivalent to the question of whether this theory is consistient.

Interesting side note: I can show that the negation of continuum hypothesis implies this is true. Let $M$ be a model of PA equinumerous with real numbers. For each $c$ in $M$, there is a countable set $Def(c)$ of numbers definable in terms of $c$ (in the language of arithmetic). By the axiom of symmetry, there will be $c_1, c_2$ such that $c_1 \notin Def(c_2)$ and $c_2 \notin Def(c_1)$. Now take all the true statements of $M$ in the language of arithmetic plus symbols for $c_1$ and $c_2$ (we discard all the true statements involving the other nonstandard numbers). This will have a countable model $M'$, and since $c_1$ and $c_2$ cannot be defined in terms of each other in $M$, this will also be true in $M'$.

Answer 1

Yes. Your use of the "axiom of symmetry" is totally unnecessary: just take $M$ to be any model of cardinality greater than $\aleph_1$, and the same argument works with no additional assumptions. Explicitly, if $A\subset M$ is a set of cardinality $\aleph_1$, then there are at most $\aleph_1$ elements of $M$ that are definable from an element of $A$. So there is some $c_1 \in M$ which is not definable from any element of $A$. Since only countably many elements of $M$ are definable from $c_1$, some $c_2 \in A$ is not definable from $c_1$. So neither of $c_1$ and $c_2$ is definable from the other.

Alternatively, instead of using uncountable models, you can just use compactness. By compactness, it suffices to consider finitely many possible definitions at a time. The argument above can then be carried out in any infinite model, taking $A$ to be a finite set of cardinality greater than the number of definitions you are considering.

Answer 2

Given any first-order theory $T$ (with infinite models) and any cardinal $\kappa\geq|T|$, there is a model of $T$ of size $\kappa$ containing a non-constant indiscernible sequence $I = (a_i)_{i\in \kappa}$ (so $a_i \neq a_j$ for all $i\neq j$). I claim that the elements of $I$ are mutually non-definable. Indeed, if there is some formula $\varphi(x,a_i)$ defining $a_j$, with $i<j$, then also $a_k$ satisfies $\varphi(x,a_i)$, so $a_k = a_j$, contradicting the fact that the sequence is non-constant.

Answer 3

Here's yet another argument, this time via elementary chains and elementary counting:

---

We begin with an easy observation:

Lemma: Suppose $\mathcal{A}\preccurlyeq\mathcal{B}$, $a\in\mathcal{A}, b\in\mathcal{B}$, with $b$ definable from $a$. Then $b\in\mathcal{A}$.

Proof: By elementarity, $\mathcal{A}$ contains a $b'$ with $\mathcal{A}\models\varphi(a, b')$, where $\varphi$ is the formula defining $b$ from $a$ in $\mathcal{B}$. By elementarity again, $\mathcal{B}\models\varphi(a, b')$ so $b=b'$. $\quad\Box$

As an easy corollary, consider a proper elementary sequence $(\mathcal{A}_\eta)_{\eta<\theta}$, let $a_\eta\in \mathcal{A}_\eta\setminus(\bigcup_{\alpha<\eta}\mathcal{A}_\alpha)$, and let $\mathcal{A}=\bigcup_{\eta<\theta}\mathcal{A}_\eta$. Then no $a_\eta$ is definable in $\mathcal{A}$ from parameters in $\{a_\alpha: \alpha<\eta\}$.

This is the only way we will use compactness: to guarantee that our theory has proper elementary chains of arbitrary length. Everything else is just flagrant abuse of vermin and vacancies.

---

Now let's show how this lets us get a pair of mutually undefinable elements (note that the above is "one-way" only). Let $(\mathcal{A}_\eta)_{\eta<\omega_1+1}$ be a proper elementary chain with union $\mathcal{A}$ (ok fine, $\mathcal{A}=\mathcal{A}_{\omega_1}$, but meh). As before let $a_\eta\in\mathcal{A}_\eta\setminus(\bigcup_{\alpha<\eta}\mathcal{A}_\alpha)$ for $\eta\le\omega_1$, and think about $a_{\omega_1}$. No $a_\eta$ with $\eta<\omega_1$ can define it; conversely, $a_{\omega_1}$ can define at most countably many $a_\eta$s. So for some $\gamma<\omega_1$ we have that neither $a_{\omega_1}$ nor $a_\gamma$ is definable from the other in $\mathcal{A}$; now take a countable elementary submodel of $\mathcal{A}$ containing $a_{\omega_1}$ and $a_\gamma$.

---

Now the fun bit:

What about building a triple?

Well, here we need to be careful. We might be tempted to run the same argument as above but with length $\omega_1+\omega_1+1$. If we do this, we get a triple of elements $a_{\omega_1+\omega_1}, a_\eta$ (with $\omega_1<\eta<\omega_1+\omega_1$), $a_\gamma$ (with $\gamma<\omega_1$) such that $a_{\omega_1+\omega_1}$ doesn't define $a_\eta$ and $\{a_\eta, a_{\omega_1+\omega_1}\}$ doesn't define $a_\gamma$; and clearly $\{a_\gamma, a_\eta\}$ won't define $a_{\omega_1+\omega_1}$. However, there's no obvious reason why $a_\eta$ can't be definable from $\{a_\gamma,a_{\omega_1+\omega_1}\}$.

Instead, we need to look at an even longer chain - $(\mathcal{A}_\eta)_{\eta<\omega_2+1}$. (Below, when we say "definable" we mean "definable in $\bigcup_{\eta<\omega_2+1}\mathcal{A}_\eta$;" and yes, that's just $\mathcal{A}_{\omega_2}$.)

We again pick elements $a_\eta$ as before, and start at $a_{\omega_2}$. There are $\omega_2$-many indices $\eta$ with $\omega_1<\eta<\omega_2$ such that $a_\eta$ isn't definable from $a_{\omega_2}$; and for each such $\eta$ there is some $\gamma_\eta<\omega_1$ such that $a_{\gamma_\eta}$ isn't definable from $\{a_\eta, a_{\omega_2}\}$.

Now consider the map $\eta\mapsto\gamma_\eta$; this is a map from a size-$\omega_2$ set to a size-$\omega_1$ set, so there's some $\gamma<\omega_1$ such that for $\omega_2$-many $\eta$s with $\omega_1<\eta<\omega_2$, we have

• $a_\eta$ is not definable from $a_{\omega_2}$,

• $a_\gamma$ isn't definable from $\{a_\eta, a_{\omega_2}\}$.

Let $E$ be the set of these $\eta$s. Only countably many $\eta\in E$ can have the property that $a_\eta$ is definable from $\{a_\gamma, a_{\omega_2}\}$, so pick some $\theta\in E$ with $a_\theta$ not definable from $\{a_\gamma, a_{\omega_2}\}$; no element of $\{a_\gamma, a_\theta, a_{\omega_2}\}$ is definable from the other two.

Now take a countable elementary submodel of $\mathcal{A}$ containing $\{a_\gamma, a_\theta, a_{\omega_2}\}$. Not so bad, right? All we needed was to go up to $\omega_2$.

Hehehehehe.

Exercise: how long must our chains be to get a set of cardinality $\kappa$, no element of which is definable from the rest?

Note: in the above, we "counted down" in our chain. Once $\kappa$ is infinite, this obviously isn't going to work, so we need to use the same intuition but instead "count up" the chain.