The Art and Craft of Problem Solving

146 CHAPTER 5 ALGEBRA

logarithm 10gbY' For example, if b = 3, then log 3 81 = 4 because x = 4 is the

unique^3 solution to 3x = 81.

Now consider the function x � logbx. Verify that the domain is the positive

reals, and the range is all reals.

Floors and Ceilings For each x E JR, define the floor function Lx J to be the

greatest integer less than or equal to x (another notation for Lx J is [xl, but this

is somewhat old-fashioned). For example, L3.7J = 3, L2J = 2, L -2.4J = -3.

Likewise, the ceiling function IX 1 is defined to be the smallest integer greater

than or equal to x. For example, 13. 11 = 4, 1 - 1. 21 = -1. For both functions,

the domain is JR and the range is Z. Both functions are onto and neither is

1-to-l. In fact, these functions are oo-to-l!

Sequences If the domain of a function / is the natural numbers N, then the

range values will be /( 1 ),/( 2 ),/( 3 ), .... Sometimes it is more convenient to

use the notation

/ (^1) '/2'/ 3 , ... ,
in which case the function is called a sequence. The domain need not be N
precisely; it may start with zero, and it may be finite. Sometimes an infinite
sequence is denoted by (Ii) r, or sometimes just by (Ii). Since the subscript

takes on integer values, the conventional letters used are i, j,k, l,m, n.^4

Indicator Functions Let U be a set with subset A. The indicator function

of A is denoted by lA and is a function with domain U and range {O, I} defined

by

1

( ) -

{ O ifx Ii A,

A x - I if x E A,

for each x E U. For example, if U = N and A is the set of primes, then lA (9) = °

and lA( 17 ) = 1.

Problems and Exercises

5.1.1 Let A,B respectively denote the even and odd

integers (remember, 0 is even).

(a) Is there a bijection from A to B?

(b) Is there a bijection from Z to A?

5.1.2 Prove that for any sets A,B,

(a) 1A (X)lB (X) = 1AnB(X),

(b) I -lA (x) = 1X(x).

In other words, the product of two indicator func­

tions is the indicator function of the intersection of the

two sets, and the indicator function of a set's comple­

ment is the difference of I and the indicator function

of that set.

5.1.3 True or false and why: 0 = {0}

5.1.4 Prove the following "dual" statements, which

show that, in some sense, both the rational and irra­

tional numbers are "grainy."

(a) Between any two rational numbers there is an

irrational number.

(^3) If we include complex numbers, the solution is no longer unique. See [2 (^9) ] for more information.
(^4) In the pioneering computer programming language FORTRAN, integer variables had to begin with the letters
I, J, K, L, M, or N (the mnemonic aid was "INteger.")