Googology Wiki


Higher order set theory

LittlePeng9 September 21, 2014 User blog:LittlePeng9

In this blog post I'll try to define in precise way my extension of language of set theory to transfinite orders.


Most of us know the definition of FOST (first order set theory) - it's a language in which have infinite set of variables, logical connectives \(\lor,\land,\neg,\Rightarrow,\exists,\forall,(,)\) (three of these connectives don't appear in original definition, but I decided to add them, for simplicity) and set connectives \(=,\in\). Both quantifiers range over a prespecified universe of sets \(V\), and all variables are meant to be elements of this class. \(V\) isn't precisely defined, but it's supposed to be a class which satisfies, intuitively, everything we think is true, e.g. every Goodstein sequence terminates, RS theorem holds and so on.

Agustin Rayo has defined the language along with formal definition how it should be understood. I'm going to avoid this here. I think it's quite clear what we mean by FOST formula being true.

\(Rayo(n)\) is defined as the largest natural number we can define in FOST using at most n symbols, where "definition" is a formula which is true for precisely one set, and "natural number" is a finite Von Neumann ordinal.


Second order set theory. This is an extension of FOST in which we introduce second class of variables - in FOST there were only variables which could range over elements of \(V\). Now, our new variables can range over subcollections of \(V\), which are collections of sets, or classes. I will now present a sketch of idea on how to define Rayo's function in this system, thus proving it strictly stronger than FOST.

The following construction is essentially due to J. D. Hamkins, you can see it here.

First we will define truth predicate as follows: it's a formula \(\psi(\phi,a)\), where \(\phi\) is a formula encoded in a simple way and \(a\) is variable assignment for \(\phi\), coded as a single set, and this predicate satisfies Tarskian definition of truth, which I'm not gonna explain in detail here, it just means that if \(\phi(a)\) is true under standard understanding of logical and set connectives, then \(\psi\) is true too.

We define satisfaction class for a formula \(\phi\) if it works like a truth predicate limited to subformulas of \(\phi\), and it's a class of pairs \(\langle\phi',a'\rangle\). This is definable quite easily, because from description of \(\phi\) we can quickly figure out all the subformulas and how they are related by truth definition. Now we can define truth predicate \(\psi(\phi,a)\) as "There exists a satisfaction class \(X\) for formula \(\phi\), such that \(\langle\phi,a\rangle\in X\)". This can be shown to be a truth predicate by using Morse-Kelley set theory, which has quite "natural" axioms, so we can assume they hold in \(V\). 

Now, process of finding the length of formula given its number \(n\) is very simple, and can be done even by a Turing machine. With truth predicate we can also easily check if formula is definition - is formula \(\exists x \phi(x)\land\forall y: \phi(y)\Rightarrow y=x\) true? We can also easily verify that the definition defines natural numbers. With these tools, it's a simple step to define \(Rayo(n)\).

Here I'm going to denote second order analogue of Rayo's number by \(Rayo_2(n)\) (not to be confused with Rayo-based FGH).


Let's now introduce third type of variables - they could range over subcollections of subcollections of \(V\) - we could quantify over "superclasses", elements of which would be classes. A question arises - can the above construction be extended so that in this third order set theory we could define second-order truth predicate? As far as I know there is absolutely no obstructions. If that's really true, we can similarly define \(Rayo_2(n)\) in third order set theory, so, again, we have a significant improvement in strength. Define \(Rayo_3\) in obvious way.

This pattern can continue - we can have nth order set theory for any n by adding more classes of variables, and \(Rayo_n\) function can be defined straightforwardly. What now is defined is higher order set theory - this is the "union" language of every n-th order set theory. What it means is that it has infinitely many possible quantifiers, which can quantify over sets, classes, superclasses, hyperclasses, classclasses and whatever one imagines. This can be thought of as an upper bound on all of nOST for finite n, so we can give it a name \(\omega\)OST - \(\omega\)-th order set theory.

There is however a problem when we try to define \(Rayo_\omega(n)\) - now that we have infinitely many types of symbols to choose from, it isn't obvious that this number is well defined. Solution I came up with is adding a special syntax as follows: if we have subformula of form x(y), where x,y are variable symbols, and y takes some natural number value n in some assignment, then we interpret x as n-th order variable. Thanks to this construction we have only finitely many non-isomorphic (isomorphic - equivalent up to renaming the variables) formulas of fixed size, which can define only finitely many natural numbers, thus there exists the largest one among them. This will be the basis of function \(Rayo_\omega\).

Now it's clear that this function outgrows all of \(Rayo_n\) for finite n. Can \(\omega\)OST define a two variable function \(Rayo(m,n)=Rayo_m(n)\)? I don't know, but I think this might be possible, because, as opposed in my earlier formulation, in x(y) variable y isn't forced to be fixed. It can vary, but for it to be \(Rayo_\omega\) contestant it must actually define a number - irrespectively of choice of y. But because we could quantify over variable y... I don't know.

There is also one thing I wanted to mention - notice how this hierarchy of sets, classes, superclasses,... actually is smoothly extending - sets are actually classes, classes are superclasses, and so on. We will be taking union of all of these next, so I thought I'll mention it.


Hmm, what can we do now that we have \(\omega\) types of variables? It's simple - add another one! Right now we just have to barely extend out semantics so that x(y) is meaningful when y takes on value \(\omega\). This way the variable can range over subcollections of this monstrosity mentioned at the end of above section. Can we now define truth predicate for \(\omega\)OST in \(\omega+1\)OST? I hope so, but I wouldn't say for sure (the restriction on y in x(y) might break something in our argument, but I doubt it does). Thus we can define \(Rayo_\omega\), and, well, outgrow it with \(Rayo_{\omega+1}\), which is defined... you know how it's defined.


I think it's quite clear how the pattern continues, and here I'm going to specify how the construction continues for general ordinal \(\alpha\).

First of all, let's define \(V^1=V\) to be universe of all sets we have. Further let \(V^2\) be universe of all classes of \(V\), let \(V^3\) be universe of all superclasses and so on. Generally, let \(V^{\alpha+1}\) be the universe of all subcollections of \(V^\alpha\), and for \(\alpha\) limit we define \(V^\alpha=\bigcup_{\beta<\alpha}V^\beta\). By simple transfinite induction we can see that if \(\alpha<\beta\), then \(V^\alpha\subsetneq V^\beta\).

Now we can formalize our considerations on \(\alpha\)OST. For ordinal \(\alpha\) we define it as a language with syntax just as FOST, plus another rule that if x,y are variables, then x(y) is a valid formula. We give it following semantics: in a given truth assignment, if y takes an ordinal value \(\beta\leq\alpha\), and x is element of \(V^\beta\), then we interpret x(y) just like x. If, however, x isn't element of \(V^\beta\), or y isn't an ordinal \(\leq\alpha\), then we think of it as an object which contains nothing, is contained in nothing and equals nothing, even itself (this is so that we can check if x is in \(V^\beta\) by using formula x=x). Note that it differs a bit from sections above, because there x(y) for y=\(\omega\) already ranged over subcollections of \(V^\omega\), but I changed that for simplicity.

I forgot to mention that \(Rayo_\alpha\) is defined in obvious way. But note that it's not necessarilly true that \(\alpha+1\)OST can define \(Rayo_\alpha\) - if \(\alpha\) is ridiculously large countable ordinal, then it will be too large to differ from some smaller ordinal - it will have so called reflection properties. So that for every formula which \(\alpha\) satisfies, we will have smaller ordinal \(\alpha'\) which satisfies it too, thus we will have no way to find out which one is which. But such large ordinals are far beyond imagination.

This is quite close to the best thing we can get from this system. One more thing we can do is to remove \(\alpha\) completely, leaving no size bound for \(\alpha\). This will lead to...


Ordinal order set theory!

The definition is quite simple - it's just an analogue of \(\alpha\)OST, except it doesn't have any \(\alpha\). Let's look back at the definition of \(\alpha\)OST - where was the ordinal used? It was used only to put a limit on \(\beta\). So OOST will be the same, except there is no limit on \(\beta\) - variable y in expression x(y) can now take any ordinal value, so x can take value from any level of hierarchy \(V^\beta\) (note however, that y still needs to be an ordinal). By setting y to be a free variable, or putting it under existential quantifier, allows us to get absolutely any value of x from the hierarchy.

While we can make fair use of countable ordinals, it's not perfect, because we can easily see that there still are countable ordinals which we can't define, but this will happen always with countable language and finite formulas. But we are not limited only to countable ordinals - OOST actually contains \(\omega_1\)OST, which contains formulas of all \(<\omega_1\)OST. It might also contain a uniform truth predicate for \(\alpha\)OST for \(\alpha<\omega_1\) (with uniform I mean that it is a single formula which can take \(\alpha\) as parameter), and if it doesn't, then \(\omega_1+1\)OST quite surely does.

We can then continue with hierarchy, we can have \(\omega_2\)OST, \(\omega_\omega\)OST, (fixed point of \(\alpha\rightarrow\omega_\alpha\))OST and so on and so on. Who knows, maybe there is an inaccessible cardinal to top it off with? Maybe there is even two of them? How about the whole large cardinal hierarchy? While some of it can be argued to exist "naturally", not all of them are the subject to "intuitively true" existence.

Oh, I almost forgot - define \(Rayo_O(n)\) as... well, it's clear, but I'm going to say it - it's the largest natural number which can be defined in OOST using at most n symbols. But definitions of many of these concepts can be quite long - for example, imagine the uniform truth predicate for \(\omega_\omega\)OST - this thing is going to be long as hell when written in formal language of set theory. However, I can say that in googolplex symbols we can write something quite large. And now imagine we have that many symbols to deal with! This is unreasonably large now. So the number \(Rayo_O(Rayo_O(10^{10^{100}}))\) is already quite a number...


As both Deedlit and Wyth have pointed out, we can extend this idea beyond OOST by going "beyond ordinal numbers". As Wyth points out, O doesn't really have to be an absolute infinity, but for this to be of good use we will need it to be beyond all ordinals we will ever define, just like in ordinal collapsing functions we don't define \(\Omega\) as BH ordinal, because we might later want to extend the notation beyond BH, and such small \(\Omega\) might mess something up. So O might be thought of as a "surordinal" number of a sort. For now this is just an idea, which I might develop further.


Okay now, from now on all of this might be a meaningless gibberish, and I'll assume some of the things intuitively, but I'll try my best.

Let's define \(O\) to be the order type of class \(\text{Ord}\) of all ordinals. It can be also understood to be kind of ordinal number - a "superordinal". It's similar to ordinals in a way that we can still do operations on this, for example, \(O+1\) would be order type of \(\text{Ord}\) plus one element at the end.

Now we can extend our construction of \(V^\alpha\) to \(\alpha\) which are these "superordinals" beyond \(O\) in quite straightforward way. When one actually thinks about it, we can actually figure out that \(V^\alpha=V_{O+\alpha}\), where construction of \(V\) is extended beyond all ordinals. But let's stick to notation used above.

To allow definitions beyond \(O\) we don't actually need to add anything to our language - we can define \(O\) as class of all ordinals, and then define \(O+1=O\cup\{O\}\) and so on. The definition of \(\alpha\)OST is just as above, also with \(\alpha\) being superordinal.

Is it any stronger? I believe that it actually is - I cannot see any point at which construction of \(\alpha\)OST truth predicate in \(\alpha+1\)OST would fail when \(\alpha=O\), so it seems that we can just keep the hierarchy going. 

Now that we have notion of \(O\), we can easily go to \(O+1,O+O, O*O, O^O, \epsilon_{O+1}, \omega_{O+1}\) and what not (at least I believe so (I mean, I'm quite sure we can make a definition of it, but will it make sense?)). Now, while \(O\) is a class, \(O+1\) is actually a superclass, \(O+2\) is in \(V^4\) and so on. \(O*2\) is already in \(V^{O+1}\) I believe, and \(O^2\) is in \(V^{O^2+1}\). This, however, isn't useless, because we can define \(O^2\) in weaker systems - it will just be a useless definition up until \(O^2+1\)OST. 

Note that all these superordinals so far can be thought of as order type of some well ordering of \(\text{Ord}\), or equivalently \(O\). We can then define something which would be a collection of all such order types, and it would create even weirder thing, which I'll denote \(O_1\) (in analogy to \(\omega\) and \(\omega_1\)). Now we could take collection of all reordering of this, thus getting \(O_2\). Continuing, we can get \(O_3,O_\omega,O_{\omega_\omega}\), even \(O_O,O_{O_O}\), the least fixed point of \(\alpha\mapsto O_\alpha\), and so on and so on. I bet we can even continue this madness, by defining some analogue of ordinal collapsing function in here, which would get us beyong everything reasonable (as if there was anything reasonable left!).

So yeah, \(Rayo_{O_O}^{100}(10^{10^{100}})\) would be quite big.

Beyond "Beyond!"?

Now let's define \(O'\) to be a limit of everything above...

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.