14
$\begingroup$

A subset of $\mathbb{R}^n$ is

  • $G_\delta$ if it is the intersection of countably many open sets
  • $F_\sigma$ if it is the union of countably many closed sets
  • $G_{\delta\sigma}$ if it is the union of countably many $G_\delta$'s
  • ...

This process gives rise to the Borel hierarchy.

Since all closed sets are $G_\delta$, all $F_\sigma$ are $G_{\delta\sigma}$. What is an explicit example of a $G_{\delta\sigma}$ that is not $F_\sigma$?

$\endgroup$
9
$\begingroup$

Any dense $G_{\delta}$ with empty interior is of II Baire category, and cannot be $F_\sigma$ by the Baire theorem (and of course it is in particular a $G_{\delta\sigma}$).

$\endgroup$
5
  • $\begingroup$ A doubt: isn't that you wanted a $G\delta\sigma$ that is neither $F\sigma$ nor $G\delta$? Then, I don't know. $\endgroup$ Feb 25 '11 at 15:00
  • $\begingroup$ Can't you simply improve your example by taking the union of the positive irrationals (which is a $G_{\delta}$ but not an $F_{\sigma}$ by your argument) with the negative rationals (which is an $F_{\sigma}$ but not a $G_{\delta}$). Since both are $G_{\delta\sigma}$-sets, their union is as well. $\endgroup$ Feb 25 '11 at 15:20
  • $\begingroup$ Good point . $\endgroup$ Feb 25 '11 at 15:26
  • $\begingroup$ On the other hand, it's still slightly cheated. It is an ambiguous set in the sense that it is both a $G_{\delta\sigma}$ and an $F_{\sigma\delta}$, so in this sense not a "true" $G_{\delta\sigma}$ $\endgroup$ Feb 25 '11 at 15:36
  • $\begingroup$ Afer reading the comments, I guess that what I really wanted (and still want) is an example of a $G_{\delta\sigma}$ which is not a $F_{\sigma\delta}$ $\endgroup$ Feb 25 '11 at 15:47
24
$\begingroup$

You want a $\Sigma^0_3$ set which is not $\Pi^0_3$. The canonical answer is a "universal $\Sigma^0_3$ set". You can find these concepts in books on Descriptive Set Theory (such as the one by Moschovakis or the one by Kechris).

A specific example: Let $N_{10}$ be the set of normal numbers (each digit appears with the right asymptotic frequency in the decimal expansion). Then $N_{10}$ is a $\Pi^0_3$ set which as complicated as $\Pi^0_3$ sets get (in particular: every $\Pi^0_3$ set is a continuous preimage of it). In particular, it is not $\Sigma^0_3$. So the complement of $N_{10}$ is what you want.

References:

  1. Haseo Ki and Tom Linton, "Normal numbers and subsets of $\mathbb N$ with given densities", Fundamenta Math (1994). MR1273694

  2. Goldstern, "Complexity of uniform distribution", Mathematica Slovaca (1994). MR1338422

$\endgroup$
6
$\begingroup$

Here are some examples from recursion theory which are boldface $\mathbf{\Pi^0_3}$ (the first is $\Pi^0_3(\emptyset')$ and the others are lightface $\Pi^0_3$) but not boldface $\mathbf{\Sigma^0_3}$:

The collection of weakly-2-random reals;

The collection of Schnorr random reals;

The collection of computably random reals.

References:

  1. The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. ACM Transactions on Computational Logic, 2007.

  2. Descriptive set theoretical complexity of randomness notions. Liang Yu. To appear.

$\endgroup$
1
$\begingroup$

There is a class of (natural?) examples here.

$\endgroup$
0
1
$\begingroup$

I just stumbled upon this old question, and thought I would add a simple and natural example, which is $G_{\delta \sigma}$ but neither $G_{\delta}$ nor $F_{\sigma}$.

Consider $f\colon \mathbb{C}\to\mathbb{C}; z\mapsto e^z$, and its iterates $$f^n(z) = \underbrace{f(f(\dots f(z)\dots))}_{\text{$n$ times}}=e^{e^{\cdot^{\cdot^{\cdot^{e^z}}}}}.$$ Consider the set $$ X := \{z\in\mathbb{C}\colon f^n(z)\not\to\infty\} $$ and its subset $$ X_0 := \{z\in\mathbb{C}\colon \{f^n(z)\colon n\geq 0\} \text{ is dense in $\mathbb{C}$}\}.$$

It follows from the definitions that $X_0$ is a $G_{\delta}$ and $X$ is a $G_{\delta \sigma}$. It is well-known that $X_0$ is dense in $\mathbb{C}$, as is the complement $I(f) = \mathbb{C}\setminus X$. (For an elementary proof, see The exponential map is chaotic, Amer. Math. Monthly 2017, arxiv:1408.1129.)

So $X_0$ contains a dense $G_{\delta}$, and can therefore not be $F_{\sigma}$, as noted by Pietro Majer.

That $X$ is not $G_{\delta}$ follows from the fact that $I(f)$ is not $F_{\sigma}$. (Escaping sets are not sigma-compact, arxiv:2006.16946.)

(More generally, for any transcendental entire function, the set of non-escaping points is a $G_{\delta \sigma}$ but neither $G_{\delta}$ nor $F_{\sigma}$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.