This isn't a homework problem. I've seen a proof of the following statement online, and I think the proof is suspect, or at least incomplete.

Theorem. Every subset of $\Bbb N$ is countable.

Proof. Let $A \subseteq N$. Suppose without loss of generality $A$ is not finite. Since $\Bbb N$ is well-ordered, $A$ has a least element $a_{1}$. Since $A$ is infinite, $A - \{a_{1}\} \neq \emptyset$, and again by the well-ordering of $\Bbb N$, there is a least element $a_{2} \in A - \{a_{1} \}$.

Proceeding inductively, for each $k \in \Bbb N$, we can find $a_{k} \in A - \{a_{1}, a_{2}, \dots, a_{k - 1} \}$ with $a_{1} < a_{2} < \dots < a_{k}$.

Then $A = \{a_{1}, a_{2}, \dots \}$, and so $A$ is countable, as desired.

I don't think this proof is complete. It should be shown that $A \subseteq \{a_{1}, a_{2}, \dots \}$, right? I don't think this is obvious because pretend we have a different ordering on $\Bbb N$, i.e., the following ordering:

$$1 < 3 <5 < \dots < 2 < 4 < 6 < \dots$$

Then if $A = \{1, 2, 3, \dots \}$, using the above procedure, we would only get the odd numbers, so we wouldn't be able to say $A \subseteq \{1, 3, 5, \dots \}$. Does my objection to the proof of the theorem make sense? How do you complete the proof (i.e., how do you show the containment I want to show)?

  • $\begingroup$ $1 < 3 <5 < \dots < 2 < 4 < 6 < \dots$ seems like an unusual (read: suspicious) order to me. Shouldn't $2$ have a predecessor, or is that not important? $\endgroup$ – pjs36 May 8 '15 at 5:12
  • $\begingroup$ @pjs36 I'm not sure what you mean (or whether it is important or not). I think with the ordering specified, the set $\{1, 3, 5, \dots, 2, 4, 6 \dots \}$ is still a well-ordered set. $\endgroup$ – layman May 8 '15 at 5:13
  • $\begingroup$ I deleted my answer, because I didn't like the constant stream of comments. You should perhaps behave less frantically when someone is posting an answer to your question. $\endgroup$ – Asaf Karagila May 8 '15 at 5:20
  • $\begingroup$ @user46944 You're probably right. It just caught me off guard that your order didn't "feel" like the usual order on $\Bbb N$. $\endgroup$ – pjs36 May 8 '15 at 5:21
  • $\begingroup$ @AsafKaragila Nice! Actually, I deleted the constant stream about 3 minutes ago, so I'm not sure why you decided to comment about it and delete now. Also, I was originally planning to accept your answer. $\endgroup$ – layman May 8 '15 at 5:21

Let $x \in A$

By induction, $a_k \geq k$ for all $k$. Therefore, $a_x \geq x$. Hence, $x$ was achieved at some point.

| cite | improve this answer | |
  • $\begingroup$ His argument is that we will never achieve $a_x$ even, since there is always a next odd number. $\endgroup$ – SalmonKiller May 8 '15 at 5:40
  • $\begingroup$ You misunderstood his question, I think. He is not asking about the order he mentions, nor about the sequence he mentions as a set. I think he simply doesn't think the fact is trivial as implicitly stated. $\endgroup$ – Aloizio Macedo May 8 '15 at 5:41
  • $\begingroup$ Well, this answer is correct if we assume the usual ordering of $1 < 2 < 3 < \dots $. This was my original question -- how do you show this rigorously. According to @AsafKaragila (who deleted his answer because I commented too much on it -- huh? I know...) it doesn't matter which order you take on $\Bbb N$ -- we can still prove any subset of $\Bbb N$ is countable. $\endgroup$ – layman May 8 '15 at 5:43
  • $\begingroup$ @AloizioMacedo Nice argument. :) $\endgroup$ – layman May 8 '15 at 5:43
  • $\begingroup$ I didn't read Asaf's answer, but I think he meant that the concept of enumerability doesn't depend on the ordering. The proof of this theorem uses the well-ordering of the natural numbers as a tool, but that doesn't mean that the concept of enumerability depends on an order. You can consider a different order, all right, but why would that be useful? (at least, for the purposes of the theorem). $\endgroup$ – Aloizio Macedo May 8 '15 at 5:48

Try this argument:

Let $S_1 = \lbrace 1, 3, 5, ...\rbrace$ and $S_2 = \lbrace 2, 4, 6, ...\rbrace$ all with the order $1 < 3 < 5 < ... < 2 < 4 < ...$. By that process, both $S_1$ and $S_2$ are countable. That implies that $S_1 \cup S_2$ is countable.

| cite | improve this answer | |
  • $\begingroup$ Well, assuming we know that a finite union of countable sets is countable, this would be OK in showing that $\Bbb N$ with the specified order is countable. But I needed to show that every subset of $\Bbb N$ is countable, so this argument would be incomplete in that regard. $\endgroup$ – layman May 8 '15 at 5:45
  • $\begingroup$ @user46944 if you want any subset of $\Bbb N$, just split any subset into the subsets of $S_1$ and $S_2$ and then take the union to show countability. $\endgroup$ – SalmonKiller May 8 '15 at 5:46
  • $\begingroup$ @user46944 I think this would be a more elementary rigorous explanation, because I thought of the OP's explanation before, but it didn't seem "right" enough because of your objections. $\endgroup$ – SalmonKiller May 8 '15 at 5:48
  • $\begingroup$ But you would need to know the finite union of countable sets is countable, and I think the proof of that requires that you know any subset of $\Bbb N$ is countable. So the argument becomes recursive. $\endgroup$ – layman May 8 '15 at 5:48
  • 1
    $\begingroup$ @user46944 You got me :). $\endgroup$ – SalmonKiller May 8 '15 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.