Injection surjection bijection examples clarify how functions map elements between sets and how those mappings behave. Understanding these core ideas helps you analyze relations in data, logic, and programming with precision.
These function types define whether every input is used, whether outputs are unique, and whether a perfect pairing exists. The table below summarizes the essential conditions for injection, surjection, and bijection.
| Function Type | Condition on Mapping | Visual Intuition | Reversible |
|---|---|---|---|
| Injection (Injective) | Distinct inputs map to distinct outputs | No horizontal line crosses the graph twice | Left-invertible on its image |
| Surjection (Surjective) | Every element in the codomain is hit | Range equals codomain | Right-invertible |
| Bijection | Both injection and surjection | Perfect one-to-one pairing | Fully invertible |
| Neither Injection Nor Surjection | Collisions and uncovered elements | Graph overlaps and gaps | No global inverse |
Defining Injection With Concrete Examples
How Injection Preserves Uniqueness
An injective function ensures that no two different inputs share the same output. In the example f: {1,2,3} → {a,b,c,d} with f(1)=a, f(2)=b, f(3)=c, each input has a distinct image, so the mapping is injection surjection bijection injective but not surjective.
Real-world scenarios, such as unique employee IDs linked to distinct people, demonstrate injection naturally. Even when the codomain is larger, the key property is that distinctness in the domain is preserved in the range.
Understanding Surjection Fully Covered
Surjection Requires Every Codomain Element to Be Hit
A surjective function covers the entire codomain, meaning for every y in the target set there is at least one x such that f(x)=y. Consider g: {1,2,3,4} → {a,b} with g(1)=a, g(2)=b, g(3)=a, g(4)=b; here the mapping is not injective due to collisions, but it is surjective because both a and b are outputs.
When the domain and codomain are finite and have the same size, surjection implies injection and vice versa. In larger or infinite sets, however, a function can cover all outputs without being one-to-one.
Bijection As a Perfect One-to-One Correspondence
Combining Injection and Surjection
A bijection is both injective and surjective, establishing a perfect pairing between domain and codomain. The function h: {x,y,z} → {1,2,3} with h(x)=1, h(y)=2, h(z)=3 is bijective, because it is injection surjection bijection bijective and fully invertible.
Bijections enable inverse functions, isomorphisms in algebra, and reversible transformations in computer science. Identifying whether a mapping is bijective tells you whether information is preserved exactly without loss or ambiguity.
Comparing Function Types in a Structured Table
Side-by-Side View of Mapping Properties
The following comparison table aligns injection surjection bijection examples with their conditions, visuals, and invertibility, so you can quickly choose the right lens for your problem.
| Type | Formal Condition | Injection Surjection Bijection Example | Invertible |
|---|---|---|---|
| Injection Only | If f(x1)=f(x2) then x1=x2 | f: {a,b} → {1,2,3}, a→1, b→2 | Left inverse on image |
| Surjection Only | Range equals codomain | g: {p,q,r} → {x,y}, p→x, q→y, r→x | Right inverse exists |
| Bijection | Injective and surjective | h: {1,2,3} → {A,B,C}, 1→A, 2→B, 3→C | Fully invertible |
| Neither | Collisions and uncovered elements | k: {m,n} → {P,Q}, m→P, n→P | No inverse |
Practical Applications Across Domains
In database design, injection surjection bijection examples guide primary key choices and referential integrity. A primary key constraint enforces injection on identifiers, while careful schema design can achieve surjection for mandatory relationships.
Cryptography relies on bijective transformations for encryption and decryption, ensuring that every ciphertext maps back to a single plaintext. Hash functions often sacrifice surjection and injection to achieve efficient fixed-size outputs, accepting collisions intentionally for performance.
Key Takeaways on Functions and Their Mapping Properties
- Injection guarantees unique outputs for unique inputs
- Surjection guarantees full use of the codomain
- Bijection combines both and enables true inverses
- Real systems often trade injection for surjection or vice versa
- Use structured comparison to select function types for algorithms and data models
FAQ
Reader questions
How can I test whether a small finite function is injective using its table of values?
Check that no two rows have the same output value; if all outputs are distinct, the function is injective.
Is it possible for a function to be both injective and surjective if the domain and codomain have different sizes?
No, for finite sets a bijection requires equal sizes; if sizes differ, the function can be either injective or surjective but not both.
When a function is surjective but not injective, what does that imply about its inverse? A right inverse exists, but it is not unique because multiple domain elements can map to the same codomain element. How do these function types relate to real-world concepts like permissions and coverage in systems?
Injection models one-to-one access rights, surjection models full coverage of resources, and bijection models perfectly paired permissions and operations.