Proof of Basic Properties of Finite Sets

We use the numbered claims of Basic Properties of Initial Segments of the Natural Numbers, of Properties of the Order on the Natural Numbers and of Injectivity, Composition, and Restriction of Bijections. Every appeal to induction means an application of Principle of Induction for the Natural Numbers, so it suffices to verify a property at $1$ and to pass from $n$ to $S(n)$.

Claim 1. The identity map of $[n]$ is a bijection, since every $y\in[n]$ has $y$ as its only preimage. Hence $[n]$ has $n$ elements.

Claim 2. By claim 2 of Basic Properties of Initial Segments of the Natural Numbers we have $[1]=\{1\}$, and the map sending $1$ to $x$ is a bijection from $[1]$ onto $\{x\}$; so $\{x\}$ has $1$ element.

Now let $g:[k]\to A$ be a bijection and $x\notin A$. By claim 3 of Basic Properties of Initial Segments of the Natural Numbers we have $[S(k)]=[k]\cup\{S(k)\}$ with $S(k)\notin[k]$, so we may define $g':[S(k)]\to A\cup\{x\}$ by

Let $y\in A\cup\{x\}$. If $y\in A$, there is exactly one $i\in[k]$ with $g(i)=y$, and $g'(S(k))=x\ne y$ because $x\notin A$; so $y$ has exactly one preimage under $g'$. If $y=x$, then $g'(S(k))=y$, while no $i\in[k]$ satisfies $g'(i)=y$ since $g'(i)=g(i)\in A$; again exactly one preimage. Hence $g'$ is a bijection and $A\cup\{x\}$ has $S(k)$ elements.

Claim 3, subsets of initial segments. We show by induction on $n$ that every $B\subseteq[n]$ is empty or has $m$ elements for some $m\le n$.

For $n=1$ we have $[1]=\{1\}$, so $B=\emptyset$ or $B=\{1\}$; in the latter case $B$ has $1$ element by Claim 2, and $1\le 1$ by claim 1 of Properties of the Order on the Natural Numbers.

Assume the assertion for $n$ and let $B\subseteq[S(n)]$. Put $B'=\{i\in B: i\in[n]\}$, a subset of $[n]$; by the inductive hypothesis $B'$ is empty or has $m$ elements with $m\le n$. By claim 3 of Basic Properties of Initial Segments of the Natural Numbers we have $[S(n)]=[n]\cup\{S(n)\}$ and $S(n)\notin[n]$, so $S(n)\notin B'$.

If $S(n)\notin B$, then $B=B'$. If $B'$ is empty we are done; otherwise $B$ has $m$ elements, and $m\le n\le S(n)$ using claim 5 and transitivity from claim 1 of Properties of the Order on the Natural Numbers, so $m\le S(n)$.

If $S(n)\in B$, then $B=B'\cup\{S(n)\}$. If $B'$ is empty then $B=\{S(n)\}$ has $1$ element by Claim 2, and $1\le S(n)$ by claim 4 of Properties of the Order on the Natural Numbers. Otherwise $B'$ has $m\le n$ elements, so $B$ has $S(m)$ elements by Claim 2, and $S(m)\le S(n)$ by claim 6 of Properties of the Order on the Natural Numbers.

Claim 3, general case. Let $X$ be finite and $A\subseteq X$. If $X=\emptyset$ then $A=\emptyset$, which is finite. Otherwise $X$ has $n$ elements for some $n\in\mathbb{N}$; let $f:[n]\to X$ be a bijection and put $A'=\{i\in[n]: f(i)\in A\}$.

Write $f(A')=\{f(i): i\in A'\}$. Then $f(A')=A$: the inclusion $f(A')\subseteq A$ holds by the definition of $A'$, and conversely every $a\in A\subseteq X$ equals $f(i)$ for some $i\in[n]$ because $f$ is surjective, and that $i$ lies in $A'$.

By the subset case above, $A'$ is empty or has $m$ elements with $m\le n$. If $A'=\emptyset$ then $A=f(A')=\emptyset$, which is finite. Otherwise let $g:[m]\to A'$ be a bijection. By claim 3 of Injectivity, Composition, and Restriction of Bijections the restriction of $f$ to $A'$ is a bijection from $A'$ onto $f(A')=A$, and by claim 2 of that lemma its composite with $g$ is a bijection from $[m]$ onto $A$. Hence $A$ has $m$ elements with $m\le n$, and $A$ is finite. In particular, if $A\ne\emptyset$ then the second alternative occurred.

Claim 4. We argue by induction on $n$ on the property $P(n)$: for every set $X$ with $n$ elements, every set $Y$ and every surjection $q:X\to Y$, the set $Y$ has $m$ elements for some $m\le n$.

For $n=1$: let $f:[1]\to X$ be a bijection. Since $[1]=\{1\}$, surjectivity of $f$ gives $X=\{f(1)\}$. Every $y\in Y$ equals $q(x)$ for some $x\in X$, hence $y=q(f(1))$; and $q(f(1))\in Y$. So $Y=\{q(f(1))\}$, which has $1$ element by Claim 2, and $1\le 1$.

Assume $P(n)$, let $X$ have $S(n)$ elements with bijection $f:[S(n)]\to X$, and let $q:X\to Y$ be surjective. Put $x_0=f(S(n))$ and $X'=\{x\in X: x\ne x_0\}$. By claim 3 of Injectivity, Composition, and Restriction of Bijections the restriction of $f$ to $[n]$ is a bijection onto $f([n])$, and $f([n])=X'$: indeed $f(i)\ne f(S(n))=x_0$ for $i\in[n]$ because $S(n)\notin[n]$ and $f$ is injective by claim 1 of Injectivity, Composition, and Restriction of Bijections, so $f([n])\subseteq X'$; conversely every $y\in X'$ equals $f(i)$ for a unique $i\in[S(n)]$, and $i\ne S(n)$ since $f(S(n))=x_0\ne y$, so $i\in[n]$ by claim 3 of Basic Properties of Initial Segments of the Natural Numbers. Hence $X'$ has $n$ elements.

Put $Y'=\{q(x): x\in X'\}$. The restriction of $q$ to $X'$ is a surjection onto $Y'$, so by $P(n)$ the set $Y'$ has $k$ elements for some $k\le n$. Every $y\in Y$ equals $q(x)$ with $x\in X$, and either $x\in X'$, giving $y\in Y'$, or $x=x_0$, giving $y=q(x_0)$; hence $Y$ is the union of $Y'$ and $\{q(x_0)\}$. If $q(x_0)\in Y'$ then $Y=Y'$ has $k$ elements with $k\le n\le S(n)$. Otherwise $Y=Y'\cup\{q(x_0)\}$ with $q(x_0)\notin Y'$, so $Y$ has $S(k)$ elements by Claim 2, and $S(k)\le S(n)$ by claim 6 of Properties of the Order on the Natural Numbers. This proves $P(S(n))$.

In either case $Y$ has finitely many elements and is nonempty, since a set with $m$ elements contains $h(1)$ for any bijection $h:[m]\to Y$.