Difference between revisions of "Bijection"
(2x doesn't equal x - use your head) |
m |
||
| Line 1: | Line 1: | ||
| − | A '''bijection''' is a [[injectivity|one-to-one]], [[surjectivity|onto]] [[mapping]] between two [[set]]s. In other words, a bijection between sets A and B is a mapping such that every element in | + | A '''bijection''' is a [[injectivity|one-to-one]], [[surjectivity|onto]] [[mapping]] between two [[set]]s. In other words, a bijection between sets A and B is a mapping such that every element in set A is mapped to a distinct element in set B, and every element in set B has a distinct element in the set A mapped to it. For example, one bijection between the sets {A, B, C} and {1, 2, 3}, maps: A to 1, B to 2, and 3 to C. |
If there is a bijection between two sets, then we say that they have the same [[cardinality]], or size. | If there is a bijection between two sets, then we say that they have the same [[cardinality]], or size. | ||
Revision as of 15:00, January 17, 2009
A bijection is a one-to-one, onto mapping between two sets. In other words, a bijection between sets A and B is a mapping such that every element in set A is mapped to a distinct element in set B, and every element in set B has a distinct element in the set A mapped to it. For example, one bijection between the sets {A, B, C} and {1, 2, 3}, maps: A to 1, B to 2, and 3 to C.
If there is a bijection between two sets, then we say that they have the same cardinality, or size.
Bijections between infinite sets are particularly interesting, as they produce some counterintuitive results. For instance, there is a bijection between the integers and the even integers that maps every integer x to the even integer 2x. Notice that this satisfies the definition of bijection, even though it would then seem to imply that the integers and the even integers have the same size. However, since both sets are of infinite size, it merely illustrates the idea that "infinity times two is infinity".
The existence of a bijection from one set to the other also implies that a converse bijection exists.