Comparing finite sets
Task number: 3376
Prove by mathematical induction that for all finite sets \(X\) and \(Y\):
Variant
If there exists an injective mapping from \(X\) to the set \(Y\), then \(|X|\leq |Y|\).
Solution
We proceed by mathematical induction on \(n=|X|\).
I. For \(n=1\), if \(f:X\to Y\) is a mapping, then \(Y\) must have at least one element, otherwise \(f\) would not be a mapping. This yields the desired conclusion \(|X|=1\leq |Y|\).
II. Let \(|X|=n+1\) and assume that the assertion holds for all mappings from \(n\)-element sets. We choose an arbitrary element \(x\in X\) and define \(X'=X\setminus x\) and \(Y'=Y\setminus f(x)\).
Because \(f\) is injective, \(f(x)\) is not the image of any element other than \(x\). So \(f'=f\setminus (x,f(x))\) is a mapping from \(X'\) to \(Y'\).
The mapping \(f'\) is injective, because if it were not, i.e. if there existed distinct elements \(z,z'\in X'\) such that \(f'(z)=f'(z')\), then we would have \(f(z)=f'(z)=f'(z')=f(z')\), which contradicts the assumption that \(f\) is injective.
Because \(|X'|=n\), we can apply the inductive hypothesis to \(f'\) and obtain \(|X'|\leq|Y'|\). And now \(|X|=|X'|+1\leq|Y'|+1=|Y|\).
Note: Notice that the given inequality really follows from the fact that if \(f\) is injective, then \(Y\) must have at least as many elements as \(f\) (considered as a relation), because elements in the second coordinate of the relation cannot repeat.
Variant
If there exists a surjective mapping from \(X\) to \(Y\), then \(|X|\geq |Y|\).
Solution
We proceed by mathematical induction on \(n=|Y|\).
I. For \(n=1\), if \(f:X\to Y\) is surjective and \(Y\) is non-empty, then \(X\) must have at least one element, otherwise \(f\) would be the empty mapping and would not be surjective. This yields the desired result \(|X|\geq 1=|Y|\).
II. Let \(|Y|=n+1\) and assume that the assertion holds for mappings onto all \(n\)-element sets. Choose an arbitrary element \(y\in Y\) and let \(Y'=Y\setminus y\). In the set \(X\) determine the non-empty set of elements that map to \(y\) and remove them from \(X\), formally \(X'=X\setminus \{x: f(x)=y\}\).
Restricting \(f\) to \(X'\) again gives us a mapping \(f'=f\setminus \{(x,y):f(x)=y\}\) from \(X'\) to \(Y'\).
The mapping \(f'\) is surjective, because if it were not, i.e. if there existed an element \(z\in Y'\) such that \(\forall x\in X': z\ne f(x)\), then the existence of \(z\) would contradict the fact that \(f\) is surjective, because \(\forall x\in X\setminus X': f(x)=y\ne z\).
Because \(|Y'|=n\), we can apply the inductive hypothesis to \(f'\), yielding \(|X'|\geq|Y'|\). And then \(|X|>|X'|\geq|Y'|=|Y|-1\) or \(|X|\geq |Y|\).
Note: Note that the given inequality really follows from the fact that if \(f\) is surjective, then \(f\) must have at least as many elements as \(Y\), because of every element of \(Y\) appears as the second coordinate of some pair in \(f\).
