Well-ordered set: Difference between revisions
no edit summary
RhubarbJayde (talk | contribs) (Created page with "A well-ordered set is a set \(X\) endowed with a relation \(\leq\) on \(X^2\), called a well-order, so that \(\leq\) has the following properties * Transitivity: If \(a \leq b\) and \(b \leq c\) then \(a \leq c\). * Antisymmetry: If \(a \leq b\) and \(b \leq a\), then \(a = b\). * Totality: For all \(a, b\), either \(a \leq b\) or \(b \leq a\). * Well-foundedness: For any \(S \subseteq X\), there is \(s \in S\) so that, for all \(t \in S\), \(s \leq t\). * Reflexivity:...") |
RhubarbJayde (talk | contribs) No edit summary |
||
Line 4:
* Antisymmetry: If \(a \leq b\) and \(b \leq a\), then \(a = b\).
* Totality: For all \(a, b\), either \(a \leq b\) or \(b \leq a\).
* Well-foundedness: For any nonempty \(S \subseteq X\), there is \(s \in S\) so that, for all \(t \in S\), \(s \leq t\).
* Reflexivity: For all \(a\), \(a \leq a\).
Line 10:
Well-ordered sets are part of the motivation of [[Ordinal|ordinals]], and are used to define their equivalence class definition. In particular, for any well-ordered set \(X\), there is an ordinal \(\alpha\) and a map \(\pi: X \to \alpha\) so that \(x \leq y\) implies \(\pi(x) \leq \pi(y)\): the unique such ordinal is called its order-type. The order-type of the natural numbers is [[Omega|\(\omega\)]], where the map \(\pi\) is just the identity function, and any ordinal is its own order-type. Also, any [[countable]] set has a countable order-type, and any [[finite]] set has a finite order-type (which is necessarily equal to its [[cardinality]], unlike the case with infinite sets).
You can see that, assuming the axiom of choice, the well-foundedness criterion is equivalent to there not being an infinite descending chain. Assume \(S \subseteq X\), and there is no infinite descending chain. Assume towards contradiction that \(S\) has no minimal element. Use AC to define a choice function \(f\) for \(\{X: X \subseteq S\}\). Let \(s_0 = f(S) \in S\), and then \(s_{n+1} = f(\{x \in S: x \leq s_n \land x \neq s_n\})\). \(\{x \in S: x \leq s_n \land x \neq s_n\}\) is always nonempty, because else \(s_n\) would be a minimal element of \(S\). Then \(s\) forms an infinitely descending chain. Contradiction! For the converse, assume that every nonempty subset has a minimal element, and assume \((s_i)_{i = 0}^\infty\) is an infinite sequence with \(s_i \leq s_j\) for \(j < i\). Let \(S = \{s_i: i \in \mathbb{N}\}\). Therefore \(s\) is eventually constant, and so can't be infinitely ''strictly'' decreasing.
| |||