Another formulation of the Wadge lemma in terms of incomparable Wadge classes

84 Views Asked by At

Let $A, B$ be finite sets, and denote by $A^{\mathbb N}$ and $B^{\mathbb N}$ the set of (one-sided) infinite sequences over $A$ and $B$ equipped with the product topology.

Let $X \subseteq A^{\mathbb N}, Y \subseteq B^{\mathbb N}$. We call $X$ Wadge reducible to $Y$, denoted by $X \le_W Y$, if there exists a continuous function $f : A^{\mathbb N} \to B^{\mathbb N}$ such that $$ X = f^{-1}(Y). $$

Now according to William Wadge we have:

If $X \subseteq A^{\mathbb N}$ and $Y^{\mathbb N}$ are Borel sets, then either $X \le_W Y$ or $Y \le_W X^C$.

We call $X$ and $Y$ Wadge equivalent, written $X \equiv_W Y$, iff $X \le_W Y$ and $Y \le_W X$. Another formulation of the above is the following:

The pairs formed by the classes $X$ and $X^C$ when $X \not\equiv_W X^C$ are the only incomparable pairs of Wadge classes.

I do not understand the other formulation, what should it mean that "pairs of Wadge classes are comparable or incomparable"?

These notions are taken from this book.

1

There are 1 best solutions below

0
On BEST ANSWER

I found it out, but to interpret this sentence some more properties of the Wadge order should be stated.

Lemma 1: For $X\subseteq A^{\mathbb N}, Y \subseteq B^{\mathbb N}$ we have $X \le_W Y$ iff $X^C \le_W Y^C$.

Proof. Clear by definition as inverse images preserve the complement. $\square$

Lemma 2: If $X \subseteq A^{\mathbb N}, Y \subseteq B^{\mathbb N}$ are incomparable and Borel, then $Y \equiv_W X^C$ (and hence also $Y^C \equiv_W X$).

Proof. By the Wadge lemma $X \not\le_W Y$ implies $Y \le_W X^C$. Similar we have $X \le_W Y^C$, which gives $X^C \le_W Y$ by Lemma 1, hence $Y \equiv_W X^C$. Again by Lemma 1 we also have $Y^C \equiv_W X$ (Note that in the first part Lemma 1 could be avoided, for if we assume $X^C \not\le_W Y$ then by Wadge lemma $Y \le X$, contradicting the assumption). $\square$

With this, assume $X,Y$ are incomparable and Borel, then $Y \equiv X^C$ and we have $\{ [X]_{\equiv_W}, [Y]_{\equiv_W} \} = \{ [X]_{\equiv_W}, [X^C]_{\equiv_W} \}$, i.e. giving that the only distinct classes are of the form $[X], [X^C]$ for some $X$ with $X \not\equiv_W X^C$ on the Borel sets. This is meant with the above sentence.

Note one further property on the Borel sets, that for three distinct Borel sets at least two of them must be comparable. This is a direct consequence of Lemma 2, or for a direct proof if $X,Y,Z$ are Borel and incomparable then we have $$ \begin{array}{lll} Z \le_W Y^C & Z \le_W X^C & Y \le_W X^C \\ Y \le_W Z^C & X \le_W Z^C & X \le_W Y^C. \end{array} $$ So we could not have $X^C \le_W Y$, for otherwise $Z \le_W Y$ would follow. By Wadge lemma this gives $Y \le X$, again a contradiction to the assumption, which means that the assumption must be wrong.