Criteria for finiteness of a set

We relate sets to $\mathbb{N}$ to decide finiteness.

• (Q)
  Let $\mathbb{A}$ be a non-empty set.
  Then $\mathbb{A}$ is finite if and only if there is an injection $\alpha: \mathbb{A} \rightarrow \mathbb{N}$, but no surjection $\beta: \mathbb{A} \rightarrow \mathbb{N}$.

Suppose that the set $\mathbb{A}$ is finite with $n \in\mathbb{N}$ elements, so there is a bijection $\gamma: \mathbb{A} \rightarrow \mathbb{N}_n$.

Put $\alpha = \delta_n \circ \gamma: \mathbb{A} \rightarrow \mathbb{N}$.
Then $\alpha$ is a composition of injections, so is an injection.

Next suppose that there is a surjection $\beta: \mathbb{A} \rightarrow \mathbb{N}$.
Put $\delta = \epsilon_{n + 1}\circ \beta\circ \gamma^{-1}: \mathbb{N}_n \rightarrow \mathbb{N}_{n + 1}$.
Then $\delta$ is well-defined and is a composition of surjections, so is a surjection.
But this violates the Pigeonhole Principle, theorem (L) above, so the map $\beta$ cannot exist as required.

Conversely, suppose that there is an injection $\alpha: \mathbb{A} \rightarrow \mathbb{N}$, but no surjection $\beta: \mathbb{A} \rightarrow \mathbb{N}$.
We must prove that $\mathbb{A}$ is finite.
Note that the map $\alpha$ induces a bijection with $\alpha(\mathbb{A})\subset \mathbb{N}$ so the set $\mathbb{A}$ is finite if and only if $\alpha(\mathbb{A})$ is finite, so, without loss of generality, replacing $\mathbb{A}$ by $\alpha(\mathbb{A})$, we may assume that $\mathbb{A} \subset \mathbb{N}$. So we need only prove the result:

• Let $\phi \ne \mathbb{A}\subset \mathbb{N}$.
  If there is no surjection from $\mathbb{A}$ to $\mathbb{N}$, then $\mathbb{A}$ is finite.

Using POW, we define a map $g$ from a subset of the integers to the set $\mathbb{A} \subset \mathbb{N}$, recursively, by the formulas:

• $g(1) = \inf(\mathbb{A})\ge 1$, $\mathbb{A}_1 = \mathbb{A} - \{g(1)\}\subset \mathbb{A}$, $\mathbb{B}_1 = \{g(1)\}$, $\mathbb{A} = \mathbb{A}_1 \cup \mathbb{B}_1$, $\mathbb{A}_1 \cap \mathbb{B}_1 = \phi$. If now $\mathbb{A}_1 = \phi$, we stop and $\mathbb{B}_1 = \mathbb{A}$.
• If instead $\mathbb{A}_1 \ne \phi$, we define $g(2) = \inf(\mathbb{A}_1)> g(1)\ge 1$, $g(2) \ge 2$, $\mathbb{A}_2 = \mathbb{A}_1 - \{g(2)\}\subset \mathbb{A}_1$, $\mathbb{B}_2 = \mathbb{B}_1 \cup \{g(2)\}$, $\mathbb{A} = \mathbb{A}_2 \cup \mathbb{B}_2$, $\mathbb{A}_2 \cap \mathbb{B}_2 = \phi$. If now $\mathbb{A}_2 = \phi$, we stop and $\mathbb{B}_2 = \mathbb{A}$.
• If instead $\mathbb{A}_2 \ne \phi$, we define $g(3) = \inf(\mathbb{A}_2)> g(2) \ge 2$, $g(3) \ge 3$, $g(3) \in \mathbb{A}_2$, $\mathbb{A}_3 = \mathbb{A}_2 - \{g(3)\}\subset \mathbb{A}_2$, $\mathbb{B}_3 = \mathbb{B}_2 \cup \{g(3)\}$, $\mathbb{A} = \mathbb{A}_3 \cup \mathbb{B}_3$, $\mathbb{A}_3 \cap \mathbb{B}_3 = \phi$. If now $\mathbb{A}_3 = \phi$, we stop and $\mathbb{B}_3 = \mathbb{A}$.

We continue in this vein as long as possible: the resulting recursion is well-defined and either goes on for ever or terminates at some point.
If the recursion terminates, after $k \in \mathbb{N}$ steps, we obtain a map $g: \mathbb{N}_k \rightarrow \mathbb{A}$, which is injective, since it is increasing.
Also the range of $g$ is $\mathbb{B}_k = \mathbb{A}$.
So $g$ is a bijection and $\mathbb{A}$ is finite, with $k$ elements.
If the recursion never terminates, we obtain a map $g: \mathbb{N} \rightarrow \mathbb{A}$, which is injective, since it is increasing.
We claim that $g$ is bijective.
Suppose $g$ is not surjective.
Then there is some $t \in \mathbb{A}\subset \mathbb{N}$, such that $g(x) = t$ has no solutions, for $x \in \mathbb{N}$.
Now $g(t) \ge t$, a property of the recursion, so $g(t) > t$. Also $t < g(1)$ is false by definition of $g(1)$. So $t > g(1)$.
Let $\mathbb{S} = \{x \in \mathbb{N}: g(x) < t\}\subset \mathbb{N}$.
Then $s = \sup(\mathbb{S})$ exists and $1 \le s < t$ since $\mathbb{S}$ is bounded above by $t$ and below by $1$. Then we have $g(s) < t < g(s + 1)$.
But since $t \in \mathbb{A}$, this contradicts the definition of $g(s + 1)$, since $t \ne g(k)$, for any $k \in \mathbb{N}_s$, since $g$ is increasing, so that $t \notin \mathbb{B}_s$, so $t \in \mathbb{A}_s$, so $\inf(\mathbb{A}_s) \le t < g(s +1)$, a contradiction.
So $g$ is surjective, so bijective. So $\beta = g^{-1}$ is a surjection from $\mathbb{A}$ to $\mathbb{N}$, a contradiction. So the recursion must terminate and $\mathbb{A}$ is finite, as required. Note that in the last part of this proof, we also proved here the result:

• (R)
  If $\alpha: \mathbb{A} \rightarrow \mathbb{N}$ is an injection and if $\mathbb{A}$ is not finite, then there is a bijection from $\mathbb{A}$ to $\mathbb{N}$.

Next we give the "dual" version:

• (S)
  Let $\mathbb{A}$ be a non-empty set.
  Then $\mathbb{A}$ is finite if and only if there is a surjection $\alpha: \mathbb{N} \rightarrow \mathbb{A}$, but no injection $\beta: \mathbb{N} \rightarrow \mathbb{A}$.

If $\mathbb{A}$ is finite, with $k$ elements, then we may take $\mathbb{A} = \mathbb{N}_k$, without loss of generality and then the map $\alpha = \epsilon_k$, defined above, gives a surjection from $\mathbb{N}$ to $\mathbb{A}$. If there were also an injection $\beta$ from $\mathbb{N}$ to $\mathbb{N}_k$, then the composition $\beta \circ \delta_{k + 1}$ gives a well-defined map from $\mathbb{N}_{k + 1}$ to $\mathbb{N}_k$, which is an injection, since it is a composition of injections.
This contradicts the Pigeonhole Principle, so $\beta$ cannot exist.
Conversely we have to prove that if $\mathbb{A}\ne \phi$ and there is a surjection $\alpha: \mathbb{N} \rightarrow \mathbb{A}$ but no injection $\beta: \mathbb{N} \rightarrow \mathbb{A}$, then $\mathbb{A}$ is finite.
We begin by constructing an injection of $\mathbb{A}$ into $\mathbb{N}$.
For any $a \in \mathbb{A}$, define $\gamma(a) = \inf(\alpha^{-1}(\{a\}))$.
Then $\gamma(a)$ is well-defined by POW and $\gamma(a) \in \alpha^{-1}(\{a\})$, whence we have $\alpha(\gamma(a)) = a$. This gives a well-defined map $\gamma: \mathbb{A} \rightarrow \mathbb{N}$.
Now if for elements $a$ and $b$ of $\mathbb{A}$ we have $\gamma(a) = \gamma(b)$, then we have:

$$a = \alpha(\gamma(a) ) = \alpha(\gamma(b)) = b.$$

So $\gamma$ is injective. By the previous theorem, if $\mathbb{A}$ is not finite, then there is a bijection $\rho: \mathbb{A}\rightarrow \mathbb{N}$, so in particular an injection $\rho^{-1}$ from $\mathbb{N}$ to $\mathbb{A}$, a contradiction, so $\mathbb{A}$ is finite and we are done.
Note that the last part of this proof also gives the theorem:

• (T)
  Let $\mathbb{A}$ be a non-empty set.
  If there is a surjection $\alpha: \mathbb{N} \rightarrow \mathbb{A}$ and $\mathbb{A}$ is not finite, then there is a bijection from $\mathbb{A}$ to $\mathbb{N}$.

Finally we have the theorems (corollaries of the Pigeonhole Principle):

• (U)
  Let $\mathbb{A}$ be a non-empty set and $f: \mathbb{A} \rightarrow \mathbb{A}$, a map, which is an injection, but not a bijection. Then $\mathbb{A}$ is not finite.
• (V)
  Let $\mathbb{A}$ be a non-empty set and $f: \mathbb{A} \rightarrow \mathbb{A}$, a map, which is a surjection, but not a bijection. Then $\mathbb{A}$ is not finite.