Complexity of formulae involving projective sets in Polish spaces

68 Views Asked by At

I am no expert in descriptive set theory, but for some reason want to estimate the complexity of a certain formula.

The framework. Let be $F$ a projective set in the Polish space $X=\mathbb R^{\mathbb N}$, say it is in the family $\mathbf \Pi^1_n$. Then, for a fixed $x_0 \in X$ I consider the formula $\varphi$:

$$ x_0\cdot y \in F,$$

where multiplication is performed pointwise and $y$ is the free variable bounded by $X$.

Question. Is it possible to compute (or estimate) the complexity of $\varphi$ in terms of the projective complexity of $F$, that is, $n$?

This could well be obvious, however, it is not my area of expertise at all.

1

There are 1 best solutions below

7
On BEST ANSWER

I believe that the term arithmetic complexity is not used for projective sets such as the one above, because in the arithmetic hierarchy one is concerned with first order formulas on the language of arithmetic: individual variables range over the natural numbers and you have $+$, $\cdot$, $0$ and $1$ as available operations; notably quantifiers $\forall$ and $\exists$ can only be used with those individual variables. But in order to define a projective set, you need variables that range over (possibly uncountable) Polish spaces. This is better understood on the space $2^{\mathbb{N}} \cong \mathop{\mathrm{Pow}}(\mathbb{N})$, but of course there are Borel isomorphisms between this and any other uncountable Polish space (and this will not change the result, if we start at $\boldsymbol\Pi^1_1$, $\boldsymbol\Sigma^1_1$, or above).

A finer detail is that in the hypothesis you refer to a boldface $\boldsymbol\Pi^1_n$ set. Those, apart from the (second order) formula, need a parameter to be defined.

Now, let's consider the complexity of $$ Y := \{ y \in X : x_0 \cdot y \in F\}. $$

It is clear that if all components of $x_0$ are non null, then it will have exactly the same complexity as $F$ ($y\mapsto x_0\cdot y$ being a homeomorphism). As soon as some component is $0$, then $Y$ will be homeomorphic to a projection of $F$, and hence hence its complexity may grow to $\boldsymbol\Sigma^1_{n+1}$ (that is, one extra second order existential quantifier). Had we started with a $\boldsymbol\Sigma^1_n$ set, $Y$ would have been also $\boldsymbol\Sigma^1_n$.