Davisson–Germer experiment: Difference between revisions
en>KConWiki No edit summary |
en>Jim.henderson |
||
Line 1: | Line 1: | ||
{| style="margin: 0 0 0 0; float:right" | |||
|- valign="top" | |||
| [[Image:Bijection.svg|thumb|x150px|Injective and surjective (bijection)]] | |||
| [[Image:Injection.svg|thumb|x150px|Injective and non-surjective (injection, or one-to-one)]] | |||
|- valign="top" | |||
| [[Image:Surjection.svg|thumb|x150px|Non-injective and surjective (surjection, or onto)]] | |||
| [[Image:Total function.svg|thumb|x150px|Non-injective and non-surjective (projection)]] | |||
|} | |||
In [[mathematics]], '''injections''', '''surjections''' and '''bijections''' are classes of [[function (mathematics)|functions]] distinguished by the manner in which ''[[parameter|arguments]]'' (input [[expression (mathematics)|expressions]] from the [[domain (mathematics)|domain]]) and ''[[image (mathematics)|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. | |||
*A function <math>f: \; A \to B</math> is '''[[injective function|injective]]''' ('''one-to-one''') if every element of the codomain is mapped to by ''at most'' one element of the domain. Notationally, | |||
:<math>\forall x, y \in A, f(x)=f(y) \Rightarrow x=y\ </math> or, equivalently (using [[Transposition_(logic)|logical transposition]]), | |||
:<math>\forall x,y \in A, x \neq y \Rightarrow f(x) \neq f(y).\ </math> | |||
An injective function is an '''injection'''. | |||
*A function is '''[[surjective function|surjective]]''' ('''onto''') if every 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.) Notationally, | |||
:<math>\forall y \in B, \exists x \in A \text{ such that } y = f(x).\ </math> | |||
A surjective function is a '''surjection'''. | |||
*A function is '''[[bijective function|bijective]]''' ('''one-to-one and onto''' or '''one-to-one correspondence''') if every 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 a '''bijection'''. | |||
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 right diagrams. | |||
==Injection== | |||
{{main|Injective function}} | |||
[[Image:Injective composition.svg|thumb|300px|Injective composition: the second function need not be injective.]] | |||
A function is '''injective''' ('''one-to-one''') if every 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'''. The formal definition is the following. | |||
:The function <math>f: A \to B</math> is injective [[iff]] for all <math>a,b \in A</math>, we have <math>f(a) = f(b) \Rarr a = b.</math> | |||
*A function ''f'' : ''A'' → ''B'' is injective if and only if ''A'' is empty or ''f'' is left-invertible; that is, there is a function g : f(A) → A such that ''g'' o ''f'' = identity function on ''A''. Here f(A) is the image of f. | |||
*Since every function is surjective when its [[codomain]] is restricted to its [[image (mathematics)|image]], every injection induces a bijection onto its image. More precisely, every injection ''f'' : ''A'' → ''B'' can be factored as a bijection followed by an inclusion as follows. Let ''f''<sub>''R''</sub> : ''A'' → ''f''(''A'') be ''f'' with codomain restricted to its image, and let ''i'' : ''f''(''A'') → ''B'' be the inclusion map from ''f''(''A'') into ''B''. Then ''f'' = ''i'' o ''f''<sub>''R''</sub>. 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 the figure at right. | |||
*Every [[embedding]] is injective. | |||
==Surjection== | |||
{{main|surjective function}} | |||
[[Image:Surjective composition.svg|thumb|300px|Surjective composition: the first function need not be surjective.]] | |||
A function is '''surjective''' ('''onto''') if every possible image is mapped to by at least one argument. In other words, every 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'''. The formal definition is the following. | |||
:The function <math>f: A \to B</math> is surjective [[iff]] for all <math>b \in B</math>, there is <math>a \in A</math> such that <math>f(a) = b.</math> | |||
*A function ''f'' : ''A'' → ''B'' is surjective if and only if it is right-invertible, that is, if and only if there is a function ''g'': ''B'' → ''A'' such that ''f'' o ''g'' = identity function on ''B''. (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'' : ''A'' → ''B'' can be factored as a projection followed by a bijection as follows. Let ''A''/~ be the equivalence classes of ''A'' under the following equivalence relation: ''x'' ~ ''y'' if and only if ''f''(''x'') = ''f''(''y''). Equivalently, ''A''/~ is the [[Set (mathematics)|set]] of all preimages under ''f''. Let ''P''(~) : ''A'' → ''A''/~ be the projection map which sends each ''x'' in ''A'' to its equivalence class [''x'']<sub>~</sub>, and let ''f''<sub>''P''</sub> : ''A''/~ → ''B'' be the well-defined function given by ''f''<sub>''P''</sub>([''x'']<sub>~</sub>) = ''f''(''x''). Then ''f'' = ''f''<sub>''P''</sub> 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 the figure. | |||
==Bijection== | |||
{{main|bijective function}} | |||
[[Image:Bijective composition.svg|thumb|300px|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'''). A function is bijective [[if and only if]] every possible image is mapped to by exactly one argument. This equivalent condition is formally expressed as follow. | |||
:The function <math>f: A \to B</math> is bijective [[iff]] for all <math>b \in B</math>, there is a unique <math>a \in A</math> such that <math>f(a) = b.</math> | |||
*A function ''f'' : ''A'' → ''B'' is bijective if and only if it is invertible, that is, there is a function ''g'': ''B'' → ''A'' such that ''g'' o ''f'' = identity function on ''A'' and ''f'' o ''g'' = identity function on ''B''. 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 (mathematics)|group]] under composition, called the [[symmetric group]]. | |||
==Cardinality== | |||
Suppose you want 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, we can define two sets to "have the same number of elements" if there is a bijection between them. We say that the two sets have the same [[cardinality]]. | |||
Likewise, we can say that set <math>A</math> "has fewer than or the same number of elements" as set <math>B</math> if there is an injection from <math>A</math> to <math>B</math>. We can also say that set <math>A</math> "has fewer than the number of elements" in set <math>B</math> if there is an injection from <math>A</math> to <math>B</math> but not a bijection between <math>A</math> and <math>B</math>. | |||
==Examples== | |||
It is important to specify the domain and codomain of each function since by changing these, functions which we think of as the same may have different ''jectivity''. <!-- someone change this wording please. MarSch --> | |||
===Injective and surjective (bijective)=== | |||
* For every set ''A'' the identity function id<sub>''A''</sub> and thus specifically <math>\mathbf{R} \to \mathbf{R} : x \mapsto x</math>. | |||
* <math>\mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto x^2</math> and thus also its inverse <math>\mathbf{R}^+ \to \mathbf{R}^+ : x \mapsto \sqrt{x}</math>. | |||
* The [[exponential function]] <math>\exp : \mathbf{R} \to \mathbf{R}^+ : x \mapsto \mathrm{e}^x</math> and thus also its inverse the [[natural logarithm]] <math>\ln : \mathbf{R}^+ \to \mathbf{R} : x \mapsto \ln{x}</math> | |||
===Injective and non-surjective=== | |||
* The exponential function <math>\exp : \mathbf{R} \to \mathbf{R} : x \mapsto \mathrm{e}^x</math> | |||
===Non-injective and surjective=== | |||
* <math>\mathbf{R} \to \mathbf{R} : x \mapsto (x-1)x(x+1) = x^3 - x </math> | |||
* <math>\mathbf{R} \to [-1,1] : x \mapsto \sin(x)</math> | |||
==Properties== | |||
* For every function ''f'', subset ''A'' of the domain and subset ''B'' of the codomain we have ''A'' ⊂ ''f''<sup> −1</sup>(''f''(''A'')) and ''f''(''f''<sup> −1</sup>(''B'')) ⊂ ''B''. If ''f'' is injective we have ''A'' = ''f''<sup> −1</sup>(''f''(''A'')) and if ''f'' is surjective we have ''f''(''f''<sup> −1</sup>(''B'')) = ''B''. | |||
* For every function ''h'' : ''A'' → ''C'' we can define a surjection ''H'' : ''A'' → ''h(A)'' : a → h(a) and an injection ''I'' : ''h(A)'' → ''C'' : a → a. It follows that ''h'' = ''I'' ∘ ''H''. This decomposition is unique [[up to isomorphism]]. | |||
==Category theory== | |||
In the [[category (mathematics)|category]] of [[Set (mathematics)|sets]], injections, surjections, and bijections correspond precisely to [[monomorphism]]s, [[epimorphism]]s, and [[isomorphism]]s, respectively. | |||
==History== | |||
This terminology was originally coined by the [[Bourbaki]] group. | |||
==See also== | |||
*[[Bijective function]] | |||
*[[Horizontal line test]] | |||
*[[Injective module]] | |||
*[[Injective function]] | |||
*[[Permutation]] | |||
*[[Surjective function]] | |||
==External links== | |||
*[http://jeff560.tripod.com/i.html Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.] | |||
[[Category:Basic concepts in set theory]] | |||
[[Category:Mathematical relations]] | |||
[[Category:Functions and mappings]] |
Revision as of 03:11, 4 November 2013
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.
- A function is injective (one-to-one) if every element of the codomain is mapped to by at most one element of the domain. Notationally,
- or, equivalently (using logical transposition),
An injective function is an injection.
- A function is surjective (onto) if every 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.) Notationally,
A surjective function is a surjection.
- A function is bijective (one-to-one and onto or one-to-one correspondence) if every 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 a bijection.
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 right diagrams.
Injection
Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church.
A function is injective (one-to-one) if every 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. The formal definition is the following.
- The function is injective iff for all , we have
- A function f : A → B is injective if and only if A is empty or f is left-invertible; that is, there is a function g : f(A) → A such that g o f = identity function on A. Here f(A) 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. More precisely, every injection f : A → B can be factored as a bijection followed by an inclusion as follows. Let fR : A → f(A) be f with codomain restricted to its image, and let i : f(A) → B be the inclusion map from f(A) into B. Then f = i o fR. 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 the figure at right.
- Every embedding is injective.
Surjection
Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church.
A function is surjective (onto) if every possible image is mapped to by at least one argument. In other words, every 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. The formal definition is the following.
- The function is surjective iff for all , there is such that
- A function f : A → B is surjective if and only if it is right-invertible, that is, if and only if there is a function g: B → A such that f o g = identity function on B. (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 : A → B can be factored as a projection followed by a bijection as follows. Let A/~ be the equivalence classes of A under the following equivalence relation: x ~ y if and only if f(x) = f(y). Equivalently, A/~ is the set of all preimages under f. Let P(~) : A → A/~ be the projection map which sends each x in A to its equivalence class [x]~, and let fP : A/~ → B be the well-defined function given by fP([x]~) = f(x). Then f = fP 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 the figure.
Bijection
Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church.
A function is bijective if it is both injective and surjective. A bijective function is a bijection (one-to-one correspondence). A function is bijective if and only if every possible image is mapped to by exactly one argument. This equivalent condition is formally expressed as follow.
- The function is bijective iff for all , there is a unique such that
- A function f : A → B is bijective if and only if it is invertible, that is, there is a function g: B → A such that g o f = identity function on A and f o g = identity function on B. 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
Suppose you want 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, we can define two sets to "have the same number of elements" if there is a bijection between them. We say that the two sets have the same cardinality.
Likewise, we can say that set "has fewer than or the same number of elements" as set if there is an injection from to . We can also say that set "has fewer than the number of elements" in set if there is an injection from to but not a bijection between and .
Examples
It is important to specify the domain and codomain of each function since by changing these, functions which we think of as the same may have different jectivity.
Injective and surjective (bijective)
- For every set A the identity function idA and thus specifically .
- and thus also its inverse .
- The exponential function and thus also its inverse the natural logarithm
Injective and non-surjective
Non-injective and surjective
Properties
- For every function f, subset A of the domain and subset B of the codomain we have A ⊂ f −1(f(A)) and f(f −1(B)) ⊂ B. If f is injective we have A = f −1(f(A)) and if f is surjective we have f(f −1(B)) = B.
- For every function h : A → C we can define a surjection H : A → h(A) : a → h(a) and an injection I : h(A) → C : a → a. It follows that h = I ∘ H. This decomposition is unique up to isomorphism.
Category theory
In the category of sets, injections, surjections, and bijections correspond precisely to monomorphisms, epimorphisms, and isomorphisms, respectively.
History
This terminology was originally coined by the Bourbaki group.
See also
- Bijective function
- Horizontal line test
- Injective module
- Injective function
- Permutation
- Surjective function