# Order of ordinals

Let $R_i$ is an ordinal for every $i\in n$ (where $n$ is also an ordinal) and $S_{i,j}$ is an ordinal for every $i\in n$ and $j\in m_i$ (where $m_i$ is also an ordinal for every $i\in n$).

What is a formula for the ordinal representing the pair $(R_i;S_{i,j})$ in the lexicographic order of pairs?

-
For fix $i,j$ the pair $(R_i; S_{i,j})$ is represented by their sum. – azarel Mar 18 '12 at 20:13
@azarel: "Their sum"? What is "their"? I don't understand. – porton Mar 18 '12 at 20:20
the pair $(R_i;S_{i,j})$ is represented by $R_i+S_{i,j}$. – azarel Mar 18 '12 at 20:29
@azarel: $R_i+S_{i,j} < R_{i'}+S_{i',j'}$ isn't equivalent (consider the case of natural numbers) to $R_i<R_{i'}\wedge (R_i=R_{i'}\vee S_{i,j}<S_{i',j'})$ (the condition for lexigraphical order). It seems that you err. – porton Mar 18 '12 at 20:36
I guess you mean the order type of $(\{(R_i;S_{i,j}:i\in n,\ j\in m_i\},<_{lex})$. – azarel Mar 18 '12 at 20:54

This question is not really well defined, as an ordered pair under the usual definition $(\alpha,\beta) := \{\{\alpha\},\{\alpha,\beta\}\}$ is not a well-orered set (as no order is given). However, assuming any order on it, its order type would be, as a finite set with two elements $\{\alpha\}$ and $\{\alpha,\beta\}$, equal to $2$. It is worth noting that that is true for any sets. The distinction between $\alpha$ and $\{\alpha\}$ is critical - the former is a set with $card(\alpha)$ elements, the latter is a set with one element, namely $\alpha$.

However, the comments and the remark on lexicographical order seem to indicate you actually mean the order type of the set $\{ (R_i,S_{i,j}): i \in n, j \in m_i \}$ under lexicographical order. The lexicographical ordering means that the order the $R_i$ appear in the series does not matter, and neither for $S_{i,j}$.

Define $R = \{R_i:i \in n\}$ and $S_i = \{S_{i,j}:j \in m_i \}$ and $S = \bigcup S_i$. Then we're looking at the order type of $R \times S$. And with $m=\bigcup m_i$, this in turn is going to be equal to $mn$ if there's not "too much overlap" in the $S_{i,j}$ - otherwise, we have to resort to the cardinality of $S$ as factor instead of $m$.

Now, all that said, I suspect you wanted to ask a different question: Actually meaning "order type of $R_i$ followed by $S_{i,j}$" instead of "ordered pair". This is by definition $R_i + S_{i,j}$, something very different from the ordered pair.

But in that case, "lexicographic ordering" really makes no sense. I think you meant to state "We have $R_1$ followed by $S_{1,1}$ followed by $S_{1,2}$ ... followed by $R_2$ followed by $S_{2,1}$ ...." with your entire question. If that's true, then I don't think there's a simple version - there is no common definition for $\sum$ or $\prod$ for an infinite number of ordinals. In fact, I'm not even convinced that the "intended" result would be a well-ordered set as this "infinite addition/product" might introduce the possibility for infinite descending chains. That'd be impossible to verify without a clearer, more rigorous definition than my interpretation of your intention, though.

Here's one possible interpretation that actually would work. Define $F: n->ON$ and $G_i: m_i->ON$ recursively as following:

$G_i(0)=F(0)=0$

$\alpha$ successor: $G_i(\alpha)=G_i(\alpha-1)+S_{i,\alpha-1}$ and $F(\alpha)=F(\alpha-1)+G_{\alpha-1}(m_{\alpha-1})$

$\alpha$ limit: $G_i(\alpha)=sup(G_i(\beta):\beta<\alpha)+S_{i,\alpha}$ and $F(\alpha) = sup(F(\beta):\beta<\alpha)+G_{\alpha}(m_{\alpha})$

Note the little technicality that if $n$ is limit ordinal, then we actually need an $G_n$, $m_n$ and $S_{n,m_n}$ that's not given in the original question for this to work. We can just assume them all as $0$, of course. Or we could revise the definition to include the special case.

Then $F(n)$ is the result. Now, as for how to evaluate that, that entirely depends on the sets $R_i$ and $S_{i,j}$, of course.

-

If I understand your question correctly, the set that contains the ordered pairs may not be a product. In the lex order on that set, each "column" will correspond to some $i$ for $i\in n$. And the content of each "column" will correspond to some $m_i$. Then the order type of $(R_i,S_{i,j})$ in the $\le_{lex}$ order is $o.t.(R_i,S_{i,j}) = (\sum_{t<i} m_t) + j$.

-