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

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'$.

• Just for fun, here's a really stupid argument in ZFC alone: the statement "For every countable theory, there is a countable model and a pair of elements which are mutually undefinable" is (appropriately phrased) $\Pi^1_2$; now force $\neg$CH, run your argument, and use Shoenfield absoluteness. – Noah Schweber Nov 17 '17 at 23:24
• @NoahSchweber You mean force $\lnot CH$ in $V$? That's great! – PyRulez Nov 17 '17 at 23:40
• I'm not sure what you mean by "force $\neg$CH in $V$." Forcing takes a model of ZFC, and produces a larger model of ZFC with controlled properties. So we're really producing a bigger model, $V[G]$, in which CH holds; this tells us nothing about whether CH holds in $V$. – Noah Schweber Nov 17 '17 at 23:42
• (You might object that there is no bigger model than $V$. This is right if we're taking $V$ to be the "actual" universe of all sets. To get around this, we can develop forcing internally, and produce a Boolean-valued proper class structure $W$, interpreted in $V$, such that $W$ satisfies ZFC+$\neg$CH in the sense that each axiom of ZFC, and $\neg$CH, has truth value $\top$ in $W$.) – Noah Schweber Nov 17 '17 at 23:43
• Assuming that there is any model with two mutually undefinable elements, can't we get a countable one from Lowenheim-Skolem? The number of pairs $\phi,\psi$ of formulas that could make the mutual definition is only countable. So the real question is only consistency, not count ability. – Carl Mummert Nov 18 '17 at 0:37

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.

• How do you prove that $c_1 \notin Def(c_2)$ and $c_2 \notin Def(c_1)$ for a model of cardinality greater than $\aleph_1$? – PyRulez Nov 17 '17 at 20:05
• This is literally just the proof of the axiom of symmetry from the negation of CH. That proof has nothing to do with real numbers; it's just a fact about sets of size greater than $\aleph_1$. – Eric Wofsey Nov 17 '17 at 20:08
• @celtschk: As mentioned in the question, the cardinality doesn't matter since you are just showing the consistency of a certain first-order theory. – Eric Wofsey Nov 17 '17 at 20:13
• You can have any number (up to the size of your model). Here's how you get three. Start by taking a set $A$ of size $\aleph_2$ in a model $M$ of size $\aleph_3$. Then at most $\aleph_2$ elements of $M$ are definable from any pair of elements of $A$, so there is some $m\in M$ definable from no pair of elements of $A$. Now extend your language by adding a constant symbol for $m$ and use the argument of my answer to find two elements $a_1,a_2\in A$ which are mutually undefinable. Then $m,a_1,$ and $a_2$ are mutually undefinable. – Eric Wofsey Nov 17 '17 at 20:37
• Continuing similarly by induction, you can get $n$ mutually undefinable elements for any $n\in\mathbb{N}$, and thus infinitely many by compactness. – Eric Wofsey Nov 17 '17 at 20:37

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.

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:

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.

• For minimal cardinality of the resulting $\mathcal{A}$, just let $\vert\mathcal{A}_\eta\vert\le\aleph_0\cdot \vert\eta\vert$. In particular, to get a triple we need only consider models of cardinality $\le\aleph_2$. – Noah Schweber Nov 17 '17 at 23:14