8
$\begingroup$

This was previously asked and bountied on MSE:

For brevity, let $T$ be $\mathsf{ZFC+V=L}$.

Say that an extension of $\mathsf{ZFC}$ is $\omega$-complete iff it has exactly one $\omega$-model up to elementary equivalence. While the $\omega$-incompleteness of $T$ is easily provable in theories only slightly stronger than $T$ itself, I don't immediately see how to do it in $T$ alone. My question is:

Is the theory $S:=T+$ "$T$ is $\omega$-complete" consistent?

Here are a couple observations:

  • If we replace "$\omega$-model" by "well-founded model," the answer is obviously yes under standard assumptions. Let $\alpha$ be the second-smallest ordinal such that $L_\alpha\models\mathsf{ZFC}$. Then $L_\alpha$ also satisfies "$\mathsf{ZFC+V=L}$ has exactly one well-founded model." Unfortunately, we have no analogous hierarchy of $\omega$-models, so this is a non-starter here.

  • As to the specific choice of theory in question, the point is that (something like) $\mathsf{V=L}$ is needed to block an easy proof of a negative answer via forcing. For example, reasoning in $\mathsf{ZFC}$, if $\mathsf{ZFC}$ had an $\omega$-model $\mathcal{M}$ it would have a countable one $\hat{\mathcal{M}}$, and we could force over $\hat{\mathcal{M}}$ to get a non-elementarily-equivalent $\omega$-model $\hat{\mathcal{N}}$. (Forcing over ill-founded countable models is no harder really than forcing over well-founded ones.) The key point here is that forcing preserves $\mathsf{ZFC}$. This breaks down of course for $\mathsf{V=L}$ and so this argument is irrelevant here. Given the paucity of techniques we currently have for building models of $\mathsf{ZFC}$ in the first place, this seems to be a real issue.

Ultimately I suspect that the answer is negative, but the above two points between them rule out all the lines of attack I've been able to think of so far.


EDIT: In light of Farmer S's answer below, let me explicitly mention a rule of thumb which I forgot: when thinking about properties which are not too far from first-order definable, always consider the hyperarithmetic hierarchy!

For example, for every $\mathcal{L}_{\omega_1,\omega}$-sentence $\varphi$, if $\varphi$ has a model then it has a model $M$ which is countable in $L$, and moreover the $L$-least (real coding a) model of $\varphi$ is hyperarithmetic relative to (any real coding) $\varphi$. The property "Is an $\omega$-model of $T$" is expressible as a computable $\mathcal{L}_{\omega_1,\omega}$-sentence, and this drives Farmer S's point that $T^+\in L_{\omega_1^{CK}}$.

$\endgroup$
11
  • 1
    $\begingroup$ Is an $\omega$-model one where the natural numbers are the standard ones? I tried to find a definition, and could only find: math.stackexchange.com/questions/1113639/what-is-an-omega-model $\endgroup$ Mar 8, 2021 at 20:39
  • 1
    $\begingroup$ @PaceNielsen Yup, an $\omega$-model is one where the naturals are standard. In general, in any context where we have a theory $T$ together with a canonical interpretation of some theory of arithmetic into $T$, we say that an $\omega$-model of $T$ is one in which this interpretation yields a structure isomorphic to $\mathbb{N}$ itself. The usual examples are: second-order (or higher-order) arithmetic together with the "first-order part" interpretation, and set theories together with the "$\omega$" interpretation. ("Categoricity" results can justify the privileging of a specific interpretation.) $\endgroup$ Mar 8, 2021 at 20:39
  • $\begingroup$ So, if I'm understanding correctly, what you'd like is (under the assumption that $T$ has an $\omega$-model) the construction of a structure (in the language of set theory) that satisfies $T$, it has a unique proper substructure satisfying $T$, and $\omega$ is standard in the structure. Is that correct? I ask because I'm trying to figure out what "$T$ is $\omega$-complete" would mean as a statement in some language. I can see how to express it using a language that allows infinite conjunctions, but that goes beyond the language of set theory. $\endgroup$ Mar 8, 2021 at 20:50
  • $\begingroup$ @PaceNielsen "$T$ is $\omega$-complete" is already a statement in the object language: every model $M$ of $\mathsf{ZFC}$ has a notion of "$\omega$-model of $\mathsf{ZFC}$," namely "model of $\mathsf{ZFC}$ whose $\omega$ is isomorphic to my $\omega$." There's no linguistic or otherwise "meta" issue here. (In particular, note that if $M\models\mathsf{ZFC}$ is not an $\omega$-model itself then the $\omega$-models of $\mathsf{ZFC}$ in the sense of $M$ - assuming $M$ thinks there are any at all - will not be genuine $\omega$-models.) So the $S$ of the OP is a genuine first-order theory. $\endgroup$ Mar 8, 2021 at 20:55
  • 2
    $\begingroup$ @NoahSchweber Using Barwise compactness one can prove an appropriate version of Gödel's second incompleteness for this context to shows that for any r.e. extension $T$ of ZF, if $T$ has an $\omega$-model, then $T$ has an $\omega$-model that satisfies "$T$ has no $\omega$-model", which provides a high level explanation of what's happening in Farmer F.'s recursion-theoretic solution. I will try to the flesh out this as an alternative answer to your question "before long". $\endgroup$
    – Ali Enayat
    Mar 10, 2021 at 3:48

1 Answer 1

13
$\begingroup$

Claim: $T+$"$T$ is $\omega$-complete" is inconsistent. For suppose it's consistent and now work in a model $V$ of this theory. Let $T^+$ be the resulting completion of $T$ (i.e. the unique theory of the $\omega$-models of $T$ in the sense of $V$). Then note that $T^+$ is a $\Delta^1_1$ real, so $T^+\in L_{\omega_1^{\mathrm{ck}}}$. But $L_{\omega_1^{\mathrm{ck}}}\subseteq\mathrm{wfp}(M)$ whenever $M\models T$ is an $\omega$-model, and therefore every real $x\in L_{\omega_1^{\mathrm{ck}}}$ is such that $x\leq_{\mathrm{T}} T^+$ (the sub-$\mathrm{T}$ there being "Turing", as opposed to the theory $T$). (Given $x$, fix a wellorder $W$ of $\omega$ in ordertype $\alpha$ with $x\in L_\alpha$. Then (roughly) $T^+$ models "$W$ is a wellorder", and can recover $x$ from $W$. (Edited in:) Formally, fix an integer $e$ which indexes a recursive wellorder of $\omega$ in ordertype $\alpha$ with $x\in L_\alpha$. Recall $L_\alpha$ projects to $\omega$, and $x\leq_{\mathrm{T}} t^{L_\alpha}$, the first-order theory of $L_\alpha$. Fix a Turing reduction $n$ of $x$ from $t^{L_\alpha}$. Then for $m<\omega$, we have $m\in x$ iff $T^+$ contains the statement "Let $\beta$ be the ordertype of the wellorder coded by $e$, and let $y\leq_{\mathrm{T}} t^{L_\beta}$ via the $n$th Turing program; then $m\in y$".) But with $T^+\in L_{\omega_1^{\mathrm{ck}}}$, this gives a contradiction.

$\endgroup$
7
  • $\begingroup$ Very nice! However, I think your proof that $x\le_TT^+$ isn't complete. Specifically, we cannot computably build $L_\alpha$ from a copy of $\alpha$, so "[we] can recover $x$ from $W$" isn't really correct on the nose. (In fact, given a well-ordering $A$, the only reals computable from all copies of $A$ are the computable ones.) I think I see how to get around this though. $\endgroup$ Mar 8, 2021 at 21:12
  • $\begingroup$ Hmm, I guess it also doesn't really make sense to say $T^+$ models "$W$ is a wellorder''; it should be that we let $e$ be some integer which is the index of a wellorder of $\omega$ of the right length in whatever coding we're using, and from that integer, $T^+$ recovers $x$. (That's more formally what I had in mind.) $\endgroup$
    – Farmer S
    Mar 8, 2021 at 21:15
  • $\begingroup$ I think the following works: grab a whole model instead of just the theory. Specifically, working within $V\models S$, the $L$-least real $r$ coding an $\omega$-model of $\mathsf{ZFC+V=L}$ is hyperarithmetic and hence its jump is an element of the structure it codes, which it consequently computes - an obvious absurdity. $\endgroup$ Mar 8, 2021 at 21:15
  • $\begingroup$ (I'm not saying to computably build (the theory of) $L_\alpha$ from the wellorder, but that for each $x$, there are integers $e,n$ such that $m\in x$ iff $T^+$ contains the statement "Let $\alpha$ be the ordertype of the wellorder given by $e$, and $y$ be the $n$th real of the theory of $L_\alpha$; then $m\in y$".) $\endgroup$
    – Farmer S
    Mar 8, 2021 at 21:23
  • $\begingroup$ Ah, I see. I find it a bit easier to think in terms of coding structures, but you're right, that works; if you modify the answer to include this, I'll accept it! $\endgroup$ Mar 8, 2021 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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