Definition 0.2.1 (Partial ordering). Let and a relation on . We say is a partial ordering if:
- (i) and ;
- (ii) and ;
- (iii) for all .
A set with a partial ordering is also called a “poset”. If also satisfies “(iv) if then either or ”, then is called a total (or linear) ordering.
Example 0.2.2. If is a set, then induces a partial ordering on ; and is linearly ordered by its usual ordering.
A partial ordering on gives a partial ordering on all nonempty subsets of . Two partially ordered sets are said to be order isomorphic if there exists a bijection such that .
If is partially ordered by , a maximal (minimal) element of is an such that the only satisfying () is itself. Max/min elements needn’t exist, and needn’t be unique unless the ordering is linear.
If , an upper bound (lower bound) for is an element such that () for all . may or may not be in . Unless the ordering is total, a maximal (minimal) element of needn’t be an upper (lower) bound for .
If is totally ordered by and every nonempty subset of has a unique minimal element, is said to be well ordered by , and is called a well ordering on . For example, is well ordered by its natural ordering.
Theorem 0.2.3 (The Hausdorff Maximal Principle). Every partially ordered set has a maximal linearly ordered subset.
That is: if is a poset, then there exists such that is linearly ordered and there is no with that is linearly ordered by .
Lemma 0.2.4 (Zorn’s Lemma). If is a poset and every linearly ordered subset of has an upper bound, then has a maximal element.
Example 0.2.5 (Conceptual example). . Its subsets:
| 1 element |
2 elements |
3 elements |
4 or 0 elements |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
is marked as the maximal linearly ordered subset.
Theorem 0.2.6. Every nonempty set can be well ordered.
Proof. Let be the collection of well orderings of subsets of , regarded as subsets of . We partially order by declaring iff and the domain of is an initial segment of . By Zorn there exists a maximal element. This maximal element must be a well ordering of itself, since if is a well ordering on and , then can be extended to a well ordering on by declaring for all . ∎
Theorem 0.2.7 (The Axiom of Choice). If is a nonempty collection of nonempty sets, then is nonempty.
Proof. Let , pick a well ordering on , and for let be the minimal element of . Then . ∎
Corollary 0.2.8. If is a disjoint collection of nonempty sets, then there exists a set such that contains precisely one element for every .