The *Cartesian product* of two sets *X* and *Y* is the set

That is, it is the set of all ordered pairs where the first coordinate
comes from *X* and the second coordinate comes from *Y*.

A *relation* between two sets *X* and *Y* is *any* subset of
. That is, it is any subset of ordered pairs, where the
first coordinates are drawn from *X* and the second coordinates are
drawn from *Y*.
The *domain* of a relation *S* is the set of first coordinates
in the relation; i.e.,

The *range* of a relation *S* is the set of second coordinates
in the relation; i.e.,

Here are my high school teacher's definitions:
A *ficklepicker* of a relation
is a first coordinate that appears in more than
one ordered pair of the relation.
A *function* is a relation with no ficklepickers.

If *f* is a function, then we write, for example, to mean
that the ordered pair is in the function.
When we write is a function, we mean that the
domain of *f* is the entire set *X*, and the range of *f* is contained
in (but not necessarily equal to) *Y*.

A function is *one-to-one* or an *injection*
if no element of the range is paired with more than one element of *X*.
A function is *onto* or a *surjection* if
its range is all of *Y*.
A function is *one-to-one and onto*
or a *bijection* if it is both one-to-one and onto.

If is a bijection and *X* and *Y* are both
finite sets, then we quite naturally say that *X* and *Y* are the same
size.
Try to find a bijection between the set of natural numbers and the set
of integers. Do you feel comfortable saying that and are
the same size?

Wed Sep 30 08:36:10 EDT 1998