Are all countable, infinite sets countably infinite?

Question

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.

Answer 1

It does indeed take a proof to show that every infinite countable set is countably infinite (using the definitions you've given). However, it's a very simple argument in retrospect.

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<a_n\}\vert=n.$

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$ ...

Answer 2

With the Axiom of Choice, these are equivalent. But without, who knows? See Dedekind infinite set