355
APPENDIXES
APPENDIX 1 Axioms for the Real Numbers and the Positive Integers
2.This proof is similar to the proof of Theorem 2, that the additive inverse of each real number is unique. In
fact, we can just mimic that proof, changing addition to multiplication and 0 to 1 throughout. Let xbe a
nonzero real number. Suppose that yandzare both multiplicative inverses of x. Then
y= 1y(by the multiplicative identity law)
= (zx)y(because zis a multiplicative inverse of x)
=z(xy) (by the associative law for multiplication)
=z1 (because yis a multiplicative inverse of x)
=z(by the multiplicative identity law) :
It follows that y=z.
4.To show that a number equals (x+y), the additive inverse of x+y, it suces to show that this number
plusx+yequals 0, because Theorem 2 guarantees that additive inverses are unique. We have
(( x) + ( y)) + ( x+y) = (( y) + ( x)) + ( x+y) (by the commutative law)
= ( y) + (( x) + (x+y)) (by the associative law)
= ( y) + (( x) +x) +y) (by the associative law)
= ( y) + (0 + y) (by the additive inverse law)
= ( y) +y(by the additive identity law)
= 0 (by the additive inverse law) ;
as desired.
6.Ifx+z=y+z, then adding the additive inverse of zto both sides gives another equality. But ( x+z)+( z) =
x+ (z+ ( z)) =x+ 0 = xby the associative, inverse, and identity laws, and similarly for the right-hand side.
Thus x=y.
8.Ifx=y, then by de nition x y=x+ ( y) =x+ ( x). But this equals 0 by the additive inverse law.
Conversely, if x y=x+ ( y) = 0, then xis the additive inverse of y(additive inverses are unique by
Theorem 2). Thus x= ( y). But by Exercise 7, ( y) =y, so we have proved that x=y.
10.Since multiplicative inverses are unique (Theorem 4), it suces to show that ( y=x)(x=y) = 1, that is,
(y(1=x))(x(1=y)) = 1. Applying the associative law twice gives us ( y(1=x))(x(1=y)) =y(((1=x)x)(1=y)),
which equals y(1(1=y)) =y(1=y) = 1, as desired.
12.If 1=xwere equal to 0, then we would have 1 = (1 =x)x= 0x= 0 (by Theorem 5), contradicting the axiom
that 06= 1. If 1 =xwere less than 0, then we could multiply both sides by the positive number x(by the
multiplicative compatibility law) to get 1 <0x= 0 (by Theorem 5), which we saw in the proof of Theorem 7
cannot be true. Therefore by the trichotomy law, 1 =x > 0. 356 Appendixes
14.This follows immediately from the multiplicative compatibility law (and the commutative law and Theorem 5),
by multiplying both sides of 0 > ybyx.
16.Ifx= 0, then x2= 0 by Theorem 5. (Note that x2is just a shorthand notation for xx.) This proves the
\if" part by contraposition, since if x2= 0, then x2is not greater than 0 (by trichotomy). For the \only
if" part, it follows from the multiplicative compatibility law that if x > 0 then xx > 0, and it follows
from Exercise 15 that if x <0 then xx >0. By trichotomy these are the only two cases that need to be
considered.
18.By Exercise 12, if xandyare positive, so are 1 =xand 1 =y. Therefore we can use the multiplicative
compatibility law to multiply both sides of x < y by 1=xand then by 1 =y, and after some simpli cations
(using the commutative, associative, inverse, and identity laws) we reach 1 =y < 1=x, as desired.
20.Call the numbers aandb, with a < b . Ifais negative and bis positive, then 0 is the desired real number.
Ifa < b < 0, then if we can nd a rational number cbetween band a, then the rational number c
will be between aandb. Therefore we can restrict our attention to the case in which aandbare positive.
Notice that b ais a positive real number. By Exercise 19 we can nd an integer nsuch that n(b a)>1,
which is equivalent to nb > na+ 1. Now look at the set of natural numbers that are greater than na. By
the Archimedean property, this set is nonempty, and so by the well-ordering property there is a least positive
integer msuch that m > na. We claim that m < nb. If not, then we have mnb > na+ 1, so
m 1> na, contradicting the choice of m(because m 1 is positive). Therefore we have proved that
na < m < nb, from which it follows that a < m=n < b , and m=n is our desired rational number.
22.The proof practically writes itself if we just use the de nitions. First note that the restriction that the second
entry is nonzero is preserved by these operations, because if x6= 0 and z6= 0, then by Theorem 6 we know
that xz6= 0. We want to show that if ( w; x)(w0; x0) and ( y; z)(y0; z0), then ( wz+xy; xz)
(w0z0+x0y0; x0z0) and that ( wy; xz)(w0y0; x0z0). Thus we are given that wx0=xw0and
that yz0=zy0, and we want to show that ( wz+xy)(x0z0) = ( xz)(w0z0+x0y0) and that
(wy)(x0z0) = (xz)(w0y0). For the second of the desired conclusions, multiply together the two given
equations, and we get the desired equality (applying the associative and commutative laws). For the rst, if
we multiply out the two sides (i.e., use the distributive law), then we see that the expression on the right is
obtained from the expression on the left by making the substitutions implied by the given equations (again
applying the associative and commutative laws as needed).
APPENDIX 2 Exponential and Logarithmic Functions
2. a) Since 1024 = 210, we know that log21024 = 10.
b)Since 1 =4 = 2 2, we know that log2(1=4) = 2.
c)Note that 4 = 22and 8 = 23. Therefore 2 = 41=2, so 8 = (41=2)3= 43=2. Therefore log48 = 3 =2.
4.We show that each side is equal to the same quantity.
alogbc=
blogbalogbc=b(logba)(logbc)
clogba=
blogbclogba=b(logbc)(logba)
6.Each graph looks exactly like Figure 2, with the scale on the x-axis changed so that the point ( b;1) is on the
curve in each case. 357
APPENDIX 3 Pseudocode
2.We need three assignment statements to do the interchange, in order not to lose one of the values.
procedure interchange (x; y)
temp :=x
x:=y
y:=temp 1
CHAPTER 1
The Foundations: Logic and Proofs
SECTION 1.1 Propositional Logic
2.Propositions must have clearly de ned truth values, so a proposition must be a declarative sentence with no
free variables.
a)This is not a proposition; it's a command.
b)This is not a proposition; it's a question.
c)This is a proposition that is false, as anyone who has been to Maine knows.
d)This is not a proposition; its truth value depends on the value of x.
e)This is a proposition that is false.
f)This is not a proposition; its truth value depends on the value of n.
4. a) Janice does not have more Facebook friends than Juan.
b)Quincy is not smarter than Venkat.
c)Zelda does not drive more miles to school than Paola.
d)Briana does not sleep longer than Gloria.
6. a) Jennifer and Teja are not friends.
b)There are not 13 items in a baker's dozen. (Alternatively: The number of items in a baker's dozen is not
equal to 13.)
c)Abby sent fewer than 101 text messages yesterday. Alternatively, Abby sent at most 100 text messages
yesterday.
d)121 is not a perfect square.
8. a) True, because 288 >256 and 288 >128.
b)True, because C has 5 MP resolution compared to B's 4 MP resolution. Note that only one of these
conditions needs to be met because of the word or.
c)False, because its resolution is not higher (all of the statements would have to be true for the conjunction
to be true).
d)False, because the hypothesis of this conditional statement is true and the conclusion is false.
e)False, because the rst part of this biconditional statement is false and the second part is true.
10. a) I did not buy a lottery ticket this week.
b)Either I bought a lottery ticket this week, or [in the inclusive sense] I won the million dollar jackpot on
Friday.
c)If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
d)I bought a lottery ticket this week, and I won the million dollar jackpot on Friday.
e)I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.
f)If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.
g)I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday.
APPENDIXES
APPENDIX 1 Axioms for the Real Numbers and the Positive Integers
2.This proof is similar to the proof of Theorem 2, that the additive inverse of each real number is unique. In
fact, we can just mimic that proof, changing addition to multiplication and 0 to 1 throughout. Let xbe a
nonzero real number. Suppose that yandzare both multiplicative inverses of x. Then
y= 1y(by the multiplicative identity law)
= (zx)y(because zis a multiplicative inverse of x)
=z(xy) (by the associative law for multiplication)
=z1 (because yis a multiplicative inverse of x)
=z(by the multiplicative identity law) :
It follows that y=z.
4.To show that a number equals (x+y), the additive inverse of x+y, it suces to show that this number
plusx+yequals 0, because Theorem 2 guarantees that additive inverses are unique. We have
(( x) + ( y)) + ( x+y) = (( y) + ( x)) + ( x+y) (by the commutative law)
= ( y) + (( x) + (x+y)) (by the associative law)
= ( y) + (( x) +x) +y) (by the associative law)
= ( y) + (0 + y) (by the additive inverse law)
= ( y) +y(by the additive identity law)
= 0 (by the additive inverse law) ;
as desired.
6.Ifx+z=y+z, then adding the additive inverse of zto both sides gives another equality. But ( x+z)+( z) =
x+ (z+ ( z)) =x+ 0 = xby the associative, inverse, and identity laws, and similarly for the right-hand side.
Thus x=y.
8.Ifx=y, then by de nition x y=x+ ( y) =x+ ( x). But this equals 0 by the additive inverse law.
Conversely, if x y=x+ ( y) = 0, then xis the additive inverse of y(additive inverses are unique by
Theorem 2). Thus x= ( y). But by Exercise 7, ( y) =y, so we have proved that x=y.
10.Since multiplicative inverses are unique (Theorem 4), it suces to show that ( y=x)(x=y) = 1, that is,
(y(1=x))(x(1=y)) = 1. Applying the associative law twice gives us ( y(1=x))(x(1=y)) =y(((1=x)x)(1=y)),
which equals y(1(1=y)) =y(1=y) = 1, as desired.
12.If 1=xwere equal to 0, then we would have 1 = (1 =x)x= 0x= 0 (by Theorem 5), contradicting the axiom
that 06= 1. If 1 =xwere less than 0, then we could multiply both sides by the positive number x(by the
multiplicative compatibility law) to get 1 <0x= 0 (by Theorem 5), which we saw in the proof of Theorem 7
cannot be true. Therefore by the trichotomy law, 1 =x > 0. 356 Appendixes
14.This follows immediately from the multiplicative compatibility law (and the commutative law and Theorem 5),
by multiplying both sides of 0 > ybyx.
16.Ifx= 0, then x2= 0 by Theorem 5. (Note that x2is just a shorthand notation for xx.) This proves the
\if" part by contraposition, since if x2= 0, then x2is not greater than 0 (by trichotomy). For the \only
if" part, it follows from the multiplicative compatibility law that if x > 0 then xx > 0, and it follows
from Exercise 15 that if x <0 then xx >0. By trichotomy these are the only two cases that need to be
considered.
18.By Exercise 12, if xandyare positive, so are 1 =xand 1 =y. Therefore we can use the multiplicative
compatibility law to multiply both sides of x < y by 1=xand then by 1 =y, and after some simpli cations
(using the commutative, associative, inverse, and identity laws) we reach 1 =y < 1=x, as desired.
20.Call the numbers aandb, with a < b . Ifais negative and bis positive, then 0 is the desired real number.
Ifa < b < 0, then if we can nd a rational number cbetween band a, then the rational number c
will be between aandb. Therefore we can restrict our attention to the case in which aandbare positive.
Notice that b ais a positive real number. By Exercise 19 we can nd an integer nsuch that n(b a)>1,
which is equivalent to nb > na+ 1. Now look at the set of natural numbers that are greater than na. By
the Archimedean property, this set is nonempty, and so by the well-ordering property there is a least positive
integer msuch that m > na. We claim that m < nb. If not, then we have mnb > na+ 1, so
m 1> na, contradicting the choice of m(because m 1 is positive). Therefore we have proved that
na < m < nb, from which it follows that a < m=n < b , and m=n is our desired rational number.
22.The proof practically writes itself if we just use the de nitions. First note that the restriction that the second
entry is nonzero is preserved by these operations, because if x6= 0 and z6= 0, then by Theorem 6 we know
that xz6= 0. We want to show that if ( w; x)(w0; x0) and ( y; z)(y0; z0), then ( wz+xy; xz)
(w0z0+x0y0; x0z0) and that ( wy; xz)(w0y0; x0z0). Thus we are given that wx0=xw0and
that yz0=zy0, and we want to show that ( wz+xy)(x0z0) = ( xz)(w0z0+x0y0) and that
(wy)(x0z0) = (xz)(w0y0). For the second of the desired conclusions, multiply together the two given
equations, and we get the desired equality (applying the associative and commutative laws). For the rst, if
we multiply out the two sides (i.e., use the distributive law), then we see that the expression on the right is
obtained from the expression on the left by making the substitutions implied by the given equations (again
applying the associative and commutative laws as needed).
APPENDIX 2 Exponential and Logarithmic Functions
2. a) Since 1024 = 210, we know that log21024 = 10.
b)Since 1 =4 = 2 2, we know that log2(1=4) = 2.
c)Note that 4 = 22and 8 = 23. Therefore 2 = 41=2, so 8 = (41=2)3= 43=2. Therefore log48 = 3 =2.
4.We show that each side is equal to the same quantity.
alogbc=
blogbalogbc=b(logba)(logbc)
clogba=
blogbclogba=b(logbc)(logba)
6.Each graph looks exactly like Figure 2, with the scale on the x-axis changed so that the point ( b;1) is on the
curve in each case. 357
APPENDIX 3 Pseudocode
2.We need three assignment statements to do the interchange, in order not to lose one of the values.
procedure interchange (x; y)
temp :=x
x:=y
y:=temp 1
CHAPTER 1
The Foundations: Logic and Proofs
SECTION 1.1 Propositional Logic
2.Propositions must have clearly de ned truth values, so a proposition must be a declarative sentence with no
free variables.
a)This is not a proposition; it's a command.
b)This is not a proposition; it's a question.
c)This is a proposition that is false, as anyone who has been to Maine knows.
d)This is not a proposition; its truth value depends on the value of x.
e)This is a proposition that is false.
f)This is not a proposition; its truth value depends on the value of n.
4. a) Janice does not have more Facebook friends than Juan.
b)Quincy is not smarter than Venkat.
c)Zelda does not drive more miles to school than Paola.
d)Briana does not sleep longer than Gloria.
6. a) Jennifer and Teja are not friends.
b)There are not 13 items in a baker's dozen. (Alternatively: The number of items in a baker's dozen is not
equal to 13.)
c)Abby sent fewer than 101 text messages yesterday. Alternatively, Abby sent at most 100 text messages
yesterday.
d)121 is not a perfect square.
8. a) True, because 288 >256 and 288 >128.
b)True, because C has 5 MP resolution compared to B's 4 MP resolution. Note that only one of these
conditions needs to be met because of the word or.
c)False, because its resolution is not higher (all of the statements would have to be true for the conjunction
to be true).
d)False, because the hypothesis of this conditional statement is true and the conclusion is false.
e)False, because the rst part of this biconditional statement is false and the second part is true.
10. a) I did not buy a lottery ticket this week.
b)Either I bought a lottery ticket this week, or [in the inclusive sense] I won the million dollar jackpot on
Friday.
c)If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
d)I bought a lottery ticket this week, and I won the million dollar jackpot on Friday.
e)I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.
f)If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.
g)I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday.
