2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ How many generators do you need for $S_3$? $\endgroup$ – Asaf Karagila Apr 8 at 18:17
  • 4
    $\begingroup$ @TarasBanakh I think Asaf's point is that the transposition axiom only includes one transposition (swapping second and third coordinates), and more generally a "one permutation per axiom" set-up will require two axioms. (And if we drop that setup, then we can just take the conjunction of the axioms.) $\endgroup$ – Noah Schweber Apr 8 at 18:29
  • 4
    $\begingroup$ Taras, any finite number of axioms can be replaced by one. Just take the conjunction... $\endgroup$ – Asaf Karagila Apr 8 at 18:32
  • 5
    $\begingroup$ You need infinitely many transpositions to generate the group of finitary permutations of $\omega$, hence it is a minor miracle that you can make do with only finitely many axioms at all; it certainly does not give a reason to think that you can reduce the two premutation axioms to one. $\endgroup$ – Emil Jeřábek Apr 8 at 18:34
  • 4
    $\begingroup$ Taras, over-optimisation can be a bad thing. Redundancies exist to make things easier. We include Replacement and Separation as axioms in ZFC because it's easier, and we don't have to go through the proof that Replacement implies Separation. Likewise for Pairing, or Empty Set. $\endgroup$ – Asaf Karagila Apr 9 at 8:35
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. Ok, let me ask a concrete question: can the axiom of transposition be simplied to the form: $\forall A\exists B\;\forall x\forall y \;((x,y)\in A\Leftrightarrow (y,x)\in B)$? As I understood the axiom of cyclic permutation composed with the axiom of domain is necessary for the proof of the existence of projections on each coordinate. And the axiom of transposition makes the main job generating all the permutations. Right? $\endgroup$ – Taras Banakh Apr 8 at 20:38
  • 2
    $\begingroup$ @TarasBanakh You might be interested to know that Godel's original set of operations has three different permutation rules. en.wikipedia.org/wiki/G%C3%B6del_operation $\endgroup$ – Pace Nielsen Apr 8 at 21:27
  • $\begingroup$ Thank you for this link. I mentions the book of Jech who defined 10 Godel's operations but in Exercise 13.4 Jech remarks that those 10 can be reduced to 8. The number of NBG axioms allowing to construct classes is also 8. Maybe 8 is this optimal number? What I will try to realize now is if the 9-th Godel's operation of Jech (en.wikipedia.org/wiki/G%C3%B6del_operation) is expressible via 8-th and other operations. $\endgroup$ – Taras Banakh Apr 9 at 4:25
  • $\begingroup$ Eight is not minimal, since one can always arrange for operations to be extremely complicated and do more than one job at once. $\endgroup$ – Pace Nielsen Apr 9 at 18:42
  • $\begingroup$ I have in mind the minimality of elementary operations (those that cannot be decomposed into simpler pieces). If you want, the minimality of the total number of symbols necessary for writing these axioms, so each artificial conjunction increases the number of such symbols. But let us leave this minimality discussion as fruitless. $\endgroup$ – Taras Banakh Apr 9 at 19:10
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You don’t need intersection if you have complement: $X\cap Y=X\setminus(X\setminus Y)$. $\endgroup$ – Emil Jeřábek Apr 9 at 14:11
  • 1
    $\begingroup$ Good point! Thank you. But anyway the smallest number of (elementary) Godel's operations at the moment remains 8. $\endgroup$ – Taras Banakh Apr 9 at 14:23
  • 2
    $\begingroup$ Yes, but it means you can drop one of your axioms of NBG. $\endgroup$ – Emil Jeřábek Apr 9 at 14:34
  • 1
    $\begingroup$ This cannot be right, as it would also make these axioms redundant in ZFC by the usual expand-a-model-with-definable-classes argument. Obviously, the operations $\bigcup X$ and $\mathcal P(X)$ are definable using only set quantifiers, hence the existence of $\bigcup X$ and $\mathcal P(X)$ as classes follows from the class existence axioms. But the point of the axioms of union and powerset is that if $x$ is a set, then the (already existing classes) $\bigcup x$ and $\mathcal P(x)$ are also sets. $\endgroup$ – Emil Jeřábek Apr 9 at 15:05
  • 1
    $\begingroup$ @PaceNielsen Very good! Thank you. Following your suggestions I made the simplifications of the proofs. Now all of them are almost trivial. $\endgroup$ – Taras Banakh Apr 9 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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