1
$\begingroup$

Are there set theories that extend some complete infinitary language $\mathcal L_{\kappa, \lambda}$, prove all axioms of $\sf ZFC$, and are finitary $\textbf{FOL}$ complete? That is, every sentence in $\mathcal L(=,\in)_{\omega,\omega}$ is decidable.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

To avoid triviality (e.g. "The true $\mathcal{L}_{\kappa,\lambda}$-theory of $V$") let's look specifically for theories which $(1)$ consist of adding to $\mathsf{ZFC}$ a single infinitary sentence and $(2)$ have that single sentence being "reasonably simple." As long as we stick to $\mathcal{L}_{\omega_1,\omega_1}$ this last condition has a natural interpretation, namely that we want a single computable sentence (once our syntax gets too big it's unclear what this should mean).

Even with this restriction, the answer is yes. In $\mathcal{L}_{\omega_1,\omega_1}$ we can express true well-foundedness, so the class of well-founded models of "$\mathsf{ZFC+V=L}$ + '$\mathsf{ZFC}$ has no well-founded model'" is $\mathcal{L}_{\omega_1,\omega_1}$-elementary. But this class has a single element (up to isomorphism), so a fortiori its theory is $\mathsf{FOL}$-complete.

  • Similarly, $\mathsf{ZFC+V=L}$ + "The ordertype of the levels of $L$ satisfying $\mathsf{ZFC}$ is $\omega^2+17$" + $\mathcal{L}_{\omega_1,\omega_1}$-wellfoundedness is categorical so a fortiori $\mathsf{FOL}$-complete. You have to go quite a ways up the $L$-hierarchy before you get a level which is not $\mathcal{L}_{\omega_1,\omega_1}$-"identifiable."

What if we try to work in the much weaker (and better behaved) logic $\mathcal{L}_{\omega_1,\omega}$? Well, here things are trickier. To start off, here's an easy affirmative answer to a weak version of the question. Every countable structure is pinned down up to isomorphism by a single $\mathcal{L}_{\omega_1,\omega}$-sentence (this is Scott's isomorphism theorem), so letting $\sigma$ be the sentence so characterizing the Cohen-Shepherdson minimal wellfounded model of $\mathsf{ZFC}$ we get that $\mathsf{ZFC+\sigma}$ is categorical. However, this $\sigma$ is in no way computable. In fact, no model of $\mathsf{ZFC}$ can have a computable Scott sentence, so if we demand that our single sentence be computable then the "categoricity trick" won't work. Fortunately, you only asked for $\mathsf{FOL}$-completeness; if memory serves there's a trick that gives an affirmative answer here too, but I'll have to recall the details.

$\endgroup$
4
  • 1
    $\begingroup$ @ZuhairAl-Johar Sorry, that comment was incorrect as written (I meant to shift to $\mathcal{L}_{\omega_1,\omega_1}$ there). Since it's too late to edit, I've deleted it. $\endgroup$ Commented Jul 1, 2023 at 22:43
  • 1
    $\begingroup$ @Ok, I've deleted my comment too. It would be nice to see a theory in $\mathcal L_{\omega_1, \omega}$ that is $\sf FOL$-complete, I don't know what is the trick. I hope I'll see it with a posting\comment\answer of yours. $\endgroup$ Commented Jul 1, 2023 at 22:48
  • 1
    $\begingroup$ @ZuhairAl-Johar To be clear, it's only hard if you demand computability of the theory. Otherwise you can just use Scott's theorem. $\endgroup$ Commented Jul 1, 2023 at 23:53
  • 1
    $\begingroup$ @ZuhairAl-Johar Just fixed a nasty typo FYI. $\endgroup$ Commented Sep 24, 2023 at 4:38

You must log in to answer this question.

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