MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is about the notion of a companion for a Spector class, as defined in Moschovakis's book Elementary Induction on Abstract Structures. I am interested in Spector classes on $\mathbb{R}$, which are just a type of boldface pointclass. The smallest one is IND, the class of (boldface) inductive sets, which I will consider as a typical example.

The companion of a Spector class $\bf \Gamma$ on $\mathbb{R}$ is a structure $(M,\in,R)$ with certain properties (listed in the book) such that $\bf \Gamma$ is the class of pointsets that are $\Sigma_1$-definable in $M$ with real parameters from the relation $R$. The companion of $\bf \Gamma$ is not unique, but its underlying set $M$ is unique and also the class of relations on $M$ that are $\Sigma_1$-definable from $R$ in $M$ with real parameters is unique.

The pointclass IND can also be described as the class of pointsets that are $\Sigma_1$-definable over $M$ from parameters in $\mathbb{R} \cup \lbrace\mathbb{R} \rbrace$ where $M = L_\kappa(\mathbb{R})$ is the least admissible level of $L(\mathbb{R})$. We must allow $\lbrace\mathbb{R} \rbrace$ itself as a parameter here or we would just get the ${\bf \Sigma}^1_2$ sets. For any companion $(M,\in,R)$ of IND we must have $M = L_\kappa(\mathbb{R})$.

Question: Is there a companion $(M,\in,R)$ of IND where the relation $R$ has a simple definition over $M = L_\kappa(\mathbb{R})$ (simpler than in Moschovakis's general construction of a companion?) Maybe something that is already studied in the fine structure of $L(\mathbb{R})$?

share|cite|improve this question
up vote 3 down vote accepted

The relation $R$ can be empty; i.e., if $\kappa$ is the least ordinal such that $L_\kappa(\mathbb{R})$ is admissible, then the structure $(L_\kappa; \in, \emptyset)$ is a companion of the pointclass $\mathrm{IND}$ of inductive sets. We can prove a somewhat more general statement.

Assume that $\kappa$ is an ordinal such that

  • $J_\kappa(\mathbb{R})$ is admissible (in which case $J_\kappa(\mathbb{R}) = L_\kappa(\mathbb{R})$, but there may be points later in the argument where it is necessary to use the Jensen hierarchy) and

  • $\kappa$ begins a $\Sigma_1$-gap in $L(\mathbb{R})$, meaning that $J_\alpha(\mathbb{R})$ is not a $\Sigma_1(\mathbb{R} \cup \{\mathbb{R}\})$-elementary substructure of $J_\kappa(\mathbb{R})$ for any ordinal $\alpha <\kappa$.

Then the structure $(L_\kappa; \in, \emptyset)$ is a companion for the pointclass $\mathbf{\Sigma}_1^{J_\kappa(\mathbb{R})}$. (So letting $J_\kappa(\mathbb{R})$ be the least admissible level of $L(\mathbb{R})$ we obtain the desired result for the pointclass $\mathrm{IND}$.)

The criterion for "companionship" that was not clear to me when posting the question was projectability: the existence of a $\mathbf{\Delta}_1^{J_\kappa(\mathbb{R})}$ partial surjection $\mathbb{R} \dashrightarrow J_\kappa(\mathbb{R})$.

The existence of a $\Sigma_1^{J_\kappa(\mathbb{R})}$ partial surjection $\mathbb{R} \dashrightarrow J_\kappa(\mathbb{R})$ is well-known. Moreover, from this we can easily get a $\Delta_1^{J_\kappa(\mathbb{R})}$ partial surjection as follows.

(I have edited my answer below to replace the more convoluted argument that I wrote before.)

Let $F: \mathbb{R} \dashrightarrow J_\kappa(\mathbb{R})$ be a $\Sigma_1^{J_\kappa(\mathbb{R})}$ partial surjection and let $\theta$ be a $\Sigma_1$ formula defining it over $J_\kappa(\mathbb{R})$. Then define $G: \mathbb{R} \dashrightarrow J_\kappa(\mathbb{R})$ by letting $(x,a) \in G$ if and only if there is an $\alpha < \kappa$ such that $$J_\alpha(\mathbb{R}) \models \theta(x,a) \quad\And\quad \forall \xi < \alpha\, J_\xi(\mathbb{R}) \models \forall y \in \mathbb{R}\, \neg\theta(y,a).$$ Then $F \subset G$ and it is easy to check that $G$ is $\Delta_1^{J_\kappa(\mathbb{R})}$ and that the range of $G$ is equal to the range of $F$, which is all of $J_\kappa(\mathbb{R})$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.