Injection#
An injective function is a one-to-one function where every distinct input in the domain maps to a unique output in the codomain. No two different elements share the same image, meaning no target value is hit more than once.
Key Characteristics
- At Most One Preimage
Every element in the codomain has at most one corresponding element (preimage) mapped to it. Some codomain elements may have zero preimages.
- No Collisions
Two distinct inputs are never allowed to result in a shared output value.
- Cardinality Rule
If a function maps from a finite set \(A\) to finite set \(B\) injectively, the size of the domain must be less than or equal to the size of the codomain (\(|A| ≤ |B|\)).
- Left-Invertible
An injection with a non-empty domain has a left inverse, meaning you can “undo” the mapping for elements in the range.
Source: GeeksforGeeks#
How to Prove#
To prove that a function \(f: A → B\) is an injection (one-to-one), show that equal outputs imply equal inputs. Assume \(f(x_1) = f(x_2)\) for arbitrary elements \(x_1, x_2 \in A\), and use algebra to prove \(x_1 = x_2\).
Let \(x_1, x_2 \in A\) and suppose \(f(x_1) = f(x_2)\).
Use the formula for \(f(x)\) to expand both sides.
Use algebra to cancel terms and solve until you reach \(x_1 = x_2\).
Example
Prove that \(f: \mathbb{R} → \mathbb{R}\) defined by \(f(x) = 3x - 2\) is injective.
Let \(x_1, x_2 \in \mathbb{R}\) and assume \(f(x_1) = f(x_2)\).
By the definition of \(f\), this means:
Add \(2\) to both sides:
Divide by \(3\):
Thus, \(f\) is injective.