A mapping can be a valid function without being one-to-one or onto. Most mistakes begin by mixing up domain, codomain and range. On small finite sets you can settle any of these questions by listing the ordered pairs and counting arrows, which is faster and safer than reaching for a remembered rule. If the notation feels unfamiliar, revise Set Theory and Relations Explained first.
What a function actually requires
A function from A to B assigns every element of A to exactly one element of B. A is the domain, B is the codomain, and the range is the subset of B that receives an arrow.
Let
A = {1, 2, 3, 4}
B = {a, b, c, d, e}
f = {(1, b), (2, d), (3, b), (4, e)}
The range is {b, d, e}. This is valid because every input appears exactly once. Inputs 1 and 3 may share b. That changes the function's type, not its validity.
Now consider R = {(1, a), (1, b), (2, c), (3, d), (4, e)}. This relation is not a function from A to B because input 1 has two outputs. A relation that left 4 without any output would also fail the definition.
Injective, surjective and bijective functions
After the basic function test, ask whether outputs repeat and whether the whole codomain is covered.
Map | Mapping | Classification | Reason |
|---|---|---|---|
f: {1, 2, 3, 4} to {a, b, c, d, e} | 1 to b, 2 to d, 3 to b, 4 to e | Neither | b is shared; a and c are not reached |
h: {1, 2, 3} to {p, q} | 1 to p, 2 to q, 3 to q | Surjective, not injective | Both outputs are reached; q is shared |
k: {1, 2} to {p, q, r} | 1 to p, 2 to r | Injective, not surjective | Outputs are distinct; q is not reached |
g: {1, 2, 3} to {p, q, r} | 1 to q, 2 to r, 3 to p | Bijective | Outputs are distinct and cover the codomain |
For an injective function, equal outputs must come from equal inputs. For a surjective function, every codomain element has a preimage. A bijection passes both tests.
For finite sets, |A| > |B| makes an injection impossible, while |A| < |B| makes a surjection impossible. A bijection requires equal cardinalities, but equal sizes do not prove that a particular map is bijective. Both tests are quantified statements, one running over every pair of inputs and the other over every codomain element, so if that notation is where you slip, work through Propositional and Predicate Logic: Truth Tables to Proofs.
Counting functions without memorising isolated formulas
Take X = {x1, x2, x3} and Y = {a, b, c, d}. Each input has four independent choices, so the unrestricted count is:
4 × 4 × 4 = 4^3 = 64.
For an injection, outputs cannot be reused. The successive choices are four, three and two:
4 × 3 × 2 = 24.
For an onto function from U = {1, 2, 3} to V = {0, 1}, begin with 2^3 = 8 functions. Two are constant and not onto, one sends every input to 0 and one sends every input to 1. Therefore:
8 - 2 = 6 onto functions.
One valid example is 1 to 0, 2 to 0 and 3 to 1. Both codomain values have a preimage.
In general, an n-element domain and m-element codomain give m^n functions. If n ≤ m, the injective count is m!/(m-n)!. Two m-element sets have m! bijections. General onto counts use inclusion-exclusion, as the two constant functions were excluded above.
Composition: order and compatibility matter
Define f: {1, 2, 3} to {2, 4, 6} by f(x) = 2x, and g: {2, 4, 6} to {1, 3, 5} by g(y) = y - 1. For g composed with f, apply f first:
1 goes through f to 2, then through g to 1.
2 goes through f to 4, then through g to 3.
3 goes through f to 6, then through g to 5.
Thus g composed with f = {(1, 1), (2, 3), (3, 5)}, and (g composed with f)(2) = g(4) = 3.
The reverse is not defined on all of {2, 4, 6}: g(6) = 5, but 5 is outside f's domain {1, 2, 3}. Composition is not generally commutative. Write the right-hand function first, track its outputs, then apply the left-hand function.
Inverse functions and why bijection is the gatekeeper
Let p: {1, 2, 3} to {4, 7, 10} be p(x) = 3x + 1. Its outputs are distinct and cover the codomain, so p is bijective. Solving y = 3x + 1 for x gives:
p inverse(y) = (y - 1)/3, for y in {4, 7, 10}.
Check both directions: p inverse(10) = (10 - 1)/3 = 3, p(p inverse(7)) = p(2) = 7, and p inverse(p(1)) = p inverse(4) = 1.
The opening f has no inverse from B to A. Output b would need to return to both 1 and 3, while a and c were never reached. Either failure blocks a two-sided inverse. Also, p inverse(x) is not the reciprocal 1/p(x).
How GATE-style and interview questions test functions
Typical tasks ask you to classify a map, count constrained functions, find a composition, test for an inverse, or disprove a statement with a counterexample. An interview asks for the same things out loud and then asks why, so the one-line reasons in the table above matter as much as the labels.
On A = {1, 2, 3}, let t = {(1, 2), (2, 3), (3, 1)}. Apply t twice:
1 goes to 2, then 2 goes to 3, so t squared sends 1 to 3.
2 goes to 3, then 3 goes to 1, so t squared sends 2 to 1.
3 goes to 1, then 1 goes to 2, so t squared sends 3 to 2.
Thus t squared = {(1, 3), (2, 1), (3, 2)}. One more application gives t cubed = {(1, 1), (2, 2), (3, 3)}, the identity. Since t is bijective and t composed with t squared is the identity, t inverse = t squared.
For structured, subject-wise GATE preparation and performance-guided practice, use the GATE Guidance course.
Traps that cost otherwise easy marks
Codomain versus range: In the opening f, B = {a, b, c, d, e} is the codomain, but {b, d, e} is the range. Missing a and c is why f is not onto.
Valid versus one-to-one: The equality f(1) = f(3) = b breaks injectivity, not the definition of a function.
Composition order: Compute (g composed with f)(2) as g(f(2)) = g(4) = 3. Reversing the order answers a different question.
Formula misuse: Check cardinalities first. There are zero injections from a four-element set to a three-element set, and zero surjections from a two-element set to a three-element set.
Inverse too early: Establish bijectivity before treating an inverse rule as a full function.
The short version and the next practice step
Keep these five lines in your revision notes:
Every domain element gets exactly one output.
An injection forbids shared outputs.
A surjection covers the entire codomain.
A bijection permits a two-sided inverse.
Composition is evaluated right to left after checking compatible sets.
Redraw f, classify h, k and g, and reproduce 64, 24 and 6 without notes. Then calculate t squared and t cubed again. Next, put the same tasks under a clock with the GATE Test Series.
The GATE CS preparation courses give you the broader route across subjects. Once these five lines are automatic, graph theory is the natural next Discrete Mathematics topic: graph isomorphism is defined as a bijection, so the vocabulary above carries straight over.
