More Abstract Background for my Question

Assuming a sort of realism about mathematical objects, there is an intuitive notion of the properties a mathematical object instantiates which is non-linguistic. Predicates express these properties but, assuming the language is countable, there may be more properties than can be expressed by predicates of the language. While I'm somewhat familiar with how to characterize the predicates the objects of a theory satisfy (in terms of various hierarchies, e.g., arithmetical hierarchy, analytical hierarchy, and projective hierarchy), I am less clear on how to characterize properties these same objects have when there may be more properties than formulas in the language.

More Concrete Background for my Question

For example, first-order arithmetic as given by $\mathsf{PA}$ is not categorical and so admits non-standard models. There is, however, a standard model captured by True Arithmetic -- the set of sentences in the language of first-order arithmetic that are true in the structure given by $\mathsf{PA}$. These can captured in second-order arithmetic as the sentences that are arithmetical -- either $\Sigma^0_n$ or $\Pi^0_n$.

Since, however, there are only countably many formulas and a fortiori only countably many sentences. So, formulas that are $\Sigma^0_n$ or $\Pi^0_n$ with $n$ free variables can characterize $n$-place arithmetical predicates, but these don't obviously express every "truly arithmetic" property of the natural numbers. (Maybe there are only countably many "truly arithmetic" properties, but then the same issue arises for the properties of the reals as described by the (categorical) axioms characterizing the reals as a Dedekind-complete ordered field. Since there are uncountably many reals, if there is at least one distinct property per real then there are uncountably many properties of the reals.)

The Question

Since properties can typically be identified with sets of sorts (e.g., unary properties with sets of their instances and $n$-ary relations with sets of $n$-tuples instantiating them), is the relevant notion of "arithmetical property" that doesn't force the countability of the set of properties given by the sets classified by some relativized version of the arithmetical hierarchy? Or something like the Borel hierarchy? Is there a general way of pairing any categorical theory with the sets that correspond to properties possessed by objects of that theory? (In a way that doesn't count every set in the powerset of the domain as a "legitimate" property.)


In lieu of at least a vague definition of "legitimate property," this question is difficult to answer. However, one reasonable response is to say a bit about transfinite hierarchies of definability in general, in the hope that one or more of these is of interest.

Let's begin by focusing on $\mathbb{N}$. There is no obvious notion of "arithmetic mod parameters" which will work here: either our parameters are elements of $\mathbb{N}$ in which case (a) they're countable and (b) we gain nothing since each natural number is definable, or our parameters are elements of $\mathcal{P}(\mathbb{N})$ in which case every set corresponds to a property.

Instead of relativizing things, one possible line of attack is extending them: continue the arithmetic hierarchy "past $\omega$" in some reasonable way. The hyperarithmetic hierarchy is of course the best known way to do this, but it still reaches only countably many sets. Can we do better?

The answer is yes. Recall the definition of the constructible universe:

  • $L_0=\emptyset$

  • $L_\lambda=\bigcup_{\alpha<\lambda} L_\alpha$ for $\lambda$ limit.

  • $L_{\alpha+1}$ is the set of subsets of $L_\alpha$ which are definable in the structure $(L_\alpha, \in)$ (this is usually denoted "$\mathcal{P}_{def}(L_\alpha)$").

Let $\mathcal{P}^L(\mathbb{N})$ denote the collection of subsets of $\omega$ in $L$. I suspect that this will be fairly satisfying to you, based on the following:

  • $L$ is definable, and if $V$ is the set-theoretic universe and $W$ is an "inner model" of $V$ (= a class containing all ordinals and satisfying ZFC), then $L$ is definable in $W$ via the same definition defining it in $V$. So $L$, and its theory and the theory of its levels, are "absolute" in a precise sense.

  • It is consistent that there are uncountably many, but still fewer than continuum, subsets of $\mathbb{N}$ in $L$ - this will happen whenever we have $\omega_1^L=\omega_1<2^{\aleph_0}$ (and this can be gotten by e.g. adding $\aleph_2$-many Cohen reals to $L$). So I think this may be what you are looking for.

  • $\mathcal{P}^L(\omega)$ comes equipped with a hierarchy, namely $(L_\alpha\cap\mathcal{P}^L(\omega))_{\alpha<\omega_1^L}$, and this jibes nicely with the idea that legitimate properties should fall into a complexity hierarchy like the arithmetic hierarchy. Two quick notes on this:

    • Every set $s$ of naturals in $L$ shows up at some countable-in-$L$ level: letting $M$ be the minimal elementary substructure of $L$ containing $s$, the Mostowski collapse of $M$ alsocontains $x$ and is isomorphic to some $L_\gamma$ with $\gamma<\omega_1$ by the condensation lemma).

    • We can find even finer hierarchies - e.g. by looking at master codes - and these reveal tight connections with the Turing jump.

Now what about generalizing past $\mathbb{N}$?

For an arbitrary structure $\mathcal{A}$, we can form an analogue $L^\mathcal{A}$ of $L$ - this time a model of ZF + "urelements" corresponding to the elements of $\mathcal{A}$ - built with $\mathcal{A}$ on the "ground floor." We can then define $\mathcal{P}^{L^\mathcal{A}}(\mathcal{A})$ to be the collection of subsets of $\mathcal{A}$ which are in $L^\mathcal{A}$. A similar argument shows that $\mathcal{P}^{L^\mathcal{A}}(\mathcal{A})$ has size at most $\vert\mathcal{A}\vert^+$, which consistently is $<\vert\mathcal{P}(\mathcal{A})\vert$, so again we may can get an interesting hierarchy of sets.

Incidentally, going back to the countable, generalizations of the hyperarithmetic hierarchy (and related hierarchies) on arbitrary structures have been studied by Moschovakis and others.

We can also generalize past $L$ - under certain hypotheses, there are other "canonical" inner models which yield similar hierarchies - but that seems of secondary interest for now.

  • $\begingroup$ I didn't know Moschovakis' excellent book was reprinted by Dover! Awesome! $\endgroup$ – Nagase Oct 30 '17 at 22:40
  • $\begingroup$ @Nagase Yup! It's excellent! $\endgroup$ – Noah Schweber Oct 30 '17 at 22:49
  • $\begingroup$ Once again, exactly what I was after. You have a knack for sussing out the question I would have asked were I able to express it. The Moschovakis book is especially helpful. It had been sitting in my database for a while -- clearly I thought it was relevant to my interests at some point -- and looking at it now I wish I had started to work through it earlier. $\endgroup$ – Dennis Oct 31 '17 at 0:32

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.