Talk:Ordinal notation

From Wikipedia, the free encyclopedia

[edit] What is an ordinal notation?

To Logicnazi (talk · contribs): You inserted the following "definition" of ordinal notations following Rogers:

... a system of notations as being a map v from a set of integers D onto a segment of the ordinal numbers such that

• there is a partial recursive function k such that
  • v(x) = 0 implies k(x) = 0
  • v(x) is a successor implies k(x) =1
  • v(x) is a limit implies k(x) =2
• there is a partial recursive function p such that if v(x) is a successor then p(x) convergent and v(x) = v(p(x))+1
• there exists a partial recursive function q such that if v(x) a limit then q(x) convergent and q(x) is an index for a total function and

The members of the set D are referred to as ordinal notations or simply notations for short.

This definition is inappropriate as I will explain.

Definitions are not arbitrary; they must serve a purpose. What is the purpose of ordinal notations? An ordinal notation is something which denotes an ordinal, that is, it is a way of naming an ordinal so that we can communicate about them with others and with ourselves. In other words, they are words in a language specialized to ordinals. As with natural languages, there are many different such languages, i.e. there are many different schemes of ordinal notations. Translation between them may be difficult or even virtually impossible in some cases; and I doubt that it is possible to give an exact formal definition. This should not be too surprising in as much as there are other mathematical concepts which cannot be defined exactly, such as definable real number and large cardinal axiom. However, to describe ordinals (which are, after all, well-ordered), they must have certain properties (additional to those you described above) including (here I follow your choice of natural numbers as the symbols, although I prefer sequences of characters):

• The set of x for which v(x) exists must be recursive.
• (Equality relation) The set of pairs <x,y> for which v(x) = v(y) must be recursive.
• (Order relation) The set of pairs <x,y> for which v(x) < v(y) must be recursive.
• It should be possible to translate informal notions such as ordinal addition, ordinal multiplication, ordinal exponentiation, and the epsilon function into the language of ordinal notations. For example, there should be a partial recursive function which takes x and y to z when v(x)+v(y) = v(z).

Kleene's O does not have these properties. Furthermore, no scheme of ordinal notations could include notations for all recursive ordinals without also either: including some "notations" for things which are not ordinals (types of pseudo-well-orders); or being non-effective (non-recursive) and thus not being usable for communication by human beings. JRSpriggs (talk) 06:08, 7 March 2008 (UTC)

[edit] Feferman's theta functions -- C(alpha,beta)

To R.e.b.: In the subsection Ordinal notation#Feferman's θ functions, you said "The set C(α,β) is defined by induction on α to be the set of ordinals that can be generated from 0, ℵ₁, ℵ₂,...,ℵ_ω, by the operations of ordinal addition and the functions θ_ξ for ξ<α, and the function θ_α is defined to be the function enumerating the ordinals β with β∉C(α,β).". How is β being used in the definition of C? You only used it in the definition of the function θ_ξ as far as I can see. Also α is being used for two different things which is confusing. JRSpriggs (talk) 09:17, 10 March 2008 (UTC)

I tried to fix these problems, but the system still seems too weak to me (no collapsing). JRSpriggs (talk) 11:17, 14 March 2008 (UTC)

[edit] Buchholz's notation?

The bit that says C_v(α) contains all ordinals less than Ω_v doesn't seem to make sense because then the least ordinal not in C_v(α) would be at least Ω_v, i.e. uncountable. I thought the point was to produce notations for countable ordinals.

Maybe they meant Ω_u for all u<v ? —Preceding unsigned comment added by 85.210.115.219 (talk) 22:29, 9 May 2008 (UTC)

No, that's right. The function which produces notations for countable ordinals is ψ₀, the other ψ_v are used to produce notations for certain uncountable ordinals that are themselves used to denote countable ordinals. See the article on ordinal collapsing functions (which should be referenced from this page, urgh…) for the details. --Gro-Tsen (talk) 18:14, 10 May 2008 (UTC)