# I Question Regarding Linear Orders

#### SSequence

Consider a linear order (on $\mathbb{N}$). Now it will have a comparison relation associated with it (a function from $\mathbb{N}^2$ to $\{0,1\}$). Let's denote it as $\prec$.

I want to define a certain notion, which I will just call "uniformity" (just for brevity). For each $i \in \mathbb{N}$, we want to define a (linear) order on a set $S_i \subseteq \mathbb{N}$. Let's denote the corresponding relation for this order as $\prec_i$ (a function from $(S_i)^2$ to $\{0,1\}$). The set $S_i$ is defined as:
$S_i=\{x\in \mathbb{N} \,\,|\,\, i \preceq x\}$
The function $\prec_i$ agrees with the function $\prec$ on all points of its domain (so, in this sense, it is just a restriction of the function $\prec$). Intuitively, it is simply the order obtained by removing all element that are less than $i$ in the original ordering.

Now every linear order has a well-ordered initial segment, and hence the order-type of that initial segment being an ordinal. I will call this ordinal "initial ordinal" for the rest of this post. Now we want define the notion of uniformity for the order corresponding to $\prec$. The conditions for it are:
(1) The initial ordinal for all $\prec_i$ ($i \in \mathbb{N}$) must be equal to the same ordinal say $\alpha$.
(2) For any $i \in \mathbb{N}$, $\prec_i$ can never represent a well-order.

For any linear order we say that it contains a certain segment of order-type $O$ when we find some initial sections and final sections such that the whole order can visualised as:
initial_segment, O, final_segment

For any (countable) ordinal $\alpha$ define $\alpha^*$ as order-type that is obtained by reversing a well-order relation (of $\mathbb{N}$) with order-type $\alpha$. That is in the well-order relation of $\alpha$ we switch $1$'s with $0$'s and $0$'s with $1$'s. For example, here are examples of two linear orders (on $\mathbb{N}$) with order-type $\omega^*$ and $(\omega \cdot 2)^*$:
$......,6,5,4,3,2,1,0$
$......,13,11,9,7,5,3,1 \,\,$ $\,\,......,12,10,8,6,4,2,0$

Now define a certain order-type as AB (meaning informally that B is placed to the right of A):
(A) $\alpha$
(B) $\omega^*$
So by AB I essentially mean placing $\omega^*$ to the right of $\alpha$. For example, if I had written $\omega$ instead of $\omega^*$ in B, then AB would simply mean the order-type $\alpha+\omega$.

Now here is the question. For some given value of $\alpha$, can we find example of any linear order relation $\prec$ that is uniform but doesn't contain the segment AB described above in it.

=================

Here are few examples that I think will help clarify the question a bit (since I didn't describe it well formally). If we define $Z$ to be the order-type of integers (under their usual comparison relation) and $N=\omega$ to be the order-type of natural numbers (under their usual comparison relation), then consider the following order-types:
(1) $N,Z,Z,Z,Z,Z,......$
(2) $Z,Z,Z,Z,Z,Z,......$
(3) $......,Z,Z,Z,Z,Z,Z,Z,Z,Z......$

Any linear-order whose order-type is (1) would be uniform. No matter which "starting position" we pick, we will exactly encounter $\omega$ many elements before the well-ordered part ends. Same can be said for (2) and (3). Further we observe that the second condition is also satisfied for (1),(2),(3).

Here is an example of first condition for uniformity being satisfied but second condition failing:
(4) $Z,Z,Z,Z,Z,Z,......,N$

Here is an example of first condition for uniformity failing:
(5) $N,Z,N,Z,N,Z,N,Z,N,......$
The order-type (5) isn't uniform. For example, if we pick our "starting position" from within the "very first" N, we will encounter $\omega$ many elements before the well-ordered part ends. However, if we pick our starting position from within any of the Z's we will observe that the initial ordinal turns out to be $\omega \cdot 2$. We must have the same initial ordinal for every starting position.

Now here is an observation about (1),(2) and (3). We could write them as:
(1) $\omega,\omega^*,\omega,Z,Z,Z,Z,......$
(2) $\omega^*,\omega,\omega^*,\omega,Z,Z,Z,Z,......$
(3) $......,Z,Z,Z,Z,\omega^*,\omega,\omega^*,\omega,Z,Z,Z......$

We can observe that if we take the initial_segment to be [empty], [$\omega^*$],[ $......,Z,Z,Z,Z,\omega^*$] respectively in (1),(2),(3) then right after it we have a segment of the form $\omega,\omega^*$. Since, in our case, we noted $\alpha=\omega$ (the initial ordinal in uniformity condition), we note that we can write it as: $\alpha,\omega^*$.
Main Question Ends at this Point

============================================================

Motivation: Here is some context for the question. I will describe it very briefly. It is related to the paper https://arxiv.org/abs/math/9808093 (in particular, the relevant theorems are 2.2 (page-8), 3.2 (page-17). It is also mentioned that, starting from empty tape, it is impossible to halt at $\omega_{CK}$.

Suppose we consider all decidable/recursive sets. Consider the indexes of these functions/sets. We first determine these first and then write the indexes in an increasing order. Then we sort out and keep those indexes whose corresponding function encodes a linear order. This can be easily checked. Now call the set the remaining set $C \subset \mathbb{N}$.

Further by theorem-2.2 we will be able to sort out all those which represent a well-order. But because we can't halt at $\omega_{CK}$ (starting from empty tape), we have to assume that there will be some linear orders relations (in the set $C$) whose initial ordinal will be $\omega_{CK}$. If we don't have that we could halt at $\omega_{CK}$ because the set $C$ will become empty right at that point (and a flag cell can signal this).

If we simply check all the functions in the usual manner, the set $C$ will become empty $\omega_{CK} \cdot \omega$ probably(?). However, what I was thinking was that to check whether function representing a linear-order represents a well-order or not, we could try to be a bit more efficient. Normally we find the smallest position, then the next smallest one and so on.

However, what if we tried all starting positions in our linear order? Remember that the starting positions are described by natural numbers so it isn't difficult to do so. However, we will have to be a bit careful. We don't want to compute the initial ordinal of first starting position, then the second one and so on (we could get unlucky and the initial ordinal for first position could be $\omega_{CK}$). Instead we complete first stage for all positions. Then we complete the second stage for all positions (and so on). This way if any single starting position has an initial ordinal less than $\omega_{CK}$ it would be detected. And actually, in that case we would be able to figure out whether linear order is well-order or not in recursive length of time.

There is a possiblity that perhaps some peculiar machine limitation (since $\omega$ tape machines can have this sometimes I think) that prevents this construction (probably needs to be looked more closely). However, it seems to me that there is a more important question that probably should be asked first I feel. That is that based on last paragraph we must assume the existence of recursive sets which encode a linear order whose initial ordinal is equal to $\omega_{CK}$ for all starting positions. But it seems the linear-order (in its order-type), at some point, can't have a $\omega^*$ right after the $\omega_{CK}$ part (this would require some further justification, but I will skip it for brevity).

So the question I stated is related to this (in the more general sense so that the condition of being recursive etc. are removed), and asks for example of any uniform linear-order whose initial ordinal is equal (say $\alpha$) for all starting positions and further it doesn't contain a $\omega^*$ right after $\alpha$.

Related Set Theory, Logic, Probability, Statistics News on Phys.org

#### WWGD

Gold Member
I suggest you summarize the question, make it more concise, easier to read.

#### SSequence

Here is the question (while skipping some descriptions):
Every linear order (on some fixed/given set) has a well-ordered initial segment, and hence the order-type of that initial segment being an ordinal. Let's call this ordinal "initial ordinal". We want define the notion of uniformity (just naming it generically) for a linear order:
(a) The initial ordinal must be the same no matter which starting position we use (and remove the elements that are smaller than the starting position). Note that removing all the elements smaller than a given position (while preserving the ordering for all remaining elements) will also lead to a linear order (just on a smaller set).
(b) For any starting position, after removing all elements that are smaller than starting position (while preserving the order for remaining ones), we must not get a well-order.

Secondly I defined the notion of $\alpha^*$ (which is basically the mirror of $\alpha$ in a sense) corresponding to any ordinal $\alpha$. The question is that for a uniform linear order, can one prove or disprove (via an example) that it always contains a section of the form:
$\beta,\omega^*$ ($\beta$ immediately followed by $\omega*$)
within it at some point. Here $\beta$ denotes the (unique) initial ordinal that corresponds to any starting position in the given (uniform) linear order.

Also, the question is divided into three sections (the first two are related to main question). I wrote down a good number of examples in the second section. I think looking at them should probably clarify the question.

Last edited:

#### SSequence

I think the answer to question I asked is negative via the following example:
Let's denote the order-type of rational numbers as $Q$. Now we can define $Q_{\omega}$ (or $Q_{\omega^2}$ for example) as the order-type obtained by replacing each individual "point" by "$\omega$". A linear order on $\mathbb{N}$ can be constructed (recursively) with this order-type and will have no section within it that will be of the type $\omega+\omega^*$.

Last edited:

#### SSequence

While the previous post answers the question I originally asked, it seems it doesn't resolve my confusion. It seems to me that perhaps there might be something more that can be said. I thought about this after making the last post, so I don't make any claim of correctness. Nevertheless, I will describe the idea I had (meanwhile I will try to think about it more carefully over many times to see where I might be missing something or making a mistake).

============

First note that we can add another condition to uniformity (described in previous posts):
(c) the linear order should have a minimal element.

If the construction which I describe below (and in the OP) can indeed be implemented (which can be determined by very careful examination) specifically on machines described in the paper then: if it is correct then it seems to contradict theorem-8.8 in the linked paper. For obvious reasons, it would be safe to assume as being exceedingly unlikely that there would be a logical mistake in the proof of that theorem. So I will probably try to check all aspects (after making the post) to see where I am making a mistake.

============

Anyway, here is the point I was thinking. If we look at the context/motivation section of the OP, the main barrier to why the construction I described goes beyond $\omega_{CK}$ time is because of uniform linear orders (formed by decidable/recursive sets) whose initial ordinal is always equal to $\omega_{CK}$. So one question to ask is whether we can try devising a method that would remove all such orders in less than CK time (while not removing arbitrarily large well-orders described by decidable sets).

Consider any uniform linear order (with initial ordinal $\omega_{CK}$) whatsoever described by some recursive set. Let's denote its comparison relation by $less_1:\mathbb{N}^2 \rightarrow \{0,1\}$. Now we wish to form another linear-order defined by the relation $less_2:\mathbb{N}^2 \rightarrow \{0,1\}$. The idea here is that if the order-type of original order was $R$ then the order-type of this new order will be $R+\omega$.
The definition for $less_2$ is simply:
$less_2(x,y)=less_1(x/2,y/2)$ ----if x and y are both even
$less_2(x,y)=$truth value of $x<y$ ----if x and y are both odd
$less_2(x,y)=1$ ----if x is even and y is odd
$less_2(x,y)=0$ ----if x is odd and y is even

The new order-type can be seen as:
(order-type R formed with even numbers) $+$ ($1,3,5,7,9,11,13,......$)
The main thing to note here is that if $less_1$ is a recursive function then so will be $less_2$.

Let's note that in the procedure in the OP a set $C \in \mathbb{N}$(of indexes) corresponding to all linear orders (formed with decidable sets) was formed in the beginning. We want to append the following one-time procedure right after the formation of set $C$.

First we wish to identify all those functions (via indexes) in set $C$, which towards the "very end" contain a section exactly of the form:
$1,3,5,7,9,11,13$
Further we require that $1$ must have not have any predecessor element (note: this can be easily checked by the machine because of the underlying relations being recursive).

We need to consider carefully which kind of functions will be identified. Certainly some (but definitely not all) functions with order-type $\alpha+\omega$ ($\alpha<\omega_{CK}$ being a limit) will be identified. But so will many functions that correspond to uniform linear orders AND in the end contain that section. Note that this will still leave all all functions forming ordinals of form $\omega^2 \cdot x$ ($x<\omega_{CK}$).
A couple of points here:
First we won't be identifying a function like:
$1,3,5,7,9,11,13,.....\,\,$ $\,\,0,2,4,6,8,10,12,.......$
since the required section is in the beginning and not in the end.
Secondly all functions forming $\omega^2 \cdot x$'s will not be identified because they don't have any "line" towards the end. And thirdly, something like the following will not be identified either (because $1$ has a predecessor):
$2,4,6,8,10,12,......\,\,$ $\,\,0,1,3,5,7,9,11,13,.....$

Also, note that in the above we have just identified some functions (via indexes) in the set $C$. As of yet, we haven't removed anything from $C$ yet. We will first modify all the functions obtained in a fixed/preset manner described below.

Now generically denote a function that we identified from set $C$ as $less_1:\mathbb{N}^2 \rightarrow \{0,1\}$ then we want to form a function $less_2:\mathbb{N}^2 \rightarrow \{0,1\}$ as (need to check):
$less_2(x,y)=less_1(2x,2y)$
The point is that the original function formed an order-type $R+\omega$ and we modified it to form order-type $R$.

It seems (perhaps a mis-step on my part?) that with this modification we have identified all functions forming limit ordinals (that is, ones of form $\omega \cdot x$, where $x<\omega_{CK}$). But more substantially it seems that we also have identified all functions describing uniform linear orders with this modification. Now we use the "program equivalence" function [meaning one that takes two indexes as input returns true iff the two indexes represent equivalent (ordinary) programs] and remove every single index from the set $C$ that corresponds to family of functions we obtained. Note that program equivalence is just an arithmetic function so it is easy for the machines in question.

But there are two main things, it seems, that need to be considered:
(i) What have we actually removed.
(ii) Have we actually left anything in the set $C$?

(i) It seems that we have removed functions for both (a) all uniform linear orders and (b) all functions describing limit values less than $\omega_{CK}$. To see (b) first consider an arbitrarily chosen (recursive) well-order for $\omega^2$ as follows (for convenience, I have chosen one based on the usual cantor pairing function):
$0,1,3,6,10,.......\,\,\,2,4,7,11,......\,\,\,5,8,12,......\,\,\,9,13,.......\,\,\,14,.......$
Well how and why instances of all programs forming this function will be removed? The reason is because the following well-order for $\omega^2+\omega$ is also recursive:
$[0,2,6,12,20,.......\,\,4,8,14,22,......\,\,10,16,24,......\,\,18,26,.......\,\,28,.......]+[1,3,5,7,9,11,13,......]$

And the way the procedure I described above is supposed to work is that it will take the function corresponding to well-order relation for $\omega^2+\omega$ above and then it will modify that well-order to exactly get the well-order relation for well-order of $\omega^2$ which I just described above (and then the equivalence function removes all indexes corresponding to given function for $\omega^2$ ..... which was chosen arbitrarily).

And, for the same reason, it seems to me that all uniform linear orders in the set $C$ will also be removed by this process (please correct if I have made a mistake here since this is the main point). For example, consider any arbitrary uniform linear-order in set $C$ with order-type $R$. Now its underlying relation is recursive. But that implies that we can now form a recursive relation which just uses even numbers to form the order-type $R$(0 replacing 0, 2 replacing 1, 4 replacing 2, .....) and, in the end, adds the section $1,3,5,7,9,11,.....$ [note that $1$ will never have any predecessor here as long as we are appending this section to a uniform linear order]. This recursive relation describing $R+\omega$ will be identified in the set $C$, modified to form the "original" relation of type $R$ and then all programs forming this relation will be removed.

Also, note that whether all non-uniform linear orders are removed or not doesn't matter since they can be handled with construction in OP.

(ii) Now it might seem like we have removed everything in the set $C$ but maybe not? The point is that while we have removed many well-orders in the set $C$, we do want to keep arbitrarily large (below $\omega_{CK}$) well-orders in our set, otherwise the construction wouldn't be of any use.

It doesn't seem to me that well-orders for any non-limit elements can be removed (please correct if I have made a mistake). Re-call that we identified the following section in our linear-orders towards the very end (with $1$ not having any predecessor):
$1,3,5,7,9,11,13,15,.......$
So, for well-orders, we identified some functions forming values of the form $\alpha+\omega$ ($\alpha$ being a limit less than $\omega_{CK}$). Note that $\alpha$ will have to be a limit because we required that $1$ can't have any predecessor. After that we removed the $\omega$ part to form a well-order for $\alpha$. It doesn't seem possible to me that we could get $\alpha$ as a non-limit.

So it seems that the construction in the OP should work? (or perhaps more like I made an erroneous step somewhere). One minor detail to add is that in the construction in OP we simulated one stage for all starting positions, second stage for all starting positions and so on. Because we only have well-orders for non-limit elements now we need to add a stipulation that we will ignore start positions that lead to halt in $< \omega$ stages.

P.S.
I could have described the construction in more organised manner I think (since one-half of it I described in OP and the other half in this post), but it's only worth writing it in a fully organised form once it is checked to a reasonable degree of certainty. I will think over it next few days. Due to the simplicity of the basic idea, I think if there is a mistake hopefully I would be able to spot it relatively quickly.

Last edited:

#### SSequence

I think I will put the construction I described in last part of post#1 and in post#5 in a an organised form. I have also thought of a simplification of one aspect of the construction. Of course the advantage to an organised description is that it becomes easier to understand and also easy to spot an error if there is one (and it seems it would have to be a silly one, since the construction is quite short and simple).

But anyway, I will do that in the post that follows this one. Before that, I will first describe the main idea in the theorem (for paper linked in OP) that is relevant to the construction (since the construction I described is just a modification of the procedure in that theorem). I will of course describe things in my own words, while just focusing on aspects that are more relevant to specific discussion in the thread. Hopefully it will make the post (following this one) easier to understand.

theorems 2.2 (page-8)
Given any function from N2N2 to {0,1}{0,1}, suppose we encode it as a function from NN to {0,1}{0,1} in any reasonably obvious way. If this encoded function is given as input then the machine can always decide whether it describes the well-order relation (for a well-order of NN) with some order-type (say XX).

For the purpose of this question, it is important to describe the main idea that is discussed in proof of theorem-2.2. Suppose we are given a function f:N→{0,1}f:N→{0,1}. Now let's denote the comparison relation (from N2N2 to {0,1}{0,1}) induced by this function (after "deciphering" it) is <f<f. We want to know that whether <f<f is a well-order relation or not. First we verify the <f<f is a linear order (on NN). After that, the idea is to proceed in stages. Intuitively, at each stage αα we have stored all the elements that occur in positions <α<α and we want to determine the αα-th minimal element (if one exists). So we just use a set AαAα that changes as the stages proceed. Initially we have A0=ϕA0=ϕ. For convenience, we let Bα=N−AαBα=N−Aα denote the complement of AαAα (note that initially B0=NB0=N).

At beginning some stage αα, suppose the elements of BαBα in strictly increasing order were b0,b1,b2,b3,b4,......b0,b1,b2,b3,b4,....... First we set-up a cell which serves as flag (it will be set to 00 initially before we start our processing in each stage). We set up a variable (say vv) which is initially set to b0b0. Furthermore, we have a counter that ranges from i=0i=0 to i<ωi<ω. For each ii we make the comparison bi+1<bibi+1<bi. If this comparison turns out to be false, we do nothing and increase ii by 11. If the comparison bi+1<bibi+1<bi turns out to be true then we check whether bi+1∈Bαbi+1∈Bα. If both conditions in previous sentence turn out to be true, then we do two things: (1) Set the variable vv to bi+1bi+1 (2) simply change the flag cell to 11 and back to 00 again. In the limit, when ωω stages pass, we can simply check the flag. If it's 11 we return false (the given <f<f doesn't describe a well-order). That's because the value 11 in the flag cell (at the end of a stage) implies that it oscillated infinitely often in the limit. If the flag is 00, then suppose the value VV was stored in the variable vv. We set:
Aα+1=Aα∪{V}Aα+1=Aα∪{V}
Bα+1=Bα−{V}Bα+1=Bα−{V}
Note that since values are only ever added to AA and only ever removed from BB, there is an obvious way to form these sets on limit stages. We can halt and return true when we discover that, at some stage XX we have AX=ϕAX=ϕ (or alternatively BX=NBX=N).

The above paragraph is similar to how the procedure is described in the paper. It might be added (in case it isn't clear) that there is a slightly less efficient way to find Aα+1Aα+1 (from AαAα) too. At each stage αα, we are just looking for an element xx with the following property:
∃x∈Bα∀y∈Bα∃x∈Bα∀y∈Bα [x≠y→x<fy][x≠y→x<fy]
When we find this element, it will be removed from AA and added to BB (in preparing for the next stage). If such an element exists for each stage (until we run into a stage where AA becomes empty) then ff encodes a well-order. Otherwise, if such an element doesn't exist at some stage (before AA becomes empty), then ff doesn't encode a well-order.

==============================

A bit of search seems to show that linear-orders based on decidable sets are quite a well-studied topic. At any rate, anything specific from what is mentioned below is not used. However, I thought it was interesting enough to mention (it is certainly relevant).

Another paper that might be of interest:

The recursion theory involved is few notches too advanced for me. However, the most relevant part (in context of the topic) is right at the beginning. The author seems to describe certain recursive linear orders (presumably ones defined on NN, that can be described by recursive sets) whose order-type can be written as:
ωCK⋅(1+η)+α=(ωCK⋅+ωCK⋅η)+αωCK⋅(1+η)+α=(ωCK⋅+ωCK⋅η)+α
where α<ωCKα<ωCK and ηη is order-type of rationals in the interval (0,1)(0,1).

Now if someone read the definition for a "uniform linear order" which I posted in main question of post#1 and then in post#3, one could note that:
---- when α≠0α≠0, then the uniformity condition fails
---- when α=0α=0, then the uniformity condition is satisfied

EDIT:
I deleted the post after this one, because I identified the mistake after writing it in an organised way.

Last edited:

#### SSequence

Heh I feel pretty silly about post#5. Here is the issue with post#5 (and the method in post I deleted) ......... both of which are basically along very similar lines. The method deletes programs for all limit elements $<\omega_{CK}$. The problem it causes is that we have to add an extra stipulation of the form (towards the end of post#5):
"One minor detail to add is that in the construction in OP we simulated one stage for all starting positions, second stage for all starting positions and so on. Because we only have well-orders for non-limit elements now we need to add a stipulation that we will ignore start positions that lead to halt in $<\omega$ stages."

This is regarding construction which uses all starting positions and hence goes over $\omega_{CK}$ time for only those linear orders where the initial ordinal is always $\omega_{CK}$. However, adding this detail has an unintended side-effect (which isn't minor). But when we remove well-orders for all limit elements, we have no choice but to add this stipulation. Now consider an order-type of form $R+n$ say [where $R$ is (recursive) linear-order whose initial ordinals is always $\omega_{CK}$ and $n<\omega$]. The method will stumble over $\omega_{CK}$ time for all order-types of these forms (due to this extra stipulation).

==============================

But that isn't the reason for bumping this thread. I have thought of a (short) method which avoids all the deletion stuff from post#5. Instead it does something else. It still uses the "simultaneous start states" construction in OP in an essential way. I will post it in a few hours (unless I find some trivial issue). Perhaps I will feel silly about that again (but I suppose that's part of thinking over things). It definitely does feel worth taking a look at it at least though.

P.S. post#6 isn't displaying correctly for some reason (maybe its just me?).

#### SSequence

Now here is a different method which I thought of. Let's consider the case of recursive linear-orders specifically. I will first describe little bit detail for the "simultaneous start positions" construction in OP (basically because that's the central element). Some of it is copy-paste from my deleted post.

For simplicity, let's just focus/restrict our attention to recursive linear-orders. Given a comparison relation $\prec$ for a recursive linear-order: for any $i \in \mathbb{N}$ we can define the relation $\prec_i$ (described in the very beginning of OP). We can convert $\prec_i$ from a linear-order on $S_i$ to one on $\mathbb{N}$ if we wish. The main point is that we can define an "initial ordinal" $\alpha_i$ corresponding to every value $i$ which describes the order-type of the initial well-ordered segment corresponding to $\prec_i$.

Now lets define (defined for the order $\prec$):
$\alpha_{min}=min\{ \alpha_i | i \in \mathbb{N} \}$

==============================

Description of Simultaneous Start Procedure
Now lets look at the procedure in first-half of post#6. Suppose we are given a relation $<_f$ which describes a linear-order, but doesn't describe a well-order. The main thing to note is that the initial well-ordered segment for $<_f$ can still be extracted in the same manner.

In fact, if we look at theorem-3.2 --page-17 (for paper linked in OP) it seems to use an r.e. relation whose initial ordinal is $\omega_{CK}$. I am guessing that the r.e. relation used would be describing a linear-order on a subset of $\mathbb{N}$. It wouldn't be difficult to convert the relation to be one defined on $\mathbb{N}$ (the relation wouldn't be r.e. anymore, but it shouldn't matter). In fact, this is how the machine gets $\omega_{CK}$ time by discovering the initial well-ordered segment of this relation. The machine spends some extra time to find whether there is a minimal element after this. Because there isn't one, it halts a little time later.

The actual procedure find the smallest element, second smallest element, and proceeding in a generic manner finds the $\alpha$-th smallest element. The very first time the number of stages reach the order-type of well-order encoded by $<_f$, it halts. If $<_f$ is a linear-order but not a well-order, it just stops when the stage becomes equal to the initial ordinal.

However, we can modify the procedure so that it uses all possible starting positions and proceed from there. More precisely, if comparison relation of the linear-order was $\prec$, then as in post#1, we can define $\prec_i$:

For each $i \in \mathbb{N}$, we want to define a (linear) order on a set $S_i \subseteq \mathbb{N}$. Let's denote the corresponding relation for this order as $\prec_i$ (a function from $(S_i)^2$ to $\{0,1\}$). The set $S_i$ is defined as:

$S_i=\{x \in \mathbb{N}| i \preceq x\}$

The function $\prec_i$ agrees with the function $\prec$ on all points of its domain (so, in this sense, it is just a restriction of the function $\prec$). Intuitively, it is simply the order obtained by removing all element that are less than $i$ in the original ordering.
For the purpose of convenience, we might want to convert $\prec_i$ to form a linear-order on $\mathbb{N}$ (instead of $S_i$), which should be quite easy. However, it doesn't seem to make an essential difference.

Note that in the first iteration, we want to complete the first stage for all starting positions. In the second iteration, we want to complete the second stage for all starting positions. In the $\alpha$-th iteration, we complete the $\alpha$-th stage for all starting positions. What we do not want to do is pick up one starting position and not stopping until we find its initial ordinal.

Now the main thing to ask is whether there is a certain advantage to use all possible starting positions? In a certain sense, the answer is yes. First suppose that $\prec$ describes a well-order for an ordinal of the form $\alpha=\omega^x$ ($x \geq 1$). No matter which starting position we use, the number of iterations before halting would always be $\alpha$. Now suppose that $\prec$ describes a linear-order (but not a well-order). In that case, the number of iterations before halting will always be equal to $\alpha_{min}$ (the smallest order-type corresponding to some start position for $\prec$).

In the context of a recursive linear order, what that means is that unless $\alpha_{min}=\omega_{CK}$, the above procedure will always halt in $<\omega_{CK}$ time (for a recursive linear-order). This is true because it is an easy exercise to show $\alpha_{min} \leq \omega_{CK}$ for any recursive linear-order (I have skipped the proof but let me know if there is any doubt about this). The worst case scenario is $\alpha_{min} = \omega_{CK}$ and this is what the simultaneous start positions procedure can't handle (that is, the procedure will take $>\omega_{CK}$ time to process these linear-orders).

Last edited:

#### SSequence

And now here is what I was thinking. What I am trying to avoid is the issue in post#5 (which I described in post#7). What happened was that removal of every program/index corresponding to certain well-orders [in case of post#5, all limit ordinals $<\omega_{CK}$] forced us to add an exception to "simultaneous start procedure". And this exception caused the procedure to stumble [above $\omega_{CK}$ in processing time] for certain (recursive) linear orders with $\alpha_{min}<\omega$, even when we removed all programs/indexes for those that had $\alpha_{min}=\omega_{CK}$.

Now once again we identify all recursive linear orders (that is, linear orders based on decidable sets). Store the indexes for the corresponding programs in set $C \subset \mathbb{N}$. Corresponding to every index/program in set $C$, we modify it in a fixed manner. There are no deletions etc. Only a fixed way to modify every index/program in $C$.

How we make the modification has to be important. In the OP I defined $\prec_i$ corresponding to the relation $\prec$. I sometimes call this (inclusive) "right-cut". Since this keeps the element $i$ and all the elements to the "right" of it while removing all elements to the "left". I think what we can do is make a left-cut corresponding to every program in set $C$ (the left-cut being non-inclusive and made for element $0$). Meaning for any relation $\prec$, we preserve the ordering for all elements less than $0$, while removing $0$ and all elements greater than it in the ordering.

Writing the relation as $<_L$, we can define it on a set $A_0$ as:
$A_0=\{x\in \mathbb{N}|x<_L 0\}$
Once again, the relation $<_L$ will agree with $\prec$ on all points in its domain. We might make $<_L$ to be an order on $\mathbb{N}$ instead of $A_0$ [replacing smallest element in $A_0$ with $0$, second smallest element in $A_0$ with $1$, and so on].

Apparently, it seems that this process when applied to every function in $C$ will always keep some programs corresponding to order-type of any recursive well-order [this is what we want, as discussed in beginning of this post]. But for it to work, it also to change every recursive linear-order with $\alpha_{min}=\omega_{CK}$ in such a way that after transformation the resulting linear-order will have $\alpha_{min}<\omega_{CK}$.

So we apply the simultaneous start procedure after making this change to every index/program in set $C$ ...... that is, making a non-inclusive left-cut at $0$. After this change to every element in $C$, we start from the smallest index (in $C$), and proceeding in increasing order. And this time we make no exception as to how the simultaneous start procedure runs (for each individual index) ...... as soon as it identifies $\alpha_{min}$ for some relation, it ends the processing for that linear-order immediately [removing the corresponding index from $C$]. The whole process ends when the set $C$ becomes empty (indicated by a single flag cell).

Let me know if I have made an important mistake in this post.

Last edited:

#### SSequence

The method in above post also has an issue. It doesn't always change $\alpha_{min}$ from $\omega_{CK}$ to $<\omega_{CK}$.

#### SSequence

I have thought of yet another construction. It is a combination of the previous ideas with one or two new different elements added. However, admittedly, the last two times I wasn't careful enough.

Because I was able to find the issue relatively quickly in both cases [post#5, deleted-post AND then later for post#9], once in about three days and then later in just a day ........... so I am going to be much more careful this time before posting.

I am not going to post anything in full detail for now. Rather I will take a week to carefully write-out every step and try to check for any implicit assumptions [and then try to repeat it a number of times].

If even after a week of constant thinking I can't find the issue, then I will post the construction. Otherwise, if I don't make any other post after this then it can be assumed that I have found some issue in the construction and don't think it is worth writing everything in detail here. Also, in that case, it can be understood that the thread has run its due course.

#### SSequence

I think I will try to describe what I was thinking. It is essentially a question since, if it worked, I don't think it's possible that no one would have thought of it.

I have also pinged @Deedlit on MSE so he will perhaps give some input on this (as the PF account doesn't seem to have been logged-in for a long time). What are your thoughts on the description in the post below?

As for the structure of post below, there are two main parts:
(a) I first made a certain assumption. I think the assumption can be made weaker significantly. However, it is important to be very explicit about it. That's because, unfortunately, I have very little knowledge/understanding of the underlying theory [partly because I just haven't studied it]. So I don't know whether the assumption I made [or even the much simpler assumption] is true or false.

I will try to improve my knowledge of my theory to understand whether the assumption holds or not. But honestly, the underlying study required would probably take a long time. I think it is likely that an expert on the specific topic will be able to give a swift answer.

(b) I describe a certain point which is supposed to work IF the assumption in (a) is actually correct. In that case, I would also like to know whether I am making some mistake in this part or not.

#### Deedlit

Hi SSequence,

I haven't taken the time yet to read over the whole thread, but let me just address the initial question: what about Q? Is there some condition that eliminates Q from the list of available linear orders?

Edit: Looking further, you seem to have answered the initial question yourself. I'll try to find time to read the rest later.

#### SSequence

You are quite right of course about $Q$. Another example is:
$\omega^4 +(\omega^2) \cdot \omega^* + \omega^4$
From any start point, the (maximum) initial well-ordered segment has type $\omega^4$, but there is no section of the form $\omega^4+\omega^*$ (no matter which postion we look from). But anyway, $Q$ (or close variations) was much closer to example I was trying to look for.

I do not think that the whole thread needs to be read. Just read post#6 as this is the most relevant to what follows. It isn't displaying in correct format for me though (I can re-post it if needed). But you can also look at the same theorem from the source (paper linked in post#1).

I will post the observation that I have been thinking (currently) during past week or so in a day or two [it is significantly different from what I have posted till now]. I couldn't get to post it because (i) it was very long (ii) and I was also trying to think about aspects of it [I have made number of modifications from what I thought initially .....]. I will probably post in two or three parts, because it gets a bit long.

P.S.
Also, this is just a brief re-capitulation of the whole thread till now. I basically thought of a (quite basic) modification of procedure described in post#6. The actual procedure discovers the initial well-ordered segment of any recursive linear-order. What I thought of was starting from all possible "positions". The point was that even if the initial well-ordered segment extends till $\omega_{CK}$, if there is any position from which the linear-order has an initial segment that has length $<\omega_{CK}$ it will be detected in recursive time [note that being unable to detect an arbitrary recursive linear-order (that are non-wellorders) in recursive time (as not being well-orders) is one of the main things preventing a machine (such as for paper in OP) from halting at $\omega_{CK}$].

But if one looks at paper linked in second-half of post#6, there exist recursive linear-orders which have an initial segment of length $\omega_{CK}$ from any starting position. I looked at a number of changes to the "modified procedure"("simultaneous start procedure") to see whether these kind of linear-orders could be dealt with (in recursive time) [some changes/ideas I posted, and some I didn't post here]. I didn't find any reliable way (that I could see or guarantee to work in all cases).

Nevertheless, this is not directly relevant to what follows (I will post it in a day or two).

Last edited:

#### SSequence

I think I will post the lines along which I have been thinking. One problem is that I have changed my idea too many times in last few days. In particular, there is one step I am quite uncertain about (it seems to be an important one). I couldn't get the time to think about it, so I will post it in a slightly speculative manner as such and clearly mentioning it (in a few days or a week I can probably comment on it better).

Other than that, I have not given reference to a number of results. That's mostly to get to the basic point a little quicker. I have added [ref.] at all such points. So if someone is interested, I will describe the specific reference for those points/results.

Some background below (for the post that follows):

=============================

We assume a generic computational model (ORM/OTM or something equivalent). The supremum of all halting positions (on empty input) will be denoted as $c$.

[ref if needed for this paragraph] Defining the notion of an $\alpha$-TM and $\alpha$-RM.
So for example, to define collection of partial computable $\alpha$-RM functions:
"For each $x \in \alpha$ either the program halts in less than $\alpha$ time or it loops forever"
So for example, to define collection of computable $\alpha$-RM functions:
"For each $x \in \alpha$ the program must halt in less than $\alpha$ time"

So we have the following collections of functions from $\alpha$ to $\alpha$. The first three contain both partial and total functions and the last three only contain total functions:
(1) $\alpha$-$r.e.$ [link]
(2) $\alpha$-RM partial computable
(3) $\alpha$-TM partial computable
(4) $\alpha$-$recursive$ [link]
(5) $\alpha$-RM computable
(6) $\alpha$-TM computable

(1),(2),(3) define exactly the same class of functions ........... and similarly, so do (4),(5),(6). Obviously, we also have (1)=(2)=(3) $\supset$ (4)=(5)=(6).

=============================

Further, for any value $a \in Ord$, it is known to be true that [ref if needed]:
$sup(a$-$recursive)=sup(a$-$r.e.)$
The left-hand-side means the supremum of order-types for which we have a well-ordering of $a$ [in the collection of functions (4) above]. Sorry I have put in a bit weird way I think. For right-hand-side, as far as I can understand, I think we will consider well-orderings based on some subset of $a$.

Now define the function $F: Ord \rightarrow Ord$:
$F(0)=\omega$ (say)
$F(x+1)=S(F(x))$
For limit values the function $F$ is sup of all values below it (meaning it is a continuous function).

For any value $a \in Ord$, $S(a)=sup(a$-$recursive)$.

=============================

Since I don't know about the underlying theory, I should add clearly where an assumption is made. I will make the assumption that for any value $a \in Ord$ there is no $a$-$r.e.$ linear-order whose order-type is greater than $S(a)$.

For a lot of values $a \in Ord$, it is definitely true that there is no $a$-$recurive$ linear-order whose order-type is greater than $S(a)$ (since I could find a definite [ref] for it).

At any rate, it might be possible to work around this assumption perhaps. It seems better to assume it if it is true though.

Last edited:

#### SSequence

The programs we are considering have one input variable. Note that, normally, when we are considering halting positions we either consider input $0$ to the program or a program with no input. We can note that these programs (with one input variable) are enumerated quite easily.

Now mostly I have been thinking along the following lines. What I have been trying to consider is based around the point that the program with same index can be thought of as computing a function on domain $a$ or domain $b$ (where $a,b \in Ord$). More specifically, if we have an $a$-partial computable then it can be thought of as from $a$ to $a$. Similarly, a $b$-partial computable function can be thought of as from $b$ to $b$. Now interestingly, it is the same program can be thought of as computing both the functions.

What I have been thinking about is how a program with some specific index changes its "category" as we increase the value $a \in Ord$.

Let's consider the task of categorizing what a specific program is doing for an arbitrary $a \in A$. We have the following:
(1) It calculates an $a$-partial computable function but not a linear-order
(2) It calculates an $a$-partial computable well-order
(3) It calculates an $a$-partial computable linear-order that isn't a well-order

Note that the underlying set for orderings in (1), (2) and (3) is assumed to be some subset of $a$.

=============================

Consider two different values $a,b \in Ord$ so that $b>a$. The point is that which of the "transitions" can we definitely rule out while moving from $a$ to $b$. It seems that we can definitely rule out the transitions:
(1) $\rightarrow$ (2)
(1) $\rightarrow$ (3)
(3) $\rightarrow$ (2)

The meaning for ruling out first transition is supposed to be that if we had some program categorised as (1) for $a$, then it isn't possible (in an a priori sense) that the same program would be categorised (2) for $b$. And similarly for other transitions that have been mentioned.

To describe some reasoning, if we consider (3) $\rightarrow$ (2), the reason for ruling it out is that if there was an infinite descent containing values (all of whom are less than $a$) then that infinite descent will never be removed (as long as we are considering the same program) and will carry over for all future values $b>a$.

P.S.
This isn't complete. I will post the observation a bit later probably. But if there are parts where I have skipped over too much or haven't been clear enough (or perhaps a ref. is needed for a part in previous post), please do mention it.

Last edited:

#### SSequence

Post#15,#16 can be skipped. The idea I was thinking about in that direction doesn't work.

Anyway, I thought of another idea closely related to procedure from post#6. But it is quite different from "simultaneous start" method mentioned in second-half of OP (and also summarized in second half of post#14). I will describe that idea in this post.

First of all a copy-paste of first-half of post#6 in correct format (even though the same point can be understood from the source, since it is central to this modified method ...... it doesn't seem a bad idea to include this):
theorems 2.2 (page-8)
Given any function from $\mathbb{N}^2$ to $\{0,1\}$, suppose we encode it as a function from $\mathbb{N}$ to $\{0,1\}$ in any reasonably obvious way. If this encoded function is given as input then the machine can always decide whether it describes the well-order relation (for a well-order of $\mathbb{N}$) with some order-type (say $X$).

For the purpose of this question, it is important to describe the main idea that is discussed in proof of theorem-2.2. Suppose we are given a function $f:\mathbb{N} \rightarrow \{0,1\}$. Now let's denote the comparison relation (from $\mathbb{N}^2$ to $\{0,1\}$) induced by this function (after "deciphering" it) is $<_f$. We want to know that whether $<_f$ is a well-order relation or not. First we verify the $<_f$ is a linear order (on $\mathbb{N}$). After that, the idea is to proceed in stages. Intuitively, at each stage $\alpha$ we have stored all the elements that occur in positions $<\alpha$ and we want to determine the $\alpha$-th minimal element (if one exists). So we just use a set $A_\alpha$ that changes as the stages proceed. Initially we have $A_0=\phi$. For convenience, we let $B_\alpha=\mathbb{N}-A_\alpha$ denote the complement of $A_\alpha$ (note that initially $B_0=\mathbb{N}$).

At beginning some stage $\alpha$, suppose the elements of $B_\alpha$ in strictly increasing order were $b_0,b_1,b_2,b_3,b_4,......$. First we set-up a cell which serves as flag (it will be set to $0$ initially before we start our processing in each stage). We set up a variable (say $v$) which is initially set to $b_0$. Furthermore, we have a counter that ranges from $i=0$ to $i<\omega$. For each $i$ we make the comparison $b_{i+1}<b_i$. If this comparison turns out to be false, we do nothing and increase $i$ by $1$. If the comparison $b_{i+1}<b_i$ turns out to be true then we check whether $b_{i+1} \in B_\alpha$. If both conditions in previous sentence turn out to be true, then we do two things: (1) Set the variable $v$ to $b_{i+1}$ (2) simply change the flag cell to $1$ and back to $0$ again. In the limit, when $\omega$ stages pass, we can simply check the flag. If it's $1$ we return false (the given $<_f$ doesn't describe a well-order). That's because the value $1$ in the flag cell (at the end of a stage) implies that it oscillated infinitely often in the limit. If the flag is $0$, then suppose the value $V$ was stored in the variable $v$. We set:

$A_{\alpha+1}=A_\alpha \cup \{V\}$

$B_{\alpha+1}=B_\alpha - \{V\}$

Note that since values are only ever added to $A$ and only ever removed from $B$, there is an obvious way to form these sets on limit stages. We can halt and return true when we discover that, at some stage $X$ we have $A_X=\phi$ (or alternatively $B_X=\mathbb{N}$).

The above paragraph is similar to how the procedure is described in the paper. It might be added (in case it isn't clear) that there is a slightly less efficient way to find $A_{\alpha+1}$ (from $A_\alpha$) too. At each stage $\alpha$, we are just looking for an element $x$ with the following property:

$\exists x \in B_\alpha \forall y \in B_\alpha$ $[ x \neq y \rightarrow x<_f y ]$

When we find this element, it will be removed from $A$ and added to $B$ (in preparing for the next stage). If such an element exists for each stage (until we run into a stage where $A$ becomes empty) then $f$ encodes a well-order. Otherwise, if such an element doesn't exist at some stage (before $A$ becomes empty), then $f$ doesn't encode a well-order.
Now, as far as I can understand, exactly the same method can be used to discover the initial well-ordered segment for a recursive linear-order. Something similar is done in theorem-3.2 (page-18) [though I don't fully understand whether there is a certain advantage or necessity to using a r.e. relation instead of a recursive relation ...... it shouldn't matter though].

But now we won't reach a stage $X$ so that $A_X=\phi$ (as mentioned in quote above). Instead we will reach a stage where an infinite descent will be discovered (and it will become clear that the given relation doesn't form a well-order). Meaning that there will be no $X$-th minimal element.

Now suppose the initial ordinal is equal to $\omega_{CK}$[which I will denote as $W$ for the rest of this post] for the given linear-order. Lets define a function $f:W+1 \rightarrow \omega+1$ so that for any value $x \leq W$ the value $f(x)$ gives us the number of descents (to reach $x$). Note that we have:
$f(x)<\omega$ for $x<W$
$f(W)=\omega$
One thing that I noticed (about a month ago) is that we can define a function $g:W+1 \rightarrow \omega+1$ such that:
$g(0)=f(0)$
$g(x+1)=g(x)$
$g(x)$=lim inf of all values $h(i)$ (where $i \rightarrow x$)

One interesting thing I was able to show was that:
$g(x)<\omega$ for all $x<W$
$g(W)=\omega$
So actually, the first time $g$ becomes equal to $\omega$ is exactly at time $W$. I have skipped the proofs (I am reasonably confident about them) here to avoid getting side-tracked. Anyway, that result doesn't seem to change things much. That's because, for example, to simulate this kind of function reliably using a tape, we would keep changing the number of $1$'s and $0$'s on, say some allocated tape. I couldn't think of any other reliable method that worked better than this. Eventually when the value of $g$ is equal to $\omega$ at some point, the whole tape will be all $0$'s or all $1$'s (depends on cell convention). However, to scan through and confirm this requires an extra time equal to $\omega$.

@Deedlit
Nevermind. I posted a certain idea (not the one mentioned above), but I think at this point it is too incomplete and tentative at this point (and probably, it doesn't work anyway). I will ping in-case there is something substantial to add.

Last edited:

#### SSequence

Actually, I do think that there maybe a question here w.r.t. post#15,16. When I wrote (in prev. post):
Post#15,#16 can be skipped. The idea I was thinking about in that direction doesn't work.
The direction I was thinking about was an iterative procedure which, in the end, seems to show that there exist bad ordinals and the smallest one must definitely be less than $c$. The definition of good and bad ordinals is:
For any $\alpha$, let $\alpha^+$ denote the smallest value that is greater than $\alpha$ but belongs to range of the function $x \mapsto \omega^{CK}_x$.
good-ordinal: $\alpha^+=sup(\alpha-recursive)$
bad-ordinal: $\alpha^+>sup(\alpha-recursive)$

==============================

I was a bit surprised that a simple construction could show this existence [but ofc it uses the theorem from paper in OP along with one more theorem ....... which probably contain much of the substantial content]. But it didn't seem that one could proceed any further with that construction (and hence the quoted part above). But, after some more thoughts on this, I think there might be a genuine underlying question (to which I do not know the answer).

I will first link all the references that are used in post#15,#16. Then I will describe in detail the iterative procedure which I was talking about.

==============================

First a link to relevant papers:
A---- https://arxiv.org/abs/math/9808093
B---- https://www.sciencedirect.com/science/article/pii/S0168007209000086
D---- https://www.sciencedirect.com/science/article/pii/0003484379900251

I should also add that I am a complete newbie on this topic (and well almost all topics). I merely learned about (existence of) papers C and D from this question/answer(link).

What I have referred to in post#15,16 and above are merely some easy-to-understand statements made in the above papers. Here are all of them in order:
----- The paragraph in post15 relating various computability notions is just a paragraph in B towards the end of page-14 (towards the end of section-3).

----- Regarding the relations between a-recursive and a-r.e., it is mentioned in beginning of section-2 of D

----- Regarding what I mentioned in this post, see the beginning (first-page) of D

----- Also, for any a-recursive linear-order (on a), the length of initial segment can never exceed $a^+$. This is mentioned at the very beginning of proposition-2.1 (in section-2) of D

----- Also, regarding the last theorem in A, one question is does it generalise to OTMs? Because it is possible that a few small changes in computational model will change the applicability of the theorem (in fact, this becomes even more clear considering the result I described in post#17).

I tried to search for it quite a bit. I was able to find a seemingly reliable reference stating that the theorem does generalise to OTMs. I might link that later on.

Last edited:

#### SSequence

Here is a sketch of the construction (continued from post#16). As I mentioned there:
Let's consider the task of categorizing what a specific program is doing for an arbitrary $a \in Ord$. We have the following:
(1) It calculates an a-partial computable function but not a linear-order
(2) It calculates an a-partial computable well-order
(3) It calculates an a-partial computable linear-order that isn't a well-order

Note that the underlying set for orderings in (1), (2) and (3) is assumed to be some subset of a.
So we can classify and write-down the underlying indexes as $A_1,A_2,A_3$ respectively. Note that we have:
$A_1 \cup A_2 \cup A_3 =\mathbb{N}$
I also described how we can rule out some transitions as we move from a stage $a \in Ord$ to a higher stage $b \in Ord$ (where $b>a$). The basic idea is quite simple. If we carefully observe the transitions that were ruled out (second-half of post#16), it becomes clear that:
----- the set $A_2$ will have never any elements added to it as we increase the ordinal value (at which it is evaluated), but instead values will be possibly eliminated from this set as we increase the value.

So now if we take the definition of function $F$(second last paragraph of post#15) and the assumption I described (last paragraph of post#15), an obvious idea is to iterate and proceed in stages. That is, first we evaluate $A_2$ at point $\omega$ [I will denote this as $A_2(0)$]. Then we continue this and evaluate $A_2$ for sup of $\omega$-partial recursive well-orders. This value will be $F(1)=\omega^{CK}_1$ (as $\omega$ is good). We denote the value of set $A_2$ at $F(1)=\omega^{CK}_1$ as $A_2(1)$. In general the value of $A_2$ at any point $F(a)$ will be denoted as $A_2(a)$.

At limits we have to be a bit careful. For example, if $l \in Ord$ is a limit, it is by no means necessary that $A_2(l)$ is the intersection of all $A_2(i)$'s for all stages $i$ below $l$. For example, if we define a set $B(x)$ ($x \in Ord$) which varies as $x$ changes, then we might want to define it for all limit stages (and say, constant between limit stages). For any limit stage $l$, we could define $B(l)$ as the intersection of all $A_2(i)$'s for all stages $i$ below $l$. Then in general the following is not true for limit stages:
$A_2(l)=B(l)$

Note that when we arrive at some limit stage $p$, then calculating $B(p)$ for that stage is a relatively inexpensive operation. That is, we will be able to do it well before $F(p+1)$ time [usually values in the range of $F$ should be sufficiently closed]. If it ever occurred the first time that $A_2(p)=B(p)$ there would be a program that could definitely halt at a time equal to $F(p+1)$ exactly. So we might ask ourselves: does such a stage $p$ ever occur? I believe the answer should be yes. In particular, whenever $p$ is a limit greater than or equal to $c$ (supremum of halting positions), we also have $F(p) \geq c$ obviously. At this point if it occurred that $A_2(p) \neq B(p)$ then that would mean that there are some indexes missing from $A_2(p)$ but present in $B(p)$. If we consider the smallest such index it would be some specific natural number. This would give a finite signal to the program to halt at a point $\geq c$. This is impossible by definition of $c$.

Also observe that it should not be difficult to conclude that $F(c)=c$. That's because if we assumed $F(a) \geq c$ for some $a<c$, it is not derive a contradiction.

So now we have established $p<c$. But now $F(p)$ must be a bad ordinal. If it weren't then, by definition, we would have:
$F(p+1)=S(F(p))=[F(p)]^+$
But then, as I mentioned, we have a program that (on empty input) halts exactly at time $F(p+1)$. This can happen because when we would, at every limit stage, check each index in $B(p)$ for being a well-order (on some subset of $F(p)$) ........ the check will prove true for every single value in $B(p)$. The given program would halt just the first time it encounters this kind of stage (where every index in $B(p)$ proves to be a well-order). And the time it would require to detect all the well-orders (and make the set $B(p)$ empty) would take it exactly to $F(p+1)$. Halting on $F(p+1)$ contradicts that all values in range of $x \mapsto \omega^{CK}_x$ are impossible to halt at (from empty input).

Hence due to last paragraph we must conclude that $F(p)$ is bad.

P.S.
One thing to note is that generally determining all elements in the set $A_2(a)$ can't be assumed to be an inexpensive operation. This detection would generally be expected to take more than $F(a+1)$ time, but not much more than that [making the assumption towards the every end of post#15] ......... so we will end up doing this well-before $F(a+2)$ time.

But this construction itself isn't enough. Some more work is required to frame the question I was thinking. I will put that a bit later. Meanwhile if I have been unclear on some part in this post, please do mention.

Edit:
It has occurred to me there is a significant complication in the "construction" above. Just focusing on set $A_2$, the way the procedure works is to check (on each stage-a) for all inputs $x<F(a)$ whether a program with given index runs for a time less or greater-equal to $F(a)$. Whenever the run-time exceeds $F(a)$ the given input is supposed to be ignored (equivalent to looping).

However, it is entirely possible of course that for a given value $x<F(a)$ the computation runs for a time greater than $F(a)$ and halts after that. So, in a direct sense, what is being done in the procedure described in the post doesn't match with the notion of $F(a)$-partial recursive function [which is either run for time less than $F(a)$ or loop].

If this issue is not salvageable then what I wrote above doesn't work (meaning it doesn't show what it claims). But if it is, then there shouldn't be any problem I think. But if would require justification nevertheless. I think it might possibly be salvageable completely (but it is difficult to see directly, I wouldn't be surprised if I am mistaken though). The reason is that we are only interested in a very limited region ....... namely below the smallest limit stage $p$ where the set $A_2$ has no missing index [meaning $A_2(p)=B(p)$].

So if we can mange to show that for any stage equal or less than the ones we are interested in the functions considered by our procedure (as in previous paragraph) can be made to match the notion of $F(a)$-partial recursive function then it should be fine. One way it might be possible could be to show that, for the stages we are interested in, we can always modify a program (with any index) so that whenever it runs a time greater than $F(a)$, we can make it loop. I am thinking that perhaps the missing index values (which are just natural numbers) can help us with it?

Anyway, this part should be considered quite carefully.

Last edited:

#### SSequence

I think at this point I have been able to convince myself (to some degree) that the issue mentioned in "Edit:" in previous post#19 is manageable. Note that what we want is that for any limit stage $l$ [which is less-equal than the first limit stage where there is no missing index, call it $p$] if a program halts at a time greater-equal than $F(l)$ for some input less than $F(l)$, then we want to be able to make it loop for all such inputs. And I think the reasoning why it should be possible for any limit $l<p$ would be due to the fact that $l$ has a (smallest) missing index(that is, $A_2(l) \neq B(l)$). Sure the (smallest) missing-index for some limit $k<l$ will be discovered a bit later at a time little greater than $F(k+1)$. But that doesn't seem like a problem to me (it would be a problem, say, if the missing index for stage-k was being discovered at a time greater $F(k+\omega)$.

So, for any input $x$, to the program we modify it such that it searches for which "region" it falls into (the one "before" $F(l)$ or the one "after" it). and proceeds based upon that. The main thing to ensure is that if (for limit stage-$l$) the input is smaller than $F(l)$ what we want is that this search process does not take us beyond $F(l)$. If it does go beyond, then it doesn't help us much. And at least, on the face of it, it seems to me that this condition can be satisfied here.

==============================

Anyway, now in this post I will try to proceed further and just try to frame the main question I am trying to get at. I should add that I will be a skip a few steps in this post. Because I feel that I should try to get to the main question first. Of course, the main question being well-formed does require that all the intermediate steps do work out (and each of the steps need to be checked carefully). But, for now, I will leave some of this for later and just give a very brief sketch of the rest of what I am thinking.

Now one thing that we need to ask ourselves is that if we denote $p$ as the smallest limit stage with no missing-index, then if we start counting the "number of times" missing indexes occur (say on limit-stages) what this counting will lead us to? Meaning what ordinal value (call it $r$) will this count equal to? Excluding some boundary-cases (which need to be looked at separately), it seems that if $p$ is sufficiently "rare", then there are two main possibilities:
(a)------ $r<F(p)$ (and $r$ is a limit)
(b)------ $r=F(p)$ (and $r$ is a limit)

I think that if we consider the possibility-(a), it seems a bit difficult for me to see how it can be true. The thing is that, if (a) is true, then basically I think that would imply that there is program (with no input) which has a non-decreasing variable which equals $\omega$ for the first time at runtime $F(p)$. Why this would happen requires some detailed justification. To summarise though, I think this should be true because as I see it for every limit stage $l<p$ [but the boundary cases here also need to be considered carefully, as they don't seem trivial], it seems that we can construct a program that writes-down a strictly increasing $\omega$-sequence for $F(l)$ and then halts a little later (the halting signal should be provideable by missing index for stage-$l$ I think). And the main reason for why it should be possible is simply that all values of form $F(l)$ (where $l$ is a limit that is multiple of $\omega^2$ and less than $p$) can be assigned a sequence using the missing indexes.

So when we claim $r<F(p)$ and also that it is a limit, if we combine this with last paragraph (giving us a sequence for $r$), this is giving us a sequence for $F(l)$ itself [since $r$ is just counting the missing indexes, which are "embedded" (so to speak) in $F(l)$].

Why I think that matter is that in this case, I get the feeling that if the above is true [a non-decreasing variable getting to $\omega$ first time at $F(p)$], then using the fact that stage-$p$ has no missing indexes, we can actually construct an $F(p)$-partial recursive function which represents an order-type equal to $sup(F(p)-r.e.)$ [which has to be impossible]. Once again the why of this requires some fairly detailed justification [again skipping it for now].

I should add that between the:
---- precise justification required for Edit: in post#19
---- the boundary cases for above mentioned point
---- each of the two paragraphs above

Quite a detailed explanation is required for these. It would probably require four or five pages (or possibly even more). But I have described the salient reasons why I think they should be true though.

To be honest though, before proceeding, while I do have somewhat detailed sketches for the previous statements in mind, there is a fairly non-negligible probability that I have made a mistake in the statements above. So, until I write all of it in detail, this possibility is in my mind.

I will try to write a more detailed explanations for the above statements later-on (and if I happen to find a mistake, point it out). But for now, I will just move to the question.

==============================

So assuming the above statements to hold. That is assuming that the count of missing indexes (denoted by $r$) indeed equals $F(p)$, there is a question that one can ask.

Denoting the set of smallest missing indexes at each stage by $I$, it seems to me we now essentially have our $F(p)$-partial recursive programs being capable of emulating any ordinary program that has access to a well-order of $I \subset \mathbb{N}$ (with order-type $F(p)$ itself). But this is very similar to the definition of $\omega^{CK}_{\alpha}$ (all I know about this is from an answer to the question I asked here)? Note that if $F(p)$-partial recursive programs are truly able to emulate an ordinary program with an access to a "copy" of $F(p)$ (see the link) this contradicts $F(p)$ being a bad ordinal.

Consider any $i_1,i_2 \in \mathbb{N}$. More precisely now for each of the following possibilities we can think of an oracle which:
------- returns $0$ or $1$ if both $i_1,i_2 \in I$
------- gets into a loop if either of $i_1,i_2$ don't belong to $i$
And now far as I know, when we say that such and such set defines a well-order of a subset $S$ of $\mathbb{N}$, then for comparisons where one or both elements are not in $S$, we are simply supposed to loop? No? Or am I being mistaken somewhere?

If we were treating a subset $I \in \mathbb{N}$ as a copy, things are a bit different though.
Now for each of the following possibilities we can think of an oracle which:
------- returns $0$ or $1$ if both $i_1,i_2 \in I$
------- say returns $2$ if either of $i_1,i_2$ don't belong to $i$

So in-case everything I wrote previously before holds, then would that mean for a subset $S \subset \mathbb{N}$, the definition of $\omega^{CK}_{\alpha}$ is only valid for a copy-based definition and the definition based on well-order of $S$ is strictly weaker?

P.S.
I have been thinking of a certain way to extend the idea so that above point (about distinction between copy and subset of $\mathbb{N}$ serving as well-order) can possibly be by-passed. But I think first there are too many points before for which I need to check validity. And I might be mistaken about this extension anyway (at any rate, I think I will try to think about it after establishing validity or lack of it for previous points).

Last edited:

"Question Regarding Linear Orders"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving