Proof of Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products

Throughout, by The Number of Elements of a Finite Set §cardinality and Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §unique, a bijection from $[n]$ onto a finite set $E$ shows $\#E=n$. Recall from Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §segment that $[0]=\emptyset$ and $[1]=\{1\}$, and from Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §successor that $[n+1]=[n]\cup\{n+1\}$ with $n+1\notin[n]$.

Intervals. The identity of $[n]$ is a bijection by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity, so $\#[n]=n$. Let $m\le n+1$. If $m=0$, then by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §shift the map $k\mapsto k+1$ is a bijection from $\{0,\dots,n\}$ onto $\{1,\dots,n+1\}=[n+1]$, and its inverse is a bijection by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §inverse; so $\#\{0,\dots,n\}=n+1=n-0+1$. If $m\ge1$, put $p=m-1$ and $q=n-m+1$, both in $\mathbb{N}_{0}$ since $1\le m\le n+1$. By Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §shift the map $k\mapsto k+p$ is a bijection from $\{1,\dots,q\}=[q]$ onto $\{1+p,\dots,q+p\}=\{m,\dots,n\}$, so $\#\{m,\dots,n\}=q=n-m+1$.

Empty sets and singletons. If $\#A=0$, there is a bijection $\varphi:[0]\to A$; since $[0]=\emptyset$ and $\varphi$ is surjective, $A=\emptyset$. Conversely $\mathrm{id}_{\emptyset}$ is a bijection $[0]\to\emptyset$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity, so $\#\emptyset=0$. The map $1\mapsto x$ is a bijection $[1]\to\{x\}$, so $\#\{x\}=1$.

Images. Let $n=\#A$, let $\varphi:[n]\to A$ be a bijection, and let $f:A\to C$ be a map. If $f$ is injective, the map $k\mapsto f(\varphi(k))$ from $[n]$ to $f(A)$ is injective by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §preservation, and it is surjective because every element of $f(A)$ is $f(a)=f(\varphi(\varphi^{-1}(a)))$ for some $a\in A$; so $\#f(A)=n$. In general, for $y\in f(A)$ the set $\{k\in[n]:f(\varphi(k))=y\}$ is a nonempty subset of $\mathbb{N}$; let $g(y)$ be its least element, given by Arithmetic and Order of the Natural Numbers §well-order. Then $g:f(A)\to[n]$ satisfies $f(\varphi(g(y)))=y$, so $g$ is injective. With $p=\#f(A)$ and a bijection $\psi:[p]\to f(A)$, the map $g\circ\psi:[p]\to[n]$ is injective by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §preservation, so $p\le n$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §pigeonhole.

Subsets. Let $B\subseteq A$, $p=\#B$, $n=\#A$, and let $\psi:[p]\to B$ and $\varphi:[n]\to A$ be bijections. The map $k\mapsto\varphi^{-1}(\psi(k))$ from $[p]$ to $[n]$ is injective, so $p\le n$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §pigeonhole. Suppose $B\neq A$ and choose $a\in A\setminus B$. Extending $\psi$ by $p+1\mapsto a$ gives a map $\psi':[p+1]\to A$, which is injective because $\psi$ is injective, $[p+1]=[p]\cup\{p+1\}$ and $a\notin B$. Then $k\mapsto\varphi^{-1}(\psi'(k))$ is an injective map $[p+1]\to[n]$, so $p+1\le n$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §pigeonhole, and $p<n$. Hence $\#B=\#A$ only if $B=A$.

Unions. First let $A$ and $B$ be disjoint, $k=\#A$, $l=\#B$, with bijections $\varphi:[k]\to A$ and $\psi:[l]\to B$. By Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §split (with $1$, $k$, $l$ in place of $m$, $n$, $p$) and Intervals of Natural Numbers §segment, $[k+l]$ is the union of the disjoint sets $[k]$ and $\{k+1,\dots,k+l\}$, and by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §shift the map $j\mapsto j+k$ is a bijection from $[l]$ onto $\{k+1,\dots,k+l\}$, with inverse $j\mapsto j-k$. So $\chi:[k+l]\to A\cup B$, given by $\chi(j)=\varphi(j)$ for $j\le k$ and $\chi(j)=\psi(j-k)$ for $j>k$, is a bijection onto $A$ on the first piece and onto $B$ on the second; as the pieces and the sets $A$ and $B$ are disjoint, $\chi$ is a bijection, and $\#(A\cup B)=k+l$. In general, $A\cup B$, $A\cap B$ and $B\setminus A$ are finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §union and Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §subset. Since $A\cup B$ is the disjoint union of $A$ and $B\setminus A$, and $B$ is the disjoint union of $A\cap B$ and $B\setminus A$, the disjoint case gives

$$\#(A\cup B)+\#(A\cap B)=\#A+\#(B\setminus A)+\#(A\cap B)=\#A+\#B.$$

Products. Fix $A$. We show for every $n\in\mathbb{N}_{0}$ that $\#(A\times B)=\#A\cdot n$ for every finite $B$ with $\#B=n$, checking $n=0$ and the passage from $n$ to $n+1$; the class of $n\in\mathbb{N}$ for which this holds then contains $1=0+1$ and is closed under $n\mapsto n+1$, so it is $\mathbb{N}$ by Arithmetic and Order of the Natural Numbers §induction, and $\mathbb{N}_{0}=\mathbb{N}\cup\{0\}$ by The Natural Numbers with Zero and Their Embedding into the Integers §naturals. If $\#B=0$, then $B=\emptyset$ by the clause on empty sets, and $A\times B=\emptyset$, so $\#(A\times B)=0=\#A\cdot0$. Assume the claim for $n$ and let $\#B=n+1$, with a bijection $\psi:[n+1]\to B$. Put $b=\psi(n+1)$ and $B'=\psi([n])$. The restriction $\psi|_{[n]}$ is a bijection $[n]\to B'$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §restriction, so $\#B'=n$; moreover $B=B'\cup\{b\}$ and $b\notin B'$, as $\psi$ is injective and $n+1\notin[n]$. Hence $A\times B$ is the union of the disjoint sets $A\times B'$ and $A\times\{b\}$, all finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §union and Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §small. The map $a\mapsto(a,b)$ from $A$ to $A\times\{b\}$ is injective with image $A\times\{b\}$, so $\#(A\times\{b\})=\#A$ by the image clause. By the union clause and the induction hypothesis, $\#(A\times B)=\#A\cdot n+\#A=\#A\cdot(n+1)$.