Bijection, injection and surjection

From Wikipedia, the free encyclopedia

  (Redirected from BiJection)

Jump to navigation Jump to search

	surjective	non-surjective
injective	bijective	injective-only
non- injective	surjective-only	general

In mathematics, injections, surjections and bijections are classes of functions distinguished by the manner in which arguments (input expressions from the domain) and images (output expressions from the codomain) are related or mapped to each other.

A function maps elements from its domain to elements in its codomain. Given a function ${\displaystyle f\colon X\to Y}$:

• The function is injective, or one-to-one, if each element of the codomain is mapped to by at most one element of the domain, or equivalently, if distinct elements of the domain map to distinct elements in the codomain. An injective function is also called an injection.^[1][2] Notationally:

${\displaystyle \forall x,x'\in X,f(x)=f(x')\Rightarrow x=x'.}$

Or, equivalently (using logical transposition),

${\displaystyle \forall x,x'\in X,x\neq x'\Rightarrow f(x)\neq f(x').}$^[3][4][5]

• The function is surjective, or onto, if each element of the codomain is mapped to by at least one element of the domain. That is, the image and the codomain of the function are equal. A surjective function is a surjection.^[1][2] Notationally:

${\displaystyle \forall y\in Y,\exists x\in X{\text{ such that }}y=f(x).}$^[3][4][5]

• The function is bijective (one-to-one and onto or one-to-one correspondence) if each element of the codomain is mapped to by exactly one element of the domain. That is, the function is both injective and surjective. A bijective function is also called a bijection.^{[1][2][3][4][5]}

An injective function need not be surjective (not all elements of the codomain may be associated with arguments), and a surjective function need not be injective (some images may be associated with more than one argument). The four possible combinations of injective and surjective features are illustrated in the adjacent diagrams.

Contents

• 1 Injection
• 2 Surjection
• 3 Bijection
  • 3.1 Cardinality
• 4 Examples
• 5 Properties
• 6 Category theory
• 7 History
• 8 See also
• 9 References
• 10 External links

Injection[edit]

Main article: Injective function

Further information on notation: Function (mathematics) § Notation

Injective composition: the second function need not be injective.

A function is injective (one-to-one) if each possible element of the codomain is mapped to by at most one argument. Equivalently, a function is injective if it maps distinct arguments to distinct images. An injective function is an injection.^[1][2] The formal definition is the following.

The function ${\displaystyle f\colon X\to Y}$ is injective, if for all ${\displaystyle x,x'\in X}$, ${\displaystyle f(x)=f(x')\Rightarrow x=x'.}$^[3][4][5]

The following are some facts related to injections:

• A function f : X → Y is injective if and only if X is empty or f is left-invertible; that is, there is a function g : f(X) → X such that g o f = identity function on X. Here, f(X) is the image of f.
• Since every function is surjective when its codomain is restricted to its image, every injection induces a bijection onto its image.^[1] More precisely, every injection f : X → Y can be factored as a bijection followed by an inclusion as follows. Let f_R : X → f(X) be f with codomain restricted to its image, and let i : f(X) → Y be the inclusion map from f(X) into Y. Then f = i o f_R. A dual factorisation is given for surjections below.
• The composition of two injections is again an injection, but if g o f is injective, then it can only be concluded that f is injective (see figure).
• Every embedding is injective.

Surjection[edit]

Main article: Surjective function

Surjective composition: the first function need not be surjective.

A function is surjective (onto) if each possible image is mapped to by at least one argument. In other words, each element in the codomain has non-empty preimage. Equivalently, a function is surjective if its image is equal to its codomain. A surjective function is a surjection.^[1][2] The formal definition is the following.

The function ${\displaystyle f\colon X\to Y}$ is surjective, if for all ${\displaystyle y\in Y}$, there is ${\displaystyle x\in X}$ such that ${\displaystyle f(x)=y.}$^[3][4][5]

The following are some facts related to surjections:

• A function f : X → Y is surjective if and only if it is right-invertible, that is, if and only if there is a function g: Y → X such that f o g = identity function on Y. (This statement is equivalent to the axiom of choice.)
• By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. More precisely, every surjection f : X → Y can be factored as a non-bijection followed by a bijection as follows. Let X/~ be the equivalence classes of X under the following equivalence relation: x ~ y if and only if f(x) = f(y). Equivalently, X/~ is the set of all preimages under f. Let P(~) : X → X/~ be the projection map which sends each x in X to its equivalence class [x]_~, and let f_P : X/~ → Y be the well-defined function given by f_P([x]_~) = f(x). Then f = f_P o P(~). A dual factorisation is given for injections above.
• The composition of two surjections is again a surjection, but if g o f is surjective, then it can only be concluded that g is surjective (see figure).

Bijection[edit]

Main article: Bijective function

Bijective composition: the first function need not be surjective and the second function need not be injective.

A function is bijective if it is both injective and surjective. A bijective function is a bijection (one-to-one correspondence).^[1] A function is bijective if and only if every possible image is mapped to by exactly one argument.^[2] This equivalent condition is formally expressed as follow.

The function ${\displaystyle f\colon X\to Y}$ is bijective, if for all ${\displaystyle y\in Y}$, there is a unique ${\displaystyle x\in X}$ such that ${\displaystyle f(x)=y.}$^[3][4][5]

The following are some facts related to bijections:

• A function f : X → Y is bijective if and only if it is invertible, that is, there is a function g: Y → X such that g o f = identity function on X and f o g = identity function on Y. This function maps each image to its unique preimage.
• The composition of two bijections is again a bijection, but if g o f is a bijection, then it can only be concluded that f is injective and g is surjective (see the figure at right and the remarks above regarding injections and surjections).
• The bijections from a set to itself form a group under composition, called the symmetric group.

Cardinality[edit]

Suppose that one wants to define what it means for two sets to "have the same number of elements". One way to do this is to say that two sets "have the same number of elements", if and only if all the elements of one set can be paired with the elements of the other, in such a way that each element is paired with exactly one element. Accordingly, one can define two sets to "have the same number of elements"—if there is a bijection between them. In which case, the two sets are said to have the same cardinality.

Likewise, one can say that set ${\displaystyle X}$ "has fewer than or the same number of elements" as set ${\displaystyle Y}$, if there is an injection from ${\displaystyle X}$ to ${\displaystyle Y}$; one can also say that set ${\displaystyle X}$ "has fewer than the number of elements" in set ${\displaystyle Y}$, if there is an injection from ${\displaystyle X}$ to ${\displaystyle Y}$, but not a bijection between ${\displaystyle X}$ and ${\displaystyle Y}$.

Examples[edit]

It is important to specify the domain and codomain of each function, since by changing these, functions which appear to be the same may have different properties.

Injective and surjective (bijective)

The identity function id_X for every non-empty set X, and thus specifically ${\displaystyle \mathbf {R} \to \mathbf {R} :x\mapsto x.}$

${\displaystyle \mathbf {R} ^{+}\to \mathbf {R} ^{+}:x\mapsto x^{2}}$, and thus also its inverse ${\displaystyle \mathbf {R} ^{+}\to \mathbf {R} ^{+}:x\mapsto {\sqrt {x}}.}$

The exponential function ${\displaystyle \exp \colon \mathbf {R} \to \mathbf {R} ^{+}:x\mapsto \mathrm {e} ^{x}}$ (that is, the exponential function with its codomain restricted to its image), and thus also its inverse the natural logarithm ${\displaystyle \ln \colon \mathbf {R} ^{+}\to \mathbf {R} :x\mapsto \ln {x}.}$

Injective and non-surjective

The exponential function ${\displaystyle \exp \colon \mathbf {R} \to \mathbf {R} :x\mapsto \mathrm {e} ^{x}.}$

Non-injective and surjective

${\displaystyle \mathbf {R} \to \mathbf {R} :x\mapsto (x-1)x(x+1)=x^{3}-x.}$

${\displaystyle \mathbf {R} \to [-1,1]:x\mapsto \sin(x).}$

Non-injective and non-surjective

${\displaystyle \mathbf {R} \to \mathbf {R} :x\mapsto \sin(x).}$

Properties[edit]

• For every function f, subset X of the domain and subset Y of the codomain, X ⊂ f⁻¹(f(X)) and f(f⁻¹(Y)) ⊂ Y. If f is injective, then X = f⁻¹(f(X)), and if f is surjective, then f(f⁻¹(Y)) = Y.
• For every function h : X → Y, one can define a surjection H : X → h(X) : x → h(x) and an injection I : h(X) → Y : y → y. It follows that ${\displaystyle h=I\circ H}$. This decomposition is unique up to isomorphism.

Category theory[edit]

In the category of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively.^[6]

History[edit]

The injective-surjective-bijective terminology (both as nouns and adjectives) was originally coined by the French Bourbaki group, before their widespread adoption.^[7]

See also[edit]

• Bijective function
• Horizontal line test
• Injective module
• Injective function
• Permutation
• Surjective function

References[edit]

1. ^ ^{a b c d e f g} "The Definitive Glossary of Higher Mathematical Jargon". Math Vault. 2019-08-01. Retrieved 2019-12-07.
2. ^ ^{a b c d e f} "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.
3. ^ ^{a b c d e f} "Bijection, Injection, And Surjection | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-07.
4. ^ ^{a b c d e f} Farlow, S. J. "Injections, Surjections, and Bijections" (PDF). math.umaine.edu. Retrieved 2019-12-06.
5. ^ ^{a b c d e f} "6.3: Injections, Surjections, and Bijections". Mathematics LibreTexts. 2017-09-20. Retrieved 2019-12-07.
6. ^ "Section 7.3 (00V5): Injective and surjective maps of presheaves—The Stacks project". stacks.math.columbia.edu. Retrieved 2019-12-07.
7. ^ Mashaal, Maurice (2006). Bourbaki. American Mathematical Soc. p. 106. ISBN 978-0-8218-3967-6.

External links[edit]

• Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Bijection,_injection_and_surjection&oldid=943878835"

Categories:

• Basic concepts in set theory
• Mathematical relations
• Functions and mappings

Navigation menu

Personal tools

• Not logged in
• Talk
• Contributions
• Create account
• Log in

Namespaces

• Article
• Talk

Variants

Views

• Read
• Edit
• View history

More

Search

Navigation

• Main page
• Contents
• Featured content
• Current events
• Random article
• Donate to Wikipedia
• Wikipedia store

Interaction

• Help
• About Wikipedia
• Community portal
• Recent changes
• Contact page

Tools

• What links here
• Related changes
• Upload file
• Special pages
• Permanent link
• Page information
• Wikidata item
• Cite this page

Print/export

• Create a book
• Download as PDF
• Printable version

Languages

• Español
• 中文

Edit links

• This page was last edited on 4 March 2020, at 11:24 (UTC).
• Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.

• Privacy policy
• About Wikipedia
• Disclaimers
• Contact Wikipedia
• Developers
• Statistics
• Cookie statement
• Mobile view

• 
•