Natural Numbers:Well-Ordering - Revision history

Khanh at 20:05, 7 November 2021

2021-11-07T20:05:19Z

Lila at 19:25, 12 October 2021

2021-10-12T19:25:16Z

Lila at 19:24, 12 October 2021

2021-10-12T19:24:02Z

Lila: /* Resources */

2021-10-12T19:22:30Z

Resources

Lila: /* Relationship to the axiom of choice */

2021-10-12T19:21:59Z

Relationship to the axiom of choice

Lila: /* Transfinite recursion */

2021-10-12T19:20:42Z

Transfinite recursion

Lila: /* Transfinite recursion */

2021-10-12T19:20:00Z

Transfinite recursion

Lila: /* Transfinite recursion */

2021-10-12T19:19:26Z

Transfinite recursion

Lila: /* Induction by cases */

2021-10-12T19:15:36Z

Induction by cases

Lila at 19:14, 12 October 2021

2021-10-12T19:14:14Z

@@ Line 58: / Line 58: @@
 Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify a ''unique'' value for ''A''<sub>''α''+1</sub>, given the sequence up to ''α'', but will specify only a ''condition'' that ''A''<sub>''α''+1</sub> must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step.  For inductions and recursions of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.
-==Resources==
+== Licensing ==
-* [https://en.wikipedia.org/wiki/Well-ordering_principle Well-ordering principle], Wikipedia
+Content obtained and/or adapted from:
-* [https://en.wikipedia.org/wiki/Transfinite_induction Transfinite induction], Wikipedia
+* [https://en.wikipedia.org/wiki/Well-ordering_principle Well-ordering principle, Wikipedia] under a CC BY-SA license

← Older revision		Revision as of 19:25, 12 October 2021
Line 1:		Line 1:
		+
		+	=Well-Ordering Principle=
	In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which <math>x</math> precedes <math>y</math> if and only if <math>y</math> is either <math>x</math> or the sum of <math>x</math> and some positive integer (other orderings include the ordering <math>2,4,6,...</math>; and <math>1,3,5,...</math>).		In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which <math>x</math> precedes <math>y</math> if and only if <math>y</math> is either <math>x</math> or the sum of <math>x</math> and some positive integer (other orderings include the ordering <math>2,4,6,...</math>; and <math>1,3,5,...</math>).

@@ Line 16: / Line 16: @@
 ==Induction by cases==
-Let <math>P(\alpha)</math> be a property defined for all ordinals <math>\alpha</math>. Suppose that whenever <math>P(\beta)</math> is true for all  <math>\beta < \alpha</math>, then <math>P(\alpha)</math> is also true. It is not necessary here to assume separately that <math>P(0)</math> is true.  As there is no <math>\beta</math> less than 0, it is vacuously true that for all <math>\beta<0</math>, <math>P(\beta)</math> is true.</ref>  Then transfinite induction tells us that <math>P</math> is true for all ordinals.
+Let <math>P(\alpha)</math> be a property defined for all ordinals <math>\alpha</math>. Suppose that whenever <math>P(\beta)</math> is true for all  <math>\beta < \alpha</math>, then <math>P(\alpha)</math> is also true. It is not necessary here to assume separately that <math>P(0)</math> is true.  As there is no <math>\beta</math> less than 0, it is vacuously true that for all <math>\beta<0</math>, <math>P(\beta)</math> is true. Then transfinite induction tells us that <math>P</math> is true for all ordinals.
 Usually the proof is broken down into three cases:
@@ Line 48: / Line 48: @@
 ==Relationship to the axiom of choice==
-Proofs or constructions using induction and recursion often use the axiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice.<ref>In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation ''R'' is set-like: for any ''x'', the collection of all ''y'' such that ''y''&nbsp;''R''&nbsp;''x'' must be a set.</ref> For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.
+Proofs or constructions using induction and recursion often use the axiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice. In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation ''R'' is set-like: for any ''x'', the collection of all ''y'' such that ''y''&nbsp;''R''&nbsp;''x'' must be a set. For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.
 The following construction of the Vitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:

← Older revision		Revision as of 19:22, 12 October 2021
Line 58:		Line 58:
	==Resources==		==Resources==
	* [https://en.wikipedia.org/wiki/Well-ordering_principle Well-ordering principle], Wikipedia		* [https://en.wikipedia.org/wiki/Well-ordering_principle Well-ordering principle], Wikipedia
		+	* [https://en.wikipedia.org/wiki/Transfinite_induction Transfinite induction], Wikipedia

@@ Line 48: / Line 48: @@
 ==Relationship to the axiom of choice==
-Proofs or constructions using induction and recursion often use the [[axiom of choice]] to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice.<ref>In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation ''R'' is set-like: for any ''x'', the collection of all ''y'' such that ''y''&nbsp;''R''&nbsp;''x'' must be a set.</ref> For example, many results about [[Borel sets]] are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.
+Proofs or constructions using induction and recursion often use the axiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice.<ref>In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation ''R'' is set-like: for any ''x'', the collection of all ''y'' such that ''y''&nbsp;''R''&nbsp;''x'' must be a set.</ref> For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.
-The following construction of the [[Vitali set]] shows one way that the axiom of choice can be used in a proof by transfinite induction:
+The following construction of the Vitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:
-: First, [[well-order]] the [[real number]]s (this is where the axiom of choice enters via the [[well-ordering theorem]]), giving a sequence <math> \langle r_{\alpha} | \alpha < \beta \rangle </math>, where &beta; is an ordinal with the [[cardinality of the continuum]].  Let ''v''<sub>0</sub> equal ''r''<sub>0</sub>.  Then let ''v''<sub>1</sub> equal ''r''<sub>''α''<sub>1</sub></sub>, where ''α''<sub>1</sub> is least such that ''r''<sub>''α''<sub>1</sub></sub>&nbsp;&minus;&nbsp;''v''<sub>0</sub> is not a [[rational number]].  Continue; at each step use the least real from the ''r'' sequence that does not have a rational difference with any element thus far constructed in the ''v'' sequence.  Continue until all the reals in the ''r'' sequence are exhausted.  The final ''v'' sequence will enumerate the Vitali set.
+: First, well-order the real numbers (this is where the axiom of choice enters via the well-ordering theorem), giving a sequence <math> \langle r_{\alpha} | \alpha < \beta \rangle </math>, where &beta; is an ordinal with the cardinality of the continuum.  Let ''v''<sub>0</sub> equal ''r''<sub>0</sub>.  Then let ''v''<sub>1</sub> equal ''r''<sub>''α''<sub>1</sub></sub>, where ''α''<sub>1</sub> is least such that ''r''<sub>''α''<sub>1</sub></sub>&nbsp;&minus;&nbsp;''v''<sub>0</sub> is not a rational number.  Continue; at each step use the least real from the ''r'' sequence that does not have a rational difference with any element thus far constructed in the ''v'' sequence.  Continue until all the reals in the ''r'' sequence are exhausted.  The final ''v'' sequence will enumerate the Vitali set.
 The above argument uses the axiom of choice in an essential way at the very beginning, in order to well-order the reals. After that step, the axiom of choice is not used again.
-Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify a ''unique'' value for ''A''<sub>''α''+1</sub>, given the sequence up to ''α'', but will specify only a ''condition'' that ''A''<sub>''α''+1</sub> must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step.  For inductions and recursions of [[countable set|countable]] length, the weaker [[axiom of dependent choice]] is sufficient. Because there are models of [[Zermelo–Fraenkel set theory]] of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.
+Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify a ''unique'' value for ''A''<sub>''α''+1</sub>, given the sequence up to ''α'', but will specify only a ''condition'' that ''A''<sub>''α''+1</sub> must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step.  For inductions and recursions of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.
 ==Resources==
 * [https://en.wikipedia.org/wiki/Well-ordering_principle Well-ordering principle], Wikipedia

@@ Line 45: / Line 45: @@
 Note that we require the domains of ''G''<sub>2</sub>, ''G''<sub>3</sub> to be broad enough to make the above properties meaningful.  The uniqueness of the sequence satisfying these properties can be proved using transfinite induction.
-More generally, one can define objects by transfinite recursion on any [[well-founded relation]] ''R''. (''R'' need not even be a set; it can be a [[proper class]], provided it is a [[binary relation#Relations over a set|set-like]] relation; i.e. for any ''x'', the collection of all ''y'' such that ''yRx'' is a set.)
+More generally, one can define objects by transfinite recursion on any well-founded relation ''R''. (''R'' need not even be a set; it can be a proper class, provided it is a set-like relation; i.e. for any ''x'', the collection of all ''y'' such that ''yRx'' is a set.)
 ==Relationship to the axiom of choice==

@@ Line 34: / Line 34: @@
 * '''Transfinite Recursion Theorem (version 1)'''. Given a class function <math>G:V\to V</math> (where <math>V</math> is the class of all sets), there exists a unique transfinite sequence <math>F: \text{Ord}\to V</math> (where Ord is the class of all ordinals) such that
-:''F''(''α'') = ''G''(''F'' <math>\upharpoonright</math> ''α'') for all ordinals ''α'', where <math>\upharpoonright</math> denotes the restriction of ''F'''s domain to ordinals <{{Hair space}}''α''.
+:''F''(''α'') = ''G''(''F'' <math>\upharpoonright</math> ''α'') for all ordinals ''α'', where <math>\upharpoonright</math> denotes the restriction of ''F'''s domain to ordinals < ''α''.
 As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is the following:

@@ Line 29: / Line 29: @@
 '''Transfinite recursion''' is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal.
-As an example, a [[basis (vector space)|basis]] for a (possibly infinite-dimensional) [[vector space]] can be created by choosing a vector <math>v_0</math> and for each ordinal ''α'' choosing a vector that is not in the [[Linear span|span]] of the vectors <math>\{v_{\beta}\mid\beta<\alpha\}</math>. This process stops when no vector can be chosen.
+As an example, a basis for a (possibly infinite-dimensional) vector space can be created by choosing a vector <math>v_0</math> and for each ordinal ''α'' choosing a vector that is not in the span of the vectors <math>\{v_{\beta}\mid\beta<\alpha\}</math>. This process stops when no vector can be chosen.
 More formally, we can state the Transfinite Recursion Theorem as follows:
-* '''Transfinite Recursion Theorem (version 1)'''. Given a class function<ref>A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a [[function (mathematics)|function]] because its domain and codomain are not sets.</ref> ''G'': ''V'' → ''V'' (where ''V'' is the [[Class (set theory)|class]] of all sets), there exists a unique [[transfinite sequence]] ''F'': Ord → ''V'' (where Ord is the class of all ordinals) such that
+* '''Transfinite Recursion Theorem (version 1)'''. Given a class function <math>G:V\to V</math> (where <math>V</math> is the class of all sets), there exists a unique transfinite sequence <math>F: \text{Ord}\to V</math> (where Ord is the class of all ordinals) such that
 :''F''(''α'') = ''G''(''F'' <math>\upharpoonright</math> ''α'') for all ordinals ''α'', where <math>\upharpoonright</math> denotes the restriction of ''F'''s domain to ordinals <{{Hair space}}''α''.

@@ Line 16: / Line 16: @@
 ==Induction by cases==
-Let <math>P(\alpha)</math> be a property defined for all ordinals <math>\alpha</math>. Suppose that whenever <math>P(\beta)</math> is true for all  <math>\beta < \alpha</math>, then <math>P(\alpha)</math> is also true.<ref>It is not necessary here to assume separately that <math>P(0)</math> is true.  As there is no <math>\beta</math> less than 0, it is [[vacuously true]] that for all <math>\beta<0</math>, <math>P(\beta)</math> is true.</ref>  Then transfinite induction tells us that <math>P</math> is true for all ordinals.
+Let <math>P(\alpha)</math> be a property defined for all ordinals <math>\alpha</math>. Suppose that whenever <math>P(\beta)</math> is true for all  <math>\beta < \alpha</math>, then <math>P(\alpha)</math> is also true. It is not necessary here to assume separately that <math>P(0)</math> is true.  As there is no <math>\beta</math> less than 0, it is vacuously true that for all <math>\beta<0</math>, <math>P(\beta)</math> is true.</ref>  Then transfinite induction tells us that <math>P</math> is true for all ordinals.
 Usually the proof is broken down into three cases:
 * '''Zero case:''' Prove that <math>P(0)</math> is true.
-* '''Successor case:''' Prove that for any [[successor ordinal]] <math>\alpha+1</math>, <math>P(\alpha+1)</math> follows from <math>P(\alpha)</math> (and, if necessary, <math>P(\beta)</math> for all <math>\beta < \alpha</math>).
+* '''Successor case:''' Prove that for any successor ordinal <math>\alpha+1</math>, <math>P(\alpha+1)</math> follows from <math>P(\alpha)</math> (and, if necessary, <math>P(\beta)</math> for all <math>\beta < \alpha</math>).
-* '''Limit case:''' Prove that for any [[limit ordinal]] <math>\lambda</math>, <math>P(\lambda)</math> follows from <math>P(\beta)</math> for all <math>\beta < \lambda</math>.
+* '''Limit case:''' Prove that for any limit ordinal <math>\lambda</math>, <math>P(\lambda)</math> follows from <math>P(\beta)</math> for all <math>\beta < \lambda</math>.
-All three cases are identical except for the type of ordinal considered.  They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a [[limit ordinal]] and then may sometimes be treated in proofs in the same case as limit ordinals.
+All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.
 ==Transfinite recursion==

@@ Line 12: / Line 12: @@
 [[File:omega-exp-omega-labeled.svg|thumb|300px|Representation of the ordinal numbers up to <math>\omega^{\omega}</math>. Each turn of the spiral represents one power of <math>\omega</math>. Transfinite induction requires proving a '''base case''' (used for 0), a '''successor case''' (used for those ordinals which have a predecessor), and a '''limit case''' (used for ordinals which don't have a predecessor).]]
-'''Transfinite induction''' is an extension of [[mathematical induction]] to [[well-order|well-ordered sets]], for example to sets of [[ordinal number]]s or [[cardinal number]]s.
+==Transfinite induction==
 ==Induction by cases==
-Let <math>P(\alpha)</math> be a [[Property (philosophy)#Properties in mathematics|property]] defined for all ordinals <math>\alpha</math>. Suppose that whenever <math>P(\beta)</math> is true for all  <math>\beta < \alpha</math>, then <math>P(\alpha)</math> is also true.<ref>It is not necessary here to assume separately that <math>P(0)</math> is true.  As there is no <math>\beta</math> less than 0, it is [[vacuously true]] that for all <math>\beta<0</math>, <math>P(\beta)</math> is true.</ref>  Then transfinite induction tells us that <math>P</math> is true for all ordinals.
+Let <math>P(\alpha)</math> be a property defined for all ordinals <math>\alpha</math>. Suppose that whenever <math>P(\beta)</math> is true for all  <math>\beta < \alpha</math>, then <math>P(\alpha)</math> is also true.<ref>It is not necessary here to assume separately that <math>P(0)</math> is true.  As there is no <math>\beta</math> less than 0, it is [[vacuously true]] that for all <math>\beta<0</math>, <math>P(\beta)</math> is true.</ref>  Then transfinite induction tells us that <math>P</math> is true for all ordinals.
 Usually the proof is broken down into three cases: