0
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – mag
    Apr 3, 2020 at 18:12
  • $\begingroup$ @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). $\endgroup$ Apr 3, 2020 at 19:53
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .