355 Appendixes
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 x be a
nonzero real number. Suppose that y and z are both multiplicative inverses of x. Then
y =1·y (by the multiplicative identity law)
= (z · x) · y (because z is a multiplicative inverse of x)
= z · (x · y) (by the associative law for multiplication)
= z · 1 (because y is 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 suffices to show that this number
plus x + y equals 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. If x+z = y +z , then adding the additive inverse of z to both sides gives another equality. But (x+z)+(−z) =
x + (z + (−z)) = x + 0 = x by the associative, inverse, and identity laws, and similarly for the right-hand side.
Thus x = y .
8. If x = y , then by definition x − y = x + (−y) = x + (−x). But this equals 0 by the additive inverse law.
Conversely, if x − y = x + (−y) = 0 , then x is 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 suffices 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/x were equal to 0, then we would have 1 = (1/x) · x = 0 · x = 0 (by Theorem 5), contradicting the axiom
that 0 "= 1. If 1/x were less than 0 , then we could multiply both sides by the positive number x (by the
multiplicative compatibility law) to get 1 < 0 · x = 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 > y by x.
16. If x = 0 , then x2 = 0 by Theorem 5. (Note that x2 is just a shorthand notation for x · x.) This proves the
“if” part by contraposition, since if x2 = 0 , then x2 is not greater than 0 (by trichotomy). For the “only
if” part, it follows from the multiplicative compatibility law that if x > 0 then x · x > 0 , and it follows
from Exercise 15 that if x < 0 then x · x > 0. By trichotomy these are the only two cases that need to be
considered.
18. By Exercise 12, if x and y are positive, so are 1/x and 1/y . Therefore we can use the multiplicative
compatibility law to multiply both sides of x < y by 1/x and then by 1/y , and after some simplifications
(using the commutative, associative, inverse, and identity laws) we reach 1/y < 1/x, as desired.
20. Call the numbers a and b , with a < b. If a is negative and b is positive, then 0 is the desired real number.
If a < b < 0, then if we can find a rational number c between −b and −a, then the rational number −c
will be between a and b . Therefore we can restrict our attention to the case in which a and b are positive.
Notice that b − a is a positive real number. By Exercise 19 we can find an integer n such that n · (b − a) > 1,
which is equivalent to n · b > n · a + 1 . Now look at the set of natural numbers that are greater than n · a. By
the Archimedean property, this set is nonempty, and so by the well-ordering property there is a least positive
integer m such that m > n · a. We claim that m < n · b . If not, then we have m ≥ n · b > n · a + 1 , so
m − 1 > n · a, contradicting the choice of m (because m − 1 is positive). Therefore we have proved that
n · a < m < n · b , 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 definitions. First note that the restriction that the second
entry is nonzero is preserved by these operations, because if x "= 0 and z "= 0, then by Theorem 6 we know
that x · z "= 0 . We want to show that if (w, x) ≈ (w! , x! ) and (y, z) ≈ (y ! , z ! ), then (w · z + x · y, x · z) ≈
(w! · z ! + x! · y ! , x! · z ! ) and that (w · y, x · z) ≈ (w! · y ! , x! · z ! ). Thus we are given that w · x! = x · w! and
that y · z ! = z · y ! , and we want to show that (w · z + x · y) · (x! · z ! ) = (x · z) · (w! · z ! + x! · y ! ) and that
(w · y) · (x! · z ! ) = (x · z) · (w! · y ! ). 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 first, 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 log2 1024 = 10.
b) Since 1/4 = 2−2 , we know that log2 (1/4) = −2 .
c) Note that 4 = 22 and 8 = 23 . Therefore 2 = 41/2 , so 8 = (41/2 )3 = 43/2 . Therefore log4 8 = 3/2 .
4. We show that each side is equal to the same quantity.
! "logb c
alogb c = blogb a = b(logb a)(logb c)
! " logb a
clogb a = blogb c = b(logb c)(logb a)
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 Appendixes
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
, Section 1.1 Propositional Logic 1
CHAPTER 1
The Foundations: Logic and Proofs
SECTION 1.1 Propositional Logic
2. Propositions must have clearly defined 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) 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. Note: The first printing of this edition incorrectly rendered this exercise with “every day” in
place of “yesterday.” That makes it a much harder problem, because the days are quantified, and quantified
propositions are not dealt with until a later section. It would be incorrect to say that the negation in that
case is “Abby sent at most 100 text messages every day.” Rather, a correct negation would be “There exists a
day on which Abby sent at most 100 text messages.” Saying “Abby did not send more than 100 text messages
every day” is somewhat ambiguous—do we mean ¬∀ or do we mean ∀¬?
d) 121 is not a perfect square.
6. 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 first part of this biconditional statement is false and the second part is true.
8. 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.
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 x be a
nonzero real number. Suppose that y and z are both multiplicative inverses of x. Then
y =1·y (by the multiplicative identity law)
= (z · x) · y (because z is a multiplicative inverse of x)
= z · (x · y) (by the associative law for multiplication)
= z · 1 (because y is 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 suffices to show that this number
plus x + y equals 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. If x+z = y +z , then adding the additive inverse of z to both sides gives another equality. But (x+z)+(−z) =
x + (z + (−z)) = x + 0 = x by the associative, inverse, and identity laws, and similarly for the right-hand side.
Thus x = y .
8. If x = y , then by definition x − y = x + (−y) = x + (−x). But this equals 0 by the additive inverse law.
Conversely, if x − y = x + (−y) = 0 , then x is 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 suffices 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/x were equal to 0, then we would have 1 = (1/x) · x = 0 · x = 0 (by Theorem 5), contradicting the axiom
that 0 "= 1. If 1/x were less than 0 , then we could multiply both sides by the positive number x (by the
multiplicative compatibility law) to get 1 < 0 · x = 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 > y by x.
16. If x = 0 , then x2 = 0 by Theorem 5. (Note that x2 is just a shorthand notation for x · x.) This proves the
“if” part by contraposition, since if x2 = 0 , then x2 is not greater than 0 (by trichotomy). For the “only
if” part, it follows from the multiplicative compatibility law that if x > 0 then x · x > 0 , and it follows
from Exercise 15 that if x < 0 then x · x > 0. By trichotomy these are the only two cases that need to be
considered.
18. By Exercise 12, if x and y are positive, so are 1/x and 1/y . Therefore we can use the multiplicative
compatibility law to multiply both sides of x < y by 1/x and then by 1/y , and after some simplifications
(using the commutative, associative, inverse, and identity laws) we reach 1/y < 1/x, as desired.
20. Call the numbers a and b , with a < b. If a is negative and b is positive, then 0 is the desired real number.
If a < b < 0, then if we can find a rational number c between −b and −a, then the rational number −c
will be between a and b . Therefore we can restrict our attention to the case in which a and b are positive.
Notice that b − a is a positive real number. By Exercise 19 we can find an integer n such that n · (b − a) > 1,
which is equivalent to n · b > n · a + 1 . Now look at the set of natural numbers that are greater than n · a. By
the Archimedean property, this set is nonempty, and so by the well-ordering property there is a least positive
integer m such that m > n · a. We claim that m < n · b . If not, then we have m ≥ n · b > n · a + 1 , so
m − 1 > n · a, contradicting the choice of m (because m − 1 is positive). Therefore we have proved that
n · a < m < n · b , 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 definitions. First note that the restriction that the second
entry is nonzero is preserved by these operations, because if x "= 0 and z "= 0, then by Theorem 6 we know
that x · z "= 0 . We want to show that if (w, x) ≈ (w! , x! ) and (y, z) ≈ (y ! , z ! ), then (w · z + x · y, x · z) ≈
(w! · z ! + x! · y ! , x! · z ! ) and that (w · y, x · z) ≈ (w! · y ! , x! · z ! ). Thus we are given that w · x! = x · w! and
that y · z ! = z · y ! , and we want to show that (w · z + x · y) · (x! · z ! ) = (x · z) · (w! · z ! + x! · y ! ) and that
(w · y) · (x! · z ! ) = (x · z) · (w! · y ! ). 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 first, 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 log2 1024 = 10.
b) Since 1/4 = 2−2 , we know that log2 (1/4) = −2 .
c) Note that 4 = 22 and 8 = 23 . Therefore 2 = 41/2 , so 8 = (41/2 )3 = 43/2 . Therefore log4 8 = 3/2 .
4. We show that each side is equal to the same quantity.
! "logb c
alogb c = blogb a = b(logb a)(logb c)
! " logb a
clogb a = blogb c = b(logb c)(logb a)
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 Appendixes
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
, Section 1.1 Propositional Logic 1
CHAPTER 1
The Foundations: Logic and Proofs
SECTION 1.1 Propositional Logic
2. Propositions must have clearly defined 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) 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. Note: The first printing of this edition incorrectly rendered this exercise with “every day” in
place of “yesterday.” That makes it a much harder problem, because the days are quantified, and quantified
propositions are not dealt with until a later section. It would be incorrect to say that the negation in that
case is “Abby sent at most 100 text messages every day.” Rather, a correct negation would be “There exists a
day on which Abby sent at most 100 text messages.” Saying “Abby did not send more than 100 text messages
every day” is somewhat ambiguous—do we mean ¬∀ or do we mean ∀¬?
d) 121 is not a perfect square.
6. 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 first part of this biconditional statement is false and the second part is true.
8. 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.
