Nuprl - One-to-One Correspondence

Definitions DiscreteMath Sections DiscrMathExt Doc

IF YOU CAN SEE THIS go to /sfa/Nuprl/Shared/Xindentation_hack_doc.html

One-to-One Correspondence

A one-to-one correspondence between two classes is a way of matching them member-for-member. Examples:

* At an event with assigned seating one would expect a one-to-one correspondence between the seats and the tickets, the correspondence being between each seat and the ticket printed with its location code.

* Planning for a formal dinner entails choosing a one-to-one correspondence between the guests and their places at the table.

* Counting a finite class of objects typically consists of finding a one-to-one correspondence between the items of the class and the numbers from 1 to however many there are.

* A major use for finding one-to-one correspondences is to establish, without actually counting, that some class has the same size as another class of known size.

* In programming, one often introduces, what are called variously, pointers, indices, or handles to be used in place of data objects they point to. The relation between these pointers and their objects is often expected to be a one-to-one correspondence.

Notice that a one-to-one correspondence between two classes will not be the only one if the classes have more than one member each.

As usual, this concept of a method for matching is not built-in to our growing library of mathematics, and may be introduced by definition in a variety of ways.

We shall use functions for these methods of matching: a function will be used to match each input with its output. For example, the function f such that f(n) = 2n, matches each natural number with its double, and is a one-to-one correspondence between the natural numbers , and the even natural numbers, {i:| is_even(i) }.

But not every function expresses a one-to-one correspondence. For example, f , such that f(i) = i for even i, and f(i) = 2i for odd i. Notice that, again, every natural number gets mapped to an even number, and every even number is mapped to itself, but it is not a one-to-one correspondence because both 1 and 2 get "matched" against 2.

So, both of these functions are in {i:| is_even(i) }, but we need something more to narrow such functions to those that are one-to-one correspondences. This can be done is various ways. See One-to-One Correspondence via Inverses for the our first approach via inverse functions.

To see a discussion of the concept of Counting and its relation to One-to-One Correspondence, see Introduction to Counting.

About:

IF YOU CAN SEE THIS go to /sfa/Nuprl/Shared/Xindentation_hack_doc.html

Definitions DiscreteMath Sections DiscrMathExt Doc

*	At an event with assigned seating one would expect a one-to-one correspondence between the seats and the tickets, the correspondence being between each seat and the ticket printed with its location code.

*	Planning for a formal dinner entails choosing a one-to-one correspondence between the guests and their places at the table.

*	Counting a finite class of objects typically consists of finding a one-to-one correspondence between the items of the class and the numbers from 1 to however many there are.

*	A major use for finding one-to-one correspondences is to establish, without actually counting, that some class has the same size as another class of known size.

*	In programming, one often introduces, what are called variously, pointers, indices, or handles to be used in place of data objects they point to. The relation between these pointers and their objects is often expected to be a one-to-one correspondence.