0

This question concerns Godel's Theorem on existence of classes in Set Theory of von Neumann–Bernays–Gödel.

This theorem implies that for any formula $\varphi(x)$ with one free variable $x$ whose quantifiers are of the form $\forall x\in\mathbf U$ or $\exists x\in\mathbf U$ the class $\{x:\varphi(x)\}$ exists.

Question. Is there a formula $\varphi(x)$ with one free variable in the language of set theory for which the class $\{x:\varphi(x)\}$ does not exist?

Added in Edit. Reading the comments I realized that such a formula indeed exists. So, I reformulate my question to

Question'. Find a (relatively) short formula $\varphi(x)$ for which the existence of the class $\{x:\varphi(x)\}$ cannot be proved in NBG.

I need such a formula to stress that the restricting quantifiers to run over sets in Godel's theorem on existence of classes is essential. Desirably to have such a formula as simple as possible.

Taras Banakh
  • 40,791
  • 2
    Which theorem of Godel do you have in mind? What is $\mathbf{U}$? With "the class does not exist" do you mean it provably (in NBG) doesn't exist, or one for which it is consistent that it doesn't exist? When saying "the language of set theory" do you admit quantifiers over all classes or just ones over sets? – Wojowu May 06 '20 at 21:36
  • 5
    If you admit quantifiers over all classes, then the answer is as follows: for provable nonexistence, the answer is probably no, as that would imply Morse-Kelley set theory is inconsistent. If you mean consistent nonexistence, the answer is positive, as it's consistent that the set of truths about $V$ (which is definable in the language of classes) doesn't exist, as its existence implies consistency of ZF, and hence NBG. – Wojowu May 06 '20 at 21:41
  • 1
    @Wojowu: "as its existence implies consistency of ZF, and hence NBG", is it understood to mean "as its existence would imply consistency of ZF, and hence of NBG, is provable in ZF"? – Qfwfq May 06 '20 at 22:35
  • 1
    @Qfwfq Existence of the truth class literally implies consistency of ZF, so if the existence was provable, so would be consistency. – Wojowu May 06 '20 at 22:37
  • @Wojowu, I think that @‍Qfwfq was referring to the grammar, not the logic. That is, "its existence implies consistency of ZF" seems to imply that it does exist, and so we can deduce consistency of ZF; but the subjunctive mood ("its existence would imply") says that we don't know it exists, and explains what we could deduce if we did. – LSpice May 06 '20 at 23:08
  • 1
    @LSpice "The existence of the truth class" is (formalizable as) a sentence in the language of NBG, and that sentence implies the (formalization of) the sentence "ZF is consistent". – Andreas Blass May 06 '20 at 23:28
  • @Wojowu For me $\mathbf U$ is the class of all sets, $\mathbf V$ is the class of well-founded sets, i.e., the union of the von Neumann cumulative hierarchy. The axiom of foundation (or else regularity) is equivalent to $\mathbf U=\mathbf V$. As I understood from your comment, a simple formula defining a non-existent class does not exist because it would imply the inconsistency of the Morse-Kelley Set Theory. This explanation is sufficient for me. Thank you. – Taras Banakh May 07 '20 at 05:15
  • @AndreasBlass So, the answer to my question in that the formula $\varphi(x)$ expressing that $x$ is a natural number encoding a theorem of ZF defines a class ${x\in\omega:\varphi(x)}$ whose existence cannot be proved. Right? But also cannot be disproved. And all such $\varphi$ should be of such form, i.e., encoding some paradox, like Berry paradox? Is there some short $\varphi(x)$ of this form? Because Russell uses a very short formula $x\notin x$ for his paradox. – Taras Banakh May 07 '20 at 05:24
  • 1
    No, the set of theorems of ZF does provably exist in weak fragments of Z. The truth set for $\langle V,{\in}\rangle$ cannot be proved to exist in NBG. That is, ${\phi:\langle V,{\in}\rangle\models\phi}$. Or possibly ${\langle\phi,x\rangle:\langle V,{\in}\rangle\models\phi(x)}$ (I’m not sure which of these Wojowu meant; neither class is provable to exist in NBG). – Emil Jeřábek May 07 '20 at 05:42
  • @EmilJeřábek Writing ${\phi:\langle V,\in\rangle \models \phi}$ did you have in mind ${n\in\omega:\langle V,\in\rangle \models \phi_n}$ where $\phi_n$ is the formula whose Godel number is $n$? – Taras Banakh May 07 '20 at 06:54
  • That’s a possibility, but when working in set theory, there is no particular reason to encode formulas by integers. You can directly work with their most natural syntactic definition, e.g. as strings over some alphabet, or as trees. – Emil Jeřábek May 07 '20 at 07:06
  • @EmilJeřábek But formulas are not elements of the universe $\mathbf V$ (which is built up from the empty set). So, you should encode them as sequences of natural numbers anyway. – Taras Banakh May 07 '20 at 07:17
  • No, I do not have to encode them as sequences of natural numbers. I can encode them using their most natural syntactic definition, e.g. as strings over some alphabet, or as trees. – Emil Jeřábek May 07 '20 at 07:23
  • @EmilJeřábek But anyway, you alphabet should be a subset of the universe. Because there is no such sets as $\wedge,\vee$ or $\forall$. – Taras Banakh May 07 '20 at 07:26
  • 1
    There is no such set as $\mathbb R$ either, until I define it. So just fix any sets you like and define them to be the basic symbols of the alphabet. This choice does not matter. – Emil Jeřábek May 07 '20 at 07:31
  • @EmilJeřábek There is a subtle difference between $\mathbb R$ and say $\forall$. Defining $\mathbb R$ you defined a concrete set which has properties of the real line. But defining $\forall$ you just choose any set to replace the symbol $\forall$ which is not the set. Exactly this I had in mind writing that natural numbers can be used for encoding symbols. But anyway, both of us understand what is going on. A good question though remains: find a short formula $\varphi$ for which the existence of the class ${x:\varphi(x)}$ cannot be proved in NBG. – Taras Banakh May 07 '20 at 07:47
  • 1
    No, it is exactly the same: you define a concrete set which has the properties of the symbol $\forall$. What are the properties of the symbol $\forall$? Answer: none save that it is distinct from the symbols $\land$, $\neg$, $=$, and $\in$. – Emil Jeřábek May 07 '20 at 07:55
  • @EmilJeřábek Ok. I agree. Thank you. – Taras Banakh May 07 '20 at 07:57
  • Concerning “simple” formulas: something equivalent to the existence of the truth set for $V$ can be expressed without syntax coding as follows. We consider coding of families of classes such that $X$ is a coded element of $Y$ if $X={x:\langle u,x\rangle\in Y}$ for some set $u$. Then (using the notation from https://mathoverflow.net/a/356979) you state “there exists a coded family of classes that contains $E$ and is closed under the operations $X\setminus Y$, ${\rm dom}(X)$, $X\times V$, $X^{-1}$, and circular permutation”. However, this is not a definition of a unique class by comprehension. – Emil Jeřábek May 07 '20 at 08:28
  • @EmilJeřábek Ok. Very good. So, this defines an indexed family of classes that contains all classes of constructible hierarchy. And its existence cannot be proved because of Russell and because of the consistency of $U=L$. Right? – Taras Banakh May 07 '20 at 09:06
  • 1
    No, this has nothing to do with $L$. I'm talking about operations on classes, not on sets. It gives an indexed family of classes that's closed under definability by first-order formulas without class quantifiers. It cannot be proved to exist in NBG because it implies the existence of a conventinal satisfaction predicate for $(V,\in)$, which, as already explained, implies the consistency of ZFC, which implies the consistency of NBG, which is not provable in NBG by Gödels's incompleteness theorem. – Emil Jeřábek May 07 '20 at 09:23
  • @EmilJeřábek Writing $L$ I had in mind not only constructible sets but also constructible classes (that is the minimal inner model of NBG). The same Godel' operations (with pairing applied only to sets) can be also applied to classes and produce "constructible classes" starting with the class $\mathbf E={\langle x,y\rangle:x\in y}$. So, the existence of non-constructible class (= non-definable) is not provable in NBG. Right? – Taras Banakh May 07 '20 at 10:24
  • 1
    But NBG does prove the existence of non-definable classes, such as the global well ordering of the universe. Furthermore, the argument I outlined applies all the same to any consistent extension of NBG that proves itself relatively consistent w.r.t. ZFC, disregarding whether it proves the existence of other nondefinable classes or not. It also applies to any consistent extension of NBG by sentences that only quantify over sets, such as $V\ne L$, or $V\ne HOD$. – Emil Jeřábek May 07 '20 at 11:14
  • 1
    The well-ordering of $L$ is definable in NBG, so NBG cannot prove that any well-ordering of the universe is non-definable. – Taras Banakh May 07 '20 at 11:30
  • 1
    I think the problem in the last two comments, about provable existence of non-definable classes, arises from the lack of associativity of the English language. @EmilJeřábek meant that (NBG proves $\exists X,\psi(X)$) for a certain formula $\psi$ such that, for no formula $\delta$ does NBG prove "there is a unique $X$ satisfying $\delta$ and this $X$ also satisfies $\psi$." Taras took instead the meaning that "For every formula $\delta$, NBG proves that, if there is a unique $X$ satisfying $\delta$ then that $X$ does not satisfy $\psi$." – Andreas Blass May 07 '20 at 13:58
  • @AndreasBlass From all the discussion above I realized that my innocent question was not so innocent. I just wanted after the theorem on the existence of classes in NBG (= Theorem of comprehension) in a textbook for students to add an exercise showing that the restriction of quantifiers to run only over sets in that theorem was indeed essential. But no simple formula (like $x\notin x$ in Russell's paradox) exists for this purpose because of Morse-Kelley. All such formulas need to encode that some proof or some construction does not exist and this not so simple as $x\notin x$. – Taras Banakh May 07 '20 at 14:56
  • 1
    I agree, because I know of no easy argument for why NBG isn't the same as MK, where "easy" means avoiding metamathematical facts like Gödel's incompleteness theorems. On the other hand, if one admits such facts, then you (though probably not your students) might enjoy Emil's, Joel's, and my answers at https://mathoverflow.net/questions/87238 . – Andreas Blass May 07 '20 at 15:17

0 Answers0