3
$\begingroup$

Definitions: Let $\omega^{<\omega}$ be the set of all finite sequences of natural numbers. For $u, v \in \omega^{<\omega}$, let $u \prec v$ denote that $u$ is a prefix of $v$. We call a subset $T \subseteq \omega^{<\omega}$ a tree, if $v \in T$ and $u \prec v$ imply $u \in T$. We say that $T$ contains an infinite path $p \in \omega^\omega$, if each finite prefix of $p$ is in $T$.

Let $\mathcal{T}$ denote the set of trees. We define a metrix $d$ on $\mathcal{T}$ by $d(T, S) = 2^{- n}$ if $n$ is the smallest number s.t. there is some $v \in \omega^n$ with $v \in (T \setminus S) \cap (S \setminus T)$ for $T \neq S$.

Question: Is there a continuous function $R : \mathcal{T} \to \mathcal{T}$ such that:

  • $R(T)$ contains an infinite path for each $T \in \mathcal{T}$;

  • whenever $T$ has infinite paths, then each infinite path through $R(T)$ is an infinite path through T ?

Remark: If in the second case, coincide of the set of infinite paths would be required, then there could not even be a Borel map.

$\endgroup$
3
  • $\begingroup$ Do you mean trees whose well founded part has depth not greater than $\omega$? $\endgroup$ Commented Apr 12, 2015 at 12:58
  • $\begingroup$ @Pedro We may be using a different definition of depth. I just mean that the tree can be considered as a subset of $\omega^{< \omega}$, i.e. all vertices have a finite distance to the root. $\endgroup$
    – Arno
    Commented Apr 12, 2015 at 13:43
  • $\begingroup$ Migrating to MO. Not positive that it is up to MO standards, but you know what to do, if it isn't. :-/ $\endgroup$ Commented Apr 20, 2015 at 13:57

1 Answer 1

3
$\begingroup$

Suppose, toward a contradiction, that $R$ is a function of the sort you asked about. Then, for any tree $T$, we have the equivalence "$T$ has an infinite path $\iff$ every infinite path through $R(T)$ is a path through $T$." The implication from left to right is the second of your requirements for $R$. The converse is a consequence of your first requirement: $R(T)$ always has a path, so, if all paths through $R(T)$ are also paths through $T$, then there is a path through $T$. But "every infinite path through $R(T)$ is a path through $T$" is a $\Pi^1_1$ (boldface, with a code for $R$ as a parameter) statement, whereas "$T$ has an infinite path" is complete $\Sigma^1_1$, so they can't be equivalent.

$\endgroup$
1
  • $\begingroup$ Thanks, I had overlooked that we can universally quantify over a Borel set to get $\Pi^1_1$, not just over a closed set. $\endgroup$
    – Arno
    Commented Apr 21, 2015 at 13:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .