## 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\).