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