You can read the LaTeX document online (for the latest updated chapters) from the link: https://pdf.gaomj.cn/?file=get.php?f=set-theory
* Order Structures
In this chapter we develop one of the fundamental structures in modern mathematics: the order structures. We will consider three types of orders: partial orders, total orders, and well-orders. More attention is given to well-orders. We will prove the transfinite recursion theorem for well-orders, and then use it to construct the "ordinal numbers", with which we can complete our definition of cardinal numbers of sets.
In this chapter, three new axioms are added into our axiom list, namely replacement axioms, choice axiom and regularity axiom. We have made use of a specific form of the axiom of choice in previous chapters, but there is much more. We will see there are a number of equivalent forms of the axiom of choice.
Contents
Contents
1. Three Types of Orders
1.1. Well-orders
2. Continued on Page Two
3. Transfinite Recursion Theorem
4. Isomorphic well-orders
5. Ordinal Numbers
6. Axiom of Choice
7. Regularity Axiom
1. Three Types of Orders
An order is a special kind of relation. It is common that we want to "compare" two elements of a set. The following are three basic and important examples.
- The set \mathbb R has the usual order relation <.
- The inclusion relation for \mathcal P(S).
- The divisibility relation for positive natural numbers.
We can now define the order relations.
\begin{gather*}
x\mathcal R x,\\
x\mathcal Ry\wedge y\mathcal R x\Rightarrow x=y,\\
x\mathcal R y\wedge y\mathcal R z\Rightarrow x\mathcal R z.
\end{gather*}
Such a relation is often denoted by \leqslant or the like.
Furthermore, define < such that x<y if and only if x\leqslant y and x\neq y.
In the first definition, we do not mention explicitly the underlying set A. The set ordered by this relation is implicitly its domain or range. (By reflexivity the domain and range are the same.) In the second definition we do explicitly mention A.
We have some simple consequences of these definitions immediately.
- The relation < is transitive, i.e., x<y<z\Rightarrow x<z. If x<y<z, then x\leqslant z. But antisymmetry indicates x\neq z, so x<z. Similar results hold such as x\leqslant y<z\Rightarrow x<z.
- For partial orders, at most one of the three alternatives x<y, y<x and x=y can hold.
- For total orders, exactly one of the three alternatives above holds.
An order structure is a pair (A,\mathcal R) where A is a set and \mathcal R is an order on A. Sometimes we call the set A "poset" or "loset" if A is partial ordered or linear ordered.
Special elements within an order
Let A be partially ordered by \leqslant.
- An element m is called the least (or minimum or smallest) element of A if for any x\in A, m\leqslant x.
Least element is unique by antisymmetry, but it may fail to exist. Consider the strict divisibility relation on the set \mathbb N^\ast=\{n>0\mid n\in\mathbb N\}. Then 1 is the least element of \mathbb N^\ast, but the set \{n>1\mid n\in\mathbb N\} has no least element.
However we can consider the "minimal" element. An element m is called the minimal element if there is no x such that x<m (or equivalently x\leqslant m\Rightarrow x=m). A least element is also minimal. In the above example, every prime number is a minimal element. This shows there might be quite a few minimal elements.
Similarly we can define the greatest ( or largest or maximum) element and the maximal element.
- Suppose S is partially ordered by \leqslant and A is a subset of S. We call u\in S an upper bound of A if x\leqslant u for all x\in A. If u\in A then clearly it is the greatest element of A.
If s is the least element of the set of all upper bounds of A, then s is called the least upper bound (or supremum) of A.
Lower bound and greatest lower bound (or infimum) are defined similarly.
Two quick examples:
- Let \mathcal P(S) be partially ordered by the inclusion relation. Suppose A,B\subseteq S, then the set \{A,B\} has a least upper bound A\cup B, and a greatest lower bound A\cap B.
- In the set of positive integers ordered by divisibility, greatest lower bounds are just the greatest common divisors, and least upper bounds are the least common multiples.
1.1. Well-orders
Now we shall focus our attention on a special case of total orders, the "well-orders", or "well orders". The hyphen between the words is for grammatical consideration, though it may not help too much.
The set \mathbb N of natural numbers provides an excellent example.
With the axiom of choice, the well orders can be characterized by the existence of a strictly decreasing sequence.
If there is such a sequence f, then clearly the range of f is nonempty and does not have a least element, so \leqslant is not a well-order. Conversely, suppose \leqslant is a well-order on A. Then there is a subset B\subseteq A that has no least element. Therefore for any x\in B there is a y\in B such that y<x. Intuitively we can recursively construct a decreasing sequence by successively choosing a smaller element, but we do need the axiom of choice for this process.
Specifically, since \forall x\in B\exists y\in B\, (y<x), the relation < has range B and also domain B. By the axiom of choice (Section sec:ac), there is a mapping g with domain B such that g(x)<x. Now we can set f(0) be an arbitrary element in the nonempty B, and define recursively f(n+1)=g(f(n)). We obtain a strictly decreasing sequence.□
.
As in Chapter 3, here we implicitly use our assumption that an object involving n\in\mathbb N can be defined recursively.
3. Transfinite Recursion Theorem 4. Isomorphic well-orders 5. Ordinal Numbers 6. Axiom of Choice 7. Regularity Axiom
发表回复