Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
13  
@Michael: What a bizarre edit... Isn't this a bit exaggerated? –  t.b. Oct 3 '11 at 5:06
    
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. –  Asaf Karagila Oct 3 '11 at 21:58
    
@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, I'm not surprised by his strong focus on optimal $\TeX$ code :-) –  joriki Oct 19 '11 at 15:09
    
@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. 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 :) –  t.b. Oct 19 '11 at 15:24
    
@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? –  joriki Oct 19 '11 at 15:42

3 Answers 3

up vote 16 down vote accepted

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+r_k<b_k-r_k<b_k$. Since $W_{k+1}$ is dense and open, there is a non-empty open interval $(a_{k+1},b_{k+1})$ such that $$(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}$.

share|improve this answer
    
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. –  Leandro Oct 3 '11 at 6:13
    
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$) –  Asaf Karagila Oct 3 '11 at 6:13
    
@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$." –  leo Oct 3 '11 at 18:27
    
@leo: You’re absolutely right; thanks for catching the typo. –  Brian M. Scott Oct 3 '11 at 20:03

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.

share|improve this answer
    
Hi Mariano, when you post I was typing my suggestion of solution, I hope you don't mind. Sorry about that. –  Leandro Oct 3 '11 at 5:15
    
@Leandro: of course not! The two ideas are quite different (and mine should not be taken too seriously :) ) –  Mariano Suárez-Alvarez Oct 3 '11 at 5:18
    
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)$. –  t.b. Aug 16 '12 at 11:34

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.

share|improve this answer
    
This shows that, more generally, $G_\delta$ sets are uncountable, of course. –  Mariano Suárez-Alvarez Oct 3 '11 at 6:19
1  
@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\}$? –  Asaf Karagila Oct 3 '11 at 6:46
2  
Then more generally dense $G_\delta$ sets are uncountable. :-) –  Asaf Karagila Oct 3 '11 at 6:51
1  
@Brian: Of course, just not "more generally"... since some $G_\delta$ are countable or even finite. –  Asaf Karagila Oct 3 '11 at 7:12
1  
@Asaf: Yes, I sloppily overlooked the ‘more generally’ when commenting on the nature of the uncountability. –  Brian M. Scott Oct 3 '11 at 7:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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