Axiom of Regularity ― an introduction
Beginners of axiomatic set theory encounter a list of ten axioms of Zermelo-Fraenkel set theory (in fact, infinitely many axioms: Separation and Replacement are in fact not merely a single axiom, but a schema of axioms depending on a formula parameter, but it does not matter in this post.) Most of the axioms have a clear meaning, so not hard to accept: for example, Axiom of Pairing states we can find an unordered pair
However, Axiom of Regularity has an unclear statement in a first glance:
For each non-empty set
, there is such that .
Most of the readers – especially those who have not learned axiomatic set theory – have not seen this strange axiom. It has no non-trivial application to usual mathematics. Moreover, the usual mathematics seems like neutral to this axiom: accepting or denying the axiom does not change almost all of the usual mathematics. As a result, this unfortunate axiom is fallen into an abyss of oblivion as Blass mentioned in [1] by
(…) the axiom of regularity has suffered an even worse fate than the axiom of choice; people don’t deny the axiom of regularity, they just ignore it.
Why set theorists add such an unclear and even seems-like redundant axiom as a part of ZFC? This post aims to explain the reason why. I will explain the meaning of this unfortunate axiom first and introduce its consequences:
Throughout this article,
We first analyze a cumbersome description of the axiom of regularity. I will assume that the readers already know about partial orders and well-orderings. Let me rephrase the definiton of well-ordering:
An order
over a set is well-ordered if every non-empty subset of has a minimal element with respect to .
Well-orderedness is a property of orders. Could we generalize well-orderedness for general binary relations? Here is a possible attempt:
A binary relation
, not necessarily an order, is well-founded if every non-empty subset of has a -minimal element.
We have to clarify what
An element
of a partially ordered set is minimal if no element satisfies ; i.e. no element of is smaller than .
We can also generalize the notion of minimality to general binary relations:
An element
of a set with a binary relation is -minimal if no element satisfies .
Now re-examine the statement of the axiom of regularity, with unpacking the set intersection into its definition:
For each non-empty set
, there is such that no satisfies ; that is, is a -minimal element of .
Especially, every non-empty subset of a given set has a
Since every non-empty subset of a class of all sets
Theorem (ZF) Every non-empty class
has a -minimal element.
Proof. Take any
We formulated well-foundedness by mimicing well-orderedness. Therefore, we could expect well-foundedness resembles well-orderedness. For example, no well-ordered set allows infinitely decreasing chains. We can say the same thing for well-founded sets:
Theorem Let
be a well-founded relation over a set . Then there is no infinite -decreasing sequence over ; that is, no sequence over satisfies .
Proof. Let
Especially, we have
Corollary (ZF) There is no
-decreasing sequence; that is, no satisfies .
This corollary excludes ill-founded sets (i.e. sets that make
Well-orderedness has useful consequences: for example, every well-ordered set allows transfinite induction and transfinite recursion. The same holds for general well-founded relations, not only for well-ordered sets:
Theorem (Well-founded induction)
Let
be a set with a well-founded relation and assume that holds for a formula . Then holds for all .
(Remark:
Proof. Assume the contrary that
Remind that the axiom of regularity states
Corollary (
-induction) If holds for all , then holds for all .
What is the meaning of the well-founded induction? Let me remind the transfinite induction for ordinals. Its statement is as follows:
Assume that
holds for a formula . Then holds for all ordinal .
Here
Assume that if
holds for all predecessors of , then holds. Then holds for all ordinals.
The meaning of the well-founded induction does not deviate from that of the transfinite induction: the well-founded induction states if we know the validity of
We sometimes define a function on natural numbers and ordinals recursively. The nature of recursion of them heavily relies on the induction principle over
Theorem. (Well-founded recursion) Let
be a class function and be a well-founded class such that is always a set for . Then there is a function such that .
Some readers might wonder the meaning of
One of an important consequence of the axiom of regularity is it provides a hierarchical structure of
, (where is a power set of .) for limit .
It is easy to see that
We call the union of all
Since the axiom of regularity gets rid of these peculiar sets, we may expect the axiom of regularity proves every set is a pure set: that is,
Theorem.
. That is, every set is a pure set.
Proof. We will prove it by using
The hierarchical structure of
Definition. The rank
of is the least ordinal such that .
It is not hard to check that
We can make use of the hierarchical aspects of the universe to strenghten the axiom of replacement:
Theorem. Let
be a class indexed by for some set . If is not empty for each , then there is a family of non-empty sets such that .
Proof. For each
The technique used in the theorem – collecting elements of
Hopefully, we can resolve the problem by applying Scott’s trick. Collect the following sets for each
By the same argument used in the previous proof, we can see that
Russellian definition of cardinals is useful in choiceless set theory: the usual definition of cardinals – defining it as initial ordinals – breaks down if we do not have the axiom of choice. We do not know every set is equipotent with an initial ordinal, so there might be sets whose cardinal is not represented by initial ordinals. The Russellian definition does not involve initial ordinals and the axiom of choice, and it forms cardinals from sets directly. Thus this definition works even if we do not have the axiom of choice.
I have not seen any application of collection outside of logic: in fact, the usual mathematics hardly uses the full power of ZFC. However, the Axiom of Collection is important to do set theory: for example, set theorists construct various models of ZFC via forcing or inner model. The construction includes verifying axioms of ZFC over the models, and checking the validity of Collection is sometimes easier than that of the Replacement.
Let me digress a little from the main topic of this article: the readers might ask whether the axiom of collection can be proven without the axiom of regularity. The answer seems negative: Karagila described how to construct a model of ZFC without regularity and collection, by using permutation model.
I will finish this post by mentioning the historical aspect of the main character: the axiom of regularity. The following explanation is mainly due to [2] and [3].
A weak form of the axiom of regularity
References
[1] Andreas Blass, The interaction between Category theory and Set theory..
[2] Penelope Maddy, Believing the axioms I.
[3] Adam Rieger, Paradox, ZF, and the Axiom of Foundation.
[4] Harry Altman, How can one prove the axiom of collection in ZFC without using the axiom of foundation? URL: https://math.stackexchange.com/q/1619182. (retrived: 2020-03-12 02:56 +0900)