I am wondering if there are any known bounds on how large $a\oplus b$ can get, where $\oplus$ is natural ordinal addition? I know that $a+b \le a\oplus b$, but is it true, for example, that $a\oplus b \le a+b+b$? What bounds have been put on $a\oplus b$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The bound mentioned in the OP holds: that is, $$\alpha\oplus\beta\le\alpha+\beta+\beta,$$ even with strict inequality if $\beta>0$. Since $\oplus$ is commutative, we actually obtain $$\alpha\oplus\beta\le\min\{\alpha+\beta+\beta,\beta+\alpha+\alpha\},$$ with strict inequality if $\alpha,\beta>0$.
To see this, let $\gamma$ be the leading exponent in the Cantor normal form of $\beta$ so that $$\omega^\gamma m\le\beta<\omega^\gamma(m+1)$$ for some $0<m<\omega$, and let $\alpha'$ denote the initial part of the CNF of $\alpha$ consisting of terms with exponent $>\gamma$ so that $$\alpha'+\omega^\gamma n\le\alpha<\alpha'+\omega^\gamma(n+1)$$ for some $n<\omega$. Then $$\alpha\oplus\beta<\alpha'+\omega^\gamma(n+m+1)\le\alpha'+\omega^\gamma n+\omega^\gamma(2m)\le\alpha+\beta+\beta.$$
answered Jul 16 at 8:56
-
$\begingroup$ I’ll refrain from further edits. But the bound can be shown optimal in that if $t(\alpha,\beta)$ is any expression using $\alpha$, $\beta$, $+$, $\min$, $\max$, and arbitrary ordinal constants, such that $t(\alpha,\beta)\ge\alpha\oplus\beta$ for all $\alpha,\beta$, then $t(\alpha,\beta)\ge\min\{\alpha+\beta+\beta,\beta+\alpha+\alpha\}$ for all $\alpha,\beta$. This may well be true even for expressions using $\cdot$, but this might require much more work to check. $\endgroup$ Commented Jul 16 at 12:50
-
$\begingroup$ Hmm, with $\cdot$, there are exceptions if $\alpha$ or $\beta$ is $1$: we have $\alpha\oplus\beta\le\alpha+\beta^2$, which is smaller than the bound above if $\beta=1\le\alpha$. But I think the optimality should hold for $\alpha,\beta\ge2$. $\endgroup$ Commented Jul 16 at 13:04
-
$\begingroup$ Would expressions like $a\oplus b < a+b+a$ fall under the same condition? My context is that I am writing a computer verified proof, and I need specific bounds on what $(a\oplus b)-a-b$ can be. $\endgroup$ Commented Jul 16 at 15:44
-
$\begingroup$ As noted in comments to the other (now deleted) answer, $\alpha\oplus\beta\le\alpha+\beta+\alpha$ is false in general: it fails e.g. for $\alpha=\omega$, $\beta=\omega^2+1$. $\endgroup$ Commented Jul 16 at 15:53