Talk:Ordinal notation

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 $lim_{n\to \infty }v(\varphi _{q(x)}(n))=v(x)$

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Power of Takeuti's notation

It is said in article that Takeuti's ordinal diagrams is very powerful notation. I'd like to know how powerful is it. What is bound of ordinal notations in this system? If this ordinal is too big to explain it here, I just wanted to ask: is it significantly larger than Ψ₀(Ω_ω) Wojowu (talk) 11:36, 15 August 2012 (UTC)[reply]

Unfortunately, it has been over thirty years since I worked on this stuff, so I am not up on the latest results. However, Larry Miller's article (1976) seems to indicate that Takeuti's system is at least as powerful as any of the others mentioned here (except of course for Kleene's O). But Takeuti's system is very hard to understand compared to the others, so it is difficult to make comparisons. JRSpriggs (talk) 17:45, 16 August 2012 (UTC)[reply]

I'm asking about this, because in this paper author constructed well-order of finite labeled trees which can be compared to some finite-order form of ordinal diagrams, and I'm interested in order type of that. In same paper it is stated (but not strictly proved) that this well-order is beyond the reach of Π¹₁ comprehension, so this must be at least Ψ₀(Ω_ω) (recalling what is said in ordinal analysis). At end of paper this is something about equivalence of trees labeled with finite numbers of labels and fixed-order ordinal diagrams to ID_n. If it resembles finitely iterated induction, so I can state that this ordering has order type of Ψ₀(Ω_ω). Wojowu (talk) 20:01, 18 August 2012 (UTC)[reply]

Recursive and non-recursive ordinal notations

I think it should be quite clear to anyone that the non-recursive ordinal notations vastly outnumber the recursive ones; this shouldn't require a proof, should it? At any rate, I've updated the intro to clearly distinguish between recursive ones and non-recursive ones. Your input and feedback would be greatly appreciated. Thanks 104.167.137.108 (talk) 00:40, 2 March 2016 (UTC)[reply]

The target audience of an article's intro is not restricted to experts, and that update appears to me like a regression (personally, I have some limited familiarity with ordinals, but not with ordinal notations). The previous introduction was not perfect either. Blaisorblade (talk) 11:03, 17 September 2022 (UTC)[reply]

Bashicu Matrix System

A mathematical amateur, one Samuel Vargovčík, has posted to the arXiv Well-Orderedness of the Bashicu Matrix System, which system is an vast generalization of the better known Bachmann notation (a mere 2x2 small-number entry matrix in the BMS). See the BMS entry on the googology wiki.

Until peer-reviewed or at least RS referenced, it's not yet suitable for the article. 2607:F470:E:22:3449:FB21:CB33:47F9 (talk) 13:07, 3 August 2023 (UTC)[reply]