Question

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

Short answer

An injective function from one finite set to another of the same size will necessarily be surjective because every element of the destination set must be mapped to from the source set. However, in the case of infinite sets, a function can be injective without being surjective - as we showed with the case of the set of natural numbers mapping to the set of positive integers.

Step-by-step solution

Assumptions

Assume f is an injection from A to B, and |A| = |B|. This means that A and B are finite and have the same number of elements.

Definition of Injective

An injective function means that every element in A maps to a unique element in B. This ensures that no two elements of A have the same image in B.

Argument for Surjective Function

Since A and B have the same number of elements and every element of A is mapped to a unique element of B, it means that every element of B must be a mapping of an element in A because there aren't any 'extra' elements in B that could have been skipped by the mapping.

Conclusion for Finite Sets

Hence, it is concluded that when A and B are finite sets of the same size, if a function f: A -> B is injective, it must also be surjective.

Argument for Infinite Sets

Consider A to be the set of natural numbers and B to be the set of positive integers. Though both sets are infinite, a function f where \(f(n) = 2n\) (meaning every natural number n maps to an even positive integer 2n) is clearly an injection (as every element in set A maps to a unique element in B) but not a surjection (odd positive integers are left unmapped).