Contents
Set Theory Overview:
This page states the axioms of set theory in a formal and precise manner in terms of quantifiers, logical operators, and the membership symbol. The use of the English language (including the word 'set') is very careful and consistent resulting in a text that may perhaps be parsed and analyzed by a computer program. All objects are called 'sets' even when we think of them as elements. Thus the elements of a set are also sets.
The Axiom of Choice is given on a separate page where it is shown to be equivalent with the Well-Ordering Principle, Hausdorff's Maximal Principle, and Zorn's Lemma. Strict proofs are given for the equivalence of the Axiom of Choice with any of the above-mentioned principles.
This page introduces basic operations on sets like union (A u B), intersection (A n B), and difference (A \ B), and states and proves the Boolean Algebra properties. Set includsion (A c B) is introduced and basic properties are proved.
Cartesian Product, Relation and Function
The following concepts are introduced on this page: ordered pair (a,b), power set, Cartesian product, relation, equivalence relation, function, 1-1 function, "onto" function, composition of functions fog, the inverse function f^(-1).
Infinite Union and Intersection
This page states and proves the De Morgan's Laws for infinite union and intersection of sets.
The following concepts are introduced on this page: partial order, linear order, and well-order.
This page states and proves the Induction Principle and the Recursion Principle for any well-ordered set providing the framework for recursive definitions. We use these principles to prove that the Well-Ordering Principle implies Hausdorff's Maximal Principle.
Axiom of Choice and Its Equivalents
This page states the Axiom of Choice, the Well-Ordering Principle, Hausdorff's Maximal Principle, and Zorn's Lemma, and proves that they are equivalent under the first six axioms - without the axiom of infinity and - more importantly - without the axiom of regularity.
For those professional mathematicians who have never found the time to go through the equivalence proofs this page can serve as a reassurance: it's all here on a single page and can be gone through at any time given a spare evening or two.
Cardinality - without Axiom ZF9
This page introduces the following cardinality comparisons and proves the basic theorems about these concepts.
| |X| = |Y| | X and Y have the same cardinality |
| |X| <= |Y| | Y is at least as numerous as X |
| |X| < |Y| | Y is strictly more numerous than X |
Two theorems deserve special attention:
| for any sets X,Y |
| 1 | |X| < |P(X)| |
| 2 | |X| <= |Y| or |Y| <= |X| |
The first theorem shows that we can create sets of ever greater cardinality. And what's worth noticing at this point is that we don't need the Axiom of Choice to assert that the power set P(X) has greater cardinality than X. However, the proof of the second theorem - which states that any two sets are comparable in terms of cardinality - relies on Zorn's Lemma and thus on the Axiom of Choice. Finally, the proofs show that the Axiom of Regularity is not needed for these cardinality results.
Ordinals and Cardinals - with Axiom ZF9
This page defines the concept of an ordinal and proves many basic theorems about ordinals using heavily the Axiom of Regularity (ZF9). The Axiom of Choice is not used in these proofs.
This page proves the existence of a unique minimal set M containing the empty set and having the following transitivity property: for each x:-M we have that x u {x} :- M.
We call this set the Natural Infinite Set, and we use it to define the notion of countability and the destinction between finite and infinite sets.
To obtain this set we use the Axiom of Infinity and this is the first and only time when this axiom is used. We don't need the Axiom of Choice or the Axiom of Regularity to obtain this set but we use the Axiom of Regularity to show that the Natural Infinite Set is an ordinal and that all of its elements are ordinals.