Proof of Peeling an Element off a Finite Set, and Unions of Finite Sets

Elementary order facts about $\mathbb{N}$ used below — totality of $\le$, that $l<S(k)$ implies $l\le k$, and that $k<S(k)$ — are those of Order on the Natural Numbers and Properties of the Order on the Natural Numbers.

Claim 1. If $x\in C$ then $C\cup\{x\}=C$, which is finite. If $x\notin C$ and $C=\emptyset$ then $C\cup\{x\}=\{x\}$, which has $1$ element by claim 2 of Basic Properties of Finite Sets and is therefore finite. If $x\notin C$ and $C\ne\emptyset$ then $C$ has $m$ elements for some $m\in\mathbb{N}$ by Finite Set, and claim 2 of Basic Properties of Finite Sets gives that $C\cup\{x\}$ has $S(m)$ elements, hence is finite.

Claim 2. Let $\psi:[S(k)]\to B$ be a bijection, which exists because $B$ has $S(k)$ elements. Put $x=\psi(S(k))$ and $B'=\psi([k])=\{\psi(l):l\in[k]\}$. Since $[k]\subseteq[S(k)]$ we have $B'\subseteq B$, and by claim 3 of Injectivity, Composition, and Restriction of Bijections the restriction of $\psi$ to $[k]$ is a bijection from $[k]$ onto $B'$, so $B'$ has $k$ elements.

Every element of $B$ is $\psi(l)$ for some $l\in[S(k)]$, and by totality either $l<S(k)$, whence $l\le k$ and $\psi(l)\in B'$, or $l=S(k)$, whence $\psi(l)=x$; therefore $B=B'\cup\{x\}$. Finally $x\notin B'$: if $x=\psi(l)$ with $l\in[k]$, then $\psi(S(k))=\psi(l)$ and injectivity of $\psi$, from claim 1 of Injectivity, Composition, and Restriction of Bijections, gives $S(k)=l\le k$, contradicting $k<S(k)$.

Claim 3. If $B=\emptyset$ then $A\cup B=A$ is finite. Otherwise $B$ has $k$ elements for some $k\in\mathbb{N}$, and we argue by induction on $k$, using the induction principle for the natural numbers. Let $\mathcal{P}$ be the set of natural numbers $k$ such that $A\cup B$ is finite for every finite set $A$ and every set $B$ with $k$ elements.

If $B$ has $1$ element, let $\psi:[1]\to B$ be a bijection; since $[1]$ consists of $1$ alone, $B=\{\psi(1)\}$, so $A\cup B=A\cup\{\psi(1)\}$ is finite by claim 1. Hence $1\in\mathcal{P}$.

Suppose $k\in\mathcal{P}$ and let $B$ have $S(k)$ elements. By claim 2 there are $B'$ with $k$ elements and $x\in B$ with $B=B'\cup\{x\}$. Then $A\cup B=(A\cup B')\cup\{x\}$, the set $A\cup B'$ is finite by the induction hypothesis, and claim 1 gives that $A\cup B$ is finite. Hence $S(k)\in\mathcal{P}$, and by induction $\mathcal{P}$ contains every natural number.