# cardinality of the set of all rational sequences taking exactly one value between two integers

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?

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]$$.

• Great post! This suggests that the set $T$, I believed to be 'smaller' than $Q$, is some kind of bigger than $Q$, which is, to be exact, not correct since $T\subseteq Q$. Pretty against the intuition. Therefore all the more thanks for your post.
– mag
Apr 3, 2020 at 18:12
• @mag: Right, this is an example of how an infinite set can have proper subsets of the same cardinality (in contrast to what happens in the finite case). Apr 3, 2020 at 19:53

Meanwhile I found a solution (motivated by the answer of 'hmakholm left over Monica' for another question), which I would like to share: The answer is, the set $$T$$ is uncountable.

Since there are uncountably many (infinite) binary sequences $$(b_n)_{n\in\mathbb{N}}$$, we can map them on the sequence $$(c_n)_{n\in\mathbb{N}}$$ by $$c_n:=n-1+b_n.$$ Since the mapping is obviously injective and all these sequences are contained in $$T$$, we get a uncountable subset of $$T$$.