Given well-ordered sets $\alpha$ and $\beta$, define $\left(\!\!{\alpha\choose \beta}\!\!\right)$ to be the set of weakly decreasing functions from $\beta$ to $\alpha$, ordered lexicographically; this is in fact a well-ordering, so we get an operation on ordinals.

(I denote it by multichoose since for $n$, $k$ finite, $\left(\!\!{n\choose k}\!\!\right)$ is indeed $\left(\!\!{n\choose k}\!\!\right)$ in the usual sense.)

We can also order reverse-lexicographically and get a well-order; I'm calling that $\left(\!\!{\alpha\choose \beta}\!\!\right)'$. Same questions about that. (And we can restrict to strictly decreasing functions to get $\binom{\alpha}{k}$ and $\binom{\alpha}{k}'$, but obviously $k$ has to be finite for that to be interesting.)

What are these operation ordinarily called? Where could I look up more information about them?


I have never seen either ordinal operation used; I’m not at all sure that I’ve even seen either linear order used in any substantial way. They caught my interest, however, so I played with the first one a bit; you may already know all of this, but if not, perhaps it will be of some use in lieu of a reference.

I will write $\,^{\beta\downarrow}\alpha$ for the set of weakly decreasing $\beta$-sequences in $\alpha$ and $\prec$ for the (strict) lexicographic order on ordinal sequences. All arithmetic is ordinal arithmetic (and with luck I made no serious errors in it!).

A weakly decreasing $\beta$-sequence $\sigma$ in $\alpha$ can be encoded as a finite sequence $$\Big\langle\langle\xi_k,\eta_k\rangle:k<\ell\Big\rangle\;,\tag{1}$$ where $\langle\xi_k:k<\ell\rangle$ is a strictly decreasing sequence in $\alpha$, $\eta_0+\dots+\eta_{\ell-1}=\beta$, and each $\eta_k>0$: the $\xi_k$ are the terms of the sequence, and $\eta_k$ is the order type of the subsequence of $\xi_k$ terms; I will call these the $k$-th term and the $k$-th length of $\sigma$, respectively. It will be convenient to rewrite the code $(1)$ as $\langle\xi_0,\eta_0,\xi_1,\eta_1,\dots,\xi_{\ell-1},\eta_{\ell-1}\rangle$ and denote this by $c(\sigma)$. It’s not hard to see that $\sigma\prec\sigma'$ iff $c(\sigma)\prec c(\sigma')$.

Consider first the case $\beta=\omega^\lambda$ for some ordinal $\lambda$. This is equivalent to the assertion that if $\beta=\alpha+\gamma$, then $\gamma=\beta$, so the last length of any $\beta$-sequence must be $\beta$, while the other lengths may be any ordinals less than $\beta$.

Clearly $\left(\!\!\binom1{\beta}\!\!\right)=1$. The code of a $\beta$-sequence in $2$ is either $\langle 0,\beta\rangle$, of the form $\langle 1,\eta,0,\beta\rangle$ for some $\eta$ such that $0<\eta<\beta$, or $\langle 1,\beta\rangle$, so $\left(\!\!\binom2{\beta}\!\!\right)=\beta+1$. In general suppose that $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\gamma$. Clearly $\,^{\beta\downarrow}\alpha$ is an initial segment of $\,^{\beta\downarrow}(\alpha+1)$ with respect to $\prec$. If $\sigma\in\,^{\beta\downarrow}(\alpha+1)\setminus{^{\beta\downarrow}\alpha}$, the first term of $\sigma$ must be $\alpha$. Let $\eta$ be the first length of $\sigma$, and suppose that $\eta<\beta$. What’s left of $c(\sigma)$ when $\alpha$ and $\eta$ are stripped from it is the code of some member of $\,^{\beta\downarrow}\alpha$, so the set of $\sigma\in\,^{\beta\downarrow}(\alpha+1)$ with first term $\alpha$ and first length $\eta$ has order type $\gamma$, and it follows easily that $$\left(\!\!\binom{\alpha+1}{\beta}\!\!\right)=\gamma\cdot\beta+1\;.$$

Now let $\beta=\omega^{\lambda_1}+\omega^{\lambda_2}+\dots+\omega^{\lambda_m}$, where $\lambda_1\ge\lambda_2\ge\ldots\ge\lambda_m$; this representation, which is a variant of Cantor normal form, is unique. Suppose that $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\gamma$. As before, $\,^{\beta\downarrow}\alpha$ is an initial segment of $\,^{\beta\downarrow}(\alpha+1)$. Suppose that $\sigma\in\,^{\beta\downarrow}(\alpha+1)\setminus{^{\beta\downarrow}\alpha}$, so that the first term of $\sigma$ is $\alpha$, and let $\eta$ be the first length of $\sigma$. If $\eta<\omega^{\lambda_1}$, what’s left of $c(\sigma)$ when $\alpha$ and $\eta$ are stripped off the front is the code of some member of $\,^{\beta\downarrow}\alpha$. Thus, if $c(\tau)=\langle\alpha,\omega^{\lambda_1},0,\omega^{\lambda_2}+\dots+\omega^{\lambda_m}\rangle$, the set of predecessors of $\tau$ in $\,^{\beta\downarrow}(\alpha+1)$ has order type $\gamma\cdot\omega^{\lambda_1}$. An easy induction now shows that $$\begin{align*} \left(\!\!\binom{\alpha+1}{\beta}\!\!\right)&=\gamma\cdot\omega^{\lambda_1}+\gamma\cdot\omega^{\lambda_2}+\dots+\gamma\cdot\omega^{\lambda_m}+1\\ &=\gamma\cdot\Big(\omega^{\lambda_1}+\omega^{\lambda_2}+\dots+\omega^{\lambda_m}\Big)+1\\ &=\gamma\cdot\beta+1\;.\tag{2} \end{align*}$$

Henceforth I assume that $\lambda_1\ge 1$. It follows from $(2)$ that the dominant term in the Cantor normal form of $\left(\!\!\binom{n+1}{\beta}\!\!\right)$ is $\omega^{\lambda_1\cdot n}$ for $n\in\omega$. (It’s entirely possible to write out the whole expansion, but it’s rather messy.)

If $\alpha$ is a limit ordinal, the sets $\,^{\beta\downarrow}\lambda$ for $\lambda<\alpha$ are increasing initial segments of $\,^{\beta\downarrow}\alpha$, so $$\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\sup_{\lambda<\alpha}\left(\!\!\binom{\lambda}{\beta}\!\!\right)\;.\tag{3}$$

It particular, $\left(\!\!\binom{\omega}{\beta}\!\!\right)=\omega^{\lambda_1\cdot\omega}$, and it follows from $(2)$ and $(3)$ that for $\alpha\ge\omega$ the dominant term in the Cantor normal form of $\left(\!\!\binom{\alpha}{\beta}\!\!\right)$ is $\omega^{\lambda_1\cdot\alpha}$, with $\left(\!\!\binom{\alpha}{\beta}\!\!\right)=\omega^{\lambda_1\cdot\alpha}$ when $\alpha$ is a limit ordinal.

| cite | improve this answer | |
  • $\begingroup$ Ah, thank you! I thought of that encoding but didn't think of applying it to Cantor normal form. That's a much nicer recursion than what I found. But I'm a little confused about why all those terms are being multiplied by $\gamma$ on the left, rather than $\gamma$ for the first one and smaller things thereafter. $\endgroup$ – Harry Altman Mar 1 '12 at 0:41
  • $\begingroup$ Also, it seems to me this has problems when some of the $\lambda_i=0$? Certainly it fails for $\alpha, \beta$ finite. $\endgroup$ – Harry Altman Mar 1 '12 at 2:05
  • $\begingroup$ Having looked at the problem of computing these some more, I'm now quite certain that this answer is wrong. As I noted above, it fails when α and β are finite, but it also fails in many other cases. For instance, "ω multichoose ω+1" is $\omega^\omega$, but "ω+1 multichoose ω+1" is $\omega^{\omega+1}+\omega+1$, not $\omega^{\omega+1}+1$. Your recursion is correct when β is a power of ω, though. (I actually have a rule for computing these in general, but it is unfortunately quite complicated...) $\endgroup$ – Harry Altman Jan 25 '15 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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