Bijective function: Difference between revisions
imported>Wojciech Świderski (do check language, please...) |
imported>Wojciech Świderski m (x->x-1) |
||
| Line 5: | Line 5: | ||
For example, a function from set <math>\{1,2,3,4\}</math> to set <math>\{10,11,12,13\}</math> defined by formula <math>f(x)=x+9</math> is bijection. | For example, a function from set <math>\{1,2,3,4\}</math> to set <math>\{10,11,12,13\}</math> defined by formula <math>f(x)=x+9</math> is bijection. | ||
Less obvious example is 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\cdot (2y-1)</math>. | Less obvious example is 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>. | ||
Function <math>\tan\colon(-\frac{\pi}{2},\frac{\pi}{2})\to R</math> is another example of bijection. | Function <math>\tan\colon(-\frac{\pi}{2},\frac{\pi}{2})\to R</math> is another example of bijection. | ||
Revision as of 11:15, 13 July 2008
Bijective function 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 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} from 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 X} to 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 Y} is called a bijection if and only if for each 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 y} in 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 Y} there exists exactly one 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 x} in 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 X} such that 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(x)=y} .
For example, a function from 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 \{1,2,3,4\}} to 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 \{10,11,12,13\}} defined by formula 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(x)=x+9} is bijection.
Less obvious example is 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} from 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 X=\{(x,y)\}} of all pairs (x,y) of positive integers to the set of all positive integers given by formula 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(x,y)=2^{x-1}\cdot (2y-1)} .
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 \tan\colon(-\frac{\pi}{2},\frac{\pi}{2})\to R} is another example of bijection.
A bijective function from a set X to itself is also called a permutation of the set X.
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 set have the same cardinality or the same cardinal number. Cardinal number can be thought of as a generalization of number of elements of final set.
Some more examples
- A function is a bijection is both injection and surjection.
- The quadratic function <maht>R\to R: x\mapsto x^2</math> 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 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]} of real line onto 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.