ORDINAL NUMBERS #1
Dave L. Renfro
handwritten notes I wrote about ordinals numbers
in 1991. Corrections and/or additions, if any,
will be posted in this thread, and later posts
that continue these notes will be posted in
separate threads. When I finish, I'll post the
complete table of contents, with google and Math
Forum sci.math URL's for the individual posts
that correspond to the selected parts of the
table of contents.
Almost no proofs are given in this part, since the
material is standard and can be found in most every
undergraduate level set theory text. Later installments
will include more proofs. The primary intention
of this installment is to provide a reference for
some of the basic properties of ordinal arithmetic
that will be used in proofs in later installments.
Corrections, comments, and suggestions are welcome.
NOTATION: <= and >= are "less than or equal to" and
"greater than or equal to", respectively.
w is used to denote the smallest infinite
ordinal "omega".
As is typical in mathematics, some of the
basic order-of-operations conventions are
used without comment. For example, ab + c
means (ab) + c.
TABLE OF CONTENTS
1. ORDINAL ADDITION
2. ORDINAL MULTIPLICATION
3. ORDINAL EXPONENTIATION
4. SOME CALCULATIONS
5. NOTATIONS FOR ORDINALS <= epsilon_0
6. LIMIT ORDINALS
(a) DEFINITION
(b) LIMIT ORDINALS AND ADDITION
(c) LIMIT ORDINALS AND MULTIPLICATION
(d) LIMIT ORDINALS AND EXPONENTIATION
(e) A PARADOX CONCERNING w^w
--------------------------
--------------------------
1. ORDINAL ADDITION
Recursive Definition: Fix an ordinal a. We define a + b by
transfinite recursion on b as follows:
a + 0 = a
a + (b + 1) = (a + b) + 1
a + c = sup{a + b : b < c}, if c is a nonzero limit ordinal
Note: There is also a non-recursive definition using
the left-right ordering on the union 'A union B'
of two disjoint well-ordered sets A and B, where
A has order type a and B has order type b.
Properties: associative, not commutative, continuous in the
right variable, strictly increasing in
the right variable, non-decreasing in the
left variable (not strict: 1 + w = 2 + w).
--------------------------
2. ORDINAL MULTIPLICATION
Recursive Definition: Fix an ordinal a. We define ab by
transfinite recursion on b as follows:
a0 = 0
a(b + 1) = ab + a
ac = sup{ab : b < c}, if c is a nonzero limit ordinal
Note: There is also a non-recursive definition using
the anti-lexicographic ordering on the Cartesian
product A x B of well-ordered sets A and B, where
A has order type a and B has order type b.
Remark: Cantor originally defined ab by lexicographic
ordering in 1883, but changed to anti-lexicographic
ordering in 1887 to allow for more natural
compatibility with exponentiation.
Properties: associative, not commutative, left distributive
over addition, not right distributive over
addition, continuous in the right variable,
strictly increasing in the right variable
(for nonzero ordinals), non-decreasing in the
left variable (not strict: 1w = 2w).
Corollary of left distributivity: a + a = a2.
Semi-Right Distributivity: (a + a')b <= ab + a'b.
See Sierpinski, "Cardinal and Ordinal Numbers",
pp. 332-333 for this last result.
--------------------------
3. ORDINAL EXPONENTIATION
Recursive Definition: Fix an ordinal a. We define a^b by
transfinite recursion on b as follows:
a^0 = 1
a^(b + 1) = (a^b)*b
a^c = sup{a^b : b < c}, if c is a nonzero limit ordinal
Note 1: There is also a non-recursive definition using
a last-differences ordering on the functions
in A^B that have finite support (functions
f:B --> A such that f(x) differs from min(A)
for finitely many x in B), where A and B are
well-ordered sets with order types a and b.
Note 2: For both ordinal and cardinal exponentiation,
we have 0^0 = 1.
Note 3: If a and b are countable, then a^b is countable.
Properties: not associative, not commutative, continuous
in the exponent, strictly increasing in the
exponent for bases > 1, non-decreasing in the
base for bases > 1 (not strict: 2^w = 3^w).
(a^b)(a^b') = a^(b + b') [corollary: aa = a^2]
(a^b)^b' = a^(bb')
(aa')^b can differ from (a^b)(a'^b) [a=a'=2 and b=w]
Lemma: If min{a,b} >= 2, then a + b <= ab <= a^b.
--------------------------
4. SOME CALCULATIONS
Example 1: For each n such that 1 < n < w, we have
n + w = nw = n^w = w.
Proof: n + w = sup{n + m: m < w} = w
nw = sup{nm: m < w} = w
n^w = sup{n^m: m < w}
Example 2: (w + 1)3 = (w+1) + (w+1) + (w+1)
= w + (1+w) + (1+w) + 1
= w + w + w + 1
= w3 + 1
Example 3: w^2 = (2^w)^2 = 2^(w2)
Example 4: w^w = (2^w)^w = 2^(w^2)
Example 5: w5 = w4 + w = (2^w)(2^2) + 2^w
= 2^(w+2) + 2^w
Example 6: (w+1)^w = w^w
Proof: For each n < w, we have
w^n < (w+1)^n < (w^2)^n = w^(2n).
Since sup{w^n: n < w} = sup{w^(2n): n < w} = w^w,
it follows that
(w+1)^w = sup{(w+1)^n: n < w} = w^w.
Example 7: For each n such that 1 < n < w, we have
n^(w^w) = w^(w^w). [contrast this with n^w = w]
Proof: Using w = 1+w, we have w^w = w^(1+w) = (w)(w^w),
and so n^(w^w) = n^(w*w^w) = (n^w)^(w^w) = w^(w^w).
[The last equality comes from n^w = w.]
--------------------------
5. NOTATIONS FOR ORDINALS <= epsilon_0
The following web page (3 different URL's to minimize
future web rot) gives pretty much the same type of
"build up to epsilon_0" that I gave.
"How to Count Up to the First Epsilon" by Libor Behounek
http://web.ff.cuni.cz/~behounek/eps55.htm
http://www.volny.cz/behounek/logic/papers/ordcalc/eps55.html
http://tinyurl.com/fqz7b
--------------------------
6. LIMIT ORDINALS
(a) DEFINITION
An ordinal c is said to be a limit ordinal if
c is not a successor ordinal.
Remark: 0 is a limit ordinal.
Lemma: c is a limit ordinal
<==> (a < c ==> a+1 < c)
<==> 2c = c.
(b) LIMIT ORDINALS AND ADDITION
Lemma 1: Let b > 0. Then a + b is a limit ordinal
<==> b is a limit ordinal.
Lemma 2: a is not limit <==> a = b + n
for some ordinals b and 0 < n < w.
In the case of "==>", the ordinals
b and n are unique.
(c) LIMIT ORDINALS AND MULTIPLICATION
Lemma 1: ab is a limit ordinal <==>
[ (a is limit) or (b is limit)].
We can't replace "or" with "and" above.
[Note that w2 cannot be a product of
two limit ordinals a and b. This is
because neither a nor b could be zero,
and therefore their product would be
>= (w)(w) > (w)(2).]
Corollary: For all ordinals a and b, aw and wb are
limit ordinals.
Lemma 2: c is not a limit ordinal <==> c = wb + n
for some ordinals b and 0 < n < w.
In the case of "==>", the ordinals
b and n are unique.
(d) LIMIT ORDINALS AND EXPONENTIATION
Lemma 1: c a limit ordinal and a > 1
==> a^c is a limit ordinal.
Lemma 2: c a limit ordinal and b nonzero
==> c^b is a limit ordinal.
Corollary: If a > 1 and b > 0, then both
a^w and w^b are limit ordinals.
Lemma 3: If min{a,b} >= w, then a^b is a limit ordinal.
This fails for addition: a = w and b = w+1.
This fails for multiplication: a = b = w+1
Note that (w+1)(w+1) = (w+1)w + (w+1)
= [(w+1)w + w] + 1 is not a limit ordinal.
Lemma 4: a^b is a limit ordinal <==>
[ (a isn't 1 and b >= w) or (a is limit and b > 0)].
(e) A PARADOX CONCERNING w^w?
Since every collection of ordinals is well-ordered
under the "less than" ordering relation on ordinals,
we can assign an ordinal to the collection that
"enumerates" the collection. We will call this
"enumerating" ordinal for the collection the
_order_type_ of that collection.
Example: The collections {2, 8, 9} and {1, w, w^2} each
has order type 3. The collection {w, w^2, w^3, ...}
has order type w, and the collection
{w, w^2, w^3, ..., w^w} has order type w + 1.
Definition: Given any ordinal a, we let L(a) be the
order type of
{b: b < a and b is a limit ordinal}.
Examples:
L(0) = 0 L(17) = 1 L(w5) = 5 L(w5 + 1) = 6
L(w^2) = w L(w^3) = w^2 L( (w^6)(4) ) = (w^5)(4)
Theorem: L(w^w) = w^w
Proof: Since a <= b ==> L(a) <= L(b), for each n < w we have
L(w^w) >= L(w^(n+1) = w^n.
Hence, L(w^w) >= sup{w^n: n < w} = w^w.
Also, since a <= L(a) for all ordinals a, we have
L(w^w) <= w^w.
The "paradox" is that w^w is the w^w'th limit ordinal.
In other words, there is no difference in size, as measured
by ordinals, between all ordinals less than w^w and the
smaller collection of limit ordinals less than w^w.
This fixed-point behavior of L occurs with many other
functions as well (e.g. any non-decreasing continuous
function from the countable ordinals to the countable
ordinals, for example), and this behavior has many
applications.
--------------------------
--------------------------
Dave L. Renfro
G. A. Edgar
L. Renfro <renf...@cmich.edu> wrote:
> a^c = sup{a^b : b < c}, if c is a nonzero limit ordinal
It was pointed out in this newsgroup a while back that this gives the
wrong value for 0^w
--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/
Dave L. Renfro
from the version I posted on Sept. 22. The most
significant of these occur in Section 3. I'd like
to thank G. A. Edgar for calling my attention to
what seems to be a common oversight in many texts
concerning the limit ordinal part of the recursive
definition for exponentiation of ordinal numbers.
This is the first of several posts based on some
handwritten notes I wrote about ordinals numbers
in 1991. Corrections and/or additions, if any,
will be posted in this thread, and later posts
that continue these notes will be posted in
separate threads. When I finish, I'll post the
complete table of contents, with google and Math
Forum sci.math URL's for the individual posts
that correspond to the selected parts of the
table of contents.
Very few proofs are given in this part, since
the material is standard and can be found in
most undergraduate level set theory texts. Later
installments will include more proofs. The primary
intention of this installment is to provide a
reference for some of the basic properties of
ordinal arithmetic that will be used in proofs
in later installments.
Corrections, comments, and suggestions are welcome.
This is formatted for fixed font style. Much of what
follows will be very difficult to read if you do not
view this using fixed font style. If you do not know
how to adjust for this in whatever manner you're
reading this (web browser, e-mail, newsreader, etc.),
you can simply copy and paste the entire text material
onto a text editor, such as MicroSoft's Notepad or
Wordpad.
NOTATION: <= and >= are "less than or equal to" and
"greater than or equal to", respectively.
w is used to denote the smallest infinite
ordinal "omega".
As is typical in mathematics, some of the
basic order-of-operations conventions are
used without comment. For example, ab + c
means (ab) + c.
LIST OF SECTIONS
1. ORDINAL ADDITION
2. ORDINAL MULTIPLICATION
3. ORDINAL EXPONENTIATION
4. SOME CALCULATIONS
5. NOTATIONS FOR ORDINALS <= epsilon_0
6. LIMIT ORDINALS
(a) DEFINITION
(b) LIMIT ORDINALS AND ADDITION
(c) LIMIT ORDINALS AND MULTIPLICATION
(d) LIMIT ORDINALS AND EXPONENTIATION
(e) A PARADOX CONCERNING w^w
--------------------------
--------------------------
1. ORDINAL ADDITION
Recursive Definition: Fix an ordinal a. We define a + b by
transfinite recursion on b as follows:
a + 0 = a
a + (b + 1) = (a + b) + 1
a + c = sup{a + b : b < c}, if c is a nonzero limit ordinal
Note: There is also a non-recursive definition using
the left-right ordering on the union 'A union B'
of two disjoint well-ordered sets A and B, where
A has order type a and B has order type b.
Properties: associative, not commutative, continuous in
the right variable, not continuous in the left
variable (sup{n + w: n < w} = w < w2
= sup{n: n < w} + w), strictly increasing
in the right variable, non-decreasing in the
left variable (not strict: 1 + w = 2 + w).
Infinite Ordinals Characterization: 1 + a = a <==> a >= w.
--------------------------
2. ORDINAL MULTIPLICATION
Recursive Definition: Fix an ordinal a. We define ab by
transfinite recursion on b as follows:
a0 = 0
a(b + 1) = ab + a
ac = sup{ab : b < c}, if c is a nonzero limit ordinal
Note: There is also a non-recursive definition using
the anti-lexicographic ordering on the Cartesian
product A x B of well-ordered sets A and B, where
A has order type a and B has order type b.
Ordinal multiplication can also be defined directly
from transfinite sums, where all the terms are the
same. Although this assumes that transfinite sums
have been dealt with, some texts use this approach.
Remark: Cantor originally defined ab by lexicographic
ordering in 1883, but changed to anti-lexicographic
ordering in 1887 to allow for more natural
compatibility with exponentiation.
Properties: associative, not commutative, left distributive
over addition, not right distributive over
addition, continuous in the right variable,
not continuous in the left variable
(sup{nw: n < w} = w < w^2 = sup{n: n < w} * w),
strictly increasing in the right variable
(for nonzero ordinals), non-decreasing in the
left variable (not strict: 1w = 2w),
Corollary of left distributivity: a + a = a2.
(This also follows from the recursive definition.)
Semi-Right Distributivity: (a + a')b <= ab + a'b.
This result is due to Seymour Sherman, "Some new
properties of transfinite ordinals", Bulletin of the
American Mathematical Society 47 (1941), 111-116.
A proof can also be found in Sierpinski's book "Cardinal
and Ordinal Numbers", pp. 332-333. Sherman also gives
a necessary and sufficient condition for equality
(but not Sierpinski, although it can be extracted
from the proof) that involves part of the Cantor
normal form representation for the ordinals.
--------------------------
3. ORDINAL EXPONENTIATION
Recursive Definition: Fix an ordinal a. We define a^b by
transfinite recursion on b as follows:
a^0 = 1
a^(b + 1) = (a^b)*b
a^c = sup{a^b : 0 < b < c}, if c is a nonzero limit ordinal
Remark: Many textbook authors use "b < c" instead of
"0 < b < c". A smaller number of these texts
get into trouble by using "b < c" and then
overlooking the fact that this implies 0^c = 1
for all nonzero limit ordinals c and/or overlooking
the fact that exponentiation would not be continuous
when the base is 0, such as:
Devlin [1979, p. 90 & p. 91, Lemma 5.2]
Forster [2003, p. 150, Definition 54 & comments
in the paragraph that follows]
Halmos [1960, Section 21, p. 84, bottom]
Holz/Steffens/Weitz [bottom p. 31 & p. 33,
Lemma 1.4.3(c,i)]
Monk [1969, Section 14, pp. 103-104]
Roitman [1990, Definition 15 on p. 81
& Definition 27 on p. 86]
Vaught [1995, p. 125, top & 2.4(d)]
Other textbooks restrict the recursive definition
to bases > 0. Some of these leave 0^b undefined,
while others define separately 0^0 = 1 and 0^b = 0
for b > 0. Enderton [1977, p. 232, bottom] is a
rare example of a textbook that actually discusses
this issue explicitly.
Dalen/Doets/Swart [1978, p. 175] uses "0 < b < c".
Levy [1979/2002, p. 124] uses "0 < b < c".
See also the sci.math thread "Is 0^omega = 0 or 1?"
http://groups.google.com/group/sci.math/msg/45fb20651621fae0
Note 1: There is also a non-recursive definition using
a last-differences ordering on the functions
in A^B that have finite support (functions
f:B --> A such that f(x) differs from min(A)
for finitely many x in B), where A and B are
well-ordered sets with order types a and b.
Ordinal exponentiation can also be defined directly
from transfinite products, where all the factors
are the same. Although this assumes that transfinite
products have been dealt with, some texts use this
approach.
Note 2: For both ordinal and cardinal exponentiation,
we have 0^0 = 1.
Note 3: If a and b are countable, then a^b is countable.
Properties: not associative, not commutative, continuous
in the exponent, not continuous in the base
(sup{n^w: n < w} = w < w^w = sup{n: n < w} ^ w),
strictly increasing in the exponent for bases > 1,
non-decreasing in the base for bases > 0
(not strict: 2^w = 3^w).
(a^b)(a^b') = a^(b + b') [corollary: aa = a^2]
(a^b)^b' = a^(bb')
(aa')^b can differ from (a^b)(a'^b) [a=a'=2 and b=w]
Lemma: If min{a,b} >= 2, then a + b <= ab <= a^b.
Proof: [a+b <= ab] Fix an ordinal a. We will prove the
result by transfinite induction on ordinals b >= 2.
Initial Step: a + 2 <= a + a = a2.
Successor Ordinal Step: If a + b <= ab, then
a + (b + 1) = (a + b) + 1 <= ab + 1 < ab + a
= a(b + 1).
Limit Ordinal Step: Assume c is a nonzero limit ordinal
and a + b <= ab for each 1 < b < c. Then we have
a + c = sup{a + b : b < c} [recursive definition of +]
= sup{a + b : 1 < b < c}
<= sup{ab : 1 < b < c} [induction hypothesis]
= sup{ab : b < c}
= ac [recursive definition of *]
[ab <= a^b] Fix an ordinal a. We will prove the
result by transfinite induction on ordinals b >= 2.
Initial Step: a2 <= aa = a^2.
Successor Ordinal Step: If ab <= a^b, then
a(b + 1) = ab + a <= a^b + a <= (a^b)a = a^(b+1),
where we used the addition/multiplication inequality,
which was just proved, for the next to last step.
Limit Ordinal Step: Assume c is a nonzero limit ordinal
and ab <= a^b for each 1 < b < c. Then we have
ac = sup{ab : b < c} [recursive definition of *]
= sup{ab : 1 < b < c}
<= sup{a^b : 1 < b < c} [induction hypothesis]
= sup{a^b : 0 < b < c}
= a^c [recursive definition of ^]
Question: Does there exist an inequality version for any
of the "failed" exponential distributivity
relations, analogous to the "Semi-Right
Distributivity" property in Section 2 above?
--------------------------
4. SOME CALCULATIONS
Example 1: For each n such that 1 < n < w, we have
n + w = nw = n^w = w.
Proof: n + w = sup{n + m: m < w} = w
nw = sup{nm : m < w} = w
n^w = sup{n^m : m < w} = w
--------------------------
--------------------------
6. LIMIT ORDINALS
(a) DEFINITION
Remark 1: 0 is a limit ordinal.
Remark 2: Some authors restrict the term "limit ordinal"
to nonzero ordinals. In most situations, I think
there is more harm for a casual reader to think
"limit" includes 0 (when it really excludes 0)
than to think "limit" excludes 0 (when it really
includes 0). The convention I've chosen also forces
us to be explicit when a limit ordinal statement
requires "nonzero", which should decrease a casual
reader from overlooking this restriction.
Lemma: c is a limit ordinal
<==> (a < c ==> a+1 < c)
<==> 2c = c.
(b) LIMIT ORDINALS AND ADDITION
Lemma 1: Let b > 0. Then a + b is a limit ordinal
<==> b is a limit ordinal.
Lemma 2: d is not limit <==> d = b + n
for some ordinals b and 0 < n < w.
In the case of "==>", the ordinals
b and n are unique.
(c) LIMIT ORDINALS AND MULTIPLICATION
Lemma 1: cc' is a limit ordinal <==>
[ (c is limit) or (c' is limit)].
We can't replace "or" with "and" above.
Proof of last statement: Note that w2 cannot
be a product of two limit ordinals c and c'.
This is because neither c nor c' could be zero,
and therefore their product would be >= ww > w2.
(The last inequality is from the fact that
multiplication is strictly increasing in the
right variable.)
Remark: The product closure rules for limit and successor
ordinals is the same as that for even and odd
integers under the identification
'limit ordinal' <---> 'even' and
'successor ordinal' <---> 'odd'.
In fact, an ordinal b is sometimes classified as
even or odd (especially in matters relating to
the ordinal hierarchies of Borel sets or Baire
functions) according as to whether the natural
number n < w is even or odd when b is written
uniquely as the sum of a limit ordinal and n
(this follows from the results in this sub-section).
In this classification, all limit ordinals
are even.
Corollary 1: For all ordinals a and b, aw and wb are
limit ordinals.
Corollary 2: (c is limit) <==> (there exists b)(c = wb)
Remark: In Corollary 2 above, we can't replace "c = wb"
with "c = bw" in the ==> half. [c = w2 is a limit
ordinal that cannot be written as bw for some
ordinal b.]
Lemma 2: d is not a limit ordinal <==> d = wb + n
r.e.s.
> Recursive Definition: Fix an ordinal a. We define a + b by
> transfinite recursion on b as follows:
>
> a + 0 = a
>
> a + (b + 1) = (a + b) + 1
>
> a + c = sup{a + b : b < c}, if c is a nonzero limit ordinal
The definition of a + 1 has been omitted.
>
> a^(b + 1) = (a^b)*b
That should be ... *a, of course.
Dave L. Renfro
>> a + 0 = a
>>
>> a + (b + 1) = (a + b) + 1
>>
>> a + c = sup{a + b : b < c}, if c is a nonzero limit ordinal
>
> The definition of a + 1 has been omitted.
It's not needed. Using b=0 in the middle equation gives this.
Well, technically speaking, I guess it does looks circular!
What's really going on is that we have
a + S(b) = S(a + b)
where S is the successor function. Thus, two of the +'s
in the middle equation have to do with ordinal addition,
and the other two +'s refer to "successor". With successor
having been previously defined (see any set theory text),
one can then prove the theorem S(a) = a + 1 for all ordinals a.
If I remember correctly, I think "successor" is defined
for every set A as S(A) = A union {A}.
>> a^(b + 1) = (a^b)*b
>
> That should be ... *a, of course.
Ooops!
Dave L. Renfro
Aatu Koskensilta
> If I remember correctly, I think "successor" is defined
> for every set A as S(A) = A union {A}.
You do, remember correctly that is.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
r.e.s.
>> The definition of a + 1 has been omitted.
>
> It's not needed. Using b=0 in the middle equation gives this.
> Well, technically speaking, I guess it does looks circular!
Of course we are speaking technically ;)
It ceases to be circular once a + 1 is defined.
> What's really going on is that we have
>
> a + S(b) = S(a + b)
>
> where S is the successor function.
[...]
> If I remember correctly, I think "successor" is defined
> for every set A as S(A) = A union {A}.
Yes, exactly. It's the definition a + 1 = S(a),
with S(a) = a union {a}, that was omitted.
Aatu Koskensilta
> Yes, exactly. It's the definition a + 1 = S(a),
> with S(a) = a union {a}, that was omitted.
No. S(a) was simply *written* as a + 1 in the recursion equations - a
common enough practice not worth whining about, even if, strictly
speaking, it is, if not abuse of notation, at least potentially
confusing to the some more pedantically inclined. The value of a + 1,
where + is the recursively defined function whence a + 1 is *not* taken
to be simple another way of writing S(a), but read instead as a + (0+1)
= a + S(0), can be calculated using the recursion equations given by
Dave, yelding correctly S(a).
Dave L. Renfro
> No. S(a) was simply *written* as a + 1 in the recursion
> equations - a common enough practice not worth whining
> about, even if, strictly speaking, it is, if not abuse
> of notation, at least potentially confusing to the some
> more pedantically inclined.
Well, I don't want to get bogged down on minutia, but if
it's something conceptually important and it can be dealt
with briefly, which can be done in this case, I will.
I happened to glance at sci.math just before turning off
my computer to leave work today when I noticed the reply
to my post, so I made a few quick comments before leaving.
However, on the drive home, it occurred to me that r.e.s.
was probably aware of everything I wrote, but I decided I
still should make a short comment about it in the next
version (and there certainly will be another one, because
of my a^(b + 1) = (a^b)*b oversight).
For those wondering where things are headed, here's
an outline of the next four installments. There will
be more after these (normal functions on w_1, clubs,
diagonal intersections, regressive functions, etc.),
but I haven't outlined how that will proceed sufficiently
to give specific section titles. If I don't tire of this,
I'd like to continue by then describing certain Bachmann
like ordinal notations for ordinals beyond gamma_0. This
is something I've never really looked at carefully, but
I've always wanted to. I'll probably try to follow Larry
W. Miller's 1976 paper "Normal functions and constructive
ordinal notations", which I've known about since at least
1985. (I thought I'd mentioned it several times in sci.math,
but according to google I've only mentioned it once, back
in December 1999.)
----------------- ORDINALS #2 -----------------
7. SUBTRACTION THEOREM
8. DIVISION THEOREM
9. LOGARITHM THEOREM
10. CANTOR NORMAL FORM
----------------- ORDINALS #3 -----------------
11. PRINCIPAL ORDINALS
(a) PRINCIPAL ORDINALS OF ADDITION
(b) PRINCIPAL ORDINALS OF MULTIPLICATION
(c) PRINCIPAL ORDINALS OF EXPONENTIATION
(d) FURTHER PROPERTIES OF GAMMA, DELTA, AND EPSILON NUMBERS
----------------- ORDINALS #4 -----------------
12. ORDINAL TETRATION AND BEYOND
(a) ORDINAL TETRATION
(b) PRINCIPAL ORDINALS OF TETRATION
(c) ORDINAL HYPER-TETRATION
(d) FIXED POINTS OF THE GAMMA NUMBER SEQUENCE
(e) FIXED POINTS OF THE DELTA NUMBER SEQUENCE
(f) FIXED POINTS OF THE EPSILON NUMBER SEQUENCE
Note: Ordinal tetration isn't strong enough to give a
straightforward closed form formula (i.e. without
having to use a sup and ellipses) for the b'th
epsilon number. However, such a formula can be
given in terms of the hyper-tetration operation.
The fixed points of the epsilon number sequence
wind up being the > w principal ordinals of
hyper-tetration.
----------------- ORDINALS #5 -----------------
13. A GLIMPSE AT DONNER/TARSKI'S EXTENDED ARITHMETIC
(a) BASIC PROPERTIES OF THEIR OPERATIONS
(b) PRINCIPAL ORDINALS OF THEIR OPERATIONS
(c) DONER/TARSKI EXTENDED ARITHMETIC FIXED POINT THEOREM
Dave L. Renfro
r.e.s.
> r.e.s. wrote:
>> Yes, exactly. It's the definition a + 1 = S(a),
>> with S(a) = a union {a}, that was omitted.
>
> No. S(a) was simply *written* as a + 1 in the recursion equations - a
> common enough practice not worth whining about, even if, strictly
> speaking, it is, if not abuse of notation, at least potentially
> confusing to the some more pedantically inclined. The value of a + 1,
> where + is the recursively defined function whence a + 1 is *not* taken
> to be simple another way of writing S(a), but read instead as a + (0+1)
> = a + S(0), can be calculated using the recursion equations given by
> Dave, yelding correctly S(a).
Standardly, successor is defined as S(a) = a u {a}, then ordinal
addition is defined recursively by reference to S() -- and that's
what Dave's reply said he intended. So it was simply a matter of
his having omitted to say this explicitly. My pointing out the
omission is intended as constructive advice for the sake of
beginners, not as "whining" (as you put it).
Aatu Koskensilta
> Standardly, successor is defined as S(a) = a u {a}, then ordinal
> addition is defined recursively by reference to S() -- and that's
> what Dave's reply said he intended.
Sure. But as with e.g. arithmetical recursive definitions, it is just as
standard to "sloppily" - for some values of "sloppy" - to write x+1 for
x u {x}, even if the general addition function has not yet been
introduced. Then in recursion equations terms of the form x+1 are
interpreted as x u {x}, and so forth, as context dictates.
> So it was simply a matter of his having omitted to say this explicitly.
> My pointing out the omission is intended as constructive advice for the
> sake of beginners, not as "whining" (as you put it).
That was a poor choice of words on my part, and was not really intended
to reflect on the quality of your comments. My apologies. It perhaps is
somewhat confusing to, at least some, beginners to write x+1 for x u {x}
when defining the general addition function, but, alas, this is common
practice in many contexts; and that was all I wished to point out.
Ben Rudiak-Gould
> Lemma 2: d is not limit <==> d = b + n
> for some ordinals b and 0 < n < w.
>
> In the case of "==>", the ordinals
> b and n are unique.
I assume you want to restrict b to be a limit ordinal here?
-- Ben
Dave L. Renfro
>> Lemma 2: d is not limit <==> d = b + n
>> for some ordinals b and 0 < n < w.
>>
>> In the case of "==>", the ordinals
>> b and n are unique.
Ben Rudiak-Gould wrote:
> I assume you want to restrict b to be a limit ordinal here?
Ooops! Yes, I guess that should be the case, at least
when 0 < d < w. For that matter, even when d > w,
since (for example) d = w + 4 is equal to (w+3) + 1, etc.
Dave L. Renfro