Problem 62 - Combinatorics Through Guided Discovery

Question

Show that if \(S\) and \(T\) are finite sets of the same size, then a function \(f\) from \(S\) to \(T\) is one-to-one if and only if it is onto. (h)

Step-by-Step Solution

Answer

If \(S\) and \(T\) are finite sets of the same size, a function \(f: S \rightarrow T\) is one-to-one if and only if it is onto.

Step 1 - Understanding the problem

Given two finite sets, \(S\) and \(T\), of the same size, it is required to show that a function \(f: S \rightarrow T\) is one-to-one (injective) if and only if it is onto (surjective).

Step 2 - Define injective and surjective

A function \(f\) is one-to-one (injective) if \(f(a) = f(b)\) implies \(a = b\). A function \(f\) is onto (surjective) if for every \(t \in T\), there exists an \(s \in S\) such that \(f(s) = t\).

Step 3 - Assume \(f\) is injective

Assume \(f\) is injective. Since \(S\) and \(T\) have the same size, every element in \(S\) maps to a unique element in \(T\). Therefore, no two distinct elements in \(S\) map to the same element in \(T\).

Step 4 - Prove \(f\) is onto

Because \(S\) and \(T\) have the same number of elements and \(f\) is injective, every element of \(T\) has to be mapped to by some element of \(S\). Therefore, \(f\) is surjective.

Step 5 - Assume \(f\) is surjective

Now, assume \(f\) is surjective. Since \(f\) maps every element in \(S\) to an element in \(T\), and \(S\) and \(T\) are of the same size, each element of \(T\) must be hit by exactly one element of \(S\).

Step 6 - Prove \(f\) is injective

Because every element of \(T\) is hit by exactly one element of \(S\), \(f\) must be injective because no two different elements in \(S\) can map to the same element in \(T\).

Step 7 - Conclude the proof

Since we have shown that \(f\) being injective implies it is surjective, and \(f\) being surjective implies it is injective, the function \(f\) is one-to-one if and only if it is onto.

Key Concepts

Injective Function

An injective function, also known as a one-to-one function, is a type of function where each element in the domain maps to a distinct and unique element in the codomain. This means that no two different elements in the domain can map to the same element in the codomain.
For example, consider the function \( f: \{1, 2, 3\} \rightarrow \{a, b, c\} \) defined by \( f(1) = a \), \( f(2) = b \), and \( f(3) = c \). This function is injective because each element from the set \( \{1, 2, 3\} \) maps to a unique and different element from the set \( \{a, b, c\} \).

In mathematical terms, a function \( f: A \rightarrow B \) is injective if \( f(a_1) = f(a_2) \) implies \( a_1 = a_2 \) for all \( a_1, a_2 \) in the domain \( A \). Injectivity ensures that there are no duplicates in the mapping process.

Surjective Function

A surjective function, or an onto function, is a function where every element in the codomain is mapped to by at least one element in the domain. This means that for every element in the codomain, there is some element in the domain that maps to it.
For instance, if we have a function \( g: \{1, 2, 3\} \rightarrow \{a, b\} \) defined by \( g(1) = a \), \( g(2) = b \), and \( g(3) = a \), this function is surjective because every element in the codomain \( \{a, b\} \) is mapped to by at least one element in the domain \( \{1, 2, 3\} \).

In formal terms, a function \( g: A \rightarrow B \) is surjective if for every \( b \) in the codomain \( B \), there exists some \( a \) in the domain \( A \) such that \( g(a) = b \). Surjectivity guarantees that the codomain is completely covered by the function.

Bijection

A bijection, or a bijective function, is a function that is both injective and surjective. This means that every element in the domain maps to a unique element in the codomain (injective), and every element in the codomain is mapped to by some element in the domain (surjective).
For example, the function \( h: \{1, 2, 3\} \rightarrow \{a, b, c\} \) defined by \( h(1) = a \), \( h(2) = b \), and \( h(3) = c \) is bijective. Every element in the domain \( \{1, 2, 3\} \) maps to a unique element in the codomain \( \{a, b, c\} \) and every element in the codomain is covered.

In mathematical language, a function \( h: A \rightarrow B \) is bijective if it is both injective and surjective. This means that for each \( b \) in \( B \), there is exactly one \( a \) in \( A \) such that \( h(a) = b \). Bijections are important because they establish a one-to-one correspondence between the domain and codomain, indicating that the two sets have the same cardinality.