Equivalence Relations

Definition. An equivalence relation on X is a relation R on X such that:

xRy for all x\in X,

xRy iff yRx,

xRz whenever xRy and yRz for some y.

An equivalence class of an element x is \{y\in X: xRy\}, where X is the disjoint union of these equivalence classes.



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

1) If xRy and yRx, then xRz;

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

3) xRx for all x.

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

4) If x, y\in X, then either xRy or $yRx$.

Example 1. \mathbb R is linearly ordered by its usual ordering, and we usually denote its partial orderings by \leq.

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

Definition. Two partially ordered sets X and Y are order isomorphic if $latex\exists$ a bijection f: X\to Y such that x_1\leq x_2 iff f(x_1)\leq f(x_2).

Definition. A maximal (resp. minimal) element of a partially ordered set X is an element x\in X such that the only y\in X satisfying x\le y (resp. x\ge y) is x itself.

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

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

Example 2. \mathbb N 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 E need not be an element of E, and unless E is linearly ordered, a maximal element of E need not be an upper bound for E.

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

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

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

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

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

Proof. Let \mathcal W be the collection of well orderings of subsets of X, and define a partial ordering on \mathcal W as follows. If \le_1 and \le_2 are well orderings on the subsets E_1 and E_2, then \le_1 precedes \le_2 in the partial orderings if:

1) \le_2 extends \le_1, i.e., E_1\subset E_2 and \le_1 and \le_2 agree on E_1, and

2) if x\in E_1\setminus E_2 then y\le_2 x for all y\in E_1.

Zorn’s Lemma is satisfied, so \mathcal W has a maximal element. This must be a well ordering on X itself, for if \le is a well ordering on a proper subset E of X and x_0\in X\setminus E, then \le can be extended to a well ordering on E\cup\{x_0\} by declaring that x\le x_0 for all x\in E\Box

The Axiom of Choice. If \{X_\alpha\}_{\alpha\in A} is a nonempty collection of nonempty sets, then \prod_{\alpha\in A}X_\alpha is nonempty.

Proof. Let X=\cup_{\alpha\in A}X_\alpha. Pick a well ordering on X and, for \alpha\in A, let f(\alpha) be the minimal element of X_\alpha. Then f\in\prod_{\alpha\in A}X_\alpha. \Box.

Corollary. If \{X_\alpha\}_{\alpha\in A} is a disjoint collection of nonempty sets, there is a set Y\subset \cup_{\alpha\in A}X_\alpha such that Y\cap X_\alpha contains precisely one element for each \alpha\in A.

Proof. Take Y=f(A) 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 🙂



[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