# A G-delta-sigma that is not F-sigma?

MathOverflow Asked by Julián Aguirre on August 20, 2020

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_{deltasigma}$$ 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_{deltasigma}$$. What is an explicit example of a $$G_{deltasigma}$$ that is not $$F_sigma$$?

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_{deltasigma}$).

Correct answer by Pietro Majer on August 20, 2020

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 $$fcolon mathbb{C}tomathbb{C}; zmapsto 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 := {zinmathbb{C}colon f^n(z)nottoinfty}$$ and its subset $$X_0 := {zinmathbb{C}colon {f^n(z)colon ngeq 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}$$.)

Answered by Lasse Rempe-Gillen on August 20, 2020

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

Answered by Ashutosh on August 20, 2020

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.

Answered by 喻 良 on August 20, 2020

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

Answered by Goldstern on August 20, 2020

## Related Questions

### Commutator estimates regarding pseudo-differential operators

0  Asked on December 15, 2020 by shaoyang-zhou

### English translation of Borel-Serre Le theoreme de Riemann-Roch?:

1  Asked on December 15, 2020

### Upper bound for an exponential sum involving characters of a finite field

1  Asked on December 14, 2020 by nahila

### Euler function summation

0  Asked on December 13, 2020 by andrej-leko

### A problem about an unramified prime in a Galois extension

1  Asked on December 9, 2020 by neothecomputer

### Reference request: discretisation of probability measures on $mathbb R^d$

1  Asked on December 9, 2020 by mb2009

### Smoothness of a variety implies homological smoothness of DbCoh

0  Asked on December 8, 2020 by dbcohsmoothness

### Reference for matrices with all eigenvalues 1 or -1

1  Asked on December 7, 2020

### Characterizations of groups whose general linear representations are all trivial

1  Asked on December 7, 2020 by qsh

### Continuous time Markov chains and invariance principle

0  Asked on December 6, 2020 by sharpe

### Continuity property for Čech cohomology

0  Asked on December 6, 2020 by xindaris

### Reference request: superconformal algebras and representations

0  Asked on December 6, 2020 by winawer

### Extending rational maps of nodal curves

1  Asked on December 5, 2020 by leo-herr

### How large is the smallest ordinal larger than any “minimal ordinal parameter” for any pair of an Ordinal Turing Machine and a real?

1  Asked on December 4, 2020 by lyrically-wicked

### Almost geodesic on non complete manifolds

1  Asked on December 4, 2020 by andrea-marino

### With Khinchine’s inequality, prove Fourier basis is unconditional in $L^{p}[0,1]$ only for $p=2$

0  Asked on December 3, 2020 by eric-yan

### Kähler manifolds deformation equivalent to projective manifolds

0  Asked on December 3, 2020 by user164740

### Duality of eta product identities: a new idea?

2  Asked on December 1, 2020 by wolfgang

### Is there a CAS that can solve a given system of equations in a finite group algebra $kG$?

2  Asked on December 1, 2020 by bernhard-boehmler