Infinitely recursive sets that don't contradict ZF Axiom of Regularity

[andrewkirk]

Hello, I have just been reading about the Zermelo-Frankel (ZF) axioms for set theory and thinking about their consequences. I understand that the Axiom of Regularity is needed in order to prevent contradictions like Russell's Paradox arising. That axiom says that any non-empty set A must contain an element x that is disjoint from A.

I have seen the simple proof that this axiom prevents a set from being an element of itself.

Now I'm wondering whether it prevents other forms of infinite, self-referential recursion.

For example, are the following possible within ZF?

• A is an element of B which is an element of A, hence giving infinite recursion with a two-step cycle: B = {A,x,y,...} = {{B,u,v,...},x,y,...} = {{{{B,u,v,...},x,y,...} ,u,v,...},x,y,...} etc
• {A} is an element of A, so that A = {{A},b,c,...} = {{{{A},b,c,...}},b,c,...} = {{{{{{A},b,c,...}},b,c,...}},b,c,...}, etc?

I couldn't see an obvious proof that these are impossible, but I haven't had much practice with set theory.

 

[micromass]

Hello, I have just been reading about the Zermelo-Frankel (ZF) axioms for set theory and thinking about their consequences. I understand that the Axiom of Regularity is needed in order to prevent contradictions like Russell's Paradox arising.

This is NOT true! Regularity is not needed to prevent Russell's paradox. The other axioms of ZF (more precisely, the axiom of separation) already prevents Russell's Paradox from arising.

That axiom says that any non-empty set A must contain an element x that is disjoint from A.

I have seen the simple proof that this axiom prevents a set from being an element of itself.

Now I'm wondering whether it prevents other forms of infinite, self-referential recursion.

For example, are the following possible within ZF?

• A is an element of B which is an element of A, hence giving infinite recursion with a two-step cycle: B = {A,x,y,...} = {{B,u,v,...},x,y,...} = {{{{B,u,v,...},x,y,...} ,u,v,...},x,y,...} etc
• {A} is an element of A, so that A = {{A},b,c,...} = {{{{A},b,c,...}},b,c,...} = {{{{{{A},b,c,...}},b,c,...}},b,c,...}, etc?

I couldn't see an obvious proof that these are impossible, but I haven't had much practice with set theory.

Let me present a definition and a theorem that will answer your questions:

A set A is Artins if there exists no sequence (x_n) of sets such that x_0\in A and x_{n+1}\in x_n.

Then:

Theorem: The regularity axiom implies that all sets are Artins
Proof: Let A be a set. We can safely assume that A is transitive (take the transitive closure!). If there would exist a sequence from the definition, then we put x=\{x_0,x_1,...\}, then x\subseteq A and x\neq \emptyset. But x has no minimal element with respect to \in, and thus \in is no well-founded relation. This contradicts regularity.

Note that the other implication is true in ZFC (that is, under the axiom of choice). Now, in your example, we have ...\in A\in B\in A\in B\in A, which violates that all sets are Artins...

 

[disregardthat]

This is NOT true! Regularity is not needed to prevent Russell's paradox. The other axioms of ZF (more precisely, the axiom of separation) already prevents Russell's Paradox from arising.

Wouldn't you agree with that it is not the axiom of separation that prevents Russell's paradox, but the fact that it replaced an axiom which allowed it (unrestricted comprehension)?

 

[micromass]

Wouldn't you agree with that it is not the axiom of separation that prevents Russell's paradox, but the fact that it replaced an axiom which allowed it (unrestricted comprehension)?

Yes, of course, that's what I meant Unlimited comprehension allowed Russell's paradox, while replacing it with separation does not make Russell's paradox possible. My point was that there was no axiom of regularity needed.

Of course, that does not mean that ZF will be consistent, there can still be a paradoxical statement. However, it can easily be shown that ZF is consistent if and only if ZF with regularity is consistent. Thus if there is a paradox in ZF, then there would also be a paradox in ZF + regularity. Thus it is not regularity that solves Russel's paradox...

 

[disregardthat]

It's worth mentioning that ZF with regularity and with unrestricted comprehension would still fall prey to russell's paradox: Let R be the set of all sets not contained in themselves. This set will of course be empty and thus not contained in itself, but by virtue of its definition it must be contained in itself. With our without regularity unrestricted comprehension implies russell's paradox.

 

[andrewkirk]

Thanks Micromass.

So in the examples I gave, the set that breaches the axiom of regularity would be:

• in the first case (...\in A\in B\in A\in B\in A), X={A,B}. Because B\in X\cap A and A\in X\cap B, so there is no element of X that is disjoint from X.
• in the second case (...\in A\in \{A\}\in A\in \{A\}\in A), X={A,{A}}. Because \{A\}\in X\cap A and A\in X\cap\{A\}, so there is no element of X that is disjoint from X. (I see now that this is the same as the previous case - we just write B={A}).

 

[micromass]

Thanks Micromass.

So in the examples I gave, the set that breaches the axiom of regularity would be:

• in the first case (...\in A\in B\in A\in B\in A), X={A,B}. Because B\in X\cap A and A\in X\cap B, so there is no element of X that is disjoint from X.
• in the second case (...\in A\in \{A\}\in A\in \{A\}\in A), X={A,{A}}. Because \{A\}\in X\cap A and A\in X\cap\{A\}, so there is no element of X that is disjoint from X. (I see now that this is the same as the previous case - we just write B={A}).

Yes, that's basically it!

 

[Hurkyl]

As an aside, adding axioms cannot eliminate logical contradictions. If you have an inconsistent theory, the way to make it consistent is to remove axioms.

That's how ZFC avoids Russel's paradox. Cantor's set theory had the full power of the axiom of unrestricted comprehension. ZFC, on the other hand, merely limits itself to a few special cases (e.g. pair set, power set, specification) that is enough to do mathematics, but collectively weak enough as to be unable to reproduce any of the known derivations of contradictions in set theory.