- #1
SSequence
- 559
- 96
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##.
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##.