# Are all countable, infinite sets countably infinite?

It sounds like a hilarious question to ask, but these are terms we don't want to conflate; i.e. there are separate notions of an infinite set (a set with a bijection to one of its proper subsets), a countable set (a set from which an injection to $$\mathbb N$$ exists), and a countably infinite set (a set from which a bijection to $$\mathbb N$$ exists). If some set $$A$$ proves to be a countable and infinite set, then is it automatically countably infinite?

For instance, let $$A$$ be some finite set and define the set $$S$$ to be the set of all finite sequences of elements of $$A.$$ It's easy to see that $$S$$ is an infinite set, since we can define a bijective function $$f$$ mapping $$S$$ to a proper subset of itself such that for any $$s\in S$$ we have that $$f(s)=\langle s,a\rangle$$ for some fixed $$a\in S.$$ We can also show that $$S$$ is countable by Theorem 0B stated in A Mathematical Introduction to Logic (Enderton) since $$A$$ is finite, hence countable. With these individual proofs, it does not occur to me immediately that there is a bijection from $$S$$ to $$\mathbb N,$$ because the proof for Theorem 0B involves mapping every member $$\langle a_0,...,a_n\rangle$$ of $$S$$ to some prime factorization $$2^{g(a_0)+1}\cdot 3^{g(a_1)+1}\cdot...\cdot p^{g(a_n)+1}$$ where $$p$$ is the $$(n+1)$$th prime and $$g$$ is an injective function from $$A$$ to $$\mathbb N$$ and it's clear that no member of $$S$$ is mapped to $$0$$ or $$1$$ this way. Proving that $$S$$ is countably infinite therefore should involve a completely different procedure.

Is there a theorem I'm missing that is completely relevant to this? I mean, it already sounds ridiculous to say that there's a countable, infinite set that is uncountably infinite, right? Thanks in advance.

• Reference topics: Tarski-finite & Dedekind-infinite. – DanielWainfleet Jun 2 '19 at 19:51

The key point is that every infinite subset of $$\mathbb{N}$$ is in bijection with $$\mathbb{N}$$ itself. To see this, just "collapse" the set: if $$A\subseteq\mathbb{N}$$ is infinite, consider the map from $$\mathbb{N}$$ to $$A$$ sending each $$n\in\mathbb{N}$$ to the unique $$a_n\in A$$ such that $$\vert\{b\in A: b
Now if $$f:A\rightarrow\mathbb{N}$$ is an injection and $$A$$ is infinite, then $$ran(f)$$ is an infinite subset of $$\mathbb{N}$$; hence by the above point we have a bijection $$b: ran(f)\cong\mathbb{N}$$. Now think about composing $$f$$ and $$b$$ ...
• (Minor thing that briefly confused me: this uses the convention $0 \in \mathbb{N}$, which OP also used, but still, it requires a slight adjustment if $\min \mathbb{N}=1$.) – Ian Jun 2 '19 at 17:15
• @Ian Quite right! If we're working without zero just replace "$<$" with "$\le$." – Noah Schweber Jun 2 '19 at 17:20
• This is wrong. The OP asks: "If some set 𝐴 proves to be a countable and infinite set, then is it automatically countably infinite?" (emphasis mine), and the answer to that question is simply yes. (Their definition of "countable" is "admits an injection into $\mathbb{N}$.") Every countable infinite set is indeed countably infinite; the subtlety you bring up is whether every infinite set has a countably infinite subset, which is quite different. – Noah Schweber Jun 2 '19 at 16:52