Question

Prove that if \(A\) and \(B\) are finite sets with \(|A|=|B|\), then any surjection \(f: A \rightarrow B\) is also an injection. Show this is not necessarily true if \(A\) and \(B\) are not finite.

Short answer

Assuming that \(f: A \rightarrow B\) is a surjection, if \(A\) and \(B\) are finite sets and \(|A| = |B|\), \(f\) is an injection. However, if \(A\) and \(B\) are infinite sets, \(f\) is not necessarily an injection.

Step-by-step solution

Understanding the Definitions

A function \(f: A \rightarrow B\) is called a surjection or a surjective function if for every element \(b\) in \(B\), there is at least one element \(a\) in \(A\) such that \(f(a) = b\). A function is called an injection or an injective function if different elements of \(A\) have different images in \(B\), that is, if \(f(a1) = f(a2)\), then \(a1 = a2\).

Case 1: A and B are Finite Sets

Assume that \(f: A \rightarrow B\) is a surjection and both \(A\) and \(B\) are finite with \(|A| = |B|\). Since every element of \(B\) has a preimage from \(A\), and \(|A| = |B|\), then every element in \(A\) must map to a unique element in \(B\). Therefore, the function \(f\) is an injection.

Case 2: A and B are Infinite Sets

Assume that \(f: A \rightarrow B\) is a surjection and both \(A\) and \(B\) are infinite sets, then \(f\) is not necessarily an injection. For instance, consider the function \(f: Z \rightarrow N\), where \(Z\) is the set of all integers and \(N\) is the set of all nonnegative integers defined as \(f(x) = |x|\). Then \(f\) is a surjection, but not an injection as elements -2, -1, 0, 1, 2 from Z all map to the element 1 in N, but they are not the same element.