Finite Sets and Counting

Technique: strong induction on $n$. Base case $n = 0$: $I_0 = \emptyset$ has no proper subsets, so the claim holds vacuously. Inductive step. Suppose the claim holds for all $k < n$ (strong induction hypothesis), and suppose toward contradiction that $f : I_n \to S$ is a bijection with $S \subsetneq I_n$. Consider $f(n) \in S \subseteq I_n$. We construct a new function $g : I_{n-1} \to I_{n-1}$ as follows. First define $h: I_n \to I_n$ by swapping the values $n$ and $f(n)$:

(If $f(n) = n$, take $h$ to be the identity; the swap is well-defined and is a bijection $I_n \to I_n$ in either case, since it is its own inverse.) Let $f' = h \circ f : I_n \to I_n$. Since $h$ and $f$ are both bijections, $f'$ is a bijection $I_n \to h[S]$, and $f'(n) = h(f(n)) = n$. Also $h[S] \subsetneq I_n$ since $h$ is a bijection $I_n \to I_n$ and $S \subsetneq I_n$ (bijections preserve strict containment sizes: if $S \subsetneq I_n$ then $h[S] \subsetneq h[I_n] = I_n$, because $h$ injective means $h[I_n \setminus S]$ is nonempty and disjoint from $h[S]$). Now restrict: since $f'(n) = n$ and $f'$ is injective, $f'$ restricts to a bijection

This is a bijection because $f'$ is a bijection $I_n \to h[S]$ sending $n \mapsto n$, and removing $n$ from both sides (domain $I_n \setminus \{n\} = I_{n-1}$, codomain $h[S]\setminus\{n\}$) preserves bijectivity of the restriction. Since $h[S] \subsetneq I_n$ and $n \in h[S]$ would require checking, we split into cases:

• If $n \notin h[S]$: then $h[S] \subseteq I_{n-1}$, and $h[S] \setminus \{n\} = h[S]$. Since $h[S] \subsetneq I_n$ and $h[S] \subseteq I_{n-1}$, we get $|h[S]| < n$ in the sense that $h[S]$ is a subset of $I_{n-1}$; it may equal $I_{n-1}$ or be proper. If $h[S] = I_{n-1}$ then $g : I_{n-1} \to I_{n-1}$ is a bijection, contradicting nothing yet — but we must show $h[S] \ne I_{n-1}$ is impossible to rule out directly; instead we handle both cases uniformly below.

• If $n \in h[S]$: then $h[S]\setminus\{n\} \subsetneq I_{n-1}$ (removing $n$ from a subset of $I_n$ containing $n$ lands inside $I_{n-1}$, and since $h[S] \subsetneq I_n$, we have $h[S] \setminus \{n\} \subsetneq I_n \setminus \{n\} = I_{n-1}$ is not immediate either — we need $h[S] \ne I_n$ combined with $n \in h[S]$ to force $h[S]\setminus\{n\} \ne I_{n-1}$, which holds precisely because $h[S] \subsetneq I_n$ means some element of $I_n$, necessarily in $I_{n-1}$ since $n \in h[S]$, is missing from $h[S]$, hence missing from $h[S]\setminus\{n\}$ too).

In both cases we conclude: $h[S] \setminus \{n\}$ is a subset of $I_{n-1}$ that is proper — i.e. misses at least one element of $I_{n-1}$. Let us verify this cleanly: since $h[S] \subsetneq I_n$, pick $j \in I_n \setminus h[S]$. Since $h[S] \setminus \{n\}$ omits $j$ as well (as $j \notin h[S]$ already), and $j \ne n$ is possible or $j = n$; but if $j = n$ then $n \notin h[S]$, putting us in the first case where $h[S] \subseteq I_{n-1}$ and $h[S] \ne I_{n-1}$ would need a separate witness. To avoid this case split entirely, argue directly: Since $|I_n|$ "should" exceed $|h[S]|$ by one omitted element $j\in I_n\setminus h[S]$: if $j \neq n$, then $j \in I_{n-1}$ and $j \notin h[S]\setminus\{n\}$, showing $h[S]\setminus\{n\} \subsetneq I_{n-1}$ directly. If $j = n$, i.e. $n \notin h[S]$, then since $h[S] \subsetneq I_n$ and $n$ is the only possibly-omitted element identified so far, we still know $h[S] \subseteq I_{n-1}$; since $h[S] \ne I_n \supsetneq I_{n-1} \cup \{n\}$ and $n \notin h[S]$, compare sizes: $h[S] \subseteq I_{n-1}$, and we ask whether $h[S] = I_{n-1}$ is possible. If it were, then $h[S] = I_{n-1} = I_n \setminus \{n\}$, so $h[S]$ would be exactly $I_n$ minus the single point $n$ — this is a legitimate proper subset of $I_n$, and there is no contradiction at this stage from properness alone. In this sub-case $g : I_{n-1} \to I_{n-1}$ would be a bijection, which is not a contradiction by itself — we need the induction hypothesis to rule out something else. Let us restart this final step more carefully and directly, avoiding the case explosion above.

Cleaner argument. We show directly that $g$ maps $I_{n-1}$ into a proper subset of $I_{n-1}$, using only that $S \subsetneq I_n$. Since $S \subsetneq I_n$, there exists $p \in I_n \setminus S$. Let $q = h(p) \in I_n$ (recall $h$ is the transposition swapping $n \leftrightarrow f(n)$, identity elsewhere). We claim $q \ne n$: if $q = n$ then $h(p) = n$, and since $h$ is an involution with $h(n) = f(n)$, applying $h$ to both sides gives $p = h(n) = f(n) \in S$ (as $f(n) \in S$ trivially since $f(n)$ is in the range of $f$, which is $S$). This contradicts $p \notin S$. So indeed $q \ne n$, i.e. $q \in I_{n-1}$. Now $q = h(p) \in h[I_n \setminus S]$. Since $h$ is a bijection $I_n \to I_n$, $h[I_n \setminus S] = I_n \setminus h[S]$, so $q \notin h[S]$. As $q \ne n$, also $q \notin h[S]\setminus\{n\}$, i.e. $q$ is not in the range of $g$. Since $q \in I_{n-1}$, this exhibits $I_{n-1} \setminus \mathrm{ran}(g) \ne \emptyset$, so $\mathrm{ran}(g) \subsetneq I_{n-1}$. Thus $g : I_{n-1} \to \mathrm{ran}(g)$ is a bijection onto a proper subset of $I_{n-1}$. This contradicts the strong induction hypothesis applied at $k = n-1 < n$. This contradiction shows our assumption was false: no bijection $f: I_n \to S$ with $S \subsetneq I_n$ can exist. By strong induction, the lemma holds for all $n \in \mathbb{N}$. $\blacksquare$

Proof of the Theorem (well-definedness of cardinality), technique: reduction to the Lemma. Suppose $f : I_n \to I_m$ is a bijection. We show $n = m$. Suppose toward contradiction that $n \ne m$; without loss of generality (by symmetry, replacing $f$ with $f^{-1}$ if necessary, which is also a bijection since Bijections and Inverse Functions guarantees bijections have bijective inverses) assume $m < n$. Since $m < n$, we have $I_m \subsetneq I_n$ (indeed $I_m = \{1,\dots,m\} \subsetneq \{1,\dots,n\} = I_n$ because $m+1 \in I_n \setminus I_m$). So $f$ is a bijection from $I_n$ onto $I_m$, and $I_m$ is a proper subset of $I_n$. This directly contradicts the Lemma (with $S = I_m$). Hence no such $n \ne m$ can occur: $n = m$. This proves the theorem's first statement. For the "consequently" clause: suppose $A$ is finite and $A \approx I_n$ and $A \approx I_m$ via bijections $f: I_n \to A$ and $g : I_m \to A$. Then $g^{-1} \circ f : I_n \to I_m$ is a composition of bijections, hence a bijection (composition of bijections is a bijection, a basic fact about Bijections and Inverse Functions). By the first part, $n = m$. So the witnessing $n$ is unique, justifying the notation $|A| = n$. $\blacksquare$

Technique: direct consequence of the Lemma. First prove the statement for initial segments. Suppose toward contradiction $f: I_n \to I_m$ is injective with $n > m$. Then $f$ is a bijection from $I_n$ onto its image $\mathrm{ran}(f) \subseteq I_m$ (every function is a bijection onto its range once restricted in codomain; injectivity gives injectivity onto the range, and surjectivity onto the range is automatic). Since $n > m$, $I_m \subsetneq I_n$ as shown above, so $\mathrm{ran}(f) \subseteq I_m \subsetneq I_n$, giving $\mathrm{ran}(f) \subsetneq I_n$ (a subset of a proper subset of $I_n$ is a proper subset of $I_n$ — using $\subseteq$ composed with $\subsetneq$). So $f : I_n \to \mathrm{ran}(f)$ is a bijection onto a proper subset of $I_n$, contradicting the Lemma. This proves the initial-segment case. Now for general finite $A, B$ with $|A| = n > m = |B|$: let $\alpha : I_n \to A$ and $\beta : I_m \to B$ be the witnessing bijections (which exist and are essentially unique by the Theorem). Suppose toward contradiction $f: A \to B$ is injective. Then

is a composition of injective functions ($\alpha$ bijective hence injective, $f$ injective by assumption, $\beta^{-1}$ bijective hence injective), and composition of injections is an injection (a standard fact from Images and Preimages / basic function theory: if $u,v$ injective, then for $u(v(x))=u(v(y))$, injectivity of $u$ gives $v(x)=v(y)$, then injectivity of $v$ gives $x=y$). So $\beta^{-1}\circ f \circ \alpha$ is an injection $I_n \to I_m$ with $n > m$, contradicting the initial-segment case just proved. Hence no injective $f : A \to B$ exists. $\blacksquare$