Surjection

A surjective function (also called an onto function) is a function where every element in the codomain is mapped to by at least one element from the domain. No element in the target set is left out.

Key Characteristics

Many-to-One Allowed

Multiple domain elements can point to the same codomain element.

Composition Rule

The composite of two surjective functions is always surjective.

Cardinality Constraint

If \(f: A → B\) is surjective, the size (cardinality) of the domain \(A\) must be greater than or equal to the size of the codomain \(B\) (\(|A| ≥ |B|\)).

Right Invertible

Every surjection has a right inverse \(g: B → A\) such that \(f(g(b)) = b\).

Source: GeeksforGeeks

How to Prove

1. Let \(y\) be arbitrary.

   Start by picking an arbitrary element \(x ∈ Y\) from the codomain.

2. Set up the equation.

   Write out \(f(x) = y\).

3. Solve for \(x\).

   Use algebra to solve for \(x\) in terms of \(y\).

4. Check the domain.

   Confirm that the resulting \(x\)-value belongs to the domain \(X\).

5. Verify the mapping.

   Substitute your expression for \(x\) back into \(f(x)\) to show that \(f(x) = y\).

Example

Prove that \(f : ℝ → ℝ\) defined by \(f(x) = 3x - 5\) is surjective.

1. Let \(y\) be an arbitrary real number in the codomain (\(\mathbb{Y} = \mathbb{R}\)).

2. Set \(f(x) = y\), which gives \(3x - 5 = y\).

3. Solve for \(x\).

\[ \begin{align}\begin{aligned}3x = y + 5\\x = (y + 5) / 3\end{aligned}\end{align} \]

4. Since \(y \in \mathbb{R}\), \(\frac{y + 5}{3}\) is also a real number, meaning \(x\) is in the domain \(\mathbb{R}\).

5. Verify.

\[ \begin{align}\begin{aligned}f\left(\frac{y + 5}{3}\right) = 3\left(\frac{y + 5}{3}\right) - 5\\= (y + 5) - 5\\= y\end{aligned}\end{align} \]

Since for every \(y \in \mathbb{R}\) there exists an \(x = \frac{y + 5}{3}\) such that \(f(x) = y\), the function \(f\) is surjective.