Discrete Math · Undergraduate
One-to-One, Onto and Bijective Functions
Quick answer
A function from A to B assigns each element of A exactly one element of B. It is one-to-one when different inputs always give different outputs, onto when every element of B is an output, and a bijection when it is both. A bijection pairs the two sets off perfectly, so finite sets with a bijection between them have the same size, and only bijections have inverse functions. Counting rules give the number of functions, one-to-one functions and bijections between finite sets.
What you'll learn
- Decide whether a function is one-to-one, onto or a bijection
- Prove or disprove each property for a formula
- Count functions, one-to-one functions and bijections between finite sets
- Explain why exactly the bijections have inverses
Three properties
A function assigns every element of exactly one element of . The set is the domain and the target. Two questions classify it.
- One-to-one: do different inputs always give different outputs? If forces , no two inputs share an output.
- Onto: is every element of hit? If every equals for some , the outputs cover . Onto functions are also called surjective.
A function that is both is a bijection: it pairs the elements of and off exactly, one to one, with none left over.
Why only bijections have inverses
An inverse must send each output back to the input it came from. If two inputs share an output, would not know which one to choose, so must be one-to-one. If some element of is never an output, has nothing to send it to, so must be onto. One-to-one makes the inverse well defined; onto makes it defined everywhere. That is the set-level reason behind the horizontal line test for inverse functions.
It also explains counting by pairing. Two finite sets have the same size exactly when some bijection matches them up.
Worked examples
Common mistakes
Practice problems
-
Is , from to , a bijection? Find its inverse.
Answer
Yes;
Full solution
gives , and solves for every .
-
Is , from to , one-to-one? Onto?
Answer
One-to-one, but not onto
Full solution
is increasing, so it never repeats a value, but it never reaches or any negative number. Onto it is a bijection, with inverse .
-
How many functions are there from a -element set to a -element set?
Answer
Full solution
.
-
How many bijections are there from a -element set to itself?
Answer
Full solution
: each is a rearrangement.
-
How many one-to-one functions are there from a -element set to a -element set?
Answer
Full solution
.
-
Can there be a one-to-one function from a -element set to a -element set?
Answer
No
Full solution
By the pigeonhole principle, two of the inputs must share one of the outputs.
-
Is , from the integers to the integers, a bijection? From the natural numbers to themselves?
Answer
On the integers, yes. On the natural numbers, one-to-one but not onto.
Full solution
On the natural numbers, nothing maps to . On the integers, maps to any .
-
A student says has an inverse because undoes it. What is wrong?
Answer
On all of , is not one-to-one, so only undoes it for .
Full solution
, not . Restricting to makes it a bijection whose inverse is .
Frequently asked questions
What is a one-to-one function?
A function where different inputs always give different outputs: if f(a) = f(b), then a = b.
What is an onto function?
A function whose outputs cover the whole target set: every element of B is f(a) for some a in A. It is also called surjective.
What is a bijection?
A function that is both one-to-one and onto. It pairs every element of A with exactly one element of B and leaves nothing out.
Which functions have inverses?
Exactly the bijections. One-to-one makes the inverse well defined, and onto makes it defined on all of B.
How many functions are there from a 3-element set to a 4-element set?
4³ = 64 in all, of which 4 × 3 × 2 = 24 are one-to-one. None are onto, since 3 inputs cannot cover 4 outputs.