-1
$\begingroup$

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?

  • 0
    @Brian M. Scott: There are no reason to assume that these are increasing.2012-03-20

2 Answers 2

1

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.

0

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.