Answers to Problem Set 1

Name: Simon Lee

MATH-UA 120 Discrete Mathematics
due February 2, 2024

These are to be written up in LATEX and turned in to Gradescope.

Assigned Problems
1. Let the following statements be given. 4 P.
Definition. A triangle is scalene if all of its sides have different lengths.
Theorem. A triangle is scalene if it is a right triangle that is not isosceles.
Suppose ∆ABC is a scalene triangle. Which of the following conclusions
are valid based only on the information given above? Why or why not?
(a) All of the sides of ∆ABC have different lengths.
(b) ∆ABC is a right triangle that is not isosceles.

Answer.
(a) is valid because by definition, a triangle is scalene if all of its sides have
different lengths, and since it is given that ∆ABC is a scalene triangle, the
conclusion that all of the sides of ∆ABC have different lengths is true. (b) is
not valid because the definition of scalene triangle does not define ∆ABC to be
a right triangle that is not isosceles. Just because ∆ABC is scalene, does not
mean that it has to be a right triangle that is not isosceles.
2. Without changing their meanings, convert each of the following sentences 6 P.
into a sentence of the form “For all ... x, if x ... , then .”
(a) Every prime greater than 2 is odd.
(b) Three consecutive odd integers greater than 3 cannot all be prime.
(c) An integer is divisible by 8 only if it is divisible by 4.

1
Answer.
(a) For all prime x, if x is greater than 2, then x is odd.
(b) For all integer x, if x is three consecutive odd integers greater than 3,
then x cannot all be prime.
(c) For all integer x, if x is divisible by 8, then it is divisible by 4.

3. The following claim and its proof are poorly written. They are both missing 10 P.
some crucial information. Explain why both the claim and its proof are poorly
written. Then revise both the claim and proof so that any student in this course
will understand it.
Claim. If x2 ̸= 0, then x2 > 0.
Proof. If x > 0, then x2 = xx > 0. If x < 0, then −x > 0, so (−x)(−x) > 0,
i.e., x2 > 0.

Answer.
The claim If x2 ̸= 0, then x2 > 0 is poorly written because it does not clearly
define the parameter of what x√can be. The claim must specify what type of
number x is because if x is ior −1, then x2 > 0, which would make the claim
totally false. The revised version would be: Given that x is a real number, If
x2 ̸= 0, then x2 > 0.
The proof If x > 0, then x2 = xx > 0. If x < 0, then −x > 0, so (−x)(−x) >
0 is poorly written because it is long and redundant. The revised version would
simply be: If x>0, then x2 > 0. If x<0, then x2 > 0. The case is both true
because for a number to be greater or less than 0, it has to be a real number.
4. For each of the following parts, explain why the given argument is not a 6 P.
valid proof.
(a)
Theorem. For all primes p, the integer 2p − 2 is divisible by p.

Wrong Proof.

22 − 2 = 2 · 1, 23 − 2 = 3 · 2, 25 − 2 = 5 · 6, 27 − 2 = 7 · 18 etc.

(b)
Theorem. For all x, y, and z, if x + y < x + z, then y < z.

Wrong Proof. Suppose that x + y < x + z. Take x = 0. Then

y = 0 + y < 0 + z = z.

2
 (c)
√ √ √
Theorem. 2+ 6< 15.

Wrong Proof.
√ √ √ √ √
2+ 6< 15 =⇒ ( 2 + 6)2 < 15
√
=⇒ 8 + 2 12 < 15
√
=⇒ 2 12 < 7
=⇒ 48 < 49.

Answer. (a) Given argument is not a valid proof because simply showing alge-
braic equations with numerical values is only reiterates the theorem, does not
explain or prove the Theorem using definitions and structured explanation. (b)
Given argument is not a valid proof because it does not prove the theorem with-
out changing the meaning the of the theorem. A valid proof should use only
what is given, and its definitions. Instead, your proof should show to subtract
x from x + y < x + z to arrive to y < z. (c) ...
5. Consider the following definitions. 15 P.
Definition. An integer n is alphic if n = 4k + 1 for some integer k.
Definition. An integer n is gammic if n = 4k + 3 for some integer k.
(a) Show that −17 is gammic.
(b) Give an example of an alphic integer and explain why it is alphic.
(c) Explain whether this statement is true: “If 6 is alphic, then 8 is gammic.”
(d) Prove that if x is alphic and y is gammic, then x + y is even.

Answer. (a) An integer n is gammic if n=4k+3 for some integer k. If n=-17,

then by definition, -17=4k+3, where k=-5.
(b) 9 is an alphic integer if k=2 because by definition, an integer n is alphic
if n=4k+1 for some integer k.
(c) The statement"If 6 is alphic, then 8 is gammic" is vacuously true because
the premise of implication that 6 is alphic is false. 6 cannot be alphic, or
expressed as 4k+1 for some integer k.
(d) If x is alphic and y is gammic, then x+y is even. Suppose x is alphic
and y is gammic, then for some integer a and b, x=4a+1 and y=4b+3, where
x and y are also both integers. By definition, an integer n is even when it is
divisible by 2. If x+y is even, then x+y = n = (4a+1)+(4b+3) = 4(a+b)+4.
Since x+y= 4(a+b+1) and is divisible by 2, x+y is indeed even.

3
6. Prove that an integer n is odd if and only if 2n + 2 is divisible by 4. 9 P.
Answer. An integer n is odd if and only if 2n+2 is divisible by 4.
By definition, n is an odd integer provided that 2k+1 for some integer k. This
means 2n+2= 4k+4, in which 2n+2 is divisible by 4. Which means n=4k+1,
which by definition is an odd integer.