Difference between revisions of "Bijection"

Revision as of 02:53, August 22, 2010

@@ Line 1: / Line 1: @@
-{{Math-m}}
+[[Category:Set Theory]]
-A '''bijection''' or '''bijective function''' is a mapping (or [[function]]) between two [[set]]s, that is "one-to-one" and "onto".  A function that is "one-to-one", more formally known as an [[Injection (mathematics)|injection]] or an injective function, never maps two different points in the domain to the same point in the range.  A function that is "onto", more formally known as a [[surjection]] or a surjective function, "hits" every point in the range.  That is, no point in the range isn't mapped to.
-In other words, a bijection from set A to set B is a mapping such that every element in A is mapped to a distinct element in B, and every element in B has a distinct element in A mapped to it.  For example, one bijection between the sets {X, Y, Z} and {1, 2, 3}, maps: X to 1, Y to 2, and Z to 3.  If we were use this map instead: X to 1, Y to 2, and Z also to 2, it would fail to be one-to-one because Y and Z both map to the same result, and it would fail to be onto because nothing maps to 3.
-A bijection is also known as a "one-to-one correspondence".  It specifies a precise correspondence between the points of the domain set and the points of the range set.  As such, it can be inverted&mdash;there is another map (also a bijection) going in the other direction, that returns from a range point to its domain point.
-The property of two sets being in a one-to-one correspondence is very interesting to mathematicians.  Such sets are said to have the same '''[[cardinality]]'''.  This means, roughly, that they have the same "size", but there are some subtle aspects to cardinality.  If the sets are finite, then they truly have the same number of elements.  But correspondences between [[infinite]] sets have some subtle aspects, some of which might seem counterintuitive.
-For example, there is a bijection between the integers and the even integers&mdash;it maps every integer x to the even integer 2x.  Notice that this satisfies the definition of bijection.  This means that the integers have the same cardinality as the even integers, even though the former set is "obviously bigger" than the latter.  This leads to the idea, which must be interpreted with a mathematical grain of salt, that "infinity times two is infinity".
-Does this mean that all infinite sets have the same cardinality, that is, can be placed into one-to-one correspondence with each other?  No.  Having the same cardinality as the integers is a very important property, and such sets are called "[[countable|countable]]".  But there are "uncountable" sets that can't be placed into one-to-one correspondence with the integers.  The [[real numbers]] are the best-known example of such.  The proof that the real numbers are not countable is the celebrated "[[Diagonalization|Cantor diagonalization theorem]]".
-[[Category:Mathematics]]
-[[Category:Set theory]]

Difference between revisions of "Bijection"

Revision as of 02:53, August 22, 2010

Navigation menu

Search