Skip to main content
added 8 characters in body
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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}$$\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}$$\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.

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}$ + '$\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}$ + "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.

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.

added 180 characters in body
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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 clearly yes:. In $\mathcal{L}_{\omega_1,\omega_1}$ we can express true well-foundedness, so the class of well-founded models of "$\mathsf{ZFC}$ + '$\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.

  • In $\mathcal{L}_{\omega_1,\omega_1}$ we can express true well-foundedness, so the class of well-founded models of "$\mathsf{ZFC}$ + '$\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}$ + "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.
  • What about in $\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.

    Similarly, $\mathsf{ZFC}$ + "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.

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 clearly yes:

  • In $\mathcal{L}_{\omega_1,\omega_1}$ we can express true well-foundedness, so the class of well-founded models of "$\mathsf{ZFC}$ + '$\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}$ + "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.
  • What about in $\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.

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}$ + '$\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}$ + "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.

Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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 clearly yes:

  • In $\mathcal{L}_{\omega_1,\omega_1}$ we can express true well-foundedness, so the class of well-founded models of "$\mathsf{ZFC}$ + '$\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}$ + "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.
  • What about in $\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.