Bijective function: Difference between revisions
imported>Richard Pinch (subpages) |
imported>Richard Pinch (copyedit) |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
''' | In [[mathematics]], a '''bijective function''' or '''bijection''' is a [[function (mathematics)|function]] that establishes a ''one-to-one correspondence'' between elements of two given [[Set (mathematics)|set]]s. Loosely speaking, ''all'' elements of those sets can be matched up in pairs so that each element of one set has its counterpart in the second set. | ||
More formally, a function <math>f</math> from set <math>X</math> to set <math>Y</math> is called a ''bijection'' if and only if for each <math>y</math> in <math>Y</math> there exists exactly one <math>x</math> in <math>X</math> such that <math>f(x)=y</math>. | More formally, a function <math>f</math> from set <math>X</math> to set <math>Y</math> is called a ''bijection'' if and only if for each <math>y</math> in <math>Y</math> there exists exactly one <math>x</math> in <math>X</math> such that <math>f(x)=y</math>. | ||
A bijective function from a set X to itself is also called a ''permutation'' of the set X. | |||
==Examples== | |||
* The function from set <math>\{1,2,3,4\}</math> to set <math>\{10,11,12,13\}</math> defined by the formula <math>f(x)=x+9</math> is a bijection. | |||
* A less obvious example is the function <math>f</math> from the set <math>X=\{(x,y)\}</math> of all ''pairs'' (x,y) of [[integer|positive integers]] to the set of all positive integers given by formula <math>f(x,y)=2^{x-1}\cdot (2y-1)</math>. | |||
* The function <math>\tan\colon(-\frac{\pi}{2},\frac{\pi}{2})\to R</math> is a bijection. | |||
== Composition== | == Composition== | ||
If <math>f\colon X\to Y</math> and <math>g\colon Y\to Z</math> are bijections than so is their composition <math>g\circ f\colon X\to Z</math>. | If <math>f\colon X\to Y</math> and <math>g\colon Y\to Z</math> are bijections than so is their composition <math>g\circ f\colon X\to Z</math>. | ||
A function <math>f\colon X\to Y</math> is a bijective function if and only if there exists function <math>g\colon Y \to X </math> such that their compositions <math>g\circ f</math> and <math>f\circ g</math> are [[identity function | A function <math>f\colon X\to Y</math> is a bijective function if and only if there exists function <math>g\colon Y \to X </math> such that their compositions <math>g\circ f</math> and <math>f\circ g</math> are [[identity function]]s on relevant sets. In this case we call function <math>g</math> an [[inverse function]] of <math> f</math> and denote it by <math>f^{-1}</math>. | ||
==Bijections and the concept of cardinality== | ==Bijections and the concept of cardinality== | ||
Two [[finite set]]s have the same number of elements if and only if there exists a bijection from one set to another. [[Georg Cantor]] generalized this simple observation to [[infinite set]]s and introduced the concept of cardinality of a set. We say that two set are ''equinumerous'' (sometimes also ''equipotent'' or ''equipollent'') if there exists a bijection from one set to another. If this is the case, we say the | Two [[finite set]]s have the same number of elements if and only if there exists a bijection from one set to another. [[Georg Cantor]] generalized this simple observation to [[infinite set]]s and introduced the concept of ''[[cardinality]]'' of a set. We say that two set are ''equinumerous'' (sometimes also ''equipotent'' or ''equipollent'') if there exists a bijection from one set to another. If this is the case, we say the sets have the same cardinality or the same [[cardinal number]]. Cardinality can be thought of as a generalization of number of elements of finite sets. | ||
== Some more examples == | == Some more examples == | ||
Revision as of 13:50, 2 November 2008
In mathematics, a bijective function or bijection is a function that establishes a one-to-one correspondence between elements of two given sets. Loosely speaking, all elements of those sets can be matched up in pairs so that each element of one set has its counterpart in the second set.
More formally, a function from set to set is called a bijection if and only if for each in there exists exactly one in such that .
A bijective function from a set X to itself is also called a permutation of the set X.
Examples
- The function from set to set defined by the formula is a bijection.
- A less obvious example is the function from the set of all pairs (x,y) of positive integers to the set of all positive integers given by formula .
- The function is a bijection.
Composition
If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\colon X\to Y} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\colon Y\to Z} are bijections than so is their composition Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\circ f\colon X\to Z} .
A function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\colon X\to Y} is a bijective function if and only if there exists function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\colon Y \to X } such that their compositions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\circ f} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\circ g} are identity functions on relevant sets. In this case we call function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} an inverse function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} and denote it by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{-1}} .
Bijections and the concept of cardinality
Two finite sets have the same number of elements if and only if there exists a bijection from one set to another. Georg Cantor generalized this simple observation to infinite sets and introduced the concept of cardinality of a set. We say that two set are equinumerous (sometimes also equipotent or equipollent) if there exists a bijection from one set to another. If this is the case, we say the sets have the same cardinality or the same cardinal number. Cardinality can be thought of as a generalization of number of elements of finite sets.
Some more examples
- A function is a bijection iff it is both an injection and a surjection.
- The quadratic function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\to R: x\mapsto x^2} is neither injection nor surjection, hence is not bijection. However if we change its domain and codomain to the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [0,+\infty)} than the function becomes bijective and the inverse function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt\colon [0,+\infty)\to[0,+\infty),\ x\mapsto \sqrt{x}} exists. This procedure is very common in mathematics, especially in calculus.
- A continuous function from the closed interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a,b]} in the real line to closed interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [c,d]} is bijection if and only if is monotonic funtion with f(a) = c and f(b) = d.