Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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:


$\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.

share|cite|improve this answer

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.