For any natural number $k \in \omega$ and any set $X$ the set $$T \subseteq \bigcup_{m \in \omega} (\omega^m)^k \times X^m $$ is a tree on $\omega^k \times X$ iff

$$(t_o, \ldots, t_k) \in T \: \Rightarrow \forall m \leq |t_0| \: (t_0 \upharpoonright m, \ldots, t_k \upharpoonright m) \in T,$$ i.e. the elements of $T$ are $k+1$-tuples of finite sequences of the same length.

It is known that any tree $T$ on $\omega^k \times X$ is well-founded if there is an order-preserving function $\rho: T \rightarrow Ord$.

Let $x = (x_0, x_1, \ldots x_{l-1}) \in (\omega^\omega)^l$. The set $T(x)$ is a tree on $\omega^{k-l} \times X$ defined as follows: $$(t_0, \ldots, t_{k-l}) \in T(x) \: \Leftrightarrow \: \exists m \: (x_0 \upharpoonright m, \ldots, x_{l-1} \upharpoonright m, t_0, \ldots, t_{k-l}) \in T.$$

It is also well-known that if $a \in \omega^\omega$ and $A \subseteq (\omega^\omega)^k$, then $A$ is $\Pi^1_1(a)$ iff there is a tree $T$ on $\omega^k \times \omega$ such that for any real $x \in (\omega^\omega)^k$: $$x \in A \: \Leftrightarrow \: T(x) \text{ is well-founded,}$$ where the relation $\{(i, x): s_i \in T(x)\}$ is computable from $a$, for some computable enumeration $(s_i)_{i \in \omega}$ of the set of finite sequences such that $\forall i \: |s_i| \leq i$.

Now the crucial definition: for a set $A \subseteq (\omega^\omega)^k$ and any set $X$ we say that $A$ is $X$-Suslin if there i a tree $T$ on $\omega^k \times X$ such that$A = p[T]$, i.e. for any $x \in (\omega^\omega)^k$ it holds that $$ x \in A \: \Leftrightarrow \: T(x) \text{ is ill-founded}.$$

To illustrate the definition, note that every analytic set is $\omega$-Suslin, and observe that (under CH?) any set $A \subseteq (\omega^\omega)^k$ is $2^{\aleph_0}$-Suslin, but an important thing is that the key lemma in the (standard) proof of Shoenfield's Absolutness is the fact that any $\mathbf{\Sigma^1_2}$ set is $\omega_1$-Suslin (a remark from ref. Kanamori - The Higher Infinite p.174: the reverse implication is independent of ZFC). The way you prove the key lemma is you take an appropriate well-founded tree of triples (by the definition of $\mathbf{\Sigma^1_2}$), using the above-mentioned fact that there is an order-preserving map $\rho$ from $T$ to $\omega_1$ and you define a new tree $T(x)$ on $\omega^2 \times \omega_1$, ewentually transforming it into a tree with a branch that gives us the representation - if necessary, I can put in more details into the question.

My question is as follows (I guess the answer is in the negative, but cannot find an argument): $$\text{is it true that every $\mathbf{\Sigma^1_{n+1}}$ set is $\omega_n$-Suslin?}$$

If not, what step from the proof of the case of $n=1$ does not generalize? Is it simply (that's my intuition) the fact that when we go higher in the projective hierarchy, we simply lose the ability to use the definition of our set to form an appropriate tree in the first place (in the sense in which having a $\Sigma^1_2(a)$ predicate gives us a formula 'there exists $r$ such that for all s some $\Pi^0_1$ formula holds' and this easily translates into a tree that we can handle quite feasibly)? If so, is there a proper formal argument for that? I am obviously also interested in any counterexample, but the most important thing for me is to understand which steps of the argument brake if they do?

The reason for the question is the Shoenfield's Absolutness. We can give nice counterexamples of $\mathbf{\Sigma^1_3}$ formulas (like 'there is a non-constructible real') that are not absolute for (transitive) inner models, so we know $\mathbf{\Sigma^1_2}$ (and $\mathbf{\Pi^1_2}$) is the limit, but when asked 'which step of the proof cannot be generalized?', my reply can be only: well, I know how to handle $\Pi^1_1(a)$ properties (and quantify them existentially to handle $\Sigma^1_2(a)$-ones), but I don't see a way what I could do for some $\Sigma^1_{n}(a)$ for $n>2$. Is it just this or there is some deeper, say, 'combinatorial' reason within some of the further steps of the proof that prevents us from the generalization?


1 Answer 1


I don't know the answer in ZFC, but in ZF + DC the answer is consistently no. If $V = L$ and there is an inaccessible cardinal, then in the associated Solovay model the $\Pi^1_2$ relation $\{ \langle x,y \rangle : y \notin L[x]\}$ has no uniformization, so it is not Suslin, meaning that it is not $X$-Suslin for any wellordered set $X$.

(Moreover, in the Solovay model of a slightly stronger large cardinal, every Suslin set of reals is ${\bf\Sigma}^1_2$ by Theorem 1.8 and Remark 1.9 of Wilson, Generic Vopěnka cardinals and models of ZF with few $\aleph_1$-Suslin sets: https://link.springer.com/article/10.1007/s00153-019-00662-1.)

Consequently, the answer to a version of the question for definable Suslin representations in ZFC is also no: if $V = L$ and there is an inaccessible cardinal, then in the generic extension by its Levy collapse there is a $\Pi^1_2$ set with no Suslin representation definable from a countable sequence of ordinals.

To go from $\omega$-Suslin representations of $\Sigma^1_1$ sets to $\omega_1$-Suslin representations of $\Pi^1_1$ sets, we use the fact that if $T$ is a countable tree, then rank functions witnessing well-foundedness of its sections $T(x)$ can be coded as $\omega$-sequences of countable ordinals and therefore as branches of order type $\omega$ through a tree of cardinality $\omega_1$. The most straightforward attempt to imitate this argument at the next level would seem to involve branches of order type $\omega_1$ through a tree of cardinality $\omega_2$. But the kind of tree that we are talking about can only have branches of order type $\le \omega$ by definition (and this restriction is necessary for such trees to be relevant to uniformization, etc. of sets of reals.)

It should be mentioned here that if projective determinacy holds, then all projective sets have definable Suslin representations by the second periodicity theorem of Moschovakis.

  • $\begingroup$ Thank you, Trevor! I guess there will be no better answer here in the closest future, but I'll let the question fly for the next day or so before I accept, ok? $\endgroup$
    – mtg
    Jan 31, 2020 at 9:17
  • $\begingroup$ @mtg Sure, no problem. $\endgroup$ Jan 31, 2020 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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