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

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

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$, and let $d=(n+1)-m$ be the difference, so that $d\in\mathbb{N}_{0}$ and $m+d=n+1$. Below, rearrangements of sums in $\mathbb{N}_{0}$ use the laws of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws.

If $m=0$, then $d=0+d=n+1$. 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 $\{0+1,\dots,n+1\}=\{1,\dots,n+1\}=[n+1]$, and its inverse is a bijection from $[n+1]$ onto $\{0,\dots,n\}$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §inverse; so $\#\{0,\dots,n\}=n+1=d$.

If $m\neq0$, then $m\in\mathbb{N}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets, and $m=p+1$ for some $p\in\mathbb{N}_{0}$: take $p=0$ if $m=1$, using $0+1=1$, and $p$ from Arithmetic and Order of the Natural Numbers §predecessor if $m\neq1$. Then $(p+d)+1=(p+1)+d=m+d=n+1$, so $p+d=n$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §cancellation and commutativity. 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,d\}=[d]$ onto $\{1+p,\dots,d+p\}$, and $1+p=p+1=m$ and $d+p=p+d=n$, so this interval is $\{m,\dots,n\}$. Hence $\#\{m,\dots,n\}=d=(n+1)-m$.

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$. Let $\psi':[p+1]\to A$ be given by $\psi'(k)=\psi(k)$ for $k\in[p]$ and $\psi'(k)=a$ for the other $k\in[p+1]$, a map by Maps Defined by Cases §cases with $P(k)$ the property $k\in[p]$, as $\psi(k)\in B\subseteq A$ and $a\in A$; since $[p+1]=[p]\cup\{p+1\}$ and $p+1\notin[p]$, it extends $\psi$ by $\psi'(p+1)=a$. It 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$; its hypothesis $1\le k+1$ holds, as $0\le k$ gives $1=0+1\le k+1$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws) 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 $\{1+k,\dots,l+k\}$, which is $\{k+1,\dots,k+l\}$ by commutativity of addition; let $\theta$ be its inverse, a bijection from $\{k+1,\dots,k+l\}$ onto $[l]$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §inverse. So $\chi:[k+l]\to A\cup B$, given by $\chi(j)=\varphi(j)$ for $j\le k$ and $\chi(j)=\psi(\theta(j))$ for the other $j\in[k+l]$, a map by Maps Defined by Cases §cases with $P(j)$ the property $j\le k$ (if $j\le k$, then $j\in[k]$ and $\varphi(j)\in A$; otherwise $j\in\{k+1,\dots,k+l\}$ and $\psi(\theta(j))\in B$), is $\varphi$, a bijection onto $A$, on the first piece and $\psi\circ\theta$, a bijection onto $B$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §preservation, 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$, by induction from $0$ on $\mathbb{N}_{0}$, The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction, checking $n=0$ and the passage from $n$ to $n+1$. 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)$.