It is a standard exercise (see Jech's "Set Theory" Exercise 13.8) to prove that ordinal addition and multiplication are $\Delta_1$ expressible functions. The proof for addition comes from noting that $\alpha+\beta$ is order isomorphic to the disjoint union $(\{1\}\times \alpha)\cup (\{2\}\times \beta)$ under the lexicographical order (and everything after the "order isomorphic" part is all $\Delta_0$ expressible). Similarly $\alpha\cdot \beta$ is order isomorphic to the direct product $\beta\times \alpha$ under the lexicographical order.

It was surprised to see that ordinal exponentiation was not listed in the exercise. After a serious google search, the only reference I could find was a wiki article that claimed ordinal exponentiation was indeed $\Delta_1$. I couldn't make the same argument work here, since the corresponding order structure for $\alpha^\beta$ is the set $\{f:\beta\to \alpha\,|\, f\text{ has finite support}\}$ and I couldn't find an easy way to express this set in a $\Sigma_1$ way.

Is ordinal exponentiation $\Sigma_1$? If so, how does the proof go? (Hopefully I didn't miss an easy argument!)

(This also raised the question in my mind of whether or not, given $X$, the set of finite subsets of $X$ is $\Sigma_1$. I'd like to know the answer to that as well.)

Added: If I didn't make any mistakes, ordinal exponentiation is $\Delta_1$ if and only if that finite support set above is $\Delta_1$ definable. Thus, in principle, there should be an easy way to get a $\Sigma_1$ definition of that set. This seems surprising to me.

  • $\begingroup$ A (nonempty) set $A$ is finite iff there is a surjection from some successor ordinal not above any limit ordinal. $\endgroup$ Dec 18 '18 at 20:45
  • 5
    $\begingroup$ I'd prove all these facts (for addition, multiplication, and exponentiation) by invoking the fact that the class of $\Delta_1$ functions is closed under recursion over ordinals. This ought to be in, for example, Barwise's book "Admissible Sets and Structures". $\endgroup$ Dec 18 '18 at 21:21
  • $\begingroup$ @NoahSchweber If we could get the full set $\{f:\beta\to\alpha\}$ in a $\Sigma_1$ way, then adding the finite support condition would be easy (as finiteness is $\Delta_1$). Do you see an easy way to get that full set of functions (using ordinals $\alpha,\beta$ as parameters)? Or were you thinking of some other argument? $\endgroup$ Dec 18 '18 at 22:48
  • $\begingroup$ @AndreasBlass If you have a reference, I'd appreciate it. I've thought about using Lemma 13.12 from Jech's "Set Theory" but couldn't quite get the argument to work out. $\endgroup$ Dec 18 '18 at 22:49

First, I claim that one can express in $\Delta_1$ form the following property of $\alpha,\gamma, g$, which I'll abbreviate as $P(\alpha,\gamma,g)$: $\alpha$ and $\gamma$ are ordinals, $g$ is a function with domain $\gamma$, and, for each $\beta<\gamma$, $g(\beta)$ is the set of finitely supported functions $f:\beta\to\alpha$. Being an ordinal and being a function with a specified domain are easily $\Delta_1$, so the problem is to specify the values $g(\beta)$. But this can be done by saying that $g(0)=\{\varnothing\}$, that the elements of $g(\beta+1)$ are exactly the things of the form $f\cup\{\langle\beta,\xi\rangle\}$ with $f\in g(\beta)$ and $\xi<\alpha$ (for each $\beta+1<\gamma$), and that, for all limit ordinals $\lambda<\gamma$, the elements of $g(\lambda)$ are exactly the things of the form $f\cup((\lambda-\beta)\times\{0\})$ with $\beta<\lambda$ and $f\in g(\beta)$.

Once we have this $\Delta_1$ definition of $P$, we can express "$x$ is the set of finitely supported functions $\beta\to\alpha$" by saying "there exists $g$ such that $P(\alpha,\beta+1,g)$ and $g(\beta=x)$." Except for "there exists $g$", everything here is $\Delta_1$, so the whole statement is $\Sigma_1$.

The same idea, for converting a recursive definition to an explicit definition, can be used to support my earlier comment about using the recursive definitions of addition, multiplication, and exponentiation to show that these are $\Delta_1$-definable. One says, for example, that $\alpha^\beta=\theta$ iff there is a function $g$ with domain $\beta+1$ satisfying the inductive clauses for the definition of exponentiation and $g(\beta)=\theta$. That's a $\Sigma_1$ definition and, since exponentiation is provably total, $\Delta_1$-definability follows. (As far as I know, the idea of converting recursive definitions to explicit ones goes back to Dedekind.)


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.