On page 3 of this paper https://arxiv.org/pdf/2404.01256.pdf
I spotted the claim:
Definitions of countability in terms of injection into ℕ misbehave intuitionistically, because a subset of a countable set need not be countable.
I do not understand why it the case. If $A\to \Bbb N$ is injective and $S\to A$ is an inclusion of subset, isn't the composition $S \to A \to \Bbb N$ again injective?
May I please ask for an unfold of an argument here?
Best Answer
Right before this statement, the author defines a set $S$ to be countable if there exists a surjection $\mathbb{N} \to S + 1$. Classically, this is equivalent to the existence of an injection from S to $\mathbb{N}$, but constructively this need not be so. The argument is essentially as you've surmised. If you have a subset of a set equipped with an injection into $\mathbb{N}$, then that subset also has an injection into $\mathbb{N}$.
But the definition of countable used here doesn't have that property. If S is a set with a surjection $\mathbb{N} \to S + 1$ and $A$ is a subset of $S$, there need not exist a surjection $\mathbb{N} \to A + 1$. Check out this page on subcountability for more.