I Question Regarding Linear Orders

  • Thread starter SSequence
  • Start date
289
36
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##.
 

WWGD

Science Advisor
Gold Member
3,930
1,650
I suggest you summarize the question, make it more concise, easier to read.
 
289
36
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:
289
36
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:
289
36
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:
289
36
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:
289
36
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?).
 
289
36
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:
289
36
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:
289
36
The method in above post also has an issue. It doesn't always change ##\alpha_{min}## from ##\omega_{CK}## to ##<\omega_{CK}##.
 
289
36
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.
 
289
36
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.
 
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.
 
289
36
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:

Want to reply to this thread?

"Question Regarding Linear Orders" You must log in or register to reply here.

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

Latest threads

Top