Bijective Function: Definition, Count Formula and Key Properties

A function can be one-to-one, onto, both, or neither. On an arrow diagram, the difference can feel harder than the rule itself. A bijection uses every codomain value exactly once; between two labelled n-element sets, exactly n! bijections exist. Bijections connect injectivity, surjectivity, inverse functions and finite counting throughout GATE CS preparation.

What Is a Bijective Function?

A function f: A -> B is bijective exactly when it is both injective and surjective. The most useful plain-English test is this: every element of the codomain B must have exactly one preimage in the domain A.

Keep the three sets clear. The domain is the set of permitted inputs, the codomain is the declared target set, and the range is the set of outputs actually produced. If you need to revise these foundations, start with Set Theory and Relations Explained for GATE.

Injectivity means

f(x_1) = f(x_2) implies x_1 = x_2.

Surjectivity means that for every y in B, there is some x in A such that f(x) = y.

For a quick algebraic example, take f: R -> R, where f(x) = 2x + 1. If f(x_1) = f(x_2), then 2x_1 + 1 = 2x_2 + 1, so x_1 = x_2. For any real y, choose x = (y - 1)/2. Then f(x) = 2((y - 1)/2) + 1 = y. The function is both injective and surjective, so it is bijective.

A Reliable Test for Bijection

For a finite arrow map, work in this order:

1. Confirm that every domain element has exactly one output.

2. Look for repeated outputs. A collision breaks injectivity.

3. Check whether every codomain element is hit. An unused value breaks surjectivity.

Let A = {1, 2, 3} and B = {a, b, c}. In the map g(1) = a, g(2) = a, g(3) = c, the two inputs colliding at a make g non-injective. The unused codomain value b also makes it non-surjective.

Now take h(1) = b, h(2) = c, h(3) = a. Its three outputs are distinct, and its range is {a, b, c} = B. Therefore, h is bijective.

The declared sets always matter. The function p: Z -> Z, p(n) = 2n, is injective, but it is not surjective because no odd integer has a preimage. Never call a formula bijective without naming its domain and codomain.

Worked Example: Verify the Map and Construct Its Inverse

Let A = {1, 2, 3, 4} and B = {2, 4, 6, 8}. Define f as follows:

The range is {6, 2, 8, 4} = B. All four images are distinct, so injectivity holds. Every element of B occurs, so surjectivity holds. Hence, f is bijective.

Reverse each ordered pair to construct the inverse:

• f^{-1}(2) = 2

• f^{-1}(4) = 4

• f^{-1}(6) = 1

• f^{-1}(8) = 3

Check both directions using actual values:

• f^{-1}(f(3)) = f^{-1}(8) = 3

• f(f^{-1}(6)) = f(1) = 6

Here f^{-1} means the inverse function. It does not mean the reciprocal 1/f.

How Many Bijective Functions Are Possible?

If |A| = |B| = n, the number of bijections from A to B is n!. The first domain element has n choices, the second has n - 1, and the choices continue down to 1. Thus the product is n x (n - 1) x ... x 1 = n!. If the two finite sets have unequal sizes, the number of bijections is 0.

For A = {1, 2, 3} and B = {p, q, r}, the count is

3 x 2 x 1 = 6.

Writing each function as (f(1), f(2), f(3)), the six possibilities are:

(p, q, r), (p, r, q), (q, p, r), (q, r, p), (r, p, q), (r, q, p).

Restrictions reduce the free choices. For A = B = {1, 2, 3, 4}, fixing f(1) = 3 leaves three outputs for three inputs, so the count is 3! = 3 x 2 x 1 = 6. Fixing both f(1) = 3 and f(2) = 1 leaves 2! = 2 x 1 = 2. In general, k compatible prescribed pairs leave (n - k)! arrangements.

Properties of Bijective Functions

A function has an inverse function exactly when it is bijective. For f: A -> B, the two identity laws are

• f^{-1} o f = id_A

• f o f^{-1} = id_B

The identities f^{-1}(f(3)) = 3 and f(f^{-1}(6)) = 6 illustrate these laws.

The identity function is bijective. The inverse of a bijection is bijective, and a composition of bijections is also bijective. For example, let g(x) = x + 1 and h(x) = 2x on the real numbers. Then (h o g)(x) = 2x + 2, and

(h o g)^{-1}(y) = y/2 - 1 = (g^{-1} o h^{-1})(y).

There is also a useful finite-set shortcut. Between finite sets of equal size, injective implies surjective, and surjective implies injective. Do not extend this shortcut to arbitrary infinite sets. The earlier map p: Z -> Z, p(n) = 2n, is injective but not surjective.

Common Traps and How to Correct Them

Confusing n^n with n!. Between two labelled three-element sets, there are 3^3 = 27 total functions because each input may choose any of three outputs. Only 3! = 6 are bijections because outputs cannot repeat or be omitted.

Ignoring the declared sets. The function s: R -> [0, infinity), s(x) = x^2, is onto but not one-to-one because s(2) = s(-2) = 4. In contrast, t: [0, infinity) -> [0, infinity), t(x) = x^2, is bijective and has inverse t^{-1}(y) = sqrt(y).

Assuming bijective means identity. The four-element worked map permutes values and is still bijective. Its inverse comes from reversing ordered pairs, not from calculating 1/f(x).

How Exams Test Bijective Functions

Representative questions ask you to classify an arrow map, fill a missing image so a finite map becomes bijective, count bijections with fixed pairs, or determine when an algebraic family is bijective.

For f: R -> R, f(x) = ax + b, the condition is a != 0. If a = 0, every input has the same output. If a != 0, equal outputs force equal inputs, and for any real y, choosing x = (y - b)/a gives f(x) = y. The value of b may be any real number.

For a 30-second count check, two five-element sets have

5! = 5 x 4 x 3 x 2 x 1 = 120

bijections. With one compatible prescribed pair, the remaining count is

4! = 4 x 3 x 2 x 1 = 24.

Continue with Set Theory and Relations MCQs, a set of 12 solved questions, then broaden the practice across discrete mathematics. Confirm the syllabus and paper pattern on the official GATE 2027 portal for your exam cycle.

Short Version and Next Step

• Bijective means every codomain element has exactly one preimage.

• Between finite sets of equal size n, there are n! bijections.

• Between finite sets of unequal size, there are no bijections.

• Every bijection has a bijective inverse.

Redraw the four-element worked map from memory. Then solve one classification question, one inverse question, and one counting question.

GATE Guidance by Sanchit Sir is a route into broader structured GATE preparation. Engineering Mathematics for GATE Exam supports the wider counting, permutation, and probability foundation, without implying a dedicated bijective-functions lesson.

Draw the arrows first, check for collisions and omissions, then count the remaining choices.