Timeline for A contradiction in the Set Theory of von Neumann–Bernays–Gödel?
Current License: CC BY-SA 4.0
53 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 11, 2023 at 16:35 | comment | added | Noah Schweber | Due to several inappropriate "answers," I've gone ahead and protected this question; feel free to un-protect if that was an inappropriate move here. | |
| Apr 11, 2023 at 16:34 | history | protected | Noah Schweber | ||
| Apr 11, 2023 at 4:08 | vote | accept | Taras Banakh | ||
| Apr 11, 2023 at 3:09 | vote | accept | Taras Banakh | ||
| Apr 11, 2023 at 3:15 | |||||
| Apr 11, 2023 at 1:56 | answer | added | Ali Enayat | timeline score: 21 | |
| Apr 10, 2023 at 18:16 | comment | added | Ali Enayat | @JoelDavidHamkins Thanks for the clarification Joel, as I suspected you had Kelley-Morse in mind. | |
| Apr 10, 2023 at 18:09 | comment | added | Joel David Hamkins | Meanwhile, my comments about the non-expressivity of definability in $\omega$-nonstandard models works in Kelley-Morse, where the standard cut cannot be definable even in the second-order language, and this shows that there is no definition of (meta-theoretic) definability that works in all NGB models. (But also, the nontrivial elementary extensions of pointwise definable model of NGB also shows this.) | |
| Apr 10, 2023 at 17:59 | comment | added | Joel David Hamkins | My comment was wrong, since as you mention we can have a second-order definition of the standard cut. (And yes, I was referring to first-order definability of the classes.) I was emphasizing the distinction between the internal representation of definability (as Taras is doing) and the external model-theoretic notion of definability. In the parameter-free case, these are not the same. | |
| Apr 10, 2023 at 17:17 | comment | added | Ali Enayat | @JoelDavidHamkins Hi Joel, I was confused by your statement "An ω-nonstandard model of NGB can never have a expressible account of actual definibility", since in spartan models (whether ω-nonstandard or ω-standard) the truth predicate for the ambient model of ZF is definable. Perhaps by "definability" you meant definability in the model of NBG, not definability in the ZF-model of the model of NBG? | |
| Apr 10, 2023 at 17:15 | comment | added | Joel David Hamkins | But I understand your point now---it is not a contradiction to define the standard cut, if the definition is second order. | |
| Apr 10, 2023 at 14:37 | comment | added | Joel David Hamkins | @AliEnayat My point was that if (contrary to fact) the notion of "definable" was itself expressible in an $\omega$-nonstandard model, then one could define the standard cut, and this doesn't require the spartan assumption. A number $n$ is standard iff there is a definable class X and an (internal) $\Sigma_n$ truth predicate T showing that X is definable at that level, but it is not definable at any earlier level. | |
| Apr 10, 2023 at 14:30 | comment | added | Joel David Hamkins | @TarasBanakh Yes, that principle arises in the mutual interpretability result between KM and ZFC-+the largest cardinal is inaccessible. An intermediate step attains the class collection axiom CC by going to those classes that are (internally) relatively constructible. | |
| Apr 10, 2023 at 13:57 | comment | added | Taras Banakh | @JoelDavidHamkins The internal definability of classes can be helpful because it allows introducing a well-defined axiom, which is stronger than $V=L$: every class is L-definable, i.e., can be constructed (jn this internal sense) from L and elements of L. Under this axiom not only does the class of sets $L$ admit a well-order but also the "family" of all classes can be well-ordered in a suitable sense (by some well-defined formula of the class theory). Do you know if anybody has thought about such a strong Class Constructibility Axiom? | |
| Apr 10, 2023 at 0:45 | comment | added | Ali Enayat | @JoelDavidHamkins In relation to your latest comment: An $\omega$-nonstandard spartan model of NBG, i.e., a model of NBG in which the collection of classes coincides with the collection of the parametrically definable subsets of the ambient model of ZF, the standard cut is indeed definable, see (*) on page 22 of the following (preprint of) a joint paper of ours: arxiv.org/pdf/1610.02729.pdf (as pointed out in the paper, the basic idea goes back to a 1950 paper of Mostowski). Indeed in such models the satisfaction predicate for the ambient model of ZF is definable. | |
| Apr 9, 2023 at 22:47 | comment | added | Joel David Hamkins | Yes, I agree with that. | |
| Apr 9, 2023 at 18:46 | comment | added | Taras Banakh | @JoelDavidHamkins Nonetheless that internal formula agrees with the "standard" definability in the sense that definable classes in the standard sense are definable in the internal sense, but not vice versa. This is at least something (I mean better than nothing). | |
| Apr 9, 2023 at 18:25 | comment | added | Joel David Hamkins | An $\omega$-nonstandard model of NGB can never have a expressible account of actual definibility, since then it could define the standard cut in $\omega$ as consisting of those $n$ for which there is something definable by a term of size $n$. But one cannot define the standard cut in $\omega$, since there is no least nonstandard element. | |
| Apr 9, 2023 at 18:04 | comment | added | Joel David Hamkins | No, that doesn't define definability, since the model might have nonstandard $n$. This is the internal notion of definability, and a nonstandard model can think something is definable in your sense, without it actually being definable. For example, take a pointwise definable model of NGB, where every class is definable without parameters, and then take an elementary extension of it. The new extension objects cannot be actually definable, but by elementary they will think that every class is definable in your sense. | |
| Apr 9, 2023 at 10:34 | comment | added | Taras Banakh | @JoelDavidHamkins In the above formula $Y_t=\{y\in\mathbf V:\langle t,y\rangle\in Y\}$ for any set $t$ and class $Y$. So, definability can be expressed in the language of Class Theory. The only problem that the existence of a single class (representing all definable classes) cannot be proved because of the absence of the recursion Theorem for constructing sequence of proper classes. | |
| Apr 9, 2023 at 9:55 | comment | added | Taras Banakh | @JoelDavidHamkins Thank you for the links to your papers. Thinking on definability (or constructibility) of classes, I came to the conclusion that it is expressible in the language of Class Theory: a class $X$ is definable if $\exists n\in\omega \;\exists \lambda\in 8^{2^{<n}} \exists Y (Y\subseteq 2^{\le n}\times\mathbf V\wedge Y_\emptyset=X\wedge (\forall t\in 2^n X_t=\mathbf V)\wedge (\forall t\in 2^{<n} X_t=G_{\lambda(t)}(X_{t{\hat\;}0},X_{t{\hat\;}1}))$. | |
| Apr 8, 2023 at 22:38 | comment | added | Joel David Hamkins | Meanwhile, it is a theorem of mine with David Linetsky and Jonas Reitz that every countable model of GBC has an extension in which every class is definable like that without parameters. See arxiv.org/abs/1105.4597. | |
| Apr 8, 2023 at 22:35 | comment | added | Joel David Hamkins | I would call those the first-order definable classes without parameters. The property of being such a class, however, is not expressible, even in the second-order language of GBC, and for this reason, the notion can be deemed purely meta-theoretic rather than a legitmate concept that is part of the object theory. | |
| Apr 8, 2023 at 22:11 | comment | added | Taras Banakh | @JoelDavidHamkins Dear Joel David, thank you for the comment. Now (with help of Emil Jerabek ) I have understood in which place I made a gap. Nonetheless, I would like to use the notion of a class that can be defined as $\{x:\varphi(x,\mathbf V)\}$ where $\varphi(x,v)$ is a formula with two free variables $x,v$ and all quantifiers running over sets. Do you know of any commonly accepted name for such definable classes. There are only countably many of them (in the sense of metatheory), but they include quite important classes like the class $\mathbf{On}$ of all ordinals or the ordinal $\omega$. | |
| Apr 8, 2023 at 19:43 | comment | added | Joel David Hamkins | @TarasBanakh To answer your queston, the issue for me would be the sense of "finite", whether you mean finite in the meta theory or the internal notion of finite, which might after all be nonstandard. If you use the metatheoretic notion of finite, then you will get definable classes. But if you intend some internal process of iterating, then you will get nonstandard versions of being definable (when indeed the classes exist), and they won't necessarily agree with being externally definable. | |
| Apr 8, 2023 at 16:45 | comment | added | Taras Banakh | @TimothyChow Indeed, good story, very appropriate to my today's situation. Thank you for the suggestion. Now my daughter has found me the file in Internet and I will read it. | |
| Apr 8, 2023 at 16:05 | comment | added | Timothy Chow | @TarasBanakh You may enjoy the short story "Division By Zero" by Ted Chiang (reprinted in the anthology Stories of Your Life and Others). | |
| Apr 8, 2023 at 15:55 | comment | added | Taras Banakh | @TimothyChow This was a joke, of course! When I was a student I was said about Godel's Theorem on the impossibility of proving the consistency of Mathematics, so at each moment someone can find a contradiction, after which all math will immediately lose its value. On the other hand, the (Naive) Set Theory indeed was is a danger because of Russell's Paradox. | |
| Apr 8, 2023 at 15:43 | comment | added | Timothy Chow | @TarasBanakh "NBG is saved!" To be honest, I don't think it was ever in any danger... :-) | |
| Apr 8, 2023 at 15:24 | comment | added | Taras Banakh | @EmilJeřábek This question was important for me because I started to rewrite the chapter on Godel's constructible universe in my book (from arxiv) and encountered this problem, which stopped the process. Now I can proceed further. Thank you for the help. | |
| Apr 8, 2023 at 15:20 | comment | added | Taras Banakh | @JoelDavidHamkins Is there any standard name for classes which are constructible by finitely many basic operations from the universal class? | |
| Apr 8, 2023 at 15:19 | comment | added | Emil Jeřábek | You're welcome. Sorry it took me several iterations to read and understand the question properly. | |
| Apr 8, 2023 at 14:57 | comment | added | Taras Banakh | @EmilJeřábek Thank you very much for your comment, which resolves my question and also explains why we cannot replace this particular external recursive definition of a sequence of proper classes by the internal one. So, the NBG is saved! Very good :) | |
| Apr 8, 2023 at 14:54 | comment | added | Joel David Hamkins | The principle of recursion over classes is known as ETR (elementary transfinite recursion) and it is not provable in GBC. For example, the first-order truth predicate is defined by such a recursion of length $\omega$, and there are models of GBC in which every class is first-order definable, but by Tarski's theorem truth is never itself definable. For some further analysis of ETR, see arxiv.org/abs/1707.03700. | |
| Apr 8, 2023 at 14:31 | review | Close votes | |||
| Apr 12, 2023 at 13:22 | |||||
| Apr 8, 2023 at 14:24 | comment | added | Emil Jeřábek | "there exists an ordinal $β$ such that $V_α∩G_λ(V)=V_α∩G_λ(V_γ)$ for all ordinals $γ≥β$" is not true in general. For example, take $\lambda$ such that $G_\lambda(X)=\{x\in X:\forall y\in X\,\exists z\in X\,y\in z\}$ (which is either $\emptyset$ or $X$) for all $X$. Then $G_\lambda(V)=V$, but $G_\lambda(V_\gamma)=\emptyset$ whenever $\gamma$ is a successor ordinal. It is only true that for each $\alpha$ and $\lambda$, there are arbitrarily large $\gamma$ such that $V_\alpha\cap G_\lambda(V)=V_\alpha\cap G_\lambda(V_\gamma)$. | |
| Apr 8, 2023 at 14:13 | history | edited | LSpice | CC BY-SA 4.0 |
Tidying
|
| Apr 8, 2023 at 13:37 | comment | added | Taras Banakh | @EmilJeřábek When we make recursive construction of sets $V_\alpha\cap G_\lambda(V_\beta)$ both meaning (internal and external) produce the same elements of the model for "standard" $\lambda$'s. Taking limits of those sets $V_\alpha\cap G_\lambda(V_\beta)$ produce a desirable indexed class $(C_\lambda)_{\lambda\in T}$ consisting of proper classes such that $C_\lambda=G_\lambda(V)$ for "standard" $\lambda$. | |
| Apr 8, 2023 at 13:36 | comment | added | Taras Banakh | @EmilJeřábek This "No" concerned my first impression that your comment concerned impossibility of recursion over proper classes (in indexes) and after writing my comment I realized that you had in mind recursion over counatble sets but with purpose of constructing proper classes. When I wrote $G_\lambda(X)$ is defined by the recursive formula, I have in mind that $\lambda$ is "standard" 7-labeled tree and recursion is understood from the ambient universe where the model lives. | |
| Apr 8, 2023 at 13:19 | comment | added | Emil Jeřábek | I do not know why you write "No, the Theorem of Recursion does extend ..." when your comment perfectly agrees with what I wrote. This is the usual recursion theorem for defining sequences of sets. But when you write "consider the class $G_λ(X)$ defined by the recursive formula ...", you are attempting to define a sequence of proper classes by recursion over $2^{<\omega}$. You cannot do that in NBG. | |
| Apr 8, 2023 at 12:48 | comment | added | Taras Banakh | @EmilJeřábek Concerning constructing a sequence of proper classes by recursion, you are right: I cannot construct such a sequence using the Recursion Theorem. That is why I first construct the indexed sequence of sets $(C_{\alpha,\beta})_{\alpha,\beta\in\mathbf{On}}$, which allow me to define a "legal" indexed family $C=(C_\lambda)_{\lambda\in T}$ of proper classes such that $C_\lambda=G_\lambda(\mathbf V)$ for a "standard" $\lambda$, and thus obtain a contradiction of NBG. | |
| Apr 8, 2023 at 12:40 | comment | added | Taras Banakh | @EmilJeřábek In this general version of Recursion Theorem, $F,R,G$ are classes, not necessarily sets. So, a recursion over the class of ordinals is legal in NBG and is expressed by a formula with quantifiers running over sets, so the function $G$ is constructible whenever $F$ and $R$ are constructible. For the proof of this general version of Recursion Theorem, see Theorem 22.1 in this book: arxiv.org/pdf/2006.01613.pdf | |
| Apr 8, 2023 at 12:36 | comment | added | Taras Banakh | @EmilJeřábek No, the Theorem of Recursion does extend to any well-founded classes. More precisely, for any class $X$, well-founded set-like relation $R$ and any function $F:X\times \mathbf V\to\mathbf V$ there exists a unique function $G:X\to\mathbf V$ such that $G(x)=F(x,G{\restriction}_{R^-(x)}$ for every $x\in X$, where $R^-(x)=\{z\in\mathbf V:\langle z,x\rangle\in R\}\setminus\{x\}$. The proof of this version of the Recursion Theorem is standard: the function $G$ is the union of the class of partial functions that satisfy the recursive definition of $G$. | |
| Apr 8, 2023 at 12:30 | comment | added | Emil Jeřábek | Actually, even before that: recursion only allows you to construct a sequence of sets. You cannot construct a sequence of proper classes by recursion; NBG cannot prove that even for recursion over $\omega$, let alone larger ordinals. Which also testifies to the fact that, even in stronger set theories where the sequence provably exists, it is not definable by a formula without class quantifiers, thus there is no reason for it to be constructible in your sense. | |
| Apr 8, 2023 at 12:20 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 305 characters in body
|
| Apr 8, 2023 at 11:47 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 31 characters in body
|
| Apr 8, 2023 at 11:29 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 180 characters in body
|
| Apr 8, 2023 at 11:20 | comment | added | Taras Banakh | @EmilJeřábek I constuct those classes $(C_{\alpha,\beta})_{\alpha,\beta\in \mathbf{On}}$ as one constructible subclass of $\mathbf{On}\times\mathbf{\mathbf On}\times T\times\mathbf V$ and the latter class does not have any parameter besides $\mathbf V$. And the same with the indexed family $(C_\alpha)_{\alpha\in\mathbf{On}}$: it is just a constructible subclass of $\mathbf{\mathbf On}\times T\times\mathbf V$. Now I will correct that place in my argument. Thank you for the remark. | |
| Apr 8, 2023 at 11:15 | comment | added | Emil Jeřábek | Since your definition of constructible classes does not allow arbitrary sets as parameters, you cannot construct a constructible class $C_{α,β}⊆T×V$ such that ... for every ordinals $\alpha,\beta$. This would require the use of $\alpha$ and $\beta$ as parameters. | |
| Apr 8, 2023 at 11:04 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body
|
| Apr 8, 2023 at 10:58 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body
|
| Apr 8, 2023 at 10:52 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body; edited title
|
| Apr 8, 2023 at 10:47 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body; edited title
|
| Apr 8, 2023 at 10:41 | history | asked | Taras Banakh | CC BY-SA 4.0 |