Surjective Injective Bijective Functions—Contents (Click to skip to that section):
Injective Function (“One to One”)
An injective function, also known as a one-to-one function, is a function that maps distinct members of a domain to distinct members of a range. In other words, every unique input (e.g. on the x-axis) produces a unique output (e.g. on the y-axis); It never maps distinct members of the domain to the same point of the range.
It isn’t necessary that all possible points in the function (the “codomain“) are mapped. But those that are must map a distinct input to a distinct output.
Identifying Injective Functions
You can find out if a function is injective by graphing it. An injective function must be continually increasing, or continually decreasing. Look for areas where the function crosses a horizontal line in at least two places; If this happens, then the function changes direction (e.g. from increasing to decreasing), so it isn’t injective.
A few quick rules for identifying injective functions:
- If a function is defined by an odd power, it’s injective. The simple linear function f(x) = 2 x + 1 is injective in ℝ (the set of all real numbers), because every distinct x gives us a distinct answer f(x).
- If a function is defined by an even power, it’s not injective. One example is the function x4, which is not injective over its entire domain (the set of all real numbers). The function value at x = 1 is equal to the function value at x = 1. Note though, that if you restrict the domain to one side of the y-axis, then the function is injective. For example, if the domain is defined as non-negative reals, [0,+∞).
Notation and Formal Definition
Sometimes functions that are injective are designated by an arrow with a barbed tail going between the domain and the range, like this f: X ↣ Y.
Suppose f is a function over the domain X. For f to be injective means that for all a and b in X, if f(a) = f(b), a = b. If a and b are not equal, then f(a) ≠ f(b).
We can write this in math symbols by saying
which we read as “for all a, b in X, f(a) being equal to f(b) implies that a is equal to b.”
Properties of Injective Functions
If both f and g are injective functions, then the composition of both is injective. The image below shows how this works; if every member of the initial domain X is mapped to a distinct member of the first range Y, and every distinct member of Y is mapped to a distinct member of the Z each distinct member of the X is being mapped to a distinct member of the Z, shown in the following mapping diagram.
If a function f maps from a domain X to a range Y, Y has at least as many elements as did X.
Injective and Bijective Functions
An injective function may or may not have a one-to-one correspondence between all members of its range and domain. If it does, it is called a bijective function. Both images below represent injective functions, but only the image on the right is bijective. The image on the left has one member in set Y that isn’t being used (point C), so it isn’t injective.
A surjective function, also called a surjection or an onto function, is a function where every point in the range is mapped to from a point in the domain. In other words, the function F maps X onto Y (Kubrusly, 2001).
Surjection vs. Injection
Surjection can sometimes be better understood by comparing it to injection:
- An injective function sends different elements in a set to other different elements in the other set.
- With surjection, every element in Y is assigned to an element in X.
A surjective function may or may not be injective; Many combinations are possible, as the next image shows:.
- “A” is injective (one-to-one). Different elements in the first set are sent to different elements in the second set. A is not surjective because not every element in Y is included in the mapping.
- “B” is surjective, because every element in Y is assigned to an element in X. However, these assignments are not unique; one point in Y maps to two different points in X. Therefore, B is not injective.
- “C” is surjective and injective. It sends different elements in set X to different elements in set Y (injection) and every element in Y is assigned to an element in X (surjection).
- “D” is neither. One element in Y isn’t included, so it isn’t surjective. And one point in Y has been mapped to by two points in X, so it isn’t surjective.
If a function is both surjective and injective—both onto and one-to-one—it’s called a bijective function. A bijective function is a one-to-one correspondence, which shouldn’t be confused with one-to-one functions.
Using math symbols, we can say that a function f: A → B is surjective if the range of f is B. What that means is that if, for any and every b ∈ B, there is some a ∈ A such that f(a) = b, then the function is surjective.
Examples of Surjections
Any function can be made into a surjection by restricting the codomain to the range or image. A codomain is the space that solutions (output) of a function is restricted to, while the range consists of all the actual outputs of the function. When the range is the equal to the codomain, a function is surjective.
The function f(x) = 2x + 1 over the reals (f: ℝ -> ℝ ) is surjective because for any real number y you can always find an x that makes f(x) = y true; in fact, this x will always be (y-1)/2.
The function g(x) = x2, on the other hand, is not surjective defined over the reals (f: ℝ -> ℝ ). For some real numbers y—1, for instance—there is no real x such that x2 = y.
What is a Bijective Function?
A bijective function is one that is both surjective and injective (both one to one and onto). Every element of one set is paired with exactly one element of the second set, and every element of the second set is paired with just one element of the first set. Sometimes a bijection is called a one-to-one correspondence.
Watch the video, which explains bijection (a combination of injection and surjection) or read on below:
A typical bijection is shown in the diagram below.
A function is bijective if and only if it has an inverse.
If f is a function going from A to B, the inverse f-1 is the function going from B to A such that, for every f(x) = y, f f-1(y) = x. The image below illustrates that, and also should give you a visual understanding of how it relates to the definition of bijection.
Properties of Bijections
You can identify bijections visually because the graph of a bijection will meet every vertical and horizontal line exactly once. Plus, the graph of any function that meets every vertical and horizontal line exactly once is a bijection.
The composite of two bijective functions is another bijective function. If we know that a bijection is the composite of two functions, though, we can’t say for sure that they are both bijections; one might be injective and one might be surjective.
Suppose X and Y are both finite sets. Then, there exists a bijection between X and Y if and only if both X and Y have the same number of elements. If X and Y have different numbers of elements, no bijection between them exists.
An identity function maps every element of a set to itself. This is another way of saying that it returns its argument: for any x you input, you get the same output, y. This function is sometimes also called the identity map or the identity transformation.
Although identity maps might seem too simple to be useful, they actually play an important part in the groundwork behind mathematics. They are frequently used in engineering and computer science.
A composition of two identity functions is also an identity function.
Special Identity Functions
There are special identity transformations for each of the basic operations.
- The multiplicative identity is 1, because, for any x, 1 ⋅ x = x.
- The additive identity is 0, because for any x, x + 0 = x.
You might notice that the multiplicative identity transformation is also an identity transformation for division, and the additive identity function is also an identity transformation for subtraction.
Every identity function is an injective function, or a one-to-one function, since it always maps distinct values of its domain to distinct members of its range.
It is also surjective, which means that every element of the range is paired with at least one member of the domain (this is obvious because both the range and domain are the same, and each point maps to itself).
Since the identity transformation is both injective and surjective, we can say that it is a bijective function.
When applied to vector spaces, the identity map is a linear operator. In a metric space it is an isometry. And in any topological space, the identity function is always a continuous function.
Surjective Injective Bijective: References
CTI Reviews. (2016). Foundations of Topology: 2nd edition study guide. Cram101 Textbook Reviews.
Farlow, S.J. Injections, Surjections, and Bijections. Teaching Notes; Section 4.2 Retrieved from http://www.math.umaine.edu/~farlow/sec42.pdf on December 28, 2013.
Grinstein, L. & Lipsey, S. (2001). Encyclopedia of Mathematics Education. Routledge.
Keef & Guichard. Introduction to Higher Mathematics: Injections and Surjections. Department of Mathematics, Whitman College. Retrieved from https://www.whitman.edu/mathematics/higher_math_online/section04.03.html on December 23, 2018
Kubrusly, C. (2001). Elements of Operator Theory. Springer Science and Business Media.
Loreaux, Jireh. Logic and Mathematical Reasoning: An Introduction to Proof Writing. Retrieved from http://siue.edu/~jloreau/courses/math-223/notes/sec-injective-surjective.html on December 23, 2018
Stange, Katherine. A Function is Bijective if and only if it has an Inverse. Published November 30, 2015. Retrieved from
http://math.colorado.edu/~kstange/has-inverse-is-bijective.pdf on December 28, 2013.