Bijection: Difference between revisions
Jump to navigation
Jump to search
imported>Beland m MOS:MATHSPECIAL / convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB) |
imported>StrangerCoug Use proper math formatting for consistency with the rest of the introduction |
||
| Line 2: | Line 2: | ||
{{redirect|One-to-one correspondence|one-to-one function|injective function}} | {{redirect|One-to-one correspondence|one-to-one function|injective function}} | ||
{{Use dmy dates|date=July 2022}} | {{Use dmy dates|date=July 2022}} | ||
[[Image:Bijection.svg|thumb|A bijective function, ''f'': ''X'' → ''Y'', where set X is {1, 2, 3, 4} and set Y is { | {{Dark mode invert|image=y|[[Image:Bijection.svg|thumb|A bijective function, ''f'': ''X'' → ''Y'', where set X is {1, 2, 3, 4} and set Y is {D, C, B, A}. For example, ''f''(1) = D.]]}} | ||
{{Functions}} | {{Functions}} | ||
In [[mathematics]], a '''bijection''', '''bijective function''', or '''one-to-one correspondence''' is a [[function (mathematics)|function]] between two [[set (mathematics)|sets]] such that each element of the second set (the [[codomain]]) is the image of exactly one element of the first set (the [[domain of a function|domain]]). Equivalently, a bijection is a [[binary relation|relation]] between two sets such that each element of either set is paired with exactly one element of the other set. | In [[mathematics]], a '''bijection''', '''bijective function''', or '''one-to-one correspondence''' is a [[function (mathematics)|function]] between two [[set (mathematics)|sets]] such that each element of the second set (the [[codomain]]) is the image of exactly one element of the first set (the [[domain of a function|domain]]). Given a function <math>f:A\to B</math>, the image of an [[Element of a set|element]] <math>a\in A</math> is the element <math>f(a)\in B</math> in the codomain. The pre-image of an element <math>b\in B</math> is any element <math>a\in A</math> in the domain such that <math>f(a)=b</math>. Equivalently, a bijection is a [[binary relation|relation]] between two sets such that each element of either set is paired with exactly one element of the other set. | ||
A function is bijective if it is [[inverse function|invertible]]; that is, a function <math>f:X\to Y</math> is bijective if and only if there is a function <math>g:Y\to X,</math> the ''inverse'' of {{mvar|f}}, such that each of the two ways for [[function composition|composing]] the two functions produces an [[identity function]]: <math>g(f(x)) = x</math> for each <math>x</math> in <math>X</math> and <math>f(g(y)) = y</math> for each <math>y</math> in <math>Y.</math> | A function is bijective if and only if it is [[inverse function|invertible]]; that is, a function <math>f:X\to Y</math> is bijective if and only if there is a function <math>g:Y\to X,</math> the ''inverse'' of {{mvar|f}}, such that each of the two ways for [[function composition|composing]] the two functions produces an [[identity function]]: <math>g(f(x)) = x</math> for each <math>x</math> in <math>X</math> and <math>f(g(y)) = y</math> for each <math>y</math> in <math>Y.</math> | ||
For example, the ''multiplication by two'' defines a bijection from the [[integer]]s to the [[even number]]s, which has the ''division by two'' as its inverse function. | For example, the ''multiplication by two'' defines a bijection from the [[integer]]s to the [[even number]]s, which has the ''division by two'' as its inverse function. | ||
| Line 17: | Line 17: | ||
A bijective function from a set to itself is also called a [[permutation]],<ref>{{harvnb|Hall|1959|p=3}}</ref> and the set of all permutations of a set forms its [[symmetric group]]. | A bijective function from a set to itself is also called a [[permutation]],<ref>{{harvnb|Hall|1959|p=3}}</ref> and the set of all permutations of a set forms its [[symmetric group]]. | ||
Some bijections with further properties have received specific names, which include [[automorphism]]s, [[isomorphism]]s, [[homeomorphism]]s, [[diffeomorphism]]s, [[permutation | Some bijections with further properties have received specific names, which include [[automorphism]]s, [[isomorphism]]s, [[homeomorphism]]s, [[diffeomorphism]]s, [[permutation]]s, and most [[geometric transformation]]s. [[Galois correspondence]]s are bijections between sets of [[mathematical object]]s of apparently very different nature. | ||
==Definition== | ==Definition== | ||
| Line 29: | Line 29: | ||
==Examples== | ==Examples== | ||
Every map from [[Empty set|the empty set]] to itself is a bijection. | |||
=== Batting line-up of a baseball or cricket team=== | === Batting line-up of a baseball or cricket team=== | ||
| Line 34: | Line 35: | ||
=== Seats and students of a classroom=== | === Seats and students of a classroom=== | ||
In a classroom there are a certain number of seats. A group of students enter the room and the instructor asks them to be seated. After a quick look around the room, the instructor declares that there is a bijection between the set of students and the set of seats, where each student is paired with the seat they are sitting in. What the instructor observed in order to reach this conclusion was that: | In a classroom, there are a certain number of seats. A group of students enter the room and the instructor asks them to be seated. After a quick look around the room, the instructor declares that there is a bijection between the set of students and the set of seats, where each student is paired with the seat they are sitting in. What the instructor observed in order to reach this conclusion was that: | ||
# Every student was in a seat (there was no one standing), | # Every student was in a seat (there was no one standing), | ||
# No student was in more than one seat, | # No student was in more than one seat, | ||
| Line 40: | Line 41: | ||
# No seat had more than one student in it. | # No seat had more than one student in it. | ||
The instructor was able to conclude that there were just as many seats as there were students, without having to count either set. | The instructor was able to conclude that there were just as many seats as there were students, without having to count either set. | ||
=== Fingerprints === | |||
Consider a sample of 100 distinct individuals and the corresponding set of their [[Fingerprint|fingerprints]]. Assuming that no two individuals in that sample share the same fingerprint, the set is one-to-one (injective). Furthermore, there aren’t any fingerprints without an individual; the set is onto (surjective). Since both sets have the same [[cardinality]] and the sets are injective and surjective, then it follows there’s a bijection between the set of individuals and their fingerprints. | |||
==More mathematical examples== | ==More mathematical examples== | ||
[[File:A bijection from | |||
{{Dark mode invert|image=y|[[File:A bijection from N to Z.png|thumb|alt=n mod 2 + (-1)^(n+1) n|Bijection from the natural numbers to the integers, which maps 2''n'' to −''n'' and 2''n'' + 1 to ''n+1'', for ''n'' ≥ 0.]]}} | |||
* For any set ''X'', the [[identity function]] '''1'''<sub>''X''</sub>: ''X'' → ''X'', '''1'''<sub>''X''</sub>(''x'') = ''x'' is bijective. | * For any set ''X'', the [[identity function]] '''1'''<sub>''X''</sub>: ''X'' → ''X'', '''1'''<sub>''X''</sub>(''x'') = ''x'' is bijective. | ||
* The [[multiplicative inverse]] function gives a bijection of the [[unit interval]] (0, 1) with the semi-infinite interval (1, +∞). | |||
* The function ''f'': '''R''' → '''R''', ''f''(''x'') = 2''x'' + 1 is bijective, since for each ''y'' there is a unique ''x'' = (''y'' − 1)/2 such that ''f''(''x'') = ''y''. More generally, any [[linear function]] over the reals, ''f'': '''R''' → '''R''', ''f''(''x'') = ''ax'' + ''b'' (where ''a'' is non-zero) is a bijection. Each real number ''y'' is obtained from (or paired with) the real number ''x'' = (''y'' − ''b'')/''a''. | * The function ''f'': '''R''' → '''R''', ''f''(''x'') = 2''x'' + 1 is bijective, since for each ''y'' there is a unique ''x'' = (''y'' − 1)/2 such that ''f''(''x'') = ''y''. More generally, any [[linear function]] over the reals, ''f'': '''R''' → '''R''', ''f''(''x'') = ''ax'' + ''b'' (where ''a'' is non-zero) is a bijection. Each real number ''y'' is obtained from (or paired with) the real number ''x'' = (''y'' − ''b'')/''a''. | ||
* The function ''f'': '''R''' → (−π/2, π/2), given by ''f''(''x'') = arctan(''x'') is bijective, since each real number ''x'' is paired with exactly one angle ''y'' in the interval (−π/2, π/2) so that tan(''y'') = ''x'' (that is, ''y'' = arctan(''x'')). If the [[codomain]] (−π/2, π/2) was made larger to include an integer multiple of π/2, then this function would no longer be onto (surjective), since there is no real number which could be paired with the multiple of π/2 by this arctan function. | * The function ''f'': '''R''' → (−π/2, π/2), given by ''f''(''x'') = arctan(''x'') is bijective, since each real number ''x'' is paired with exactly one angle ''y'' in the interval (−π/2, π/2) so that tan(''y'') = ''x'' (that is, ''y'' = arctan(''x'')). If the [[codomain]] (−π/2, π/2) was made larger to include an integer multiple of π/2, then this function would no longer be onto (surjective), since there is no real number which could be paired with the multiple of π/2 by this arctan function. | ||
| Line 59: | Line 65: | ||
==Composition== | ==Composition== | ||
[[Image:Bijective composition.svg|thumb|300px|A bijection composed of an injection (X → Y) and a surjection (Y → Z).]] | {{Dark mode invert|image=y|[[Image:Bijective composition.svg|thumb|300px|A bijection composed of an injection (X → Y) and a surjection (Y → Z).]]}} | ||
The [[Function composition|composition]] <math>g \,\circ\, f</math> of two bijections | The [[Function composition|composition]] <math>g \,\circ\, f</math> of two bijections <math>f : X \to Y</math> and <math>g : Y \to Z</math> is a bijection, whose inverse is given by <math>g \,\circ\, f</math> is <math>(g \,\circ\, f)^{-1} \;=\; (f^{-1}) \,\circ\, (g^{-1})</math>. | ||
Conversely, if the composition <math>g \, \circ\, f</math> of two functions is bijective, it only follows that ''f'' is [[Injective function|injective]] and ''g'' is [[surjective function|surjective]]. | Conversely, if the composition <math>g \, \circ\, f</math> of two functions is bijective, it only follows that ''f'' is [[Injective function|injective]] and ''g'' is [[surjective function|surjective]]. | ||
==Cardinality== | ==Cardinality== | ||
If ''X'' and ''Y'' are [[finite set]]s, then there exists a bijection between the two sets ''X'' and ''Y'' [[if and only if]] ''X'' and ''Y'' have the same number of elements. Indeed, in [[axiomatic set theory]], this is taken as the definition of "same number of elements" ([[equinumerosity]]), and | If ''X'' and ''Y'' are [[finite set]]s, then there exists a bijection between the two sets ''X'' and ''Y'' [[if and only if]] ''X'' and ''Y'' have the same number of elements. Indeed, in [[axiomatic set theory]], this is taken as the definition of "same number of elements" ([[equinumerosity]]), and generalizing this definition to [[infinite set]]s leads to the concept of [[cardinal number]], a way to distinguish the various sizes of infinite sets. | ||
Any [[infinite set]] that has a bijection to the [[Natural number|natural numbers]] is said to be countably infinite. Likewise, any infinite set that has a bijection with the [[Integer|integers]] or the [[Rational number|rational numbers]] is also countably infinite, since they also have a bijection to the natural numbers. This concept is integral to determining if some functions are countable. | |||
For example, the set of all even integers f(n)=2n is countably infinite because there’s a bijection between the even integers and the natural numbers. | |||
== Properties == | == Properties == | ||
| Line 88: | Line 98: | ||
''R'' (which turns out to be a partial function) with the property that ''R'' is the [[Graph of a function|graph of]] a bijection ''f'':''{{prime|A}}''→''{{prime|B}}'', where ''{{prime|A}}'' is a [[subset]] of ''A'' and ''{{prime|B}}'' is a subset of ''B''.<ref name="Borceux1994">{{cite book|author=Francis Borceux|title=Handbook of Categorical Algebra: Volume 2, Categories and Structures|url=https://books.google.com/books?id=5i2v9q0m5XAC&pg=PA289|year=1994|publisher=Cambridge University Press|isbn=978-0-521-44179-7|page=289}}</ref> | ''R'' (which turns out to be a partial function) with the property that ''R'' is the [[Graph of a function|graph of]] a bijection ''f'':''{{prime|A}}''→''{{prime|B}}'', where ''{{prime|A}}'' is a [[subset]] of ''A'' and ''{{prime|B}}'' is a subset of ''B''.<ref name="Borceux1994">{{cite book|author=Francis Borceux|title=Handbook of Categorical Algebra: Volume 2, Categories and Structures|url=https://books.google.com/books?id=5i2v9q0m5XAC&pg=PA289|year=1994|publisher=Cambridge University Press|isbn=978-0-521-44179-7|page=289}}</ref> | ||
When the partial bijection is on the same set, it is sometimes called a ''one-to-one partial [[transformation (function)|transformation]]''.<ref name="Grillet1995">{{cite book|author=Pierre A. Grillet|title=Semigroups: An Introduction to the Structure Theory|url=https://books.google.com/books?id=yM544W1N2UUC&pg=PA228|year=1995|publisher=CRC Press|isbn=978-0-8247-9662-4|page=228}}</ref> An example is the [[Möbius transformation]] simply defined on the complex plane, rather than its completion to the extended complex plane.<ref name="Campbell2007">{{cite book|editor=C.M. Campbell |editor2=M.R. Quick |editor3=E.F. Robertson |editor4=G.C. Smith|title=Groups St Andrews 2005 Volume 2|year=2007|publisher=Cambridge University Press|isbn=978-0-521-69470-4|page=367|chapter=Groups and semigroups: connections and contrasts |author=John Meakin}} [ | When the partial bijection is on the same set, it is sometimes called a ''one-to-one partial [[transformation (function)|transformation]]''.<ref name="Grillet1995">{{cite book|author=Pierre A. Grillet|title=Semigroups: An Introduction to the Structure Theory|url=https://books.google.com/books?id=yM544W1N2UUC&pg=PA228|year=1995|publisher=CRC Press|isbn=978-0-8247-9662-4|page=228}}</ref> An example is the [[Möbius transformation]] simply defined on the complex plane, rather than its completion to the extended complex plane.<ref name="Campbell2007">{{cite book|editor=C.M. Campbell |editor2=M.R. Quick |editor3=E.F. Robertson |editor4=G.C. Smith|title=Groups St Andrews 2005 Volume 2|year=2007|publisher=Cambridge University Press|isbn=978-0-521-69470-4|page=367|chapter=Groups and semigroups: connections and contrasts |author=John Meakin}} [https://www.math.unl.edu/~jmeakin2/groups%20and%20semigroups.pdf preprint] citing {{Cite journal | ||
| doi = 10.1006/jabr.1997.7242 | | doi = 10.1006/jabr.1997.7242 | ||
| title = The Möbius Inverse Monoid | | title = The Möbius Inverse Monoid | ||
| Line 101: | Line 111: | ||
== Gallery == | == Gallery == | ||
{{Gallery | {{Dark mode invert|image=y|{{Gallery | ||
|align=center | |align=center | ||
| | |File:Injection.svg|alt1=The sets X = {1, 2, 3} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, and 3 to A.|An injective non-surjective function (injection, not a bijection) | ||
| | |File:Bijection.svg|alt2=The sets X = {1, 2, 3, 4} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, 3 to C, and 4 to A.|An injective surjective function ('''bijection''') | ||
| | |File:Surjection.svg|alt3=The sets X = {1, 2, 3, 4} and Y = {B, C, D}, and a function mapping 1 to D, 2 to B, 3 to C, and 4 to C.|A non-injective surjective function (surjection, not a bijection) | ||
| | |File:Not-Injection-Surjection.svg|alt4=The sets X = {1, 2, 3, 4} and Y = {A, B, C, D}, and a function mapping 1 to D, 2 to B, 3 to C, and 4 to C.|A non-injective non-surjective function (also not a bijection) | ||
}} | }}}} | ||
==See also== | ==See also== | ||
| Line 142: | Line 152: | ||
* {{cite book|last1=Barnier|last2=Feldman|title=Introduction to Advanced Mathematics|year=2000|publisher=Prentice Hall}} | * {{cite book|last1=Barnier|last2=Feldman|title=Introduction to Advanced Mathematics|year=2000|publisher=Prentice Hall}} | ||
* {{cite book|last=Ash|title=A Primer of Abstract Mathematics|publisher=MAA}} | * {{cite book|last=Ash|title=A Primer of Abstract Mathematics|publisher=MAA}} | ||
* Lay, Steven R. ''Analysis with an Introduction to Proof''. 5th ed., Pearson, 2014. | |||
* Tao, Terence. ''Analysis I''. 3rd ed., Hindustan Book Agency, 2016. | |||
==External links== | ==External links== | ||
| Line 147: | Line 159: | ||
* {{springer|title=Bijection|id=p/b016230}} | * {{springer|title=Bijection|id=p/b016230}} | ||
* {{MathWorld|title=Bijection|urlname=Bijection}} | * {{MathWorld|title=Bijection|urlname=Bijection}} | ||
* [ | * [https://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.] | ||
{{Set theory}} | {{Set theory}} | ||