Proof of Counting a Partition into Blocks of Equal Cardinality

We refer to the recursive identities of Natural Numbers by number, in particular (iii) $m\cdot 1=m$ and (iv) $m\cdot S(n)=m\cdot n+m$, and we use the numbered claims of Basic Properties of Initial Segments of the Natural Numbers. We fix $t\in\mathbb{N}$ and argue by induction on $r$, meaning an application of Principle of Induction for the Natural Numbers; thus it suffices to prove the assertion for $r=1$ and to pass from $r$ to $S(r)$. Let $P(r)$ denote the assertion of the lemma for the given $t$ and this value of $r$.

Base case $P(1)$. By claim 2 of Basic Properties of Initial Segments of the Natural Numbers we have $[1]=\{1\}$, so hypothesis 1 says that every $x\in X$ lies in $B_1$; together with $B_1\subseteq X$ this gives $X=B_1$. By hypothesis 3, $X$ has $t$ elements, and $t=t\cdot 1$ by (iii).

Inductive step. Assume $P(r)$, and let $X$ and subsets $B_i\subseteq X$ for $i\in[S(r)]$ satisfy hypotheses 1--3. By claim 3 of Basic Properties of Initial Segments of the Natural Numbers we have $S(r)\notin[r]$ and $[S(r)]=[r]\cup\{S(r)\}$.

Put

The subsets $B_i\subseteq Y$ for $i\in[r]$ satisfy hypotheses 1--3 with $Y$ in place of $X$: hypothesis 1 holds by the definition of $Y$, and hypotheses 2 and 3 are inherited. By $P(r)$, the set $Y$ has $t\cdot r$ elements, so there is a bijection $g:[t r]\to Y$; note $t r\in\mathbb{N}$ because multiplication is an operation on $\mathbb{N}$ by Natural Numbers. By hypothesis 3 there is also a bijection $b:[t]\to B_{S(r)}$.

We record two facts. First, $X$ is the union of $Y$ and $B_{S(r)}$: indeed $Y\subseteq X$ and $B_{S(r)}\subseteq X$, and conversely every $x\in X$ lies in some $B_i$ with $i\in[S(r)]=[r]\cup\{S(r)\}$, hence in $Y$ or in $B_{S(r)}$. Second, $Y\cap B_{S(r)}=\emptyset$: if $x$ lay in both, then $x\in B_i$ for some $i\in[r]$, and $i\ne S(r)$ because $S(r)\notin[r]$, contradicting hypothesis 2.

By claim 5 of Basic Properties of Initial Segments of the Natural Numbers applied with $m=t r$, the set $[t r+t]$ is the union of the two disjoint sets $[t r]$ and $[t r+t]\setminus[t r]$, and the map $j\mapsto t r+j$ is a bijection from $[t]$ onto $[t r+t]\setminus[t r]$. Define $F:[t r+t]\to X$ by

where in the second case $j$ denotes the unique element of $[t]$ with $u=t r+j$. This is well defined because the two cases are exhaustive and mutually exclusive and because $j$ is uniquely determined by $u$.

We claim $F$ is a bijection onto $X$. Let $x\in X$. If $x\in Y$, then since $g$ is a bijection there is exactly one $u\in[t r]$ with $g(u)=x$, hence exactly one $u\in[t r]$ with $F(u)=x$; and no $u\in[t r+t]\setminus[t r]$ satisfies $F(u)=x$, because there $F(u)\in B_{S(r)}$ while $Y\cap B_{S(r)}=\emptyset$. If $x\notin Y$, then $x\in B_{S(r)}$ by the first recorded fact, and no $u\in[t r]$ satisfies $F(u)=x$ since there $F(u)\in Y$; moreover, since $b$ is a bijection there is exactly one $j\in[t]$ with $b(j)=x$, and $u\mapsto j$ is a bijective correspondence between $[t r+t]\setminus[t r]$ and $[t]$, so there is exactly one such $u$. In both cases $x$ has exactly one preimage under $F$, so $F$ is a bijection.

Therefore $X$ has $t r+t$ elements, and $t r+t=t\cdot S(r)$ by (iv). This proves $P(S(r))$ and completes the induction.