6
$\begingroup$

Problem. What is the Borel complexity of the set $$c(\mathbb Q)=\{(x_n)_{n\in\omega}\in\mathbb R^\omega:\exists\lim_{n\to\infty}x_n\in\mathbb Q\}$$ in the countable product of lines $\mathbb R^\omega$?

Remark. It is easy to see that $c(\mathbb Q)$ is an $F_{\sigma\delta\sigma}$-set in $\mathbb R^\omega$.

Question. Is $c(\mathbb Q)$ of type $F_{\sigma\delta}$ in $\mathbb R^\omega$?

$\endgroup$
5
  • $\begingroup$ Maybe a naive point, but: It'd be enough to continuously reduce an arbitrary $\Sigma^0_4$ set in $\omega^\omega$ to $c(\mathbb{Q})$. With such an argument you can show the toy version that $c(\{0\})$ is $F_{\sigma \delta}$ but "no simpler" than that, so far I wasn't able to do yours though. (I won't say complete because I'm not familiar with how good a Polish space this is, though I suspect very.) $\endgroup$
    – Ville Salo
    Commented Jun 18, 2020 at 17:24
  • $\begingroup$ Your set is an intersection of $G_{\delta \sigma}$ set and an $F_{\sigma \delta}$ set, by stating that you get arbitrarily close to some rational number arbitrarily late, and that a limit exists. I'm guessing that means my approach will not work. $\endgroup$
    – Ville Salo
    Commented Jun 18, 2020 at 17:35
  • $\begingroup$ @VilleSalo Good point! Thank you. By the way, my idea of proving that $c(\mathbb Q)$ is an $F_{\sigma\delta}$ does not work, unfortunately. So, the problem remains open. $\endgroup$ Commented Jun 18, 2020 at 17:59
  • $\begingroup$ I think I can reduce any $\Sigma^0_3$ and thus the answer is "no", but not 100% sure and it's complicated. I'll try to find some time if no one answers before. $\endgroup$
    – Ville Salo
    Commented Jun 18, 2020 at 18:22
  • $\begingroup$ Ok, I am curious to see this reduction. $\endgroup$ Commented Jun 18, 2020 at 18:32

1 Answer 1

7
$\begingroup$

The argument is some standard recursion theoretic trickery (I'm educated enough to recognize that, but not educated enough to know what this is called).

Theorem. Every $\Sigma^0_3$ subset of Cantor space continuously reduces to your set.

It follows from this that if your set were $F_{\sigma \delta}$ then every $\Sigma^0_3$ subset of Cantor space would be $\Pi^0_3$, a contradiction with the properness of the Borel hierarchy. I think.

Proof. In front of you stand $\omega$ many creatures. Every second, some subset of these creatures blinks. You have set up video surveillance and have every blink of every creature on tape. By watching these tapes in a dovetailing fashion, you eventually find out about every blink. The event that one of these creatures blinks infinitely many times models (= is an intuitive interpretation of) a general $\Sigma^0_3$ subset of Cantor space: such a set is of the form $\bigcup_n \bigcap_m \bigcup_k C_{n,m,k}$ where $C_{n,m,k}$ is clopen, and a point being in $C_{n,m,k}$ means the time between the $(m-1)$th and the $m$th blink of creature $n$ is $k$ seconds.

Finding a continuous function means we keep watching the tapes, and keep outputting real numbers (actually it's enough to output approximations to the real numbers, but I'll just output exact numbers directly).

We'll keep track of the following data: An irrational number $r \in (0,1)$, and rational numbers $1 = q_0 > q_1 > q_2 > q_3 > \cdots > r$, such that $[r, q_i]$ is disjoint from $\frac{1}{i} \mathbb{Z}$. Note that for any $r \in (0,1)$ we can find such numbers. These should also be indexed by the current time, but I'll keep that implicit.

Now, keep watching the tapes, and do as follows

  • every second, output $r$ (i.e. $x_t$ will be the value $r$ output at time $t$)
  • if creature $i$ blinks, increase $r$ to some irrational number between $(r + q_i)/2$ and $q_i$, and pick new values for the numbers $q_j$ for $j > i$ if needed

I claim that the resulting sequence $(x_t)_t$ is in $c(\mathbb{Q})$ if and only if some creature blinks infinitely many times. Namely, suppose that the $i$th creature blinks infinitely many times, but no creature with smaller index does. Then after some time $t$, no creature $j < i$ blinks. At that point, we have picked some value $q_i \in \mathbb{Q}$, and since the $i$th creature keeps blinking, we eventually increase $r$ to $q_i$ by the second rule, thus $(x_t)_t \in c(\mathbb{Q})$.

Suppose then that after some time, no creature ever blinks again. Then from that point on, we keep outputting $r$, which is irrational, so $(x_t)_t \notin c(\mathbb{Q})$.

Suppose then that no creature blinks infinitely many times, but there are infinitely many blinks altogether. Since the sequence is monotone increasing and bounded from above (by $q_0 = 1$), there is some limit $\lim_t x_t = r'$. Suppose it is rational, say $r' = n/i$. Consider the last time the $i$th creature blinks. At this time, the value $r$ satisfies $r < q_i$, and $[r, q_i]$ is disjoint from $\frac{1}{i} \mathbb{Z}$. But the way the process is defined, $r$ never increases past $q_i$ unless the $i$th creature blinks, so $r' \in [r, q_i]$ cannot be equal to $n/i \in \frac{1}{i} \mathbb{Z}$. Square.

I think the actual complexity of your set is hinted by the fact it is an intersection of a $F_{\sigma \delta}$ and a $G_{\delta \sigma}$ set, but that's more fine-grained than I'm willing to touch right now, since I'm not exactly a boldface expert.

edit

Scratch that, I will touch it a little.

Theorem. Every set that is an intersection of a $\Sigma^0_3$ and a $\Pi^0_3$ subset of Cantor space continuously reduces to your set.

I imagine this pinpoints the exact complexity, since as mentioned your set is an intersection of a $F_{\sigma \delta}$ and a $G_{\delta \sigma}$ set.

Proof. We now have a $\Sigma^0_3$ set $A$ and a $\Pi^0_3$ set $B$, and are interested in reducing $A \cap B$ to your set $c(\mathbb{Q})$. For $A$ we have the set of $\omega$ many magnificent creatures from the previous proof, which occasionally blink. For $B$ we have another $\omega$ many cute creatures, which occationally wag their tails. We interpret $A \cap B$ as the event that some magnificent creature blinks infinitely many times, and no cute creature wags its tail infinitely many times.

In the even coordinates of the output, keep writing (the current value of) $r$ according to the protocol of the previous proof. In the odd coordinates, by default also write $r$, but write $r+\frac{1}{2^i}$ whenever the $i$th creature wags its tail.

If the point of Cantor space is in $B$, then eventually the first $n$ cute creatures stop wagging their tails, and thus the value eventually stays in $[r-\frac{1}{2^n}, r+\frac{1}{2^n}]$ where $r$ is where the monotone sequence converges. If it is additionally in $A$, then $r \in \mathbb{Q}$ so $(x_t)_t \in c(\mathbb{Q})$.

If on the other hand the point is not in $B$ then there is no convergence because we keep seeing consecutive values $(r, r+\frac{1}{2^i})$ for any $i$ that never stops wagging its tail, so $(x_t)_t \notin c(\mathbb{Q})$. If the point is in $B$ but not in $A$, then we have convergence to some element of $\mathbb{R} \setminus \mathbb{Q}$, and again $(x_t)_t \notin c(\mathbb{Q})$. Square.$\;\;\;\;\;$

$\endgroup$
1
  • 1
    $\begingroup$ Cute argument (with all these blinking creatures). Thank you. $\endgroup$ Commented Jun 18, 2020 at 20:45

You must log in to answer this question.

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