We can generalize the ξ notation to a much stronger notation. First we define an auxiliary function D which serves to protect against circular definitions of ordinals. There are cases:
Now, we can define Λ by
via transfinite recursion on α. This is an injective function from ΓΩ+1 to Ω itself. Then for α, β < Ω,
It is also related to the binary Veblen functions by
where α, β < Ω and k is either 0 or 1. One can show that
This notation is a kind of Ordinal collapsing function, but we choose injectivity over continuity.
To evaluate D (α), we only need to compute the value of D on a finite number of ordinals. Given an ordinal β < Ω, there are only a countable number of ordinals α for which
Here we prove that Λ is, in fact, defined on its entire intended domain ΓΩ+1. We only need to verify that the set of countable ordinals greater than D(α) and not in the image of Λ restricted to α is non-empty.
because if
then
so for some n < ω,
a contradiction!
Identifying important ordinals with Λ:
I have not read a description of Ackermann's ordinal notations from a reliable source, so this is just a guess based on the little information available in Wikipedia. The Ackermann ordinal is probably Λ (Ω3) or maybe Λ (Ω2·3) or Λ (Ω4).
I think that Buchholz's ordinal might be Λ(εΩ·ω) and the Takeuti–Feferman–Buchholz ordinal might be Λ(εΩ·ω+1).
As we know, 0 is not in the image of Λ, but 1 = Λ(0); 2 = Λ(1); etc.. We will now characterize the countable ordinals not in the image of Λ. Suppose ν is a countable ordinal not in the image of Λ. Let
Then ρω will be the next ordinal after ν which not in the image of Λ. Also any limits of ordinals not in the image are also not in the image. If ρω were in the image of Λ, then for some α
so for some n < ω,
a contradiction! So ρω is not in the image of Λ.
If ν+1 = Λ(ν) ≤ μ < ρω, then μ is in the image of Λ. For suppose otherwise, then for some n
so μ belongs to the set in the definition of ρn and thus
a contradiction! Thus every ordinal strictly between ν and ρω is in the image of Λ.
Comparison with finitary Veblen hierarchy: In what follows, α, β, γ are less than Ω and j, k, m are less than ω.
If α is less than ω, then
where k is usually 0, but sometimes 1 when necessary to skip over values which would otherwise be fixed points; j is 1, if α=0 and β<ω, otherwise it is 0 because Λ handles mere powers of ω differently.
Otherwise,
If m is at least 3 and αm≠0, then
For example,
OK? JRSpriggs ( talk) 22:39, 21 May 2022 (UTC)
The following is a write-up of my system of ordinal notations. See also Large countable ordinal, Ordinal notation, and Ordinal collapsing function.
As I said at Talk:Ordinal notation, "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.". To this end, I tried to provide a unique notation for as many ordinals as possible. Each ordinal is to be described in terms of strictly smaller ordinals, except that a quantifier-like functional is used whose bound variable ranges over some larger ordinals (these may be taken as members of the closed unbounded class of ordinals indiscernable for L which exist if 0# exists; otherwise use uncountable regular ordinals).
As described at Ordinal notation#ξ-notation, the system begins with a zero-ary function for zero, 0, and a binary pairing function, ξ (α, β), that takes care of all non-zero ordinals except the epsinums (epsilon numbers, i.e. those α for which α = ωα).
If we restrict the pairing function ξ (α, β) to Ω×Ω (where Ω is an uncountable regular ordinal such as ω1), we can define it by transfinite recursion on Ωα+β. Let ξ(α,β) = the smallest ordinal γ such that α < γ and β < γ and γ is not the value of ξ for any smaller α or for the same α with a smaller β.
At each stage Ωα+β in the construction of ξ, the set of nonzero ordinals not in the range of ξ yet is a closed unbounded subset of Ω.
Closedness: At stage zero, 0 is removed leaving [1,Ω) which is closed in Ω. At successor stages, we are removing one element (ξ(α,β)) which will not destroy the closedness, if it is not a limit point of the remainder. If it were a limit point of the remainder, then there would be an element of the remainder strictly between max(α,β)and ξ(α,β) in which case ξ(α,β) would not be the smallest ordinal in the remainder larger than α and β, a contradiction to the definition. At limit stages, we take the intersection of the sets of remaining ordinals at earlier stages which is closed because any intersection of closed sets is closed.
Unboundedness: Removing one ordinal from the unbounded remainder will not cause it to cease to be unbounded, so the only issue is at limits when one takes infinite intersections.
Alternatively, one could argue that the remainder must be unbounded at all stages because if it were not then one could construct a naming scheme for all ordinals less than Ω by using 0, ξ, and constant symbols for all the ordinals remaining at stage Ω2 which would give us a mapping from a cardinal less than Ω onto Ω which is impossible.
The value of ξ(α,β) is independent of the choice of which uncountable regular ordinal one uses for Ω provided that Ω>max(α,β). Let ξ1 be defined relative to Ω1 and let ξ2 be defined relative to Ω2 where Ω2>Ω1. If there were a difference, let ξ1(α,β)≠ξ2(α,β) be the first such difference, i.e. Ω1α+β is minimal for such a difference. The difference could not be attributed to the constraint that ξ(α,β)>max(α,β) since that is the same in both cases. So we only have to show that the remainder below Ω1 at stage Ω1α+β is the intersection of Ω1 with the remainder below Ω2 at stage Ω2α+β. The only way that the remainder could be different is if for some γ and δ, ξ2(γ,δ)<Ω1 even though either γ>Ω1 or δ>Ω1. But that is impossible because then Ω1<max(γ,δ)<ξ2(γ,δ)<Ω1.
The terms are:
There is a total ordering on the terms given by:
where:
The (well-ordered) ordinal notations are those terms which have no free variables.
Let the key, be some unspecified uncountable regular ordinal. Notice that is the least epsinum greater than that is, the smallest ordinal larger than the key which cannot be described using the pairing function and ordinals less than or equal to the key.
Define for ordinals by:
Let be the least ordinal β such that β is an epsinum (neither 0 nor in the range of ξ) and and for any
Notice that is the maximum of the 0-parts of A when A is a term for the ordinal α.
See Veblen function. For , either or Remember that ξ (0, α) = α+1.
More generally, for and k = 0 or 1. If and then k = 1. Otherwise, if and then k = 1. Otherwise, k = 0.
The Feferman–Schütte ordinal is
The Ackermann ordinal might be
The small Veblen ordinal might be
The large Veblen ordinal might be
The Bachmann–Howard ordinal might be
Let be some unspecified uncountable regular ordinal; and let be a larger unspecified uncountable regular ordinal.
Define for ordinals α less than the supremum as n goes to ω of where the function has been applied n times by:
Let be the least ordinal β such that β is an epsinum which is not in the range of and and for any γ < α.
Notice that is the maximum of the 1-parts of A when A is a term for the ordinal α.
The Bachmann-Howard ordinal might be .
I seek to show by transfinite induction on i that the terms for which the value of the indexes are less than i and the free variables are a subset of some given finite set are well-ordered and that the notations (no free variables) among them have values which constitute a transitive set of ordinals. This will be shown by extending any order-preserving mapping of keys to uncountable regular ordinals to a mapping of said terms to ordinals in an order-preserving way.
The induction is done in an omega-sequence of phases. Phase 0 covers all indexes which can be described with 0 and ξ alone, i.e. those which are less than . For each natural number n, phase n + 1 uses those new indexes which are values of ordinal notations which use indexes from phase n and earlier phases.
The full system (which may be inconsistent) is defined here.
The terms are:
There is a (hopefully) total ordering on the terms given by:
where:
The (hopefully) well-ordered ordinal notations are those terms which have no free variables.
We can generalize the ξ notation to a much stronger notation. First we define an auxiliary function D which serves to protect against circular definitions of ordinals. There are cases:
Now, we can define Λ by
via transfinite recursion on α. This is an injective function from ΓΩ+1 to Ω itself. Then for α, β < Ω,
It is also related to the binary Veblen functions by
where α, β < Ω and k is either 0 or 1. One can show that
This notation is a kind of Ordinal collapsing function, but we choose injectivity over continuity.
To evaluate D (α), we only need to compute the value of D on a finite number of ordinals. Given an ordinal β < Ω, there are only a countable number of ordinals α for which
Here we prove that Λ is, in fact, defined on its entire intended domain ΓΩ+1. We only need to verify that the set of countable ordinals greater than D(α) and not in the image of Λ restricted to α is non-empty.
because if
then
so for some n < ω,
a contradiction!
Identifying important ordinals with Λ:
I have not read a description of Ackermann's ordinal notations from a reliable source, so this is just a guess based on the little information available in Wikipedia. The Ackermann ordinal is probably Λ (Ω3) or maybe Λ (Ω2·3) or Λ (Ω4).
I think that Buchholz's ordinal might be Λ(εΩ·ω) and the Takeuti–Feferman–Buchholz ordinal might be Λ(εΩ·ω+1).
As we know, 0 is not in the image of Λ, but 1 = Λ(0); 2 = Λ(1); etc.. We will now characterize the countable ordinals not in the image of Λ. Suppose ν is a countable ordinal not in the image of Λ. Let
Then ρω will be the next ordinal after ν which not in the image of Λ. Also any limits of ordinals not in the image are also not in the image. If ρω were in the image of Λ, then for some α
so for some n < ω,
a contradiction! So ρω is not in the image of Λ.
If ν+1 = Λ(ν) ≤ μ < ρω, then μ is in the image of Λ. For suppose otherwise, then for some n
so μ belongs to the set in the definition of ρn and thus
a contradiction! Thus every ordinal strictly between ν and ρω is in the image of Λ.
Comparison with finitary Veblen hierarchy: In what follows, α, β, γ are less than Ω and j, k, m are less than ω.
If α is less than ω, then
where k is usually 0, but sometimes 1 when necessary to skip over values which would otherwise be fixed points; j is 1, if α=0 and β<ω, otherwise it is 0 because Λ handles mere powers of ω differently.
Otherwise,
If m is at least 3 and αm≠0, then
For example,
OK? JRSpriggs ( talk) 22:39, 21 May 2022 (UTC)
The following is a write-up of my system of ordinal notations. See also Large countable ordinal, Ordinal notation, and Ordinal collapsing function.
As I said at Talk:Ordinal notation, "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.". To this end, I tried to provide a unique notation for as many ordinals as possible. Each ordinal is to be described in terms of strictly smaller ordinals, except that a quantifier-like functional is used whose bound variable ranges over some larger ordinals (these may be taken as members of the closed unbounded class of ordinals indiscernable for L which exist if 0# exists; otherwise use uncountable regular ordinals).
As described at Ordinal notation#ξ-notation, the system begins with a zero-ary function for zero, 0, and a binary pairing function, ξ (α, β), that takes care of all non-zero ordinals except the epsinums (epsilon numbers, i.e. those α for which α = ωα).
If we restrict the pairing function ξ (α, β) to Ω×Ω (where Ω is an uncountable regular ordinal such as ω1), we can define it by transfinite recursion on Ωα+β. Let ξ(α,β) = the smallest ordinal γ such that α < γ and β < γ and γ is not the value of ξ for any smaller α or for the same α with a smaller β.
At each stage Ωα+β in the construction of ξ, the set of nonzero ordinals not in the range of ξ yet is a closed unbounded subset of Ω.
Closedness: At stage zero, 0 is removed leaving [1,Ω) which is closed in Ω. At successor stages, we are removing one element (ξ(α,β)) which will not destroy the closedness, if it is not a limit point of the remainder. If it were a limit point of the remainder, then there would be an element of the remainder strictly between max(α,β)and ξ(α,β) in which case ξ(α,β) would not be the smallest ordinal in the remainder larger than α and β, a contradiction to the definition. At limit stages, we take the intersection of the sets of remaining ordinals at earlier stages which is closed because any intersection of closed sets is closed.
Unboundedness: Removing one ordinal from the unbounded remainder will not cause it to cease to be unbounded, so the only issue is at limits when one takes infinite intersections.
Alternatively, one could argue that the remainder must be unbounded at all stages because if it were not then one could construct a naming scheme for all ordinals less than Ω by using 0, ξ, and constant symbols for all the ordinals remaining at stage Ω2 which would give us a mapping from a cardinal less than Ω onto Ω which is impossible.
The value of ξ(α,β) is independent of the choice of which uncountable regular ordinal one uses for Ω provided that Ω>max(α,β). Let ξ1 be defined relative to Ω1 and let ξ2 be defined relative to Ω2 where Ω2>Ω1. If there were a difference, let ξ1(α,β)≠ξ2(α,β) be the first such difference, i.e. Ω1α+β is minimal for such a difference. The difference could not be attributed to the constraint that ξ(α,β)>max(α,β) since that is the same in both cases. So we only have to show that the remainder below Ω1 at stage Ω1α+β is the intersection of Ω1 with the remainder below Ω2 at stage Ω2α+β. The only way that the remainder could be different is if for some γ and δ, ξ2(γ,δ)<Ω1 even though either γ>Ω1 or δ>Ω1. But that is impossible because then Ω1<max(γ,δ)<ξ2(γ,δ)<Ω1.
The terms are:
There is a total ordering on the terms given by:
where:
The (well-ordered) ordinal notations are those terms which have no free variables.
Let the key, be some unspecified uncountable regular ordinal. Notice that is the least epsinum greater than that is, the smallest ordinal larger than the key which cannot be described using the pairing function and ordinals less than or equal to the key.
Define for ordinals by:
Let be the least ordinal β such that β is an epsinum (neither 0 nor in the range of ξ) and and for any
Notice that is the maximum of the 0-parts of A when A is a term for the ordinal α.
See Veblen function. For , either or Remember that ξ (0, α) = α+1.
More generally, for and k = 0 or 1. If and then k = 1. Otherwise, if and then k = 1. Otherwise, k = 0.
The Feferman–Schütte ordinal is
The Ackermann ordinal might be
The small Veblen ordinal might be
The large Veblen ordinal might be
The Bachmann–Howard ordinal might be
Let be some unspecified uncountable regular ordinal; and let be a larger unspecified uncountable regular ordinal.
Define for ordinals α less than the supremum as n goes to ω of where the function has been applied n times by:
Let be the least ordinal β such that β is an epsinum which is not in the range of and and for any γ < α.
Notice that is the maximum of the 1-parts of A when A is a term for the ordinal α.
The Bachmann-Howard ordinal might be .
I seek to show by transfinite induction on i that the terms for which the value of the indexes are less than i and the free variables are a subset of some given finite set are well-ordered and that the notations (no free variables) among them have values which constitute a transitive set of ordinals. This will be shown by extending any order-preserving mapping of keys to uncountable regular ordinals to a mapping of said terms to ordinals in an order-preserving way.
The induction is done in an omega-sequence of phases. Phase 0 covers all indexes which can be described with 0 and ξ alone, i.e. those which are less than . For each natural number n, phase n + 1 uses those new indexes which are values of ordinal notations which use indexes from phase n and earlier phases.
The full system (which may be inconsistent) is defined here.
The terms are:
There is a (hopefully) total ordering on the terms given by:
where:
The (hopefully) well-ordered ordinal notations are those terms which have no free variables.