A partial ordering on a nonempty set X is a relation R on X with the following properties.
\begin{align}
\text{Reflexive} &: (x, x) \in R \text{ for all } x\in X \\
\text{Anti-Symmetric} &: \text{if } (x,y) \in R \text{ and } (y, x) \in R, \text{ then } x= y \\
\text{Transitive} &: \text{if } (x,y) \in R \text{ and } (y, z) \in R, \text{ then } (x, z) \in R
\end{align}
We denote partial orderings by \leq, and write x < y to mean that x \leq y but x \neq y.
Partial ordering does not guarantee any two elements in set X to be comparable, but linear (or total) ordering does.
A linear (or total) ordering on X is a partial ordering on X such that for any x, y \in X, either (x, y) \in R or (y, x) \in R.
Two partially ordered sets X and Y are said to be order isomorphic if there is a bijection f: X \rightarrow Y such that
x_{1} \leq x_{2} \iff f(x_{1}) \leq f(x_{2})
If X is partially ordered by \leq,
- A maximal (resp. minimal) element of X is an element x \in X such that the only y\in X satisfying x \leq y (resp. y \leq x) is x itself.
- If E \subset X, an upper (resp. lower) bound for E is an element x \in X such that y \leq x (resp. x \leq y) for all y \in E.
- If A \subset X is nonempty, then the greatest lower bound of A (if exists) is called infimum; and denoted by \inf A
- If B \subset X is nonempty, then the least upper bound of B (if exists) is called supremum; and denoted by \sup B
A well ordering \leq on X is a linear ordering on X such that every nonempty subset of X has a \leq-minimal element. X is said to be well ordered by \leq.
Note that when X is linearly ordered, minimal (or maximal) element of A \subset X is unique if exists and is equal to \inf A. We shall discuss about properties of well ordered sets and transfinite induction.
For each x \in X, we define the initial segment of x to be
I_{x} = \left\{ y \in X: y < x \right\}
The elements of I_{x} are called predecessors of x.
(The principle of Transfinite Induction).
Let X be a well ordered set. If A is a subset of X such that x \in A whenever I_{x} \subset A, then A = X.
Suppose A \neq X. X \setminus A is nonempty, we can define x = \inf (X \setminus A). Then I_{x} \subset A but x \not\in A; contradiction. Thus A = X.
(Bourbaki's Fixed Point Theorem).
Let (X, \leq) be a partially ordered set. Assume that every nonempty linearly ordered subset of X has a supremum (least upper bound). Suppose f: X \rightarrow X and f(x) \geq x for all x \in X. Then there is some x^{\ast} \in X such that f(x^{\ast}) = x^{\ast}.
Fix a \in X. A subset A \subset X is admissible if
- a \in A
- x \in A \implies f(x) \in A
- if F is linearly ordered subset of X and F \subset A, then \sup F \in A.
- a \in B_{x} since a \leq x for all x \in M
- If y \in B_{x}, then y \leq x or f(x) \leq y. If f(x) \leq y, then f(x) \leq y \leq f(y), so f(y) \in B_{x}. Or if y < x, then by assumption f(y) \leq x; f(y) \in B_{x}.
- Suppose F \subset B_{x} is linearly ordered. Since B_{x} \subset M, F \subset M. Above we proved that M is admissible, so \sup F \in M. Since y \leq x or f(x) \leq y for all y \in F, the "least" upper bound \sup F should satisfy either \sup F \leq x or f(x) \leq \sup F. This gives \sup F \in B_{x}.
- a \in C because the statement y < a for y \in M is false (vacuously true)
- Suppose t \in C. If y < f(t) for y \in M, then since B_{t} = M, we get y \leq t. If y < t, by assumption f(y) \leq t; so that f(y) \leq t \leq f(t). If y = t, automatically f(y) \leq f(t). So f(t) \in C.
- Suppose F \subset C is linearly ordered. Since C \subset M, F \subset M. Above we proved that M is admissible, so b = \sup F \in M. Suppose y < b for some y \in M. If all t \in F satisfy f(t) \leq y, then t \leq y for all t\in F so that y is an upper bound of F, y \geq b (which is contradiction). So there is t_{0} \in F such that f(t_{0}) > y. Since t_{0} \in C, B_{t_{0}} = M. Now y \leq t_{0} \text{ or } f(t_{0}) \leq y The only possibility is y \leq t_{0}. Here we divide into two cases. (1) If y < t_{0}, then by condition of set C, f(y) \leq t_{0} \leq b, so that f(y) \leq b. (2) If y = t_{0}, b \in B_{y} = M, which again gives b \leq y \text{ or } f(y) \leq b The only possibility is f(y) \leq b (because we already assumed y < b). In both cases, b \in C.
댓글 없음:
댓글 쓰기