In the von Neumann–Bernays–Gödel axiomatic system, the Axiom of Transposition can be simplified

Question

Looking at the von Neumann–Bernays–Gödel (NBG) axioms of Set Theory in Wikipedia I noticed that it has two axioms of permutation: one for circular permutations and another for transpositions.

On the other hand, it is well-known that the group of finitary permutations of $\omega$ is generated by transpositions only.

So my question: Can those two permutation axioms in NBG be replaced by a single axiom? (In order to minimize the number of axioms).

Or at least, can the axiom of transposition:

$\forall A\;\exists B\;\forall x\;\forall y\;\forall z\;((x,y,z)\in B\;\Leftrightarrow\;(x,z,y)\in A)$

be replaced by the simpler one:

$\forall A\;\exists B\;\forall x\;\forall y\;((x,y)\in B\;\Leftrightarrow\;(y,x)\in A)$?

---

Added in Edit. It seems that two permutation axioms of NBG can be replaced by the following their versions:

The classes $\{((x_1,x_2,x_3),(x_3,x_2,x_1)):x_1,x_2,x_3\in\mathbf V\}$ and $\{((x_1,x_2,x_3),(x_1,x_3,x_2)):x_1,x_2,x_3\in \mathbf V\}$ exist. Of course those axioms can be written via formulas, which will have only one existentional quantifier instead of $\forall\mathbf A \exists\mathbf B$ in the original axioms.

---

Added in Next Edit. Reading the paper of Kanamori about Bernays I discovered (for myself) that the

Axiom of Inversion: for every class $X$ the class $\{(y,x):(x,y)\in X\}$ exists;

and

Axiom of Associativity: for every class $X$ the class $\{((x,y),z):(x,(y,z))\in X\}$ exists;

that appeared in our discussion with Pace Nielsen, have been already included to the list of 20 axioms of Bernays in his 1931 letter to Godel who adopted Bernays' system but replaced the Axioms of Inversion and Associativity by the Axioms of Cyclic Permutation and Transposition. The Bernays axioms modified by Godel were later reproduced in the book of Mendelson who coined the name NBG and popularized this system in his classical textbook on Mathematical Logic.

Answer 1

I believe that your intended question was something along the lines of whether or not the standard axioms can be simplified or reduced. This is in the spirit of Exercise 13.4 in Jech's "Set Theory", where one shows that some of the usual Gödel operations are definable in terms of the others.

So I interpret your questions as asking: Can we replace the two permutation axioms of NBG with a single axiom of the form $$ \forall A\ \exists B\ \forall x_1\ \forall x_2\ \dotsc\ \forall x_n\ ((x_1,x_2,\dotsc, x_n)\in B \leftrightarrow (x_{\sigma(1)},x_{\sigma(2)},\dotsc, x_{\sigma(n)})\in A) $$ where $\sigma\in S_n$ is some fixed permutation on $n$ letters, and $n$ is some fixed (meta) natural number. Or, perhaps more naturally, you would want to assert the existence of the class $$ \{((x_1,x_2,\dotsc, x_n),(x_{\sigma(1)},x_{\sigma(2)},\dotsc, x_{\sigma(n)}))\ :\ x_1,x_2,\dotsc,x_n\in V\}. $$ I'm also assuming that you still want to interpret ordered $n$-tuples in the usual way, (meta-)recursively using Kuratowski's trick.

I would guess that the answer to this question is no, but this is clearly not a trivial problem. The paper Gutan and Kisielewicz - "Rings and semigroups with permutable zero products" (MSN) approaches a very similar question; in the context of that paper permutations in $S_n$ can be considered as permutations in $S_{n+1}$ in a very concrete way similar to how the permutation axioms of NBG can be lifted from 3-tuples to $n$-tuples. I imagine that the permutation $\sigma$ in the context of NBG induces the same "eventual behavior" as observed in that paper.

(Note: Your parenthetical statement, which reads "to minimize the number of axioms," is nonsense. By taking the conjunction of the finitely many axioms of NBG you now have minimized the number the axioms.)

---

In a sense, one can modify Taras's answer to his own question to get the permutation axiom down to only inversion, with another axiom handling the moving of parentheses.

Throughout, assume the axiom of inversion: For each class $X$, the class $X^{-1}=\{(y,x)\, :\, (x,y)\in X\}$ exists. The axiom of inversion will act as our sole permutation axiom.

Consider the new axiom of associativity of parentheses: For each class $X$, the class $$ X^{p}=\{((x,y),z)\, :\, (x,(y,z))\in X\} $$ exists. In a sense, this axiom will allow us to move parentheses around however we like.

Now, circular permutation $\pi_3$ follows, since $\pi_3[X]=(X^{-1})^{p}$. Conversely, associativity of parentheses follows from circular permutation since $X^{p}=\pi_3[X^{-1}]$. Also notice that the class $(\pi_3^2[X])^{-1}$ has the parentheses moved to the right instead of the left, so we can shift either direction.

The identity class function $I$ can now be defined, as done by Taras, additionally using axioms of domain, membership (the class $E$ exists), complement, and the existence of $V$.

Now, let me show that $S_1=\{(((a,b),c),((a,x),y))\,:\, a,b,c,x,y\in V\}$ exists. Taking $$ S_1'=\{(((a,b),c),(a,x))\, :\, a,b,c,x\in V\} $$ we see that $S_1^p=S_1'\times V$. So (assuming closure under products from $V$) it suffices to show that $S_1'$ exists. But $(S_1')^{p}=S_1''\times V$ where $$ S_1''=\{(((a,b),c),a)\, :\, a,b,c\in V\} $$ so it suffices to show that this class exists. Now $((S_{1}'')^{-1})^{p}=S_1'''\times V$ where $$ S_1'''=\{(a,(a,b))\, :\, a,b\in V\}. $$ Applying associativity, this new class becomes $E\times V$, which exists.

Similar computations, of rearranging coordinates, and peeling off a free coordinate, show that $S_2$ and $S_3$ exist, where $$ S_2=\{(((a,b),c),((x,y),b))\, :\, a,b,c,x,y\in V\} $$ and $$ S_3=\{(((a,b),c),((x,c),y))\, :\, a,b,c,x,y\in V\}. $$ Now $S_1\cap S_2\cap S_3$ is the class function $$ \{(((a,b),c),((a,c),b))\, :\, a,b,c\in V\}. $$ The axiom of transposition (of the last two entries in triples) now follows as in Taras's answer.

Answer 2

Since I was not satisfied with the answers and comments obtained sofar, I decided to think on this question myself.

Here is the list of class existence axioms of NBG (written in an informal form):

Axiom of Extensionality: Two classes $X,Y$ are equal if and only if $X\subseteq Y$ and $Y\subseteq X$;

Axiom of Memberships: The class $E=\{(x,y):x\in y\}$ exists;

Axiom of Intersection: For any classes $X,Y$ the class $X\cap Y$ exists;

Axiom of Complement: For any classes $X,Y$ the class $X\setminus Y$ exists;

Axiom of Domain: For any class $X$ the class $dom[X]=\{x:\exists y\;(x,y)\in X\}$ exists;

Axiom of Product by $V$: For any class $X$ the class $X\times V$ exists;

Axiom of Circular Permutation: For any class $X$ the class $\{((x,y),z):((y,z),x)\in X\}$ exists;

Axiom of Transposition: For any class $X$ the class $\{((x,y),z):((x,z),y)\in X\}$ exists.

I claim that the Axiom of Transposition can be simplified to the following more natural form:

Axiom of Inversion: For any class $X$ the class $X^{-1}=\{(x,y):(y,x)\in X\}$ exists.

More precisely, I am going to prove the following

Fact. The Gödel's Axiom of Transposition can be deduced from the Axioms of Extensionality, Membership, Complement, Domain, Product, Circlular Permutation and Inversion.

The idea is to prove that the function $f:((x,y),z))\mapsto ((x,z),y)$ exists (as a class) and then observe that for any class $X$, the class $\{((x,y),z):((x,z),y)\in X\}$ coincides with the image $f[X]$, which is equal to $dom((f\cap (X\times V))^{-1})$ so exists by application of Axioms of Product, Intersection, Inversion, and Domain. As was observed by Emil Jeřábek in his comment, the Axiom of Intersection follows from the Axiom of Complement because $X\cap Y=X\setminus(X\setminus Y)$ for any classes $X,Y$.

It remains to prove that the function $f=\{((x,y),z),((x,z),y)):x,y,z\in V\}$ exists. This will be done in a series of 10 lemmas.

Consider the functions $\pi_2:(x,y)\to(y,x)$ and $\pi_3:((x,y),z)\mapsto ((z,x),y)$ of transposition and cyclic permutation.

The Axioms of Inversion and Circular Permutation say that for any class $X$ the classes $\pi_2[X]$, $\pi_3[X]$, and $\pi_3^2[X]=\pi_3[\pi_3[X]]$ exist. (At the moment we do not claim that the functions $\pi_2$ and $\pi_3$ exist as classes).

Lemma 1. The class $S=\{(x,y):x\subseteq y\}$ exists.

Proof. Observe that $V\setminus S=dom(A\cap B)$ where $A=\{((x,y),z):z\in x\}$ and $B=\{((x,y),z):z\notin y\}$.

Observe that $\pi_3[A]=\{((z,x),y):z\in x\}=E\times V$ and hence $\pi_3[A]$ exists by the Axioms of Memberships and Product by $V$. Then $A$ exists by the Axiom of Circular Permutation.

Next, the class $\pi^2_3[B]=\{((y,z),x):z\notin y\}=(\pi_2[V\setminus E])\times V$ exists by the Axioms of Memberships, Complement, Inversion and Product by $V$. Applying the Axiom of Circular Permutation, we obtain that the class $B$ exists. Then $A\cap B$ exists by Axiom of Intersection, $V\setminus S=dom(A\cap B)$ exists by Axiom of Domain and $S$ exists by Axiom of Complement. $\quad\square$

Lemma 2. The class $I=\{(x,y):x=y\}$ describing the identity function $I:x\mapsto x$, exists.

Proof. By Lemma 1, the class $S=\{(x,y):x\subseteq y\}$ exists. Since $I=S\cap\pi_2[S]$ (by the Axiom of Extensionality), the class $I$ exists by the Axioms of Inversion and Intersection. $\quad\square$

The short proofs of the following five lemmas were suggested by Pace Nielsen in his comments below.

Lemma 3. The class $p_1=\{((a,b),a):a,b\in V\}$ describing the function $p_1:(a,b)\mapsto a$ exists.

Proof. Observe that $\pi_3[p_1]=\{((a,a),b):a,b\in V\}=I\times V$, so the classes $\pi_3[p_1]$ and $p_1=\pi_3^2[\pi_3[p_1]]$ exist. $\quad\square$

Lemma 4. The class $p_2=\{((a,b),b):a,b\in V\}$ describing the function $p_2:(a,b)\mapsto b$ exists.

Proof. Observe that $\pi^2_3[p_2]=\{((b,b),a):a,b\in V\}=I\times V$, so the class $p_2$ exists. $\quad\square$

Lemma 5. The class $pr_1=\{(((a,b),c),a):a,b,c\in V\}$ describing the function $pr_1:((a,b),c)\mapsto a$ exists.

Proof. Observe that $\pi_3[pr_1]=\{((a,(a,b)),c):a,b,c\in V\}=\pi_2[p_1]\times V$ and hence the classes $\pi_3[pr_1]$ and $pr_1$ exist by Lemma 4 and Axioms of Inversion, Product, and Circular Permutation. $\quad\square$

Lemma 6. The class $pr_2=\{(((a,b),c),b):a,b,c\in V\}$ describing the function $pr_2:((a,b),c)\mapsto b$ exists.

Proof. Observe that $\pi_3[pr_2]=\{((b,(a,b)),c):a,b,c\in V\}=\pi_2[p_2]\times V$ and hence the classes $\pi_3[pr_2]$ exist by Lemma 4 and Axioms of Inversion, Product, and Circular Permutation. $\quad\square$

Lemma 7. The class $pr_3=\{(((a,b),c),c):a,b,c\in V\}$ describing the function $pr_1:((a,b),c)\mapsto c$ exists.

Proof. Observe that $\pi^{-1}_3[pr_3]=\{((c,c),(a,b)):a,b,c\in V\}=I\times(V\times V)$ and hence the class $pr_3$ exists by Lemma 2 and the Axiom of Product by $V$. $\quad\square$

Lemma 8. For any functions $F,G$ the class $\{x\in dom[F]\cap dom[G]:F(x)=G(x)\}$ exists.

Proof. Observe that $\{x\in dom[F]\cap dom[G]:F(x)=G(x)\}=dom[F\cap G]$ and apply the Axioms of Intersection and Domain. $\quad\square$

Lemma 9. For any functions $F,G$ the function $F\circ G=\{(x,z):\exists y\;((x,y)\in G\;\wedge\;(y,z)\in F)\}$ exists.

Proof. Observe that $F\circ G=dom[A_1\cap A_2]$ where $A_1=\{((x,z),y):(x,y)\in G\}$ and $A_2=\{(x,z,y):(y,z)\in F\}$.

The class $\pi_3[A_1]=\{((y,x),z):(x,y)\in G\}=G^{-1}\times V$ exists by the Axioms of Inversion and Product.

The class $\pi^2_3[A_2]=\{((z,y),x):(y,z)\in F\}=F^{-1}\times V$ exists by the Axioms of Inversion and Product.

Then the classes $A_1$ and $A_2$ exist and so does the function $F\circ G$. $\quad\square$

Lemma 10. The function $f:((x,y),z)\mapsto ((x,z),y)$ exists.

Proof. Observe that \begin{multline*} f=\{(a,b):a,b\in V^3,\;pr_1(a)=pr_1(b), \;pr_2(a)=pr_3(b),\;pr_3(a)=pr_2(b)\}=\\ \{x\in V^3{\times}V^3:pr_1{\circ}p_1(x)=pr_1{\circ}p_2(x),\; pr_2{\circ}p_1(x)=pr_3{\circ} p_2(x),\;pr_3{\circ} p_1(x)=pr_2{\circ} p_2(x)\}\end{multline*} and apply Lemmas 3--9. $\quad\square$

---

Similar arguments can be used to simplify the standard list of Godel's operations (see Definition 13.6 in the book "Set Theory" of Jech):

$G_1(X,Y)=\{X,Y\}$;

$G_2(X,Y)=X\times Y$;

$G_3(X,Y)=\{(x,y)\in X\times Y:x\in y\}$;

$G_4(X,Y)=X\setminus Y$;

$G_5(X,Y)=X\cap Y$;

$G_6(X)=\bigcup X$;

$G_7(X)=dom(X)$;

$G_8(X)=X^{-1}=\{(y,x):(x,y)\in X\}$;

$G_9(X)=\{(u,v,w):(u,w,v)\in X\}$;

$G_{10}(X)=\{(u,v,w):(v,w,u)\in X\}$.

By De Morgan laws, the operation $G_5$ is a composition of the operations $G_1,G_4,G_6$. By Exercise 13.4 in Jech's book, the operation $G_8$ is a composition of the operations $G_2,G_7,G_9,G_{10}$. More precisely, $G_8(X)=dom(G_{10}(G_{10}(G_9(G_{10}(X\times X)))))$. What we already know is that the operation $G_9$ is a composition of the other Godel's operations, so it can be removed (together with $G_5$ from the list, which will reduce to 8 axioms (the same number as was originally in Godel).

It would be interesting to write down the formula expressing the operation $G_9$ via other Godel's operations.