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

### Orderings

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 🙂

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