Next: Some Counting Questions Up: Relations and Functions Previous: Relations and Functions

## Some Definitions

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?

Next: Some Counting Questions Up: Relations and Functions Previous: Relations and Functions

Carl Lee
Wed Sep 30 08:36:10 EDT 1998