Denote by $Q:=\{ x:\mathbb{N}\to\mathbb{Q}_+ \} $ the set of all positive rational sequences, whereas $\mathbb{Q}_+:=\mathbb{Q}\cap [0,\infty[$. I know that $Q$ is an uncountable set. But what about the (smaller) set $T$:
Consider the set $T\subset Q$ of all sequences $(x_n)_{n\in\mathbb{N}}$ for which $\forall n\in\mathbb{N}: x_n\in[n-1,n]$ holds. Roughly spoken the set of all rational sequences which have exactly one element between two integers. Is this set $T$ countable or uncountable?
My intuition is, that it is countable. But all my ideas of proofs stumbeld so far. For example I tried to construct the set: Since $M_1:=[0,1]\cap\mathbb{Q}$ is countable, I can construct for every $x_1\in M_1$ the sequence $x=(x_1, 2, 3, 4, 5, ….)$ and denote the set of all these sequences by $S_1$. Analogous, for the countable set $M_2:=([0,1]\cap\mathbb{Q})\times([1,2]\cap\mathbb{Q})$ I can construct the sequence $x=(x_1, x_2, 3, 4, 5, ….)$, whereas $(x_1,x_2)\in M_2$ and denote the set of all these sequences by $S_2$. And so on. Through this I can 'exactly approximate' every sequence contained in $T$ by an sequence contained in $M_n$ in the first $n$ elements of the sequence. My idea was to consider now the union $$U:=\bigcup\limits_{n\in\mathbb{N}} M_n.$$ Obviously $U$ is a countable set of sequences, but it unfortunately contains only squences whose 'relevant part' is finite.
Has anyone an idea how to show that $T$ is countable? Or maybe a proof why $T$ is uncountable?
Best Answer
Here's some more intuition. You can squeeze a copy of $\mathbb{Q}$ (and therefore $\mathbb{Q}_+$ as well) between two consecutive integers. Given a sequence $x : \mathbb{N} \to \mathbb{Q}$, define a new sequence $\widehat{x} : \mathbb{N} \to \mathbb{Q}$ by letting $\widehat{x}_n$ be the element of the copy of $\mathbb{Q}$ inside $[n-1, n]$ that corresponds with $x_n \in \mathbb{Q}$.
The 'new' sequence completely determines the 'old' sequence, and so there are at least as many 'new' sequences as there are 'old' ones; so the new set is uncountable, too.
Here's how to make this precise.
For each $n \in \mathbb{Z}$, the function $$x \mapsto n-1 + \dfrac{1}{2} \left( 1 + \dfrac{x}{1+|x|} \right)$$ is an injection $i_n : \mathbb{Q} \to [n-1, n]$, and $i_n(q) \in \mathbb{Q}$ for each $q \in \mathbb{Q}$.
The image $i_n[\mathbb{Q}] \subseteq [n-1, n]$ is the 'copy of $\mathbb{Q}$ in $[n-1, n]$' that I was talking about before.
Given a sequence $x : \mathbb{N} \to \mathbb{Q}$, you can construct a new sequence $\widehat{x} : \mathbb{N} \to \mathbb{Q}$ by letting $\widehat{x}_n$ be the element of the image of $i_n: \mathbb{Q} \to [n-1,n]$ corresponding with $x_n \in \mathbb{Q}$—that is, $\widehat{x}_n = i_n(x_n)$.
Now the function $x \mapsto \widehat{x}$ is injective: if $\widehat{x} = \widehat{\,\!y\,}$, then $i_n(x_n) = i_n(y_n)$ for each $n$, and so $x_n=y_n$ for each $n$ by injectivity of each $i_n$. Moreover $\widehat{x}_n \in [n-1,n]$ for each $n \in \mathbb{N}$ by construction.
Hence $x \mapsto \widehat{x}$ gives an injection from the set of sequences of rational numbers to the set of sequences of rational numbers with the additional property that the $n^{\text{th}}$ term is in the interval $[n-1, n]$.