I found one problem which asks following:
Show that the set of odd positive integers greater then 3 is countable.
At the begining I was thinking that such numbers could be represented by $2k+1$,where $k>1$; but in the answers paper there was written as $2n+3$ or general function is
$$f(n)=2n+3$$
and when I was thinking how to prove that such answer is countable, the answer paper said this function is a one-to-one correspondence from the set of positive numbers set to the set of positive odd integers greater to 3.
My question is: is it enough to prove a one-to-one correspondence between two sets, that one of them is countable. If yes, then once my lecturer ask me to proof that rational numbers are countable, so in this case if I represent rational numbers by following function from set of positive numbers:
$$f(n)=\frac{n+1}{n}$$
or maybe $f(n)=\frac{n}{n+1}$. They both are one-to-one correspondences from the set of positive numbers to the set of rational numbers (positives sure). Please help me, is my logic correct or not?
Best Answer
If you know that a set $A$ is countable and you demonstrate a bijection $f:A\to B$ then you have also shown that the set $B$ is countable; when $A=\mathbb{Z}^+$ this is the very definition of countable. Both of the functions $2k+1$ and $2n+3$ can be used to show that the set of odds greater than $3$ are countable but the former uses the countable domain of $\{2,3,\dots\}$ instead of $\mathbb{Z}^+=\{1,2,3,\dots\}$.
However, neither the functions $f(n)=(n+1)/n$ or $n/(n+1)$ are bijections. Try and express the positive rational number $1/3$ in either of these forms and you will find there is no integer $n$ that works. In order for a function to be a bijection it must be both injective and surjective; your function here is not surjective (it does not obtain every value in the target in the codomain at least once - some values, like $1/3$, are left untouched).