17

I'm wondering if there are any recursion principles more general than the following, first given by Montague, Tarski and Scott (1956):

Let $\mathbb{V}$ be the universe, and $\mathcal{R}$ be a well-founded relation such that for all $x\in Fld\mathcal{R}$, $\{y:y\mathcal{R}x\}$ is a set. Further, let $\mathbb{F}$ be a function with $dmn\mathbb{F}=Fld\mathcal{R}\times\mathbb{V}$. Then there exists a unique function $\mathbb{G}$ such that $dmn\mathbb{G}=Fld\mathcal{R}$ and for all $x\in Fld\mathcal{R}$, $$\mathbb{G}(x)=\mathbb{F}(x,\mathbb G\restriction\{y:y\mathcal{R}x\}).$$

Specifically, I would like to be able to drop the requirement that $\{y:y\mathcal{R}x\}$ be a set. I am attempting to define by recursion a function on $O_n\times O_n$ ordered lexicographically, which is a well ordering and consequently a well-founded relation, however $\{y:y<(0,\alpha)\}$ is a proper class for all $\alpha>0$. The proof of the above theorem in the context of MK class theory (and even its statement) rely pretty explicitly on this not happening, however I am aware that category theorists often work in situations where they need to aggregate together many proper classes and manipulate them/construct morphisms between them.

Is there a (perhaps large-cardinal based) strengthening of this theorem that would allow one to legitimately make such a definition by recursion in a class-theoretical context?

Qfwfq
  • 22,715
Alec Rhea
  • 9,009
  • This post just received a downvote for some reason -- is there something I can do to clarify the question better? I've considered this for about a month on my own now and come up with no obvious generalizations, so prior to really digging in and trying to generalize it myself I was wondering if it had already been done. – Alec Rhea Jul 21 '17 at 23:38

1 Answers1

19

Yes, there are such principles. In fact, there is a natural hierarchy of such class-theoretic recursion principles, which form a hierarchy of strength transcending Gödel-Bernays set theory GBC. These principles have become important in the emerging field known as the reverse mathematics of second-order set theory, which seeks to classify various natural second-order set theoretic principles into a hierarchy over GBC.

The principle of elementary transfinite recursion asserts that for any well-ordered class relation $\Gamma$ on a class $I$, not necessarily set-like, and any first-order property $\varphi$, allowing class parameters $Z$, there is a solution $S$, meaning a class $S\subset I\times V$, such that $S_i=\{x\mid \varphi(x,S\upharpoonright i,Z)\}$, where $S\upharpoonright i=\{(j,x)\in S\mid j<_\Gamma i\}$ is the part of the solution below $i$. Thus, we define a class by recursion along $\Gamma$, where at each stage we define a new class in terms of the solution previous to that stage.

One can formalize your function-based recursion using this kind of formalism.

In my recent paper

V. Gitman and J. D. Hamkins, Open determinacy for class games, in Foundations of Mathematics, Logic at Harvard, Essays in Honor of Hugh Woodin’s 60th Birthday, A. E. Caicedo, J. Cummings, P. Koellner, and P. Larson, Eds., American Mathematical Society, 2016. (arxiv:1509.01099)

we proved that ETR is equivalent to the principle of clopen determinacy for class games. Meanwhile, open determinacy is a little stronger, and below $\Pi^1_1$-comprehension.

In my recent paper

V. Gitman, J. D. Hamkins, P. Holy, P. Schlicht, and K. Williams, The exact strength of the class forcing theorem, under review, (arxiv:1707.03700)

we proved that the principle of $\text{ETR}_{\text{Ord}}$, which allows recursions only of length $\text{Ord}$, is equivalent to a list of 12 natural statements, including the class forcing theorem, the existence of truth predicates of various kinds for infinitary logic, the existence of iterated truth predicates for first-order logic, the existence of Boolean set-completions of partial orders, and others.

Hierarchy of theories between GBC and KM

The picture that is emerging from this analysis is that the natural second-order set theories are ranked by the amount of recursion they support.

Joel David Hamkins
  • 224,022
  • 2
    This is exactly what I was looking for and more -- thank you. – Alec Rhea Jul 22 '17 at 01:56
  • 2
    Great! I'm glad you found it useful. Please feel free to post further questions about ETR if there are any other issues, since it isn't exactly the same as the set-up you described. – Joel David Hamkins Jul 22 '17 at 02:02
  • I wonder if you could use these ideas to come up with strong recursion principles in type theory and programming languages. In type theory we know recursion principles which allow one to compute fixed points of universe-forming operators, which amounts more or less to Mahlo cardinals. But nobody has gone beyond that. I see little reason that Mahlo cardinals would present a natural barrier. – Andrej Bauer Jul 22 '17 at 08:56
  • @JoelDavidHamkins Much appreciated -- for starters, my paper is written in the context of MK class theory, so if I understand the premise of your paper correctly I should be able to prove ETR directly, no? – Alec Rhea Jul 22 '17 at 15:01
  • @AndrejBauer I don't know enough type theory to say, but I expect that the main idea of ETR can likely be cast in that system. The fixed-point style of recursion, however, is a little different, and I'm not sure exactly how they are connected. ETR is weaker than KM, however, and so weaker than one inaccessible in consistency strength; so definitely weaker than a Mahlo. The rise of Mahloness for fixed-points is not surprising, since the closure-points of an operation is club, and so Mahloness gives you regular or even inaccessible fixed points in general circumstances. – Joel David Hamkins Jul 22 '17 at 17:58
  • @AlecRhea, Yes, KM proves the full ETR. I would encourage you to cast your theory in GBC+ETR, however, if that is what is needed, since the new subject is about finding callibrating the power of these various second-order assertions. So you can fit yours into the hierarchy by using GBC+ETR instead of KM. – Joel David Hamkins Jul 22 '17 at 17:59
  • @JoelDavidHamkins I will take you up on that! I'm still an undergraduate student so almost all of this is completely new information to me -- the original purpose of my paper was to provide a new and hopefully more straightforward definition of the Surreal and Surcomplex numbers, showing that $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R},$ and $\mathbb{C}$ were all the smallest versions of totally ordered 'number systems' that exist-- I quickly began encountering problems of this nature along the way though. Thanks again for the assistance! – Alec Rhea Jul 22 '17 at 23:13
  • Alec, I would be interested in hearing further details about what you are proving. I am a little doubtful that you will need ETR in order to establish fundamental uniqueness properties for the surreals, although I do think you will need global choice. (See my related question: https://mathoverflow.net/q/227849/1946.) Feel free to send an email to me. – Joel David Hamkins Jul 23 '17 at 16:48
  • 1
    Incidentally, I just made a blog post at http://jdh.hamkins.org/second-order-transfinite-recursion-is-equivalent-to-kelley-morse-set-theory/ concerning the principle of second-order transfinite recursion, observing that it is equivalent to KM over GBC. – Joel David Hamkins Jul 23 '17 at 16:49
  • @JoelDavidHamkins My paper essentially shows that we can build $N_0$ out of $O_n$ in exactly the same fashion that we can build $\mathbb{R}$ out of $\mathbb{N}$ -- add a notion of additive negation to a totally ordered monoid under $+$ and $\times$ to obtain a ring, create a field of fractions for the ring to make it dense and consequently a field, and then cut up the field to real-close it and produce new limits. In the process, I 'tucked' all of the recursion typically used to define the surreals all the way back into ordinal arithmetic, then built upon these operations algebraically. – Alec Rhea Jul 23 '17 at 21:23
  • It occurred to me during this process that $\gamma$-numbers, $\delta$-numbers, and $\varepsilon$-numbers were the first three instances of special ordinals that 'absorb' the first three recursively defined operations on the ordinals. I was thusly motivated to extended the first three recursively defined operations on $O_n$ into a 'transfinite hyperoperation sequence' of recursively defined binary operations on the ordinals, with successors, $+$, $\times$, and $\uparrow$ as the first four operations in the sequence. This hyperoperation sequence is what I needed more powerful recursion for. – Alec Rhea Jul 23 '17 at 21:26
  • If the sequence is a valid mathematical object (which I believe you've given me the tools to show that it is), then we can generaize the notion of $\gamma$-numbers to the $\alpha^{th}$ hyperoperation and accordingly find 'closure points' for sets of ordinals with very 'large' binary operations defined on them. For example, the $\omega^{th}$ hyperoperation takes any two natural numbers greater than $2$ and produces $\omega$ as the union of their composition under every finitely-indexed hyperoperation. – Alec Rhea Jul 23 '17 at 21:31
  • I would be interested in reading your article when it is available. – Joel David Hamkins Jul 24 '17 at 15:48
  • @JoelDavidHamkins Here's a preprint: https://arxiv.org/abs/1706.08908 -- note that I still have to update the section on recursion. After I finish that and include some work I've done on limits in the 'Surrationals', I intend to try and publish over at the Journal of Logic & Analysis. Thanks for showing interest! – Alec Rhea Jul 24 '17 at 16:08
  • Thanks for the link. I'd suggest dramatically lowering the ratio of background material/new material. You don't need to state the axioms of set theory or develop trivial facts about ordinals. But I do find extremely interesting your proposal to construct the surreals directly from the ordinals. Is there a way for you to summarize this construction without the new notation? How does your construction relate to the fact that the surreals are known to have many different incompatible integer parts? (see https://mathoverflow.net/q/72691/1946) By the way, def 3.2.1 seems to mix up alpha and beta. – Joel David Hamkins Jul 24 '17 at 17:32
  • Ah, the 'background noise' is a relic of the fact that I originally wrote this with the intention of working with a string theorist in the dept. at my college on convergent series in larger real-closed fields, and wanted to introduce him to ordinals as I saw them -- I'll take your advice for publication. I'm not entirely sure yet how my construction relates to the Omnific integers, however I believe that they satisfy a predicate relative to $N_0$ that $\mathbb{Z}\infty$ doesn't in my construction -- namely, there are $r\in N_0\ni\nexists n[n\in\mathbb{Z}\infty\wedge n\leq r<n+1]$. – Alec Rhea Jul 25 '17 at 15:32
  • Here's the shortest summary I can offer: we first move from recursive addition and multiplication to Hessenberg (commutative) multiplication and addition on the ordinals, to make them a 'dual ordered monoid' under $+$ and $\times$. We then define $$\ddot+={\big((a,b),c\big):(1^{st}a+1^{st}b,2^{nd}a+2^{nd}b)=c}.$$ $$\ddot\times={\big((a,b),c\big):(1^{st}a\times2^{nd}b+2^{nd}a\times1^{st}b,1^{st}a\times1^{st}b+2^{nd}a\times2^{nd}b)=c}.$$ These are commutative addition and multiplication structures on $O_n\times O_n$, using Hessenberg multiplication and addition of ordinals. – Alec Rhea Jul 25 '17 at 15:38
  • We then define $\mathbb{Z}_\infty$ as (essentially) the class of all Cantor normal forms with positive and negative integer coefficients. You can also consider the integral monoid algebra $\mathbb{Z}(T^{O_n})$ if that is more familiar, or the class of all ordered pairs of Cantor normal forms where the left and right coordinates share no powers of $\omega$ under the above multiplicative and additive structure, plus some equivalence classes to 'select' the correct members of $O_n\times O_n$. I think this is actually also the Grothendieck group of the ordinals under Hessenberg addition. – Alec Rhea Jul 25 '17 at 15:41
  • We then move to $\mathbb{Q}\infty=\mathbb{Z}\infty\times\mathbb{Z}\infty\sim{0}$ and write $p\in\mathbb{Q}\infty$ such that $p=(a,b)=\big((\alpha,\beta),(\gamma,\zeta)\big)$ as $p=\frac{a}{b}=\frac{\beta-\alpha}{\zeta-\gamma}$ -- this is a totally ordered field without nontrivial roots. Things get a little technical here however, as Dedekind cuts in this field are proper classes. To get around this, I first observe that we can close out smaller rings/fields at each $\delta$-number $\delta$ since $\alpha,\beta<\delta\implies\big(\alpha+\beta<\delta\wedge\alpha\times\beta<\delta\big)$. – Alec Rhea Jul 25 '17 at 15:50
  • I suggest that we then view $N_0$ as the union of all Dedekind cuts in all smaller $\mathbb{Q}\lambda$, where $\lambda$ is a $\delta$-number. Each of these cuts is a proper subset of some proper class cut in $\mathbb{Q}\infty$, and I believe that these cuts are equivalent to the 'gaps' in the Surreals. We can also restrict the construction to $\omega$ (the first transfinite $\delta$-number) to obtain $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$, and $\mathbb{Z}$ being the only cyclic ring makes $\mathbb{Q}$ the only Archimedean field, making $\mathbb{R}$ the only complete field. – Alec Rhea Jul 25 '17 at 15:55
  • When I say $\mathbb{Q}$ is the only Archimidean field, I just mean the only one in this construction that has no nontrivial roots since $\mathbb{R}$ is obviously also Archimedean. Also, $\mathbb{Q}\infty$ is technically the coprime subset of $\mathbb{Z}\infty\times\mathbb{Z}_\infty\sim{0}$, but this is pretty much just a technicality. I think this is about as short as I can make it! – Alec Rhea Jul 25 '17 at 16:01
  • Can we describe it more simply like this: you consider formal differences $\alpha-\beta$ of ordinals having no common term in their Cantor normal form, and then extend the natural ordinal arithmetic in the natural way (combining/canceling like terms); then take the quotient field; then take the Dedekindian completion (i.e. filling only bridgable gaps, as in https://math.stackexchange.com/a/530523/413). – Joel David Hamkins Jul 25 '17 at 16:54
  • That hits it right on the head, and I think I actually missed the bit about bridgeable gaps! When I shorten my paper, would it be alright with you if I mentioned you in thanks for this conversation and for catching that?Also returning to the transfinite hyperoperation sequence for a second, I think we might be assuming the existence of certain inaccessible cardinals if we assume that there is an ordinal greater than $\omega$ which 'absorbs', for example, the $\omega^{+^{th}}$ hyperoperation, but I haven't developed my large cardinal skills enough to be sure yet. – Alec Rhea Jul 25 '17 at 17:12
  • That's fine about acknowledging me. (Thanks!) About the absorbing ordinals---I haven't absorbed your hyperoperations yet, but if the operations are definable in set theory, then there will always be ordinals that are closed under those operations. One can find them by the replacement axiom: first apply all the operations as much as possible, take a supremum, and repeat. If your operations have finite arity, then you will find a closure point in $\omega$ steps this way. But even in the infinitary arity, if the operations are definable, there will be closure points by the reflection theorem. – Joel David Hamkins Jul 25 '17 at 17:29
  • You are correct once again! I must have missed the offer to continue this convo by email the first time -- I will inbox you sometime in the near future with the revised edition of my paper, and thanks again for this informal peer review. – Alec Rhea Jul 27 '17 at 02:21