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.

In class we had the following definiton of a countable set:

A set $M$ is countable if there is a bijection between $\mathbb N$ and $M$.

In our exam today, we had the following thesis given:If $A$ is a countable set, then there is a bijection $\mathbb N\rightarrow A$.

So I am really not sure if the thesis and therefore the equivalence in the definition is right. So is it correct? And how do you proove it? Thanks a lot!

share|improve this question
    
@Jean-Sébastien: It says right there in the second line. –  Asaf Karagila Nov 16 '12 at 22:13
add comment

3 Answers

up vote 1 down vote accepted

Suppose $B$ and $C$ are arbitrary sets, and suppose the following statement holds: "There is a bijection between $B$ and $C$." Observe that it isn't specified whether there is a bijection $B\to C$ or whether there is a bijection $C\to B$. (This may be the source of your confusion.) As it turns out, there is no need to specify. If there is a bijection $B\to C$, then the inverse of that bijection is a bijection $C\to B$; likewise, the existence of a bijection $C\to B$ guarantees the existence of a bijection $B\to C$. All of the following statements, then, are equivalent:

"There is a bijection between $B$ and $C$." (No direction specified.)

"There is a bijection $B\to C$." (One direction specified.)

"There is a bijection $C\to B$." (Other direction specified.)

"There is a bijection $B\to C$ and a bijection $C\to B$." (Both directions specified.)

Consequently, saying that there is a bijection between $\Bbb N$ and $A$ (i.e.: $A$ is countable) is equivalent to saying that there is a bijection $A\to\Bbb N$, or saying that there is a bijection $\Bbb N\to A$, or saying there is a bijection $A\to\Bbb N$ and a bijection $\Bbb N\to A$.

share|improve this answer
    
but why ist ' a bijection $\mathbb N\rightarrow A$ if and only if A is countable' correct? the way $\Rightarrow$ is the definition but what about $\Leftarrow$? –  user46021 Nov 16 '12 at 23:07
4  
When we say "if" in a definition, we really mean "if and only if". I discuss it more in my answer here, which is a duplicate of this post (at which you can see yet more discussion on it. –  Cameron Buie Nov 16 '12 at 23:19
add comment

Let $A$ be countable. From the definition it follows that there exists $\varphi :\mathbb N \to A$, $\varphi$ is bijective. Now prove there exists $\psi : A \to \mathbb N$ that is also bijective.

For this, take $\psi = \varphi^{-1}$, which exists and is well defined.

share|improve this answer
add comment

Suppose that $A$ is countable by your definition; then there is a bijection $f:\Bbb N\to A$. Because $f$ is a bijection, $f^{-1}$ is also a bijection, so it’s the desired bijection from $A$ to $\Bbb N$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.