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$ Commented 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$ Commented 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$ Commented 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$ Commented 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
    Commented 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$ Commented 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
    Commented 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$ Commented 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
    Commented 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$ Commented Mar 8, 2021 at 21:24

You must log in to answer this question.

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