One–to–one Correspondence

views updated

One-to-one Correspondence

In mathematics, one-to-one correspondence refers to a situation in which the members of one set (call it A) can be evenly matched with the members of a second set (call it B). Evenly matched means that each member of A is paired with one and only one member of B, each member of B is paired with one and only one member of A, and none of the members from either set are left unpaired. The result is that every member of A is paired with exactly one member of B, and every member of B is paired with exactly one member of A. One-to-one correspondence is also called bijective.

In terms of ordered pairs (a,b), where a is a member of A and b is a member of B, no two ordered pairs created by this matching process have the same first element and no two have the same second element. When this type of matching can be shown to exist, mathematicians say that: a one-to-one correspondence exists between the sets A and B. Any two sets for which a one-to-one correspondence exists have the same cardinality; that is, they have the same number of members. On the other hand, a one-to-one correspondence can be shown to exist between any two sets that have the same cardinality, as can easily be seen for finite sets (sets with a specific number of members). For example, given the sets A = and B = a one-to-one correspondence can be established by associating the first members of each set, then the

One–to–one correspondance
Positive Integers→	Odd Positive Integers→	Positive Integers
x	y =2x - 1	y +1
1	1	1
2	3	2
3	5	3
4	7	4
5	9	5

second members, then the third, and so on until each member of A is associated with a member of B. Since the two sets have the same number of members no member of either set will be left unpaired. In addition, because the two sets have the same number of members, there is no need to pair one member of A with two different members of B, or vice versa. Thus, a one-to-one correspondence exists.

Another method of establishing a one-to-one correspondence between A and B is to define a one-to-one function. For example, using the same sets A and B, the function that associates each member of A with a member in B that is twice as big is such a function. This type of function is called a one-to-one function because it is reversible. In mathematical terminology, its inverse is also a function. It could just as well be defined so it maps each member of B onto a unique member of A by associating with each member of B that member of A that is half its value.

One-to-one functions are particularly useful in determining whether a one-to-one correspondence exists between infinite sets (sets with so many members that there is always another one). For example, let X be the set of all positive integers, X = 1, 2, 3, 4, 5, . . ., (the three dots are intended to indicate that the listing goes on forever), and let Y be the set of odd positive integers Y = 1, 3, 5, . . .. At first glance, it might be thought that the set of odd positive integers has half as many members as the set of all positive integers. However, every odd positive integer, call it y, can be associated with a unique positive integer, call it x, by the function, f (x) = y = (2x - 1). On the other hand, every positive integer can be associated with a unique odd positive integer using the inverse function, namely x = (1/2)(y + 1).

The function f is a one-to-one function and so a one-to-one correspondence exists between the set of

KEY TERMS

Function —A function is a set of ordered pairs (a,b) such that: a is a member of some set A and b is a member of some other set B, each pair of elements a and b are related to one another in the same fashion, and no two pairs have the same first element.

Set —A set is a collection of things called members or elements of the set. In mathematics, the members of a set will often be numbers.

positive integers and the set of odd positive integers; that is, there are just as many odd positive integers as there are positive integers all together. Carrying this notion further, German mathematician Georg Ferdinand Ludwig Philipp Cantor (1845–1918) showed that it is also possible to find a one-to-one correspondence between the integers and the rational numbers (numbers that can be expressed as the ratio of two whole numbers). However, Cantor also showed that it is not possible to find a one-to-one correspondence between the integers and the real numbers (the real numbers are all of the integers plus all the decimals, both repeating and nonrepeating). In fact, he showed that there are orders of infinity, and invented the transfinite numbers to describe them.