**Equivalence Relations**

**Definition.** An equivalence relation on is a relation on such that:

for all ,

iff ,

whenever and for some .

An equivalence class of an element is , where is the disjoint union of these equivalence classes.

**Orderings **

**Definition.** A partial ordering on a nonempty set is a relation on such that:

1) If and , then ;

2) If and , then $x=y$;

3) for all .

A linear (total) ordering has an additional property that:

4) If , then either or $yRx$.

**Example 1.** is linearly ordered by its usual ordering, and we usually denote its partial orderings by .

**Remark 1.** Every non-empty subset of a partially ordered set is also partially ordered.

**Definition.** Two partially ordered sets and are order isomorphic if $latex\exists$ a bijection such that iff .

**Definition. **A maximal (resp. minimal) element of a partially ordered set is an element such that the only satisfying (resp. ) is itself.

If , and upper (resp. lower) bound for is an element such that (resp. $x\le y$) for all .

A linearly ordered set $X$ is said to be well ordered by if every non-empty subset of has a (necessarily unique) minimal element. is called a well ordering on .

**Example 2.** is well ordered.

**Remark 2.** Maximal and minimal elements may or may not exist, and they need not be unique unless the ordering is linear. An upper (resp. lower) bound for need not be an element of , and unless is linearly ordered, a maximal element of need not be an upper bound for .

**The Hausdorff Maximal Principle.** Every partially ordered set has a maximal linearly ordered subset.

**Zorn’s Lemma.** If is a partially ordered set and every linearly ordered subset of has an upper bound, then has a maximal element.

**Remark 3.** The Hausdorff Maximal Principle is equivalent to Zorn’s Lemma.

Proof. 1) H Z: An upper bound for a maximal linearly ordered subset of is a maximal element of . 2) Z H: Take the collection of linearly ordered subsets of , which is partially ordered by inclusion.

**The Well Ordering Principle.** Every nonempty set can be well ordered.

Proof. Let be the collection of well orderings of subsets of , and define a partial ordering on as follows. If and are well orderings on the subsets and , then precedes in the partial orderings if:

1) extends , i.e., and and agree on , and

2) if then for all .

Zorn’s Lemma is satisfied, so has a maximal element. This must be a well ordering on itself, for if is a well ordering on a proper subset of and , then can be extended to a well ordering on by declaring that for all .

**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.** If is a disjoint collection of nonempty sets, there is a set such that contains precisely one element for each .

Proof. Take where $f\in\prod_{\alpha\in A}X_\alpha$.

“As soon as you honor the present moment, all unhappiness and struggle dissolve, and life begins to flow with joy and ease. When you act out the present-moment awareness, whatever you do becomes imbued with a sense of quality, care, and love – even the simplest action.” ~ Eckhart Tolle

To be continued tomorrow 🙂

References:

[1] Gerald B. Folland, *Real Analysis: Modern Techniques and Their Applications*, 2ed, page 4-6.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf