Definition of a bijection
Task number: 3378
Show that for a mapping \(f:X\to X\) on a finite set \(X\), \(f\) is injective if and only if \(f\) is surjective.
Does this assertion hold even for infinite sets \(X\)?
Solution
We will first show by contradiction that if \(f\) is injective, then it is surjective.
If some mapping \(f:X\to Y\) between finite sets \(X\) and \(Y\) is injective but not surjective, then \(|X|=|\{x:(x,y)\in f\}|=|\{y:(x,y)\in f\}|<|Y|\).
In the first equality we've used the nature of a mapping, in the second, the fact that \(f\) is injective and in the third, the fact that \(f\) is not surjective, i.e. there exists \(y\in Y\setminus \{y:(x,y)\in f\}\) such that adding it to the finite set will increase its size.
If we let \(Y=X\), we obtain \(|X|<|X|\), which is a contradiction.
We can demonstrate the reverse implication by contradiction as well.
If some mapping \(f:X\to Y\) between finite sets \(X\) and \(Y\) is surjective but not injective, then \(|X|=|\{x:(x,y)\in f\}|>|\{y:(x,y)\in f\}|=|Y|\)
Again, in the first equality we've used the nature of a mapping, in the second, the fact that \(f\) is not injective and in the third, that \(f\) is surjective.
If we let \(Y=X\), we obtain \(|X|>|X|\), a contradiction.
For infinite sets the assertion does not hold, since \(f(x)=x+1\) is injective but not surjective on \(\mathbb N\).
