14
$\begingroup$

Consider the following sentences in a first-order language with one unary function symbol $f$:

$\forall x \exists y (fy=x)$

$\forall y\forall z(fy=fz\to y=z))$

$\forall x (\underbrace{f\dotsb f}_{n\mbox{ times}}x\neq x)$

so that any model of them is just a set equipped with a bijection with no finite orbits. This is the simplest list of axioms I could think of which has countably many non-isomorphic countable models and is uncountably categorial if you believe in Zorn's lemma, and this theory is therefore complete. Surely completeness of this theory doesn't depend on the axiom of choice. Does it?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ George, welcome to MathOverflow. It is a very nice question. I wanted to mention that in addition to accepting Emil's great answer, it is also possible for you to upvote it (as I have), and this would be normal if indeed you find it worthwhile. $\endgroup$
    – Joel David Hamkins
    Commented Jan 23 at 12:30

1 Answer 1

Reset to default
21
$\begingroup$

There are several ways how to prove the completeness of this theory (let me call it $S$) without choice:

  1. Prove in a purely syntactic way (by induction on the complexity of a formula) that $S$ has quantifier elimination.

  2. Observe that $S$ has only one countable recursively saturated model.

    For an elementary version of this argument: expand $S$ to a theory $S'$ with countably many constants $\{c_n:n\in\omega\}$, and axioms that $c_n$ is not reachable from $c_m$ in finitely many steps for $n\ne m$. Using the compactness theorem, you easily show that if $\phi$ is consistent with $S$, it is consistent with $S'$, hence it holds in a countable model of $S'$ (this needs no choice as the language is countable). But reducts of countable models of $S'$ in the original language are all isomorphic (they consist of countably many copies of $(\mathbb Z,s)$).

  3. Show that any two models of $S$ are elementarily equivalent by an Ehrenfeucht–Fraïssé argument. Or, apply a ready-made EF argument: Gaifman's locality theorem.

  4. The completeness of $S$ is an arithmetical ($\Pi_2$) statement. Thus, you can just prove the result in ZFC, and use the conservativity of ZFC over ZF for arithmetical sentences.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Expanding on (3) (which applies to all theories) for the OP: the key point here is the definition and basic analysis of Godel's constructible universe $L$. For every finite $T\subset \mathsf{ZFC}$ we have a $\mathsf{ZF}$-proof that $T$ holds in $L$, and moreover we have a separate $\mathsf{ZF}$-proof that every arithmetical sentence true in $L$ is actually true; now given a $\mathsf{ZF}$-proof that your theory is complete, apply the above with $T$ the axioms used. None of this is quite trivial but once it's all put together we have a powerful black-boxable result for de-choiceifying arguments. $\endgroup$
    – Noah Schweber
    Commented Jan 23 at 16:05
  • $\begingroup$ I was hoping someone would come along and explain that part a bit. Where can I learn about this? It seems like black magic to me. $\endgroup$
    – George Hayduke
    Commented Jan 23 at 16:29
  • $\begingroup$ @GeorgeHayduke This is basically the Shoenfield absoluteness theorem. $\endgroup$
    – Timothy Chow
    Commented Jan 23 at 21:29
  • 3
    $\begingroup$ Preservation of the truth of arithmetic sentences to transitive models of ZF such as $L$ follows immediately from the absoluteness of $\omega$. There is no need for anything as sophisticated as Shoenfield's absoluteness theorem. $\endgroup$
    – Emil Jeřábek
    Commented Jan 24 at 8:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .