Difference between revisions of "Correspondence"
m |
|||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | == Lists | + | A '''correspondence''' is a relation between two [[set]]s such that each member in one set corresponds to <math>n</math> members in the other set, where <math>n</math> commonly equals <math>1</math>. |
| − | Consider the task of counting the number of integers between 14 and 103 inclusive. We could simply list those [[integers]] and count them. However, we can renumber those integers so that they correspond to the [[counting numbers]] (positive integers), starting with 1. In this | + | == Lists - the beginning == |
| + | Consider the task of counting the number of integers between 14 and 103 inclusive. We could simply list those [[integers]] and count them. However, we can renumber those integers so that they correspond to the [[counting numbers]] (positive integers), starting with 1. In this correspondence, 14 corresponds to 1 (for the 1st integer in the list), 15 with 2, 16 with 3, etc. The relationship between the members of each pair is that the second is 13 less than the first. So, we know that 103 corresponds to the 103 - 13 = 90th integer in the list. Thus, the list is 90 integers long. | ||
Note that <math>13 = 14 - 1</math>, or 1 less than the first integer in the list. If we start our list with <math>n</math> and end with <math>m</math> (i.e. m and n inclusive), the number of integers in the list is | Note that <math>13 = 14 - 1</math>, or 1 less than the first integer in the list. If we start our list with <math>n</math> and end with <math>m</math> (i.e. m and n inclusive), the number of integers in the list is | ||
| − | <math> | + | <math>m - (n -1) = m - n + 1.</math> |
== One-to-One Correspondence == | == One-to-One Correspondence == | ||
| − | A '''one-to-one correspondence''', or ''bijection'', is a function which is both [[injection|injective]] (or ''one-to-one'') and [[surjection|surjective]] (or ''onto''). A function | + | {{main|Bijection}} |
| + | |||
| + | A '''one-to-one correspondence''', or ''bijection'', is a function which is both [[injection|injective]] (or ''one-to-one'') and [[surjection|surjective]] (or ''onto''). A function has a [[Function#The_Inverse_of_a_Function|two-sided inverse]] exactly when it is a bijection between its [[domain]] and [[range]]. | ||
One-to-one correspondences are useful in a variety of contexts. In particular, bijections are frequently used in [[combinatorics]] in order to count the elements of a set whose size is unknown. Bijections are also very important in [[set theory]] when dealing with arguments concerning [[infinite]] sets. | One-to-one correspondences are useful in a variety of contexts. In particular, bijections are frequently used in [[combinatorics]] in order to count the elements of a set whose size is unknown. Bijections are also very important in [[set theory]] when dealing with arguments concerning [[infinite]] sets. | ||
== Examples == | == Examples == | ||
| − | + | === Intermediate === | |
| − | * [ | + | * [[2006 AIME II Problems/Problem 4]] |
| − | * [ | + | * [[2001 AIME I Problems/Problem 6]] |
== See also == | == See also == | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
| + | |||
| + | [[Category:Combinatorics]] | ||
| + | [[Category:Definition]] | ||
Latest revision as of 16:17, 13 February 2009
A correspondence is a relation between two sets such that each member in one set corresponds to 
members in the other set, where commonly equals 
.
Lists - the beginning
Consider the task of counting the number of integers between 14 and 103 inclusive. We could simply list those integers and count them. However, we can renumber those integers so that they correspond to the counting numbers (positive integers), starting with 1. In this correspondence, 14 corresponds to 1 (for the 1st integer in the list), 15 with 2, 16 with 3, etc. The relationship between the members of each pair is that the second is 13 less than the first. So, we know that 103 corresponds to the 103 - 13 = 90th integer in the list. Thus, the list is 90 integers long.
Note that 
, or 1 less than the first integer in the list. If we start our list with and end with 
(i.e. m and n inclusive), the number of integers in the list is
One-to-One Correspondence
- Main article: Bijection
A one-to-one correspondence, or bijection, is a function which is both injective (or one-to-one) and surjective (or onto). A function has a two-sided inverse exactly when it is a bijection between its domain and range.
One-to-one correspondences are useful in a variety of contexts. In particular, bijections are frequently used in combinatorics in order to count the elements of a set whose size is unknown. Bijections are also very important in set theory when dealing with arguments concerning infinite sets.
