# Prove every subset of $\Bbb N$ is countable.

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

• $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? – pjs36 May 8 '15 at 5:12
• @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. – layman May 8 '15 at 5:13
• 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. – Asaf Karagila May 8 '15 at 5:20
• @user46944 You're probably right. It just caught me off guard that your order didn't "feel" like the usual order on $\Bbb N$. – pjs36 May 8 '15 at 5:21
• @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. – 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.

• His argument is that we will never achieve $a_x$ even, since there is always a next odd number. – SalmonKiller May 8 '15 at 5:40
• 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. – Aloizio Macedo May 8 '15 at 5:41
• 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. – layman May 8 '15 at 5:43
• @AloizioMacedo Nice argument. :) – layman May 8 '15 at 5:43
• 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). – 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.

• 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. – layman May 8 '15 at 5:45
• @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. – SalmonKiller May 8 '15 at 5:46
• @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. – SalmonKiller May 8 '15 at 5:48
• 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. – layman May 8 '15 at 5:48
• @user46944 You got me :). – SalmonKiller May 8 '15 at 5:52