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 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?

share|improve this question
3  
I attempted to make this question coherent. Please make sure I didn't change what you intended to say. And by the way: properly formed sentences are your friend :) –  David Mitra Dec 27 '11 at 19:50
3  
@dato: Some non-mathematical comments: The first-person singular pronoun "I" is capitalized in English. Please put space after commas. Use LaTeX formatting, the basics of which are explained here. –  Zev Chonoles Dec 27 '11 at 19:54
    
@David: I'm sorry, I completely missed your edits. –  Zev Chonoles Dec 27 '11 at 19:55
add comment

3 Answers 3

up vote 1 down vote accepted

The sufficient condition for proving countability is establishing the 1-1 correspondence of a given set with $\mathbb{N}$. For proving the countability of rationals, a method called as diagonalization is used. Take a look at the following link. Your logic is correct, only that in place of $f(x)=\frac{n}{n+1}$, we use $f(x)=\frac{m}{n}$ and express $\frac{m}{n}$ in mth row and nth column. The representation covers all possible rational numbers and their ordering makes it a set corresponding 1-1 to $\mathbb{N}$.

http://www.homeschoolmath.net/teaching/rational-numbers-countable.php

share|improve this answer
    
The proof that you describe gives a many to one map from $\mathbb{N}$ to $\mathbb{Q}$ since many of the fractions $m/n$ will be reducible. It requires a little more work to obtain a bijection from this surjection. –  Adam Dec 27 '11 at 20:18
    
@Adam the set of rationals thus produced contains "same" fractions like 1/2, 3/6 and so on. If we restrict the m & n to be least possible, then it will be taken care of, what say? –  Nikhil Bellarykar Dec 27 '11 at 20:27
    
That would work. More abstractly, once you know that there is a surjection from $\mathbb{N}$ to $\mathbb{Q}$ you can cook up an injective map from $\mathbb{Q}$ to $\mathbb{N}$ by the axiom of choice. This gives a bijection of $\mathbb{Q}$ with an (infinite) subset of $\mathbb{N}$. Since $\mathbb{N}$ is bijective with all of its infinite subsets, the result follows. –  Adam Dec 28 '11 at 6:52
    
thanks for the clarification, Adam. I did not think of the axiom of choice at all :) –  Nikhil Bellarykar Dec 28 '11 at 7:01
add comment

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

share|improve this answer
add comment

The other answers are focused on explicitly constructing an bijection to the natural numbers. In practice, one would just note that the set in the question is a subset of a countably infinite set, $\mathbb{N}$, and so it is either finite or countably infinite. It is infinite, so it must be countably infinite.

This requires some justification, but it is not too difficult. See the first chapter of Topology by Munkres, for example.

share|improve this answer
add comment

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.