How To Prove It - Chapter 3 - 3.2

Proofs involving negations and conditionals

1.
(a) Givens
P → Q - i
Q → R - ii

Goals
P → R

Suppose P. Then from (i), Q.
Since Q, from (ii), we have R.
Hence if P then R. P → R

(b)Given
¬R → (P → ¬Q)

Goal
P → (Q → R)

Suppose P.
From the given,
¬R → (P → ¬Q)
suppose ¬R.
Then,
(P → ¬Q)
Since we know P, we also know now that ¬Q.
Hence, ¬R led to ¬Q.
or,
¬R → ¬Q
or
Q → R
Hence,
P led to Q → R,
or,
P → (Q → R)

2.
(a)
Givens
P → Q
R → ¬Q

Goal
P → ¬R

Revised givens
P → Q
R → ¬Q
P
Q (because of the first given)

Revised goal
¬R

From the givens using modus tollens
Q→ ¬R

Since we already have Q as a given, we can conclude ¬R.

(b)
Givens
P

Goals
Q → ¬(Q → ¬P)
can be written as
(Q → ¬P) → ¬ Q

Revised Givens
P
Q → ¬P or written as
P → ¬Q

Revised goals
¬Q

From the revised givens we know P.
One of the givens also implies that ¬Q, which is the desired goal.

3.
Givens
A ⊆ C
x ∈ A
x ∈ C → x ∉ B

Goal
x ∉ B

From the givens,
Since x ∈ A and A ⊆ C, then x ∈ C also.
From the third given, this implies x ∉ B which is the desired conclusion.

x ∉ B

4.

Givens
x ∈ A
x ∈ C → x ∉ A \ B

Goal
If x ∈ C then x ∈ B

Revised givens
x ∈ A
x ∈ C → x ∉ A \ B
x ∈ C

Revised goal
x ∈ B

From the 2nd and 3rd givens, we can conclude x ∉ A \ B
or,
¬(x ∈ A ∧ x ∉ B)
From the given we know x ∈ A, hence the truth value of the expression becomes
¬(x ∉ B)
or,
x ∈ B, which is the desired goal.

7.

Givens
y + x = 2y − x
or,
y = 2x
x and y are not both 0

Goal
y is not 0

Revised givens
y = 2x
x and y are not both 0
x = 0

Hence, y cannot be 0

8.

Givens
a, b are non zero real numbers
a < 1/a < b < 1/b

Goal
a < -1

Revised givens
a, b are non zero real
a < 1/a
or a² < 1
or a < +1 or -1

b < 1/b
or
or b² < 1
or b < +1 or -1

1/a < 1/b
or a > b
But, it's already given a > b.
Hence, 1/a < 1/b is possible only when a and b are both < 0

Revised givens
a and b are non zero real
a < 1/a < 1/b < b
a and b are both < 0
a, b < + 1 or < -1

Since a and b are < 0, hence they have to be < -1 (and not just < 1)
Hence b < -1

9.

Givens
x and y are real
x * x = 2x + y
y ≠ 0

Goal
x ≠ 0

Revised givens, assuming contradiction that x = 0
x and y are real
x * x * y = 2x + y
y ≠ 0
x = 0

Goal
Contradiction

From the givens now,
0 = 0 + y
or y = 0
This is a contradiction to one of the givens.

Hence, the assumption that x = 0 is false.
Or x ≠ 0

10.

Givens
x and y are real
x ≠ 0
y = (3x² +2y) / (x² + 2)

Goal
y = 3

Revised givens
x²y + 2y = 3x² +2y
or
x² (y - 3) = 0

Since x is not 0, y - 3 has to be = 0

or y = 3, which is the desired goal.

11.

(a) "x = 3 and y = 8" is incorrect, as x and y may be any other real numbers too.
(b) x = 2, y = 8