PROVENMATHEverything proven from axioms

Contents

Set Theory Overview:

Axioms of Set Theory

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 which states that for any set X and any formula P there exists a subset of X containing exactly the elements x for which P(x) is true is stated very precisely using notions like
• well-formed formula
• free variable
• whether a given formula contains a given variable or not.
These concepts are introduced and defined down to the finest detail on a separate page. The result is a precise and all-questions-answering statement of this axiom.

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.

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).

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.

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.

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.

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.