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](https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory) 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](https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory) 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?
> 
> 
> 



A contradiction in the Set Theory of von Neumann–Bernays–Gödel?
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](https://eudml.org/doc/213208), 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.](https://www.pnas.org/doi/epdf/10.1073/pnas.38.11.979)


