Relations. The Axiom of Choice and Zorn's Lemma

Which of the following relations are equivalence relations?

Let us call two positive functions $f_1$ and $f_2$ on $[0,1]$ equivalent if

Verify that this is actually an equivalence relation and that the corresponding quotient set is uncountable.

Let the condition $\lim_{x \to 0} \left[f_1(x)/f_2(x)\right] = \infty$ define the relation $f_1 > f_2$ for positive functions on $[0,1]$. Verify that this is a partial-order relation and prove that any countable subset is bounded.

Let $X$ and $Y$ be partially ordered sets. Define a relation $(x_1,y_1) \geq (x_2,y_2)$ on the product $X \times Y$ by the conditions $x_1 \geq x_2$ and $y_1 \geq y_2$. Prove that this is a partial-order relation. Is it a total order relation if $X$ and $Y$ are totally ordered sets?

Let $X$ be a partially ordered set. Suppose that the partial order on $X$ has the property that $M(x) = \left\{ y \in X : y < x\right\}$ is a finite set for all $x \in X$. For any function $f(x)$ on $X$ define

Prove that $f(x)$ can be recovered from $F(x)$ by a formula of the form

The function $\mu$ is uniquely determined and is called the Möbius function for the partially ordered set $X$.

Find the Möbius functions for the following partially ordered sets:

Express the following quantities in terms of the Möbius function from Problem 6:

Let $A$ be a well-ordered set, and let $X_\alpha$ be a nonempty totally ordered set for each $\alpha \in A$. Define the lexicographical order in the set $X = \prod_{\alpha \in A}X_\alpha$ by setting $x > y$ if $x_{\alpha_0} > y_{\alpha_0}$, where $\alpha_0$ is the smallest element of $A$ for which $x_\alpha \neq y_\alpha$. Prove that this really is a total-order relation.

Suppose that $\mathbb {R}^{n}$ is totally ordered in such a way that

1. $x_1 \geq y_1$ and $x_2 \geq y_2 \Rightarrow x_1+x_2 \geq y_1+y_2$;

2. $x \geq y$ and $\lambda \geq 0$ implies that $\lambda x \geq \lambda y$ for $\lambda \in \mathbb {R}$;

3. $x \geq y$ and $y \geq x$ implies that $x = y$. Prove that $\mathbb {R}^{n}$ is isomorphic (as a totally ordered space) to the product of $n$ lines (with the usual order), endowed with the lexicographical order (see Problem 8).

Two well-ordered countable sets are said to be equivalent if there is a monotonic one-to-one correspondence between them. Let $\mathcal{M}$ be the corresponding set of equivalence classes. Define a partial order relation on $\mathcal{M}$ by setting $\mu \geq \nu$ if the classes $\mu$ and $\nu$ have representatives $M$ and $N$ such that $M$ is equivalent to an initial segment of $N$ (i.e., a set of the form $N(n_0) = \left\{ n \in N : n \leq n_0\right\}$).

Prove that:

Let $\mathcal{M}$ be the well-ordered set described in Problem 10. Let $\mathfrak {A} = \mathcal{M}\times [0,1)$ and define the lexicographical order on $\mathfrak {A}$: If $a = (\mu ,x)$, $b = (\nu ,y)$, then $a \geq b$ means that either $\mu \geq \nu$ and $\mu \neq \nu$, or $\mu = \nu$ and $x \geq y$.

Prove that any initial segment (see Problem 10) of $\mathfrak {A}$ is equivalent (as a totally ordered set) to the half-interval $[0,1)$, though the set $\mathfrak {A}$ itself is not equivalent to this half-interval.

Let $a_0 = (\mu_0,0)$ be a minimal point of the set $\mathfrak {A}$ in Problem 11. Define a topology on $\mathfrak {A}_0 = \mathfrak {A}\setminus \left\{ a_0\right\}$ by taking the ``intervals'' $(a,b) = \left\{ c \in \mathfrak {A}_0 : a < c < b\right\}$ as a base of open sets. Prove that:

Prove that in the collection of disks contained in a given square on the plane there is a maximal element but not a largest element relative to inclusion.

Using Zorn's lemma, prove that every linear space has a basis.

Zorn's Lemma. If every totally ordered subset of a partially ordered set $X$ is bounded above (below), then $X$ contains at least one maximal (minimal) element $x_0$.

Using Zermelo's theorem, show that for any two sets $A$ and $B$ there is either a one-to-one mapping from $A$ onto a subset of $B$ or a one-to-one mapping from $B$ onto a subset of $A$.

Zermelo's Theorem. Every set can be well ordered, i.e., it is possible to introduce an order relation on it such that any subset contains a smallest element.

Derive Zermelo's theorem from Zorn's lemma.

Zorn's Lemma. If every totally ordered subset of a partially ordered set $X$ is bounded above (below), then $X$ contains at least one maximal (minimal) element $x_0$.

Zermelo's Theorem. Every set can be well ordered, i.e., it is possible to introduce an order relation on it such that any subset contains a smallest element.