A description/proof of that Cantor normal form is unique
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of Cantor normal form.
- The reader admits the logarithm theorem of the ordinal numbers arithmetic.
- The reader admits the subtraction theorem of the ordinal numbers arithmetic.
- The reader admits the left cancellation law of the ordinal numbers arithmetic.
- The reader admits the proposition that any descending sequence of ordinal numbers is finite.
Target Context
- The reader will have a description and a proof of the proposition that the Cantor normal form for any nonzero ordinal number is unique.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Description
For any nonzero ordinal number, \(o\), \(o\) can be expressed as \(o = \omega^{o_1} n_1 + \omega^{o_2} n_2 + . . . + \omega^{o_k} n_k\), which is a Cantor normal form, where \(\omega\) is the natural numbers set, \(o_i\) is an ordinal number, and \(n_i\) is a natural number (as an ordinal number), but that \(\{\langle o_1, n_1 \rangle, \langle o_2, n_2 \rangle, . . ., \langle o_k, n_k \rangle\}\) is the only possibility.
2: Proof
By sequentially applying the logarithm theorem of the ordinal numbers arithmetic, \(o\) can be expressed as that: 1st, \(o = \omega^{o_1} n_1 + \rho_1\) where \(\rho_1 \in \omega^{o_1}\), 2nd, \(\rho_1 = \omega^{o_2} n_2 + \rho_2\) where \(\rho_2 \in \omega^{o_2}\) and \(o_2 \in o_1\), because \(\omega^{o_2} \in= \rho_1 \in \omega^{o_1}\), and so on, and the sequence, \(\omega^{o_1}, \omega^{o_2}, . . .\) is finite by the proposition that any descending sequence of ordinal numbers is finite. The expression is unique as far as it is generate by the procedure, but the issue is whether there is another expression generated otherwise, or not.
Let us prove that \(\omega^\lambda n \in \omega^\sigma\) for any \(\lambda \in \sigma\) and any natural number \(n\). \(\omega^\sigma = \omega^\sigma 1 + 0\) is the unique form for the logarithm theorem of the ordinal numbers arithmetic. As \(\omega^\lambda \in \omega^\sigma\), there is a \(\rho_1\) such that \(\omega^\sigma = \omega^\lambda + \rho_1\) by the subtraction theorem of the ordinal numbers arithmetic, but \(\omega^\lambda \in \rho_1\) because it cannot be a form for the logarithm theorem of the ordinal numbers arithmetic and obviously \(\rho_1\) cannot equal \(\omega^\lambda\). Then, \(\omega^\lambda 2 = \omega^\lambda + \omega^\lambda \in \omega^\lambda + \rho_1 = \omega^\sigma\), so, by the subtraction theorem of the ordinal numbers arithmetic, there is a \(\rho_2\) such that \(\omega^\sigma = \omega^\lambda 2 + \rho_2\), but \(\omega^\lambda \in \rho_2\) again, and \(\omega^\lambda 3 = \omega^\lambda 2 + \omega^\lambda \in \omega^\lambda 2 + \rho_2 = \omega^\sigma\), and so on. So, for any natural number \(n\), \(\omega^\lambda n \in \omega^\sigma\).
Let us suppose that \(o = \omega^{o'_1} n'_1 + \omega^{o'_2} n'_2 + . . . + \omega^{o'_l} n'_l\) (\(o'_1, o'_2, . . ., o'_l\) is in the descending order without loss of generality) is another expression. \(o \in \omega^{o'_1} (n'_1 + 1)\), because \(\omega^{o'_l} n'_l \in \omega^{o'_{l - 1}}\), so, \(\omega^{o'_{l - 1}} n'_{l - 1} + \omega^{o'_l} n'_l \in \omega^{o'_{l - 1}} (n'_{l - 1} + 1)\); \(\omega^{o'_{l - 1}} (n'_{l - 1} + 1) \in \omega^{o'_{l - 2}}\), so, \(\omega^{o'_{l - 2}} n'_{l - 2} + \omega^{o'_{l - 1}} (n'_{l - 1} + 1) \in \omega^{o'_{l - 2}} (n'_{l - 2} + 1)\), and so on. If \(o'_1 \in o_1\), \(o \in \omega^{o'_1} (n'_1 + 1) \in \omega^{o_1} \in \omega^{o_1} n_1 \in o\), a contradiction. By the symmetricalness, also \(o_1 \in o'_1\) is impossible, so, \(o_1 = o'_1\).
If \(n'_1 \in n_1\), \(n'_1 + 1 \in= n_1\), but \(o \in \omega^{o'_1} (n'_1 + 1) \in= \omega^{o_1} (n_1) \in= o\), a contradiction. By the symmetricalness, also \(n_1 \in n'_1\) is impossible, so, \(n_1 = n'_1\).
By the left cancellation law of the ordinal numbers arithmetic, \(\omega^{o_2} n_2 + \omega^{o_3} n_3 + . . . + \omega^{o_k} n_k = \omega^{o'_2} n'_2 + \omega^{o'_3} n'_3 + . . . + \omega^{o'_l} n'_l\). And by the likewise argument, \(o_2 = o'_2\) and \(n_2 = n'_2\), and so on. Obviously, \(l\) has to equal \(k\).
