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

  • 2
    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
  • 1
    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
  • 1
    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
  • 1
    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:

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.

  • 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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.