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.

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

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

  • 1
    $\begingroup$ (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$.) $\endgroup$ – Ian Jun 2 '19 at 17:15
  • $\begingroup$ @Ian Quite right! If we're working without zero just replace "$<$" with "$\le$." $\endgroup$ – Noah Schweber Jun 2 '19 at 17:20

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

  • 4
    $\begingroup$ 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. $\endgroup$ – Noah Schweber Jun 2 '19 at 16: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.