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.

As the question asked, Is every subset of $\mathbb{Z^+}$ countable?

share|improve this question
    
Do you bother searching the site before asking? –  Asaf Karagila Mar 15 '12 at 10:53
    
Do you know the recursion principle? In my class: A infinite subset of $\Bbb Z_+$ is countably infinite was proved by exibhiting an explicit bijection with $\Bbb Z_+$. We had to check that the bijection map was well-defined and this motivated the recursion principle. –  user21436 Mar 15 '12 at 10:56
3  
@Kirthi: Please don't tell me what to do or not to do, what I should or should not do. I have my own moral compass and my own mind for making decisions like that. Thank you very much and have a pleasant time of the day. –  Asaf Karagila Mar 15 '12 at 12:12
2  
Sorry I didn't mean to offend –  Kirthi Raman Mar 15 '12 at 12:18
3  
@Asaf: We each have a moral compass. Maybe Kirthi is just expressing what his says in this situation... –  The Chaz 2.0 Mar 15 '12 at 12:45

2 Answers 2

Definition: $A$ is countable if and only if there exists a function $f\colon A\to\mathbb Z^+$ which is injective.

Now take the identity map, which is obviously injective since $id(x)=x$.


Definition: $A$ is countable if and only if there exists a function $g\colon\mathbb Z^+\to A$ which is surjective or $A=\varnothing$.

Now let $A\subseteq\mathbb Z^+$, if $A$ is empty then we are done. Otherwise pick $a\in A$ and define $g$ as follows:

$$g(n)=\begin{cases} n &n\in A\\ a &n\notin A\end{cases}$$

It is clear that this is a surjective function, as wanted.


Definition: $A$ is countable if and only if it is finite or there is $h\colon\mathbb Z^+\to A$ which is a bijection.

Suppose $A$ is a subset of $\mathbb Z^+$. If it is finite then we are done. Otherwise define by induction:

  • $h(0)=\min\{a\in A\}$.
  • Suppose $h(n)$ was defined, $h(n+1)=\min\{a\in A\mid h(n)<a\}$.

Now we claim that $h$ is a bijection. By induction we can easily show that $h(n)<h(n+1)$ and therefore $h$ is injective,

It is surjective since every $a\in A$ has only finitely many numbers smaller than itself therefore after at most $k$ steps (for some $k$) we have that $a<h(k)$ and therefore for some $n<k$ we had to have $a=\min\{x\in A\mid x<h(n)\}$ therefore $a=h(n)$.


Theorem: All three definitions above are equivalent.

Proof: If $A$ is finite then this is clear.

Suppose $A$ is infinite, if there exists a bijection of $A$ with $\mathbb Z^+$ then it is injective and its inverse is surjective, so the third definition implies the other two.

If there exists a surjective function $g\colon\mathbb Z^+\to A$ define $f(a)=\min\{n\in\mathbb Z^+\mid g(n)=a\}$, since $g$ is a surjecitve function this is well-defined, and it is injective since $g$ is a function.

Lastly if there exists an injection $f$ from $A$ into $\mathbb Z^+$ we can define $h\colon\mathbb Z^+\to\{f(a)\mid a\in A\}$ as in the third definition. Since $A$ is infinite the set to which we want $h$ to be defined into is infinite. Now $(f^{-1}\circ h)\colon\mathbb Z^+\to A$ is a bijection.

share|improve this answer
    
From your describe of the third definition, since A is a subset of $\mathbb{Z^+} $ what if$h(n)=max{a\in A}$ then how can h map n+1 to A as there are only finite number of element in A –  Mathematics Mar 15 '12 at 11:25
    
@Mathematics: No, in the third option note that if $A$ is finite then we are done. Otherwise we define that function, namely $A$ is not finite, i.e. it is infinite. –  Asaf Karagila Mar 15 '12 at 11:27

You asked if for all sets $A \subset \mathbb{Z}^{+}$, is $A$ countable. Consider the set

$$A = \{1,2,3\} \subset \mathbb{Z}^{+}.$$

This set is a finite subset of $\mathbb{Z}^{+}$ that is not countable. Or in your question did you mean to ask if for all subsets of $\mathbb{Z}^{+}$ is it the case that they are at most countable?

Note: I am taking the definition of countable from Rudin's Principles of Mathematical Analysis that a set $A$ is said to be countable if there is a bijective function $f$ from $A$ to $\mathbb{Z}^{+}$.

share|improve this answer
    
That is an example of a countable subset. (Finite sets are countable too...) –  Asaf Karagila Mar 15 '12 at 10:58
    
@AsafKaragila I think OP was asking for at most countable.... –  user38268 Mar 15 '12 at 11:00
2  
This is really about how you define countable. Finite sets are countable. –  Asaf Karagila Mar 15 '12 at 11:05
3  
There seems to be no consensus whether "countable" allows finite set. To avoid misunderstandings it is a good idea always to write "at most countable" or "countably infinite", according to which sense one wants. –  Henning Makholm Mar 15 '12 at 11:36
2  
I have never understood this lack of consensus. A set is countable if you can count it. Clearly you can count a finite set, while if there exists a bijection $f: \mathbb{N}\rightarrow S$ then $S$ is countable as $f(1)$ is the first element, $f(2)$ is the second element, ..., $f(n)$ is the $n^{th}$ element, etc. If finite sets are not allowed then the word "countable" was a bad choice! –  user1729 Mar 15 '12 at 13:38

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.