iPedia Free Information Center

Information about One To One Correspondence

In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that
f(x) = y.

Alternatively, f is bijective if it is a one-to-one correspondence between those sets; i.e., both one-to-one (injective) and onto (surjective).[1] (See also Bijection, injection and surjection.)

For example, consider the function succ, defined from the set of integers to , that to each integer x associates the integer succ(x) = x + 1. For another example, consider the function sumdif that to each pair (x,y) of real numbers associates the pair sumdif(x,y) = (x + y, x − y).

A bijective function is also called a permutation. This is more commonly used when X = Y. It should be noted that one-to-one function means one-to-one correspondence (i.e., bijection) to some authors, but injection to others. The set of all bijections from X to Y is denoted as XY.

Bijective functions play a fundamental role in many areas of mathematics, for instance in the definition of isomorphism (and related concepts such as homeomorphism and diffeomorphism), permutation group, projective map, and many others.

Composition and inverses

A function f is bijective if and only if its inverse relation f −1 is a function. In that case, f −1 is also a bijection.

The composition g o f of two bijections f XY and g YZ is a bijection. The inverse of g o f is (g o f)−1 = (f −1) o (g−1).

On the other hand, if the composition g o f of two functions is bijective, we can only say that f is injective and g is surjective.

A relation f from X to Y is a bijective function if and only if there exists another relation g from Y to X such that g o f is the identity function on X, and f o g is the identity function on Y. Consequently, the sets have the same cardinality.

Bijections and cardinality

If X and Y are finite sets, 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 very definition of "same number of elements", and generalising this definition to infinite sets leads to the concept of cardinal number, a way to distinguish the various sizes of infinite sets.

Examples and counterexamples

  • For any set X, the identity function idX from X to X, defined by idX(x) = x, is bijective.
  • The function f from the real line R to R defined by f(x) = 2x + 1 is bijective, since for each y there is a unique x = (y − 1)/2 such that f(x) = y.
  • The exponential function g : R R, with g(x) = ex, is not bijective: for instance, there is no x in R such that g(x) = −1, showing that g is not surjective. However if the codomain is changed to be the positive real numbers R+ = (0,+∞), then g becomes bijective; its inverse is the natural logarithm function ln.
  • The function h : R [0,+∞) with h(x) = x² is not bijective: for instance, h(−1) = h(+1) = 1, showing that h is not injective. However, if the domain too is changed to [0,+∞), then h becomes bijective; its inverse is the positive square root function.
  • is not a bijection because −1, 0, and +1 are all in the domain and all map to 0.
  • is not a bijection because π/3 and 2π/3 are both in the domain and both map to (√3)/2.

Properties

  • A function f from the real line R to R is bijective if and only if its plot is intersected by any horizontal line at exactly one point.
  • If X is a set, then the bijective functions from X to itself, together with the operation of functional composition (o), form a group, the symmetric group of X, which is denoted variously by S(X), SX, or X! (the last reads "X factorial").
  • For a subset A of the domain and subset B of the codomain we have:
|f(A)| = |A| and |f−1(B)| = |B|.
  • If X and Y are finite sets with the same cardinality, and f: X → Y, then the following are equivalent:
# f is a bijection.
# f is a surjection.
# f is an injection.
  • At least for a finite set S, there is a bijection between the set of possible total orderings of the elements and the set of bijections from S to S. That is to say, the number of permutations (another name for bijections) of elements of S is the same as the number of total orderings of that set -- namely, n!.
Notice that a one-to-one function is injective, but may fail to be surjective, while a one-to-one correspondence is both injective and surjective.<ref name="OneToOne" />

References

1. ^ (Note: the use of "one-to-one" to describe an injective function is problematic, since some authors understand it to mean one-to-one correspondence, i.e. a bijective function.)

Bijections and category theory

Formally, bijections are precisely the isomorphisms in the category Set of sets and functions

See also

Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
function expresses dependence between two quantities, one of which is given (the independent variable, argument of the function, or its "input") and the other produced (the dependent variable, value of the function, or "output").
..... Click the link for more information.
SET may stand for:
  • Sanlih Entertainment Television, a television channel in Taiwan
  • Secure electronic transaction, a protocol used for credit card processing,

..... Click the link for more information.
non-injective function.]] In mathematics, an injective function is a function which associates distinct arguments to distinct values. More precisely, a function f is said to be injective if it maps distinct x in the domain to distinct y
..... Click the link for more information.
non-surjective function.]] In mathematics, a function f is said to be surjective if its values span its whole codomain; that is, for every y in the codomain, there is at least one x in the domain such that f(x) = y .
..... Click the link for more information.
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
..... Click the link for more information.
The integers (from the Latin integer, which means with untouched integrity, whole, entire) are the set of numbers including the whole numbers (0, 1, 2, 3, …) and their negatives (0, −1, −2, −3, …).
..... Click the link for more information.
For other senses of this word, see permutation (disambiguation).
Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation.
..... Click the link for more information.
In mathematics, an isomorphism (Greek: isos "equal", and morphe "shape") is a bijective map f such that both f and its inverse f −1 are homomorphisms, i.e., structure-preserving mappings.
..... Click the link for more information.
Not to be confused with homomorphism.
Topological equivalence redirects here; see also topological equivalence (dynamical systems).
In the mathematical field of topology, a homeomorphism or topological isomorphism
..... Click the link for more information.
In mathematics, a diffeomorphism is a kind of isomorphism of smooth manifolds. It is an invertible function that maps one differentiable manifold to another, such that both the function and its inverse are smooth.
..... Click the link for more information.
In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M
..... Click the link for more information.
A projective transformation is a transformation used in projective geometry: it is the composition of a pair of perspective projections. It describes what happens to the perceived positions of observed objects when the point of view of the observer changes.
..... Click the link for more information.
“Iff” redirects here. For other uses, see IFF.
If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a logical connective between statements which means that the truth of either one of the statements
..... Click the link for more information.
In mathematics, the inverse relation of a binary relation is the relation taken 'backwards', as in changing the relation 'child of' to 'parent of'. In formal terms, if

is a binary relation with


then the inverse relation is


..... Click the link for more information.
composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite.
..... Click the link for more information.
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument.
..... Click the link for more information.
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument.
..... Click the link for more information.
In mathematics, a set is called finite if there is a bijection between the set and some set of the form where n is a natural number. (The value n = 0 is allowed; that is, the empty set is finite.) An infinite set is a set which is not finite.
..... Click the link for more information.
“Iff” redirects here. For other uses, see IFF.
If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a logical connective between statements which means that the truth of either one of the statements
..... Click the link for more information.
In mathematics, axiomatic set theory is a rigorous reformulation of set theory in first-order logic created to address paradoxes in naive set theory. The basis of set theory was created principally by the German mathematician Georg Cantor at the end of the 19th century.
..... Click the link for more information.
The word infinity comes from the Latin infinitas or "unboundedness." It refers to several distinct concepts (usually linked to the idea of "without end") which arise in philosophy, mathematics, and theology.
..... Click the link for more information.
cardinal numbers, or cardinals for short, are a generalized kind of number used to denote the size of a set, known as its cardinality. For finite sets the cardinality is given by a natural number, being simply the number of elements in the set.
..... Click the link for more information.
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Some examples are:
  • the set of all integers, , is a countably infinite set; and
  • the set of all real numbers is an uncountably infinite set.

..... Click the link for more information.
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument.
..... Click the link for more information.
In mathematics, the real line is simply the set R of real numbers. However, this term is usually used when R is to be treated as a space of some sort, such as a topological space or a vector space.
..... Click the link for more information.
The exponential function is one of the most important functions in mathematics. The application of this function to a value x is written as exp(x).
..... Click the link for more information.
The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e, where e is an irrational constant approximately equal to 2.718281828459.
..... Click the link for more information.
In mathematics, the real line is simply the set R of real numbers. However, this term is usually used when R is to be treated as a space of some sort, such as a topological space or a vector space.
..... Click the link for more information.
group is a set with a binary operation that satisfies certain axioms, detailed below. For example, the set of integers with addition is a group. The branch of mathematics which studies groups is called group theory.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter