Skip to main content
MathOverflow

Return to Question

Bumped by Community user
Bumped by Community user
edited body; edited title
Source Link
Dan Turetsky
Dan Turetsky
  • 3.1k
  • 16
  • 27

A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w^1_w_1^{CK}$

In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does this via a somewhat involved process (described below) which uniformly in $\alpha \leq_{\mathscr{O}} w^{1}_CK$$\alpha \leq_{\mathscr{O}} w^{ck}_1$ produces a computable tree $T^{\alpha}_0 \subset \omega^{< \omega}$ containing only $\alpha$-subgenerics. However, at the end of the notes Harrington claims he can produce a computable tree whose elements are $\alpha$-subgeneric for all $\alpha \leq_{\mathscr{O}} w^{1}_{CK}$$\alpha \leq_{\mathscr{O}} w^{ck}_{1}$. I'm not seeing how you get this. Can anyone help me figure out how this can be proved?

Yes, you can go ahead and define these non-standard ordinal notations which must have well-ordered initial segment of length $\omega^1_{CK}$$\omega_1^{CK}$ which Harrington refers to (says something about taking the leftmost path). However, I don't see how this gets you a computable tree all of whose paths are $< \omega^1_{CK}$$< \omega_1^{CK}$ sub-generic since the method he uses to produce a computable tree of $\alpha$-subgenerics -- projecting down a tree $T_\alpha \leq_T 0^{(\alpha)}$ -- can't be directly applied to a path through $\mathscr{O}$ since that would allow the construction of a computable tree with only a single path that was $< \omega^1_{CK}$$< \omega_1^{CK}$-subgeneric contradicting the fact that if $f$ is the unique path through a computable tree $f$ is hyperarithmetic.

In case it helps, I've included a bit of a further explanation of the argument as I understand it below.

$\alpha$-subgeneric

$f \in \omega^{\omega}$ is $\alpha$-subgeneric for $\alpha \in \mathscr{O}$ if

  • $(\forall \beta \leq_{\mathscr{O}} \alpha)(0^{(\beta)} \oplus f \equiv_T f^{(\beta)})$
  • $(\forall X \leq_T 0^{(\alpha)})(\forall \beta \leq_{\mathscr{O}} \alpha)( X \leq_T f^{(\beta)} \implies X \leq_T 0^{(\beta)} $

The way he constructs such reals is (I presume since it seems to work and it's the only approach in the notes) is to start with a tree $T_\alpha$ computable in $0^{(\alpha)}$ and at each level $\beta \leq_{\mathscr{O}} \alpha$ building $T_\beta$ computable in $0^{(\beta)}$ to produce an ultimate tree $T_0$ with $[T_0]$ homeomorphic to $[T_\alpha]$ and with all paths through $T_\alpha$ being $\alpha$-subgeneric.

The basic idea is to handle this one step at a time by combining a kind of jump-inversion to build $T_\beta$ homeomorphic to $T_{\beta+1}$ while at the same time trying to force (in local forcing) $\Sigma^0_1(0^{(\beta)})$ facts. There are some tricky issues that aren't covered in the notes but if you do it right the local forcing plus the assumptions about subgenericity for $T_{\beta+1}$ (and some nasty utility lemmas to keep the notations well-behaved at limit levels) are enough to ensure that you end up with $\alpha$-subgeneric paths through $T_0$

And that's all nicely uniform, so we can assume that we have $T^{\alpha}_0$, a computable tree with only $\alpha$-subgeneric paths (e.g. say only a single one) uniformly in $\alpha$. But I don't see what lets us put them together to get a computable tree which is $< \omega^1_{CK}$$< \omega_1^{CK}$ subgeneric -- and that argument must somehow ensure that the tree we build has a perfect set of paths.

A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w^1_{CK}$

In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does this via a somewhat involved process (described below) which uniformly in $\alpha \leq_{\mathscr{O}} w^{1}_CK$ produces a computable tree $T^{\alpha}_0 \subset \omega^{< \omega}$ containing only $\alpha$-subgenerics. However, at the end of the notes Harrington claims he can produce a computable tree whose elements are $\alpha$-subgeneric for all $\alpha \leq_{\mathscr{O}} w^{1}_{CK}$. I'm not seeing how you get this. Can anyone help me figure out how this can be proved?

Yes, you can go ahead and define these non-standard ordinal notations which must have well-ordered initial segment of length $\omega^1_{CK}$ which Harrington refers to (says something about taking the leftmost path). However, I don't see how this gets you a computable tree all of whose paths are $< \omega^1_{CK}$ sub-generic since the method he uses to produce a computable tree of $\alpha$-subgenerics -- projecting down a tree $T_\alpha \leq_T 0^{(\alpha)}$ -- can't be directly applied to a path through $\mathscr{O}$ since that would allow the construction of a computable tree with only a single path that was $< \omega^1_{CK}$-subgeneric contradicting the fact that if $f$ is the unique path through a computable tree $f$ is hyperarithmetic.

In case it helps, I've included a bit of a further explanation of the argument as I understand it below.

$\alpha$-subgeneric

$f \in \omega^{\omega}$ is $\alpha$-subgeneric for $\alpha \in \mathscr{O}$ if

  • $(\forall \beta \leq_{\mathscr{O}} \alpha)(0^{(\beta)} \oplus f \equiv_T f^{(\beta)})$
  • $(\forall X \leq_T 0^{(\alpha)})(\forall \beta \leq_{\mathscr{O}} \alpha)( X \leq_T f^{(\beta)} \implies X \leq_T 0^{(\beta)} $

The way he constructs such reals is (I presume since it seems to work and it's the only approach in the notes) is to start with a tree $T_\alpha$ computable in $0^{(\alpha)}$ and at each level $\beta \leq_{\mathscr{O}} \alpha$ building $T_\beta$ computable in $0^{(\beta)}$ to produce an ultimate tree $T_0$ with $[T_0]$ homeomorphic to $[T_\alpha]$ and with all paths through $T_\alpha$ being $\alpha$-subgeneric.

The basic idea is to handle this one step at a time by combining a kind of jump-inversion to build $T_\beta$ homeomorphic to $T_{\beta+1}$ while at the same time trying to force (in local forcing) $\Sigma^0_1(0^{(\beta)})$ facts. There are some tricky issues that aren't covered in the notes but if you do it right the local forcing plus the assumptions about subgenericity for $T_{\beta+1}$ (and some nasty utility lemmas to keep the notations well-behaved at limit levels) are enough to ensure that you end up with $\alpha$-subgeneric paths through $T_0$

And that's all nicely uniform, so we can assume that we have $T^{\alpha}_0$, a computable tree with only $\alpha$-subgeneric paths (e.g. say only a single one) uniformly in $\alpha$. But I don't see what lets us put them together to get a computable tree which is $< \omega^1_{CK}$ subgeneric -- and that argument must somehow ensure that the tree we build has a perfect set of paths.

A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$

In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does this via a somewhat involved process (described below) which uniformly in $\alpha \leq_{\mathscr{O}} w^{ck}_1$ produces a computable tree $T^{\alpha}_0 \subset \omega^{< \omega}$ containing only $\alpha$-subgenerics. However, at the end of the notes Harrington claims he can produce a computable tree whose elements are $\alpha$-subgeneric for all $\alpha \leq_{\mathscr{O}} w^{ck}_{1}$. I'm not seeing how you get this. Can anyone help me figure out how this can be proved?

Yes, you can go ahead and define these non-standard ordinal notations which must have well-ordered initial segment of length $\omega_1^{CK}$ which Harrington refers to (says something about taking the leftmost path). However, I don't see how this gets you a computable tree all of whose paths are $< \omega_1^{CK}$ sub-generic since the method he uses to produce a computable tree of $\alpha$-subgenerics -- projecting down a tree $T_\alpha \leq_T 0^{(\alpha)}$ -- can't be directly applied to a path through $\mathscr{O}$ since that would allow the construction of a computable tree with only a single path that was $< \omega_1^{CK}$-subgeneric contradicting the fact that if $f$ is the unique path through a computable tree $f$ is hyperarithmetic.

In case it helps, I've included a bit of a further explanation of the argument as I understand it below.

$\alpha$-subgeneric

$f \in \omega^{\omega}$ is $\alpha$-subgeneric for $\alpha \in \mathscr{O}$ if

  • $(\forall \beta \leq_{\mathscr{O}} \alpha)(0^{(\beta)} \oplus f \equiv_T f^{(\beta)})$
  • $(\forall X \leq_T 0^{(\alpha)})(\forall \beta \leq_{\mathscr{O}} \alpha)( X \leq_T f^{(\beta)} \implies X \leq_T 0^{(\beta)} $

The way he constructs such reals is (I presume since it seems to work and it's the only approach in the notes) is to start with a tree $T_\alpha$ computable in $0^{(\alpha)}$ and at each level $\beta \leq_{\mathscr{O}} \alpha$ building $T_\beta$ computable in $0^{(\beta)}$ to produce an ultimate tree $T_0$ with $[T_0]$ homeomorphic to $[T_\alpha]$ and with all paths through $T_\alpha$ being $\alpha$-subgeneric.

The basic idea is to handle this one step at a time by combining a kind of jump-inversion to build $T_\beta$ homeomorphic to $T_{\beta+1}$ while at the same time trying to force (in local forcing) $\Sigma^0_1(0^{(\beta)})$ facts. There are some tricky issues that aren't covered in the notes but if you do it right the local forcing plus the assumptions about subgenericity for $T_{\beta+1}$ (and some nasty utility lemmas to keep the notations well-behaved at limit levels) are enough to ensure that you end up with $\alpha$-subgeneric paths through $T_0$

And that's all nicely uniform, so we can assume that we have $T^{\alpha}_0$, a computable tree with only $\alpha$-subgeneric paths (e.g. say only a single one) uniformly in $\alpha$. But I don't see what lets us put them together to get a computable tree which is $< \omega_1^{CK}$ subgeneric -- and that argument must somehow ensure that the tree we build has a perfect set of paths.

Source Link
Peter Gerdes
Peter Gerdes
  • 3k
  • 16
  • 18

A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w^1_{CK}$

In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does this via a somewhat involved process (described below) which uniformly in $\alpha \leq_{\mathscr{O}} w^{1}_CK$ produces a computable tree $T^{\alpha}_0 \subset \omega^{< \omega}$ containing only $\alpha$-subgenerics. However, at the end of the notes Harrington claims he can produce a computable tree whose elements are $\alpha$-subgeneric for all $\alpha \leq_{\mathscr{O}} w^{1}_{CK}$. I'm not seeing how you get this. Can anyone help me figure out how this can be proved?

Yes, you can go ahead and define these non-standard ordinal notations which must have well-ordered initial segment of length $\omega^1_{CK}$ which Harrington refers to (says something about taking the leftmost path). However, I don't see how this gets you a computable tree all of whose paths are $< \omega^1_{CK}$ sub-generic since the method he uses to produce a computable tree of $\alpha$-subgenerics -- projecting down a tree $T_\alpha \leq_T 0^{(\alpha)}$ -- can't be directly applied to a path through $\mathscr{O}$ since that would allow the construction of a computable tree with only a single path that was $< \omega^1_{CK}$-subgeneric contradicting the fact that if $f$ is the unique path through a computable tree $f$ is hyperarithmetic.

In case it helps, I've included a bit of a further explanation of the argument as I understand it below.

$\alpha$-subgeneric

$f \in \omega^{\omega}$ is $\alpha$-subgeneric for $\alpha \in \mathscr{O}$ if

  • $(\forall \beta \leq_{\mathscr{O}} \alpha)(0^{(\beta)} \oplus f \equiv_T f^{(\beta)})$
  • $(\forall X \leq_T 0^{(\alpha)})(\forall \beta \leq_{\mathscr{O}} \alpha)( X \leq_T f^{(\beta)} \implies X \leq_T 0^{(\beta)} $

The way he constructs such reals is (I presume since it seems to work and it's the only approach in the notes) is to start with a tree $T_\alpha$ computable in $0^{(\alpha)}$ and at each level $\beta \leq_{\mathscr{O}} \alpha$ building $T_\beta$ computable in $0^{(\beta)}$ to produce an ultimate tree $T_0$ with $[T_0]$ homeomorphic to $[T_\alpha]$ and with all paths through $T_\alpha$ being $\alpha$-subgeneric.

The basic idea is to handle this one step at a time by combining a kind of jump-inversion to build $T_\beta$ homeomorphic to $T_{\beta+1}$ while at the same time trying to force (in local forcing) $\Sigma^0_1(0^{(\beta)})$ facts. There are some tricky issues that aren't covered in the notes but if you do it right the local forcing plus the assumptions about subgenericity for $T_{\beta+1}$ (and some nasty utility lemmas to keep the notations well-behaved at limit levels) are enough to ensure that you end up with $\alpha$-subgeneric paths through $T_0$

And that's all nicely uniform, so we can assume that we have $T^{\alpha}_0$, a computable tree with only $\alpha$-subgeneric paths (e.g. say only a single one) uniformly in $\alpha$. But I don't see what lets us put them together to get a computable tree which is $< \omega^1_{CK}$ subgeneric -- and that argument must somehow ensure that the tree we build has a perfect set of paths.