-1
$\begingroup$

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

  • 0
    Do you bother searching the site before asking?2012-03-15
  • 0
    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.2012-03-15
  • 0
    i couldn't search anything2012-03-15
  • 0
    Asaf this is a friendly environment, particularly after asking a question like that you should not post an answer to this question2012-03-15
  • 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.2012-03-15
  • 2
    Sorry I didn't mean to offend2012-03-15
  • 3
    @Asaf: We each have a moral compass. Maybe Kirthi is just expressing what his says in this situation...2012-03-15

2 Answers 2

4

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)

Now we claim that $h$ is a bijection. By induction we can easily show that $h(n)

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


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.

  • 0
    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 A2012-03-15
  • 0
    @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.2012-03-15
0

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}^{+}$.

  • 0
    That is an example *of* a countable subset. (Finite sets are countable too...)2012-03-15
  • 0
    @AsafKaragila I think OP was asking for at most countable....2012-03-15
  • 2
    This is really about how you define countable. Finite sets are countable.2012-03-15
  • 0
    @AsafKaragila I have been told the definition given in Baby Rudin is not standard....2012-03-15
  • 0
    The moral of the story is this: Never let analysts tell you about set theory.2012-03-15
  • 0
    This is why I was suggesting yesterday that there should be a way to communicate privately on a single question.2012-03-15
  • 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.2012-03-15
  • 0
    @HenningMakholm I edited my answer to reflect that.2012-03-15
  • 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!2012-03-15