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

In John Steel's paper "The derived model theorem",

John Steel asserts that it is clear that $\mathrm{Hom}^{Y}_{\kappa}$ is closed downward under continuous reducibility. Unfortunately that is not clear to me and I was wondering if anyone could help me understand it.

share|cite|improve this question
I just took a look at the definitions, and it seems that some occurrences of $Y^{<\omega}$ there should be $Y^\omega$. Could that be the (or a) source of the difficulty? – Andreas Blass Oct 21 '10 at 1:49
I apologise if I am being thick. Can you tell me where I can read about how to associate a tree to a continuous function? – Rupert Oct 21 '10 at 4:39
up vote 5 down vote accepted

Rupert, I will explain the argument for $Y=\omega$ (this makes no difference, but you may find it easier to visualize) when the continuous function is particularly nice (in a way I will make precise. The general case requires a slight adaptation).

First, some basic background: The topology on $\omega^\omega$ is the product topology with the base set $\omega$ having the discrete topology. By definition of the product topology, it follows that $f:\omega^\omega\to\omega^\omega$ is continuous iff for any $x\in\omega^\omega$ and any $n$ there is an $s_n=s_n(x)\in\omega$ with $f(x)\upharpoonright n$ completely determined by $x\upharpoonright s_n$. This means that if $x,y\in\omega^\omega$ and $x\upharpoonright s_n=y\upharpoonright s_n$, then $f(x)\upharpoonright n=f(y)\upharpoonright s_n$.

The simplifying assumption I will make is that, for all $x$, $s_n=n$. It follows that there exists a function $\hat f:\omega^{<\omega}\to\omega^{<\omega}$ such that:

  1. ${}|\hat f(t)|=|t|$ for all $t\in\omega^{<\omega}$. Here, $|t|$ is the length of $t$.
  2. Whenever $s$ is an initial segment of $t\in\omega^{<\omega}$, we have that $\hat f(s)$ is an initial segment of $\hat f(t)$.
  3. For any $x\in\omega^\omega$, $f(x)=\bigcup_n \hat f(x\upharpoonright n)$.

This is standard and any book in descriptive set theory and most books in set theory will mention it in passing at the very least. You may also want to take a look at the discussion of meta-stability in Tao's blog.

Ok. Suppose now that $A=S_{\vec\mu}$ is a homogeneous subset of $\omega^\omega$, for some homogeneity system $\vec\mu=(\mu_s\mid s\in\omega^{<\omega})$. [The full details of the definition are in the paper by Steel linked to in the body of the question.] The intuitive idea to keep in mind is that "membership in $A$ is continuously reduced to well-foundedness of towers."

This suggests that if $B$ continuously reduces to $A$, then "composing continuous maps" should give a continuous reduction of $B$ to well-foundedness of towers, i.e., verify that $B$ is homogeneous. Let's verify this precisely, in the case that $f$ is the reduction map.

We are thus assuming that $B\le_W A$ via $f$, i.e., $B=f^{-1}(A)$.

Let $\vec\rho=(\rho_s\mid > s\in\omega^{<\omega})$ be given by $\rho_s=\mu_{\hat f(s)}$. This is also a homogeneity system. Then, blatantly from $A=S_{\vec\mu}$, the definition of $\hat f$, and the fact that $B=f^{-1}(A)$, we have that $B=S_{\vec\rho}$. This completes the proof.

[If this is not immediate: Note that $x\in S_{\vec\rho}$ iff the ultrapower of $V$ via the tower $(\rho_{x\upharpoonright n}\mid n<\omega)=(\mu_{\hat f(x\upharpoonright n)}\mid n<\omega)=(\mu_{f(x)\upharpoonright n}\mid n<\omega)$ is well-founded, i.e., iff $f(x)\in S_{\vec\mu}=A$. This means that $S_{\vec\rho}=f^{-1}(A)=B$.]

This needs to be slightly modified in the general case, since we stubbornly ask that each $\mu_s$ concentrates on $Z^{|s|}$ rather than $Z^{n_s}$ for some integer $n_s$, and in general in our continuous functions, we do not have the 'fast convergence' condition that $x\upharpoonright n$ suffices to determine $f(x)\upharpoonright n$. But the case I explained should help you understand the general case.

share|cite|improve this answer
Thanks a lot Andreas, I'm sorry if I was being thick. I believe I had something like this in mind but I wasn't sure how to get rid of the assumption $s_{n}=n$. But I will leave you alone now and try to figure it out for myself. – Rupert Oct 21 '10 at 22:39

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.