# AC is not refutable in ZF - Part 2Wed, 05 Oct 2011 13:21:00 GMT

This is part 2 of my series about the irrefutability of the axiom of choice from ZF. It will mainly introduce concepts about set theory.

Set theory is all about collections. While some set theories use elementary objects, ZF only knows sets. It needs no function symbol, but one binary relation symbol . Firstly of course, we notice that collections can usually be denoted by propositions with a free variable. Such collections are called classes. The intuition is that a class associated with a formula is the collection (which is of course not possible for all ). We write for , and sometimes we associate itself with the class. We write for .

Most important, classes are only syntactical objects. We cannot quantify over them. They are only a convenient form of talking about collections, but everything we do with classes could be done logically directly. For example, if we write , we could as well talk about the formula . Especially, we say that two classes are equal when they contain the same elements.

A first important class is the class . It obviously contains no element. It is the empty class, we will axiomatically postulate that it is a set, the empty set.

Furthermore, there is the class , the universe, which contains all sets. It is not a set, it is a proper class.

Another interesting class, which resembles Russel's paradoxon, is the class . It is not a set: Assume it was a set and . Then . Contradiction, so , but then . Contradiction. cannot be a set. is a proper class.

The duty of ZF is it now to provide a class of sets, by postulating the existence of sets that can be created from other sets. However, the first axiom we deal with does not give us extra powers of creating sets, but limits the existing sets. It is the axiom of extensionality.

Since we did not want to add axioms for equality, we define equality of sets as it is done in Wikipedia:

Then the extensionality axiom sais that two sets containing the same elements are equal, which can be expressed by

(EXT)

The first axiom giving us a set is the axiom of the empty set. Formally, it can be expressed by . However, we choose an equivalent, but more convenient notation, using the class we defined above:

(NUL)

Having two sets, we axiomatically postulate the existence of a set containing these two sets, . Again, we use a more convenient notation

(PAR)

As the high-level-notations should be well-known and as it should be clear how they can be rewritten into what we defined in Part 1, we will continue using high-level-notations.

For every set, there is the union of its elements:

(UNI)

Then there is the axiom of infinity, which gives us the existence of an infinite set, which will turn out to guarantee the existence of the set of finite (ordinal) numbers. If one has never worked with ordinals before, it is rather counter-intuitive, but as soon as ordinals are definet, it should become clear. Essentially, it sais that there is a set containing , and for all elements it contains, it also contains . Therefore, it contains .

(INF)

Then, for every set we want a powerset , containing all subsets of :

(POW)

A further boundary for sets is the axiom of foundation, which sais that every nonempty set contains an element which is disjoint to itself. From this axiom follows that there are no infinite -chains.

(FUN)

For the final axiom, we need an additional concept. Usually, a binary relation can be considered a set of pairs, and a function can be considered a special type of relation. That is, a function is a relation which is left-unique, that is, if it contains and , then . We can extend this notion to classes: A class is called functor, if it contains only pairs of sets, and if and implies for all .

As functors are classes, there is no way of quantifying over all of them. The final axiom is therefore not really an axiom (even though it is often considered so), but an axiom scheme, describing infinitely many axioms. It sais that if we have a functor and a set, then the image of that set under the functor is also a set. It is called replacement scheme.

(RPL) For every functor we have

From the replacement scheme follows the comprehension scheme:

Lemma: For every class and every set we have .
Proof: We can easily define a functor sending every element onto if , and onto otherwise. Applying (RPL) and (UNI) we then get what we want.

Lemma: There is no infinite -chain
Proof: Assume we had an infinitely long decreasing chain . Consider . For an arbitrary we can find an such that . Therefore, , and so, violates (FUN). Contradiction.

Now we have all axioms of ZF. The critical part, which is the center of our further attention, is the axiom of choice:

(AC)

The relevance of this axiom is not immediately clear. It becomes clearer when dealing with well-orderings and ordinals:

Definition: A strict total ordering on a set is a binary relation satisfying
• Transitivity: and imply
• Trichotomy: or or
• Irreflexivity:
for all .

Definition: A well-ordering on a set is a strict total ordering on , such that every has a minimum.

Well-orderings are interesting since their existence for every set is equivalent to the axiom of choice:

Theorem: If every set has a well-ordering , then the axiom of choice holds.
Proof: Let an arbitrary set be given. By (UNI), exists, and by assumption, there is a well-ordering . Define and let for be the minimum of regarding . Then this satisfies the axiom of choice.

Theorem: From the axiom of choice follows that every set has a well-ordering

We will not prove this here. A German version of this proof can be found on Wikipedia.

Well-orderings turn out to be extremely useful, therefore, we are interested in classifying them in a simple way. In the usual way we can define order-isomorphisms as structure-preserving bijective functions, and as usual, isomorphism becomes an equivalence relation, and therefore, we want to find representatives for every equivalence class.

Lemma: Let be a well-ordering and . Then is also a well-ordering, and is not isomorphic to .
Proof: Trivially is also a well-ordering. Assuming there was an isomorphism , then is non-empty and contains a smallest element such that . Then there must be some such that , but as was minimal and , we know that , therefore , so , which means that since was minimal, and therefore . Contradiction.

Definition: A set is called an ordinal if for all we have and is well-ordered by . The class of all ordinals is called , we will later prove that it is a proper class.

The following definition of natural numbers are examples for finite ordinals:
We call the set of these numbers , it is the smallest infinite ordinal.

Lemma: for
Proof: contains an -minimum . Assume there was some , then also , and would not be minimal anymore. Contradiction. Thus, .

Lemma: If and , then .
Proof: As , , so trivially, is also well-ordered by . Assuming and , by transitivity we have , so every element of is a subset. .

Theorem: If and are ordinals whose well-orderings regarding are isomorphic, then
Proof: Call the isomorphism . Assuming , there must be a minimal such that . Trivially, , so . Therefore, there is some . Trivially, we have . Contradiction.□

Theorem: Any two ordinals are comparable.

We will not prove this here.

Definition: For a class we define as the collection of finite sequences of sets inside .

Theorem: There is a bijective functor .
Proof: We show that there exists a well-ordering on such that the class of predecessors of every element is a set. From this, the theorem follows directly. Firstly, on , define an ordering

, where . This is a well-ordering: Firstly, it sorts according to the maximum of the sequence, then according to the length, if both are equivalent, then it uses lexicographical ordering. Form now, define .