discrete math · functions

Injective, surjective and bijective functions, explained simply

what is the difference?

A function is injective when no two inputs share an output. It is surjective when every possible output gets used. It is bijective when both are true, so inputs and outputs pair up perfectly, one to one.

updated 18 Nov 202613 min read

Try it: build a function

Arrow diagram from A = {1, 2, 3} to B = {a, b, c}: 1 goes to a, 2 goes to b, 3 goes to b.AB123abc
where each input goes
  • ✓ Function Every input has exactly one arrow.
  • ✗ Injective b gets more than one arrow.
  • ✗ Surjective c gets no arrow.
  • ✗ Bijective Needs injective and surjective together.

Tip: tap a dot in A, then a dot in B, to move its arrow. Red outputs are shared, dashed outputs are empty.

The idea in one picture

Each picture below shows a function as arrows. The left side holds the inputs. The right side holds the outputs you are allowed to use. Every input sends out exactly one arrow.

Arrow diagrams comparing injective, surjective, bijective and neither: injective has no shared outputs, surjective leaves no output empty, bijective pairs every input with exactly one output
Injective: no output is shared. Surjective: no output is left empty. Bijective: both at once.

So the whole topic comes down to two questions about the outputs. Does any output get two or more arrows? Does any output get no arrow?

First: what is a function?

Think of a class of students and the seats in a room. A seating plan tells each student where to sit. Every student needs a seat. No student can sit in two seats at once.

That seating plan is a function. A function is a rule that takes each input and gives back exactly one output.

Function

Every input gets exactly one output. Not zero. Not two.

f : A → B

read it as "f is a function from A to B." A is the set of inputs, called the domain. B is the set of outputs you are allowed to use, called the codomain.

f(a) = b

read it as "f sends a to b", or "the output of f at a is b".

Two things break the rule. An input with no arrow is not allowed. An input with two arrows is not allowed either. If you see one of these, it is not a function, so the three words on this page do not apply yet.

Arrow diagram from A = {1, 2, 3} to B = {a, b}: 1 goes to a, 2 has no arrow, 3 goes to b.AB123ab
Not a function: 2 has no arrow.
Arrow diagram from A = {1, 2} to B = {a, b, c}: 1 goes to a and b, 2 goes to c.AB12abc
Not a function: 1 has two arrows.

The outputs that actually get used are called the range (some books say image). The range can be smaller than the codomain B. This small detail decides whether a function is surjective, so keep it in mind.

Injective (one-to-one): no sharing

everyday example

Every student gets their own locker. No two students share a locker. Some lockers can stay empty. That is injective.

Injective function arrow diagram: each output receives at most one arrow, next to a counterexample where two inputs share the same output
Left: injective, every output gets at most one arrow. Right: not injective, two inputs land on b.

Injective also called one-to-one

No two inputs land on the same output.

f(a₁) = f(a₂) ⇒ a₁ = a₂

read it as "If two inputs give the same output, then they were the same input all along." The little 1 and 2 under the a just mean "first input" and "second input".

How to check it

  1. Look at the outputs on the right, one at a time.
  2. Count the arrows that land on each one.
  3. If any output has two or more arrows, the function is not injective. If every output has zero or one, it is injective.

Surjective (onto): nobody left out

everyday example

A teacher splits a class into three teams. Every team must get at least one player. Two students can be on the same team. But no team can be empty. That is surjective.

Surjective function arrow diagram: every output receives at least one arrow, next to a counterexample where one output receives no arrow
Left: surjective, every output gets at least one arrow. Right: not surjective, c gets no arrow.

Surjective also called onto

Every output in B gets at least one arrow.

for every b ∈ B, there is an a ∈ A with f(a) = b

read it as "Pick any output b. You can always find an input a that lands on it." The sign ∈ means "is in", so b ∈ B means "b is in B".

How to check it

  1. Look at the outputs on the right, one at a time.
  2. Check that each one has at least one arrow.
  3. If even one output has no arrow, the function is not surjective.

Where does the name come from? "Sur" is French for "on". The arrows land on every output, which is why surjective is also called onto.

Bijective: perfect pairs

everyday example

Dance partners. Every person in group A dances with exactly one person in group B. Nobody shares a partner, and nobody in either group is left standing alone. That is bijective.

Bijective function arrow diagram: every input paired with exactly one output and every output receiving exactly one arrow, with the reversed arrows showing the inverse function
Left: a bijection, every output gets exactly one arrow. Right: flip the arrows and you get the inverse function.

Bijective also called one-to-one correspondence

Injective and surjective at the same time. Every output gets exactly one arrow.

f is injective and f is surjective

read it as "No sharing, and nobody left out."

A bijection can be undone. Turn every arrow around and you get a new function that goes back from B to A. It is called the inverse, written f⁻¹ and read "f inverse". Only bijections have one.

For finite sets there is one more clue. A bijection between A and B can only exist when A and B have the same number of elements.

Side by side

Injective, surjective and bijective compared
CriteriaInjectiveSurjectiveBijective
Other nameone-to-oneontoone-to-one correspondence
Arrows landing on each output0 or 11 or moreexactly 1
Two inputs sharing an outputNot allowedAllowedNot allowed
An output left emptyAllowedNot allowedNot allowed
Sizes, for finite setsA has no more than BA has at least as many as BA and B are the same size
Has an inverse function?Only if also surjectiveOnly if also injectiveYes

A counting shortcut for finite sets

When A and B are small, finite sets, you can sometimes answer without looking at a single arrow. Just count.

This shortcut only works for finite sets. For infinite sets, such as all whole numbers, you have to check the rule itself.

How to check a graph: the horizontal line test

Many functions take real numbers in and give real numbers out, like f(x) = x². You can test these by looking at their graph. Imagine sliding a flat, horizontal line up and down the picture.

Horizontal line test on three graphs: y equals x squared is hit twice by a horizontal line so it is not injective, y equals e to the x is hit at most once but misses negative values so it is injective but not surjective, y equals x cubed is hit exactly once by every line so it is bijective
Every horizontal line is a possible output. Count how many times it hits the graph.

In the picture, y = x² fails the first test: the line at height 4 hits it at x = 2 and at x = −2. The graph of y = eˣ passes the first test, but lines below zero never touch it. The graph of y = x³ is hit exactly once by every line.

Worked examples: same rule, different answer

The answer depends on the rule and on the sets A and B. These three examples show why you must always say what A and B are.

example 1 · f : ℝ → ℝ, f(x) = 2x + 3

ℝ means "all real numbers". So any number can go in, and any number is allowed out.

Injective? Suppose two inputs a and b give the same output: 2a + 3 = 2b + 3. Take 3 from both sides: 2a = 2b. Divide by 2: a = b. So the two inputs were the same. Yes.

Surjective? Pick any output y. We need an input x with 2x + 3 = y. Solve it: x = (y − 3) / 2. That is always a real number, so it works for every y. Yes.

Answer: bijective.

example 2 · f : ℤ → ℤ, f(n) = n²

ℤ means "all whole numbers", including negatives: …, −2, −1, 0, 1, 2, ….

Injective? No. f(2) = 4 and f(−2) = 4. Two inputs share the output 4.

Surjective? No. No whole number squared gives 2, and no square is ever negative. So outputs like 2 and −1 get no arrow.

Answer: neither.

example 3 · g : [0, ∞) → [0, ∞), g(x) = x²

[0, ∞) means "zero and every positive number". Negative numbers are now not allowed in or out.

Injective? Yes. Without negative inputs, 2 and −2 can no longer collide. Two different non-negative numbers always have different squares.

Surjective? Yes. Any output y that is zero or more comes from the input x = √y.

Answer: bijective. The rule x² did not change. Only the sets did.

Common mistakes

Memory tricks

Check yourself

Answer each one before you open it. Guessing first and then checking helps you remember more than just reading. This is called active recall.

  1. A = {1, 2, 3} and B = {a, b}. The arrows are 1 → a, 2 → b and 3 → a. What kind of function is this?

    Arrow diagram from A = {1, 2, 3} to B = {a, b}: 1 goes to a, 2 goes to b, 3 goes to a.AB123ab

    Show answer

    Surjective. Output a gets two arrows, so it is not injective. Both a and b get at least one arrow, so it is surjective.

  2. A = {1, 2} and B = {a, b, c}. The arrows are 1 → a and 2 → c. What kind of function is this?

    Arrow diagram from A = {1, 2} to B = {a, b, c}: 1 goes to a, 2 goes to c.AB12abc

    Show answer

    Injective. No output gets two arrows, so it is injective. Output b gets no arrow, so it is not surjective.

  3. f : ℝ → ℝ with f(x) = x³. What kind of function is this?

    Show answer

    Bijective. Every horizontal line hits the graph of y = x³ exactly once. Each output y comes from exactly one input, the cube root of y.

  4. Can a function from a set with 4 elements to a set with 6 elements be surjective?

    Show answer

    No. Four inputs send out only four arrows. They can reach at most four outputs, so at least two outputs stay empty.

Study it with active recall

Reading this page once will not make it stick. Testing yourself will. Turn over each card in your head first, then click it to check.

  • What does injective mean?

    No two inputs share an output. Each output gets at most one arrow. Also called one-to-one.

  • What does surjective mean?

    Every output in the codomain gets at least one arrow. Also called onto.

  • What does bijective mean?

    Injective and surjective together. Every output gets exactly one arrow.

  • What is the difference between codomain and range?

    The codomain is the set of allowed outputs. The range is the outputs that actually get used.

  • How do you prove a function is injective?

    Assume f(a) = f(b) and show that a = b.

  • How do you prove a function is surjective?

    Pick any output y and find an input x with f(x) = y.

  • Which functions have an inverse?

    Only bijections.

  • f : ℤ → ℤ, f(n) = n². Injective or surjective?

    Neither. f(2) = f(−2) = 4, and no whole number squares to 2.

Then try blurting: close this page, take a blank sheet, and write the three definitions from memory. Draw one arrow diagram for each and add one everyday example. Check your sheet against the page and fix what you missed.

Come back to the cards tomorrow, then again in a few days. Spacing your reviews like this is called spaced repetition, and it is how a definition you learn this week is still there for the exam.

Frequently asked questions

Is one-to-one the same as injective?

Yes. One-to-one and injective mean the same thing: no two inputs share an output. Be careful with "one-to-one correspondence", which means bijective.

What is the difference between codomain and range?

The codomain is the set of outputs the function is allowed to use. You choose it when you define the function. The range is the set of outputs that actually get used. A function is surjective exactly when the range equals the codomain.

Can a function be neither injective nor surjective?

Yes. f(n) = n² from the whole numbers to the whole numbers is neither. Two inputs share an output (2 and −2 both give 4), and some outputs, like 2, are never reached.

Can a function be both injective and surjective?

Yes. That is exactly what bijective means. For example, f(x) = 2x + 3 from the real numbers to the real numbers is both.

Why do bijections matter?

A bijection pairs two sets perfectly, so it proves they have the same size. Mathematicians use this to count things and to compare the sizes of infinite sets. Bijections are also the only functions that can be undone with an inverse.

Sources

Practice it, then keep a record

Stuon has a timer, a blurting space and flashcards, and it logs the time you spend on each.

Track this in StuonAdd to Chrome, freeor use the free version without an account