Vrftsjtryk

Let $$W = {W_1, W_2, W_3, ldots}$$ denote an infinite (or finite) set of well-orders on $mathbb{N}$ and $alpha_i$ is an ordinal (order type) that corresponds to $W_i$, assuming that $alpha_1 ge omega$ and $alpha_{i+1} > alpha_i$ for all $i$. Note that $alpha_i$ can be non-recursive for any $i ge 1$.

All I want is a simple (and easy to understand) method to define a well-order $W_0$ that contains all elements of $W$. Is it possible?

I was thinking about combining unary (where $0 = 1, 1 = 11, 2 = 111$ etc.) and binary encodings of natural numbers, which allows appending $i$ zero bits to the unary encoding of a corresponding number. For example, if $W_4$ implies that $5 prec 3$, then in $W_0$, we will have $$1111110000_2 prec 11110000_2,$$ so $1008 prec 240$ because $$5 = 111111, 3 = 1111$$ in unary encoding and we need to append $i=4$ zero bits to both of them.

To find a number that corresponds to the order type of $W_i$, we simply write $i$ consecutive $1$ bits and then interpret it as a binary encoding of a natural number. Then in $W_0$, we will have $$1 prec 3 prec 7 prec 15 prec ldots,$$ where $1 = 1_2$ is the order type of $W_1$, $3 = 11_2$ is the order type of $W_2$, $7 = 111_2$ is the order type of $W_3$ etc.

Then in $W_0$, we will have $x prec 0$ if the binary representation of a natural number $x$ is a sequence of one or more $1$ bits followed by a sequence of zero or more $0$ bits. The number $0$ corresponds to an ordinal $alpha_0$.

Then consider a set of natural numbers (where each number is greater than $0$) where the binary representation of each element is not written as a sequence of one or more $1$ bits followed by a sequence of zero or more $0$ bits: $${5 = 101_2, 9 = 1001_2, 10 = 1010_2, ldots }$$

We define that a $j$-th element of this set (where $j ge 1$ ) corresponds to an ordinal $alpha_0 + j$. This allows to have a well-order $W_0$ that has the order type $alpha_0 + omega$.

Is this method mathematically correct? If no, then how can I solve this problem (if it’s possible)?

I didn't fully understand your question, but based on reading the first two paragraphs of your question, I assume that what I write below is what you meant? If it isn't, then let me know so I can delete the answer.

First of all, when you say "well-order", implicitly or explicitly we are talking about well-order of/on some set. If the context is very clear, this is omitted sometimes for brevity (I will do the same below). I am guessing (given your post) here that you are talking about well-orders on $mathbb{N}$ here.

As I understood your questions, you are saying that if we are given well-orders relations for well-orders of order-type $alpha_0,alpha_1,alpha_2,...,alpha_i,...$ is there a fixed way to combine them so we can get a well-order relation of order-type $beta=mathrm{sup}{,alpha_i,|,iin mathbb{N}}$.Yes there is, and it is fairly direct and straight-forward. But if this is not what you were asking then do mention it in comments so I can delete the answer.

Well here it is. Let $lessthan_i:mathbb{N}^2 rightarrow {0,1}$ denote the well-order relations for a well-order(on $mathbb{N}$) with order-type $alpha_i$. From these functions, we define a new function $lessthan:mathbb{N}^2 rightarrow {0,1}$ which serves as well-order relation for a well-order(on $mathbb{N}$) with order-type $beta$. For the sake of simplicity, I will assume that $beta$ is of the form $omega^x$(for some $x<omega_1$), so simply taking the sum of $alpha_i$'s gives us $beta$.

As usual, assume that we have pairing encoding function from $mathbb{N}^2$ to $mathbb{N}$ (any valid pairing function whatsoever will do). So $<x,y>$ denotes the result of applying such a function on $x,y in mathbb{N}$. Similarly, we have functions $H:mathbb{N} rightarrow mathbb{N}$ and $V:mathbb{N} rightarrow mathbb{N}$ which extract the first and second element in the pairing respectively. So, for example, we have the identities $H(<x,y>)=x$ and $V(<x,y>)=y$.

Now we define the function $lessthan(x,y)$ by dividing into sub-cases (note that there are more than one ways to do it correctly):

(a) $H(x)>H(y)$

Define $lessthan(x,y)=0$.

(b) $H(x)<H(y)$

Define $lessthan(x,y)=1$.

(c) $H(x)=H(y)$

This is the more interesting case. Denote $i=H(y)=H(x)$. Just return:
$lessthan(x,y)=lessthan_i(V(x),V(y))$

The above cases complete the required description. A careful look will show that this indeed represents a well-order relation for $beta$. (Edit: note that this is also bit of a "shortcut" phrase to avoid being too repetitive. For example, a more formal phrasing for the last sentence before the edit would be:"A careful look will show that this indeed represents a well-order relation for a well-order(on $mathbb{N}$) with order-type $beta$")

I suppose if the construction above is the very first time you have seen it, then it might look a bit complicated. I am adding one very elementary example, so it is easier to get the hang of it.

Suppose we are given a well-order (of $mathbb{N}$) with order-type $alpha$. Let the corresponding well-order relation be $lessthan_1:mathbb{N}^2 rightarrow {0,1}$. We want to construct a function $lessthan_2:mathbb{N}^2 rightarrow {0,1}$ which can serve as a well-order relation for a well-order (of $mathbb{N}$) with order-type $alpha+omega$.

Here is one such function. We again divide into sub-cases:

(a) $x$ and $y$ are both odd

$lessthan_2(x,y)=lessthan_1((x-1)/2,(y-1)/2)$

(b) $x$ and $y$ are both even

$lessthan_2(x,y)=$ return truth value of $x<y$

(c) $x$ is odd and $y$ is even

$lessthan_2(x,y)=1$

(d) $x$ is even and $y$ is odd

$lessthan_2(x,y)=0$