1.6Takeaways

A set $X$ is said to be a partially ordered set (or “poset”) if it is equipped with a relation $\le$ that satisfies the following properties:

1. Reflexivity. For every $x \in X$, $x \le x$.

2. Antisymmetry. For any $x, y \in X$, if $x \le y$ and $y \le x$, then $x = y$.

3. Transitivity. For any $x, y, z \in X$, if $x \le y$ and $y \le z$, then $x \le z$.

A poset $X$ is called a totally ordered set (also called a “chain” or “linear order”) if every pair of elements is comparable. That is, for any $x, y \in X$, either $x \le y$ or $y \le x$.

A relation $<$ on a set $X$ is a strict partial order if it satisfies:

1. Nonreflexivity. For every $x \in X$, $x < x$ is false.

2. Transitivity. For any $x, y, z \in X$, if $x < y$ and $y < z$, then $x < z$.

A relation $<$ on a set $X$ is a strict total order (often referred to in topology simply as an order relation) if it is a strict partial order that also satisfies the law of trichotomy:

1. Comparability. For any $x, y \in X$ such that $x \ne y$, either $x < y$ or $y < x$.

Strict and non-strict orders are simply two different languages describing the exact same underlying mathematical structure. You can always translate one into the other seamlessly:

From Non-Strict to Strict: Given a non-strict order $\le$, we induce a strict order $<$ by declaring:

From Strict to Non-Strict: Given a strict order $<$, we induce a non-strict order $\le$ by declaring:

Suppose $X$ is a partially ordered set. For any subset $S \subseteq X$, we say $x \in X$ is an upper bound for $S$ if $x \ge s$ for every $s \in S$.

Suppose $X$ is a partially ordered set. For any subset $S \subseteq X$, we say $x \in S$ is a maximal element for $S$ if $x \ge s$ for every $s \in S$.

Suppose $X$ is a non-empty partially ordered set for which every totally ordered subset (i.e., a chain) has an upper bound. Then $X$ has a maximal element.

Essentially, if $X \ne \emptyset$ is a partially ordered set for which every totally ordered subset is bounded above, then $X$ must have one element that is not less than any other element. We cleverly apply this to vector spaces to force the existence of a basis.

Fix $V$ to be an arbitrary vector space, even one that may be infinite-dimensional. Then, we consider the set $X$ of all linearly independent subsets of $V$. We define a partial ordering on $X$, such that for any $U, W \in X$, we say

Of course, $X \ne \emptyset$ since the empty set $\emptyset$ is trivially linearly independent, so $X$ is a valid partially ordered set.

To apply Zorn's Lemma, let $C$ be an arbitrary totally ordered subset (a chain) in $X$. We propose that the union of all sets in $C$, denoted $M = \bigcup_{U \in C} U$, is an upper bound for $C$. Clearly, $U \subseteq M$ for all $U \in C$. However, to be a valid upper bound in $X$, we must verify that $M \in X$; that is, $M$ must be linearly independent.

Suppose for the sake of contradiction that $M$ is linearly dependent. Then, there exists a finite set of vectors $\{v_1, v_2, \dots, v_n\} \subseteq M$ and scalars $c_1, \dots, c_n$ (not all zero) such that $c_1v_1 + \dots + c_nv_n = 0$. Since $M$ is the union of the chain $C$, each vector $v_i$ must belong to some set $U_i \in C$. Because $C$ is totally ordered, for any finite collection of sets in $C$, one of them must contain all the others. Let $U_{max}$ be the largest of these sets $U_1, \dots, U_n$. This implies that all $v_i \in U_{max}$. But $U_{max} \in X$, meaning it is linearly independent, which contradicts our assumption that these vectors form a linear dependence. Therefore, $M$ must be linearly independent, meaning $M \in X$ and $C$ is indeed bounded above.

By Zorn's Lemma, $X$ contains a maximal element, say $B$. Because $B \in X$, we already know $B$ is linearly independent. All that remains is to show that $B$ spans $V$. Suppose it does not; then there exists some vector $v \in V \setminus \Span(B)$. But then the set $B \cup \{v\}$ would be linearly independent, meaning $B \cup \{v\} \in X$. Since $B \subsetneq B \cup \{v\}$, this strictly contradicts the maximality of $B$. Thus, $\Span(B) = V$, and we conclude that $B$ is a basis for $V$.

Suppose $\mathcal{C}$ is a collection of non-empty sets. Then you may construct a new set by “choosing” exactly one element from each set.

Of course, this seems trivial. If you have infinitely many pairs of shoes, you don't need a special axiom to pick one from each pair (just pick only the left ones). But if you have infinitely many pairs of identical socks, there is no definable rule to pick one from each. The Axiom of Choice simply declares you can do it anyways. It assumes the existence of such a set, even without a definite construction.

A totally ordered set $(X, \le)$ is said to be well-ordered if, for any nonempty subset $A \subseteq X$, there exists a strictly least (minimum) element.

Every set can be equipped with a total ordering such that it is well-ordered.