16
$\begingroup$

Thinking on the theory NBG (of von Neumann–Bernays–Gödel) I arrived at the conclusion that it is contradictory using an argument resembling Russell's Paradox. I am sure that I made a mistake in my arguments (because NBG cannot be contradictory, as all mathematicians believe), but I can not find the exact place where the error happened.

The theory NBG is finitely axiomatizable theory whose undefined notions are "class" and "element". A class is called a set if it is an element of some other class. The axioms of NBG imply the existence of the universal class $\mathbf V$ containing all sets as elements. Axioms of NBG allow to make the following six basic operations over classes $X$, $Y$:

  • The difference: $X\setminus Y=\{z:z\in X\wedge z\notin Y\}$;

  • The Cartesian product: $X\times Y=\{\langle x,y\rangle:x\in X\wedge y\in Y\}$;

  • The transposition: $X^{-1}=\{\langle y,x\rangle:\langle x,y\rangle\in X\}$;

  • The cyclic permutation: $X^\circlearrowright=\{\langle\langle z,x\rangle,y\rangle:\langle\langle x,y\rangle,z\rangle\in X\}$;

  • The domain: $\DeclareMathOperator\dom{dom}\dom[X]=\{x:\exists y\;\langle x,y\rangle\in X\}$.

  • The membership: $X_\in=\{\langle x,y\rangle\in X:x\in y\}$.

A class $X$ is called constructible if it can be constructed from the universal class $\mathbf V$ applying finitely many basic operations over classes. For example, the empty set is constructible because $\emptyset=\mathbf V\setminus\mathbf V$. Gödel's Class Existence Theorem implies that a class is constructible if it can be described by a formula with a unique parameter $\mathbf V$ and all quantifiers running over elements of $\mathbf V$. It is clear that there are only countably many constructible classes.

All possible compositions of basic operations can be effectively enumerated by the set $T=\bigcup_{n\in\omega}7^{2^{<n}}$ of 7-labeled full binary trees of finite height.

The idea of this enumeration is as follows. First, enumerate the basic operations over classes $X$, $Y$:

\begin{align*} & G_0(X,Y):=X, \\ & G_1(X,Y):=X\setminus Y, \\ & G_2(X,Y)=X\times Y, \\ & G_3(X,Y):=X^{-1}, \\ & G_4(X,Y)=X^\circlearrowright \\ & G_5(X,Y):=\dom[X], \\ & G_6(X,Y)=X_\in. \end{align*}

Let $2^{<\omega}=\bigcup_{n\in\omega}2^n$ be the full binary tree and for every $n\in\omega$, let $2^{<n}=\bigcup_{k\in n}2^k$ be the full binary tree of height $n$. For every $k\in\{0,1\}$, consider the function $\vec k:2^{<\omega}\to 2^{<\omega}$, $\vec k:f\mapsto \{\langle 0,k\rangle:\langle i+1,v\rangle:\langle i,v\rangle\in f\}$ and observe that $\vec k[2^n]\subseteq 2^{n+1}$.

For every $n\in\omega$, function $\lambda:2^{<n}\to 7=\{0,1,2,\dotsc,6\}$, and class $X$, consider the class $G_\lambda(X)$ defined by the recursive formula $G_\lambda(X)=X$ if $n=0$ and $G_\lambda(X)=G_{\lambda(0)}(G_{\lambda\circ \vec 0}(X),G_{\lambda\circ \vec 1}(X))$ if $n>0$. So, $G_\lambda$ represents a composition of the basic operations taken in the order suggested by the labels at the vertices of the binary tree $2^{<n}$.

A class $X$ is constructible if and only if $X=G_\lambda(\mathbf V)$ for some $n\in\omega^\star$ and $\lambda\in 7^{2^{<n}}$. Here $\omega^\star$ is the set of "standard" numbers in the model of NBG. So, the constructibility of classes is an external notion to the model of NBG. Here we assume that NBG is not contradictory and fix some model of NBG. This model contains an element $\omega$ whose elements are natural numbers in the model. Among those natural numbers, there are standard natural numbers, which are successors of the empty set (from the viewpoint of the universe in which the model of NBG lives).

Let $T=\bigcup_{n\in\omega}7^{2^{<n}}$ be the set of all 7-labeled binary trees of finite height. This set is a countable constructible subset of the model.

Claim. There exists a constructible class $C\subseteq T\times\mathbf V$ such that for every standard number $n\in\omega^\star$ and every 7-labeled tree $\lambda\in 7^{2^{<n}}$, the class $C_\lambda=\{x\in \mathbf V:\langle\lambda,x\rangle\in C\}$ coincides with the class $G_\lambda(\mathbf V)$.

Assume for a moment that the Claim is proved. The constructibility of the class $C$ implies the constructibility of the class $\Lambda=\{\lambda\in T:\langle\lambda,\lambda\rangle\notin C\}$. Then there exists a standard number $n\in\omega^\star\subseteq\omega$ and a 7-labeled tree $\lambda\in 7^{2^{<n}}$ such that $\Lambda=C_\lambda:=\{x\in\mathbf V:\langle\lambda,x\rangle\in C\}$. Now we have a paradox of Russell's type:

  • if $\lambda\in\Lambda$, then $\lambda\in C_\lambda$ and hence $\langle\lambda,\lambda\rangle\in C$ and $\lambda\notin\Lambda$;

  • if $\lambda\notin\Lambda$, then $\langle\lambda,\lambda\rangle\in C$ and hence $\lambda\in C_\lambda=\Lambda$.

In both cases, we obtain a contradiction.

Proof of Claim. Let $\mathbf{On}$ be the class of ordinals and $(V_\alpha)_{\alpha\in\mathbf{On}}$ be the von Neumann hierarchy, which can be identified with the class $\bigcup_{\alpha\in\mathbf{On}}\{\alpha\}\times V_\alpha$. It can be shown that both these classes are constructible (because they can be defined by formulas in which quantifiers run over elements of the universal class $\mathbf V$). It can be shown that for every standard number $n\in\omega^\star\subseteq\omega$, every 7-labeled tree $\lambda\in 7^{2^{<n}}$ and every ordinal $\alpha$ there exists an ordinal $\beta$ such that $V_\alpha\cap G_\lambda(\mathbf V)=V_\alpha\cap G_\lambda(V_\gamma)$ for all ordinals $\gamma\ge\beta$.

Applying the Theorem of Recursion, for every ordinals $\alpha,\beta$ one can construct a class $C_{\alpha,\beta}\subseteq T\times\mathbf V$ such that for every standard number $n\in\omega^\star\subseteq\omega$ and 7-labeled tree $\lambda\in 7^{2^{<n}}$ we have $\{x\in \mathbf V:\langle \lambda,x\rangle\in C_{\alpha,\beta}\}=V_\alpha\cap C_\lambda(V_\beta)\}$. Moreover, the recursive definition of the indexed sequence $(C_{\alpha,\beta})_{\alpha,\beta\in\mathbf{On}}$ shows that it is constructible as a subclass of $\mathbf{On}\times\mathbf{On}\times T\times\mathbf V$ (because it is defined by a formula whose quantifiers run over elements of the universal set). For every ordinal $\alpha$ consider the class $$C_\alpha=\{\langle\lambda,x\rangle\in T\times\mathbf V:\exists \beta\in\mathbf{On}\;\forall \gamma\in \mathbf{On}\; (\beta\le \gamma\to \langle \lambda,x\rangle \in C_{\alpha,\gamma})\}.$$ The constructibility of the family $(C_{\alpha,\beta})_{\alpha,\beta\in \mathbf{On}}$ implies the constructibility of the set indexed family $(C_\alpha)_{\alpha\in\mathbf {On}}$ (identified with the subclass $\bigcup_{\alpha\in\mathbf{On}}\{\alpha\}\times C_\alpha$ of the class $\mathbf{On}\times (T\times\mathbf V)$. The constructibility of the indexed family $(C_\alpha)_{\alpha\in\mathbf{On}}$ implies the constructibility of the class $$C=\{\langle \lambda,x\rangle\in T\times\mathbf V:\exists \alpha\in\mathbf{On}\;\langle\lambda,x\rangle\in C_\alpha\},$$ which has the property, required in the Claim. $\square$

So

Question. In which place does this argument proving the inconsistency of NBG contain a gap?

$\endgroup$
39
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 8, 2023 at 11:15
  • 6
    $\begingroup$ 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. $\endgroup$ Apr 8, 2023 at 12:30
  • 10
    $\begingroup$ "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)$. $\endgroup$ Apr 8, 2023 at 14:24
  • 7
    $\begingroup$ 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. $\endgroup$ Apr 8, 2023 at 14:54
  • 3
    $\begingroup$ @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. $\endgroup$
    – Ali Enayat
    Apr 10, 2023 at 0:45

1 Answer 1

21
$\begingroup$

The comments to the question, especially those by Emil Jeřábek and Joel Hamkins make it clear that the proposed inconsistency proof breaks down because the recursive construction carried out in the proposed proof of inconsistency cannot be implemented in NBG.

As pointed out first by Mostowski in his 1950 paper Some impredicative definitions in set theory, when it comes to recursive constructions, the problem with NBG (as opposed to the much stronger system KM of Kelley and Morse) is that, the scheme of induction over the natural numbers is not provable in NBG. I would like to outline Mostowski's reasoning here since it sheds light on why the recursion proposed by Taras Banakh need not succeed in an arbitrary model of NBG.

The main idea is that within NBG we can describe, via a second order definition (i.e., by quantifying over classes of NBG) a subset $I$ of the ambient natural numbers of the NBG model such that NBG can prove that $I$ is closed under predecessors, contains $0$, and is closed under successors, but NBG cannot prove that $I$ coincides with the set $\omega$ of natural numbers (in the sense of NBG).

The basic idea is devilishly simple: let $I$ consist of numbers $k$ such that there is a class $S$ (in the ambient model of NBG) such that $S$ is a $k$-satisfaction class, i.e., $S$ satisfies Tarski's compositional clauses for a satisfaction predicate for the structure $(\mathbf{V},\in)$ (in the sense of the ambient NBG model) for formulae of depth at least $k$; here the depth of a formula $\varphi$ is the length of the longest path in the "parsing tree" of $\varphi$ (also known as the "formation tree" or "syntactic tree" of $\varphi$).

With $I$ defined as above, we can specify a unary formula $\sigma(x)$ in the language of NBG such that, provably in NBG, $\sigma(x)$ satisfies Tarski's compositional clauses for all set-theoretical formula whose depth (as defined above) lies in $I$. In particular, $\sigma(x)$ correctly decides the truth of all set-theoretical sentences in the ambient ZF model of NBG since for each standard natural number $k$, NBG can prove that $k \in I$.

$\sigma(x)$ expresses: $x$ is a set-theoretical formula (with parameters) $\varphi(m_1,...,m_s)$, $\mathrm{depth}(\varphi) \in I$, and there is a class $S$ (in the sense of NBG) such that $\varphi(m_1,...,m_s) \in S$ and $S$ is a $k$-satisfaction predicate for $k=\mathrm{depth}(\varphi)$. Note that, provably in NBG, any two $k$-satisfaction classes agree on the truth-evaluation of formulae of depth at most $k$.

Mostowski's construction unveiled a rather intriguing phenomena: there can be a theory $T^+$ [in this case NBG] which possesses a truth-predicate for a theory $T$ [in this case ZF], and yet the formal consistency of $T$ is unprovable in $T^+$ (due to the lack of sufficient formal induction in $U$ [because Con(ZF) is not provable in GB, since GB is set-theoretically conservative over ZF, and of course ZF cannot prove Con(ZF)].

With the above definition of $\sigma$ at our disposal, we can write a formula $\theta$ in the language of NBG that asserts that every class is definable in the sense of $\sigma$ in the following sense:

Theorem. If $(\mathcal{M},\frak{X})$ is a model of NBG, where $\mathcal{M}=(M,E)$ is a model of ZF, and $\frak{X}$ is a subset of the powerset of $M$ that specifies the classes of the model, and $M$ is $\omega$-standard, then $(\mathcal{M},\frak{X}) \models \theta$ iff $(\mathcal{M},\frak{X})$ is spartan, i.e., $\frak{X}$ consists of subsets of $M$ that are parametrically definable in $\mathcal{M}$.

N.B. In the above, the $\omega$-standardness hypothesis is only used in the left-to-right direction, in other words, $\theta$ holds in every spartan model of NBG.

Besides the Mostowski paper referenced above, readers interested in the history of this subject might want to also examine John Myhill's 1952 paper The hypothesis that all classes are nameable.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. What about the existence of definable subsets of finite sets (see my question mathoverflow.net/q/444551/61536). Can this fact be proved in NBG or also similar problems arise? $\endgroup$ Apr 11, 2023 at 3:45
  • $\begingroup$ @TarasBanakh Thanks for the correction. I will think about your other MO question and will report back if I have any success. $\endgroup$
    – Ali Enayat
    Apr 11, 2023 at 3:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.