24
$\begingroup$

I read a section of a book and it made mention of the set of rationals not being a $G_\delta$. However, it gave no proof. I read on wikipedia about using contradiction, but it made use of the Baire category theorem, which is unfamiliar to me.
I was wondering if anyone could offer me a different proof; perhaps using the fact that the complement of $G_\delta$ is $F_\sigma$.

Thanks.

  • 23
    @Michael: What a bizarre edit... Isn't this a bit exaggerated?2011-10-03
  • 0
    I voted to close as a duplicate of a similar question, but then noticed that this question requests to avoid the Baire category theorem, which essentially gave different answers. I withdraw the closing vote (and have removed the "offending" comment which is adjoined to duplicates). If someone wants to close this, **please cancel out my vote in a comment.** Thanks.2011-10-03
  • 0
    @t.b.: I haven't edited any posts to improve their inner $\TeX$ workings without visible effect, but I did find that I learned quite a few things about more efficient $\TeX$ on this site, including the fact that lots of things don't require braces where I used to put them, so I don't mind Michael improving things in that way. Also, knowing Michael from [Wikipedia](http://en.wikipedia.org/wiki/User:Michael_Hardy), I'm not surprised by his strong focus on optimal $\TeX$ code :-)2011-10-19
  • 0
    @joriki: I agree to some extent only. I think that this is purely a matter of TeXing-style (in LaTeX they *can* be omitted but *shouldn't* according to Lamport), [see here for more arguments for and against it](http://tex.stackexchange.com/q/1914/). Leaving out braces impoverishes some spacing on this site (for example when used in combination with `\operatorname`, depending on browsers and so on). I like and appreciate most of Michael's edits, but this one was a bit too much for me to take :)2011-10-19
  • 0
    @t.b.: Thanks for that link. I haven't noticed any brace and browser dependencies in spacing -- can you point to an example of that?2011-10-19
  • 0
    @joriki: [Here's an example](http://i.stack.imgur.com/z8K9y.png) of what I mean. I would argue the first line has "proper spacing" while in the second line the argument is too close to the "Hom". "Browser dependencies" are maybe not the proper technical term, it depends on how you set up your MathJaX/MathML preferences (right clicking on a formula) and which fonts are installed on your OS and so on [here's a symptom of that](http://meta.math.stackexchange.com/q/2667/). The site looks quite different, depending on which machine I'm currently using.2011-10-19
  • 0
    @t.b.: Interesting. Actually it would never have occurred to me to use braces after `\operatorname{Hom}`. I agree that it looks better. A Google search doesn't turn up any examples of people using braces there.2011-10-19

5 Answers 5

29

I suspect that just about any proof that doesn’t directly use the Baire category theorem either uses a consequence of it or proves a special case of it. I’ve chosen the second course.

Suppose that $\mathbb{Q} = \bigcap\limits_{k\in\omega}V_k$, where each $V_k$ is open in the usual topology on $\mathbb{R}$. Clearly each $V_k$ is dense in $\mathbb{R}$. Let $\mathbb{Q}=\{q_k:k\in\omega\}$ be an enumeration of the rationals, and for each $k\in\omega$ let $W_k=V_k\setminus \{q_k\}$; clearly each $W_k$ is dense and open in $\mathbb{R}$, and $\bigcap\limits_{k\in\omega}W_k = \varnothing$.

Let $(a_0,b_0)$ be any non-empty open interval such that $[a_0,b_0]\subseteq W_0$. Given a non-empty open interval $(a_k,b_k)$, let $r_k=\frac14(b_k-a_k)$; clearly $a_k$$(a_{k+1},b_{k+1}) \subseteq [a_{k+1},b_{k+1}] \subseteq W_{k+1}\cap (a_k+r_k,b_k-r_k),$$ and the construction can continue.

For $k\in\omega$ let $J_k = [a_k,b_k] \subseteq W_k$. For each $k \in \omega$ we have $J_k \supseteq J_{k+1}$, so $\{J_k:k\in\omega\}$ is a decreasing nest of non-empty closed intervals. Let $J = \bigcap\limits_{k\in\omega}J_k$; $J\subseteq J_k \subseteq W_k$ for each $k\in\omega$, so $J \subseteq \bigcap\limits_{k\in\omega}W_k = \varnothing$. But the nested intervals theorem guarantees that $J \ne \varnothing$, so we have a contradiction. Thus, $\mathbb{Q}$ cannot be a $G_\delta$-set in $\mathbb{R}$.

  • 0
    Very nice proof! Thanks for point me out the error in my argument. I deleted the post because of as you explain it is not fixable.2011-10-03
  • 0
    Do you think the fact there is no $\Delta^0_2$ universal set can be used in such proof? (Since if the rationals are $G_\delta$ then $\omega^\omega$ is $\Delta^0_2$)2011-10-03
  • 0
    @Brian M. Scott: I agree with Leandro, is very nice proof. Just a little thing, I think you mean "clearly $a_k\lt a_k+r_k\lt b_k-r_k\lt b_k$."2011-10-03
  • 0
    @leo: You’re absolutely right; thanks for catching the typo.2011-10-03
  • 0
    Why you can find a open interval $(a_0,b_0)$ from $W_0$?2016-11-28
  • 0
    @Gatsby: Because $W_0$ is open.2016-11-28
12

A strange argument follows:

Suppose $\mathbb Q$ is a $G_\delta$. Mazurkiewicz's theorem (you can read about it here ) tells us that there exists then a metric $d$ on $\mathbb Q$, equivalent to the original one, such that $\mathbb Q$ is complete with respect to $d$.

Now, a complete metric space which is countable as a set has an isolated point (to prove this one needs Baire's theorem) so we conclude that $\mathbb Q$, in its usual topology, has an isolated point. This is of course absurd.

  • 0
    Hi Mariano, when you post I was typing my suggestion of solution, I hope you don't mind. Sorry about that.2011-10-03
  • 1
    @Leandro: of course not! The two ideas are quite different (and mine should not be taken too seriously :) )2011-10-03
  • 1
    The complete metrizability of $G_\delta$'s is not so hard to prove (and is due to Alexandrov; Mazurkiewicz's contribution is the more subtle other direction): first show that an open subset $U \subset X$ of a complete metric space $X$ embeds as a closed set in $X \times \mathbb{R}$ via $u \mapsto (u,\frac1{d(u,X \smallsetminus U)})$. Similarly, a countable intersection of open sets $G = \bigcap_{n=1}^\infty U_n$ can be embedded as a closed set in $X \times \mathbb{R}^\mathbb{N}$ via $g \mapsto (g; d(g,1/d(g,X \smallsetminus U_1), 1/d(g,X \smallsetminus U_2), \ldots)$.2012-08-16
  • 0
    I know this post is over 5 years old. But we can avoid Baire by showing that a non-empty completely metrizable space with no isolated points is uncountable by constructing a sub-space homeomorphic to the Cantor set. ...."Avoiding Baire" seems to be a recurring theme on this site.2017-03-09
6

Another silly argument which I think also works:

Suppose $\mathbb Q$ is a $G_\delta$, so that there exists a sequence $(A_n)_{n\geq1}$ of open subsets of $\mathbb R$ such that $\mathbb Q=\bigcap_{n\geq1} A_n$.

Recall that each $A_n$ is a disjoint union of open intervals. For each $n\geq1$ let $\mathcal I_n$ be the set of the intervals making up $A_n$.

Without loss of generality, we can assume that $\mathcal I_1$ contains at least two elements — call them $I(0)$ and $I(1)$ — each of length at most $2^{-1}$

We can also assume that $\mathcal I_2$ it contains two elements contained in $I(0)$ each of length $2^{-1}$ — call them $I(00)$ and $I(01)$ — and two elements contained in $I(1)$, also of length at most $2^{-1}$ — call them $I(10)$ and $I(11)$.

Of course, we can continue in this way indefinitely... We thus obtain intervals $I(w)$, one for each finite word $w$ written in the letters $0$ and $1$, such that the length of $I(w)$ is at most $2^{-\mathrm{length}(w)}$, and such that whenever $w'$ is a prefix of $w$, then $I(w')\supseteq I(w)$.

Now pick any infinite sequence $w$ of zeroes and ones, and for each $n\geq1$ let $w_n$ be the prefix of $w$ of length $n$, and pick a point $x_n$ in the interval $I(w_n)$. It is easy to check that the limit $y_w=\lim_{n\to\infty}x_n$ exists and belongs to $\mathbb Q$, and that $y_w\neq y_{w'}$ if $w$ and $w'$ are distinct infinite sequences of zeroes and ones. This is absurd, as $\mathbb Q$ is countable yet there are uncountably many infinite sequences of zeroes and ones.

$$♦♦♦$$

Another way to implement the above idea.

Suppose $\mathbb Q=\cap_{n\geq1}A_n$ with $A_n$ open in $\mathbb R$.

We massage the open sets a bit first.

  • For each $b\geq1$ let $B_n=\bigcap_{i=1}^nA_n$, so that $(B_n)_{n\geq1}$ is a decreasing sequence of open sets whose intersection is also $\mathbb Q$.

  • Next, for each $n\geq1$ let $C_n=B_n\cap\Big(\mathbb R\setminus(\pi+\tfrac1{2^n}\mathbb Z)\Big)$, so that $(C_n)$ is also a decreasing sequence of open sets whose intersection is $\mathbb Q$, with the added nice property that for all $n\geq1$ each connected component of $C_n$ is of length at most $\tfrac1{2^n}$.

Let $\mathcal I_n$ be set of connected components of $C_n$. If $n\geq1$, then $C_n\supseteq C_{n+1}$ so there is a function $\phi_n:\mathcal I_{n+1}\to\mathcal I_n$ sending each element of $\mathcal I_{n+1}$ to the unique element of $\mathcal I_n$ which contains it. Since $\bigcap_{n\geq1}C_n=\mathbb Q$, it is easy to see that $\phi_n$ is surjective.

Let $$X=\varprojlim(\mathcal I_n,\phi_n)=\Big\{(i_n)_{n\geq1}\in\prod_{n\geq1}\mathcal I_n:\phi_n(i_{n+1})=i_n,\quad\forall n\geq1\Big\}$$ be the inverse limit of the sets $\mathcal I_n$ along the maps $\phi_n$. This is an uncountable set, and it is easy to construct an injective function $f:X\to\mathbb Q$. Indeed, if $\xi=(i_n)_{n\geq1}\in X$ pick, for each $n\geq1$, a point $x_n\in i_n$; then one can show that $f(\xi)=\lim_{n\to\infty}x_n$ exists, and that this defines an injective function.

  • 0
    This shows that, more generally, $G_\delta$ sets are uncountable, of course.2011-10-03
  • 0
    Not just uncountable, but of cardinality $2^\omega$. (As is true of any uncountable Borel set.)2011-10-03
  • 2
    @Brian, Mariano: What about $\{0\}\cup\{\frac{1}{n}\mid n\in\mathbb N\}$? It is a $G_\delta$ set and it is most certainly countable. Furthermore, what about $\{0\}$?2011-10-03
  • 3
    Then more generally *dense* $G_\delta$ sets are uncountable. :-)2011-10-03
  • 1
    @Asaf: Or even just *somewhere dense* $G_\delta$-sets.2011-10-03
  • 1
    @Brian: Of course, just not "more generally"... since some $G_\delta$ are countable or even finite.2011-10-03
  • 1
    @Asaf: Yes, I sloppily overlooked the ‘more generally’ when commenting on the nature of the uncountability.2011-10-03
  • 0
    Mariano Suárez-Alvarez: I am trying to understand your explanation. How can you assume that there are at least two elements in $\mathcal I_n$? why can't $\mathcal I_n$ be a one open segment? Thank you.2014-01-05
  • 0
    @MarianoSuárez-Alvarez I have a question: why is the set $X$ uncountable? I know of no means to calculate the cardinality of a projective limit. And I am not sure if the $2^{\mathbb N}$- argument works. It would be appreciated if you can elaborate on this point, thanks in advance.2015-10-17
  • 0
    Maybe we can "massage" these $C_n$ again? To cut the connected components of $C_n$ further so that it splits more?2015-10-17
2

You can use the fact that the complement of $\mathcal{G}_\delta$ is $\mathcal{F}_\sigma$. We have that the set of rationals $\mathbb{Q}$ is a $\mathcal{G}_\delta$ set if and only if the set of irrationals $\mathbb{R}\backslash\mathbb{Q}$ is an $\mathcal{F}_\sigma$ set. Suppose that is true, so $\mathbb{R}\backslash\mathbb{Q}=\bigcup\limits_{n=1}^\infty B_n$, where $B_n$ are closed. None of the $B_n$ contains any nondegenerate interval, since that would contain a rational number. Let the rational numbers be enumerated as $\{q_1,q_2,\ldots\}$ and let $C_n=B_n\cup\{q_n\}$; note that $C_n$ is closed, as a finite union of closed sets, and contains no nondegenerate interval. We have $$\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\backslash\mathbb{Q})=\{q_1,q_2,\ldots\}\cup \bigcup\limits_{n=1}^\infty B_n=\bigcup\limits_{n=1}^\infty C_n.$$ Hence $\mathbb{R}$ is the union of closed sets $C_n$, none of which contain a nondegenerate interval.

Let $I$ be a closed interval such that $I\cap C_1=\varnothing$. This exists, since $C_1$ is closed, so for all $x\notin C_1$, we can find an open interval containing $x$ lying outside $C_1$, and hence a closed interval within that, or else $C_1=\mathbb{R}$, which is impossible since $C_1$ contains no nondegenerate interval. Similarly, define a closed interval $I_2\subset I_1$ such that $I_2\cap C_2=\varnothing$, possible since $I_1\not\subset C_2$ and $C_2$ is closed and contains no nondegenerate interval. Apply this repeatedly to obtain a nested sequence of closed intervals $I_1\supset I_2\supset\ldots$, where $I_n\cap C_n=\varnothing$.

Consider the set $I=\bigcap\limits_{n=1}^\infty I_n$. We know that $I$ is nonempty, but for $x\in I$, we have $x\notin C_n$ for all $n\in\mathbb{N}$, contradicting the assumption that $\mathbb{R}=\bigcup\limits_{n=1}^\infty C_n$. Hence, by contradiction, $\mathbb{R}\backslash\mathbb{Q}$ is not $\mathcal{F}_\sigma$, so that $\mathbb{Q}$ is not $\mathcal{G}_\delta$.

  • 0
    Nice! Note that your argument about the $I_n$s is basically a proof of BCT: the complement of $C_i$ is a dense open set, and we can replace "interval" with "closed ball with positive radius" in an arbitrary metric space. (A quibble: you write "$I_1\subset I_2\subset . . .$" when you mean "$I_1\supset I_2\supset . . .$")2016-10-07
1

We prove the following by direct elementary methods without "Baire" or its immediate corollaries:

(1). A non-empty completely metrizable space with no isolated points is uncountable.( We construct a subset that is a bijective image of the set of functions from $\mathbb N$ to $\{0,1\}.$ In fact we construct a subset that is homeomorphic to the Cantor set.)

(2).(a). If X is Hausdorff and $Y$ is the intersection of a countable family of completely metrizable subspaces of $X$, then $Y$ is completely metrizable.

(2).(b). If $X$ is completely metrizable and $Y$ is an open subset of $X$ then Y is completely metrizable.

(2).(c). Corollary to (2)(a) and (2)(b): A $G_{\delta}$ subset of $\mathbb R$ is completely metrizable.

So if $S$ is a $G_{\delta}$ subset of $\mathbb R$ and $S$ is dense in $\mathbb R,$ then by (2)(c), $S$ is completely metrizable.And $S$ has no isolated points (because it is dense in $\mathbb R$). So by (1), $S$ is uncountable.

The results (1) and (2) are of interest, but the usefulness of the Baire category theorem is illustrated by using it to directly prove that $\mathbb Q $ is not $G_{\delta}$ in $\mathbb R.$