The Art and Craft of Problem Solving

5.1 SETS, NUMBERS, AND FUNCTIONS 145

closure. The natural numbers N are not closed under subtraction, Z is not closed under
division, and neither Ql nor JR is closed under square roots.
Given two sets A and B (which mayor may not be equal), the Cartesian product
A x B is defined to be the set of all ordered pairs of the form (a, b) where a E A and
bE B. Formally, we define

A x B:= {(a, b) : a E A,b E B}.

For example, if A = {I, 2, 3} and B = {Paris, London}, then

A x B = {( I, Paris), (2, Paris), (3, Paris), (1, London), (2, London), (3, London)}.

Functions

Given two sets A and B, we can assign a specific element of B to each element of A.
For example, with the sets above, we can assign Paris to both 1 and 2, and London to

3. In other words, we are specifying the subset

{( 1 , Paris), (2, Paris), (3, London)}

ofAxB.
Any subset of A x B with the property that each a E A is paired with exactly one
bE B is called a function from A to B. Typically, we write I: A ---+ B to indicate the
function whose name is 1 with domain set A and range in the set B. We write I(a) to
indicate the element in B that corresponds to a E A, and we often call I{a) the image
of a. Informally, a function 1 is just a "rule" that assigns a B-value I(a) to each A­
value a. Here are several important examples that also develop a few more concepts
and notations.

Squaring Define 1 : JR ---+ JR by I(x) = x^2 for each x E JR. An alternate no­

tation is to write x !---* x^2 or x L x^2. Notice that the range of 1 is not all of JR,

but just the non-negative real numbers. Also notice that I{x) = 9 has two so­

lutions x = ±3. The set {3, -3} is called the inverse image of 9 and we write

1-^1 (9) = {3,-3}. Notice that an inverse image is not an element, but a set,

because in general, as in this example, the inverse image may have more than

one element.

Cubing Define g : JR ---+ JR by x !---* x^3 for each x E JR. In this case, the range is

all of JR. We call such functions onto. Moreover, each inverse image contains

just one element (since the cube root of a negative number is negative and the

cube root of a positive number is positive). Functions with this property are

called I-to-l (the function 1 above is 2-to-l, except at 0, where it is I-to-1). A

function like g, which is both I-to-l and onto, is also called a 1-1 correspon­

dence or a bijection.

Exponentiation and Logarithms Fix a positive real number b i= 1. Define

h : JR ---+ JR by h(x) = lr for each x E JR. The range is all positive real numbers

(but not zero), so h is not onto. On the other hand, h is I-to-l, for if y > 0, then

there is exactly one solution x to the equation lr = y. We call this solution the