How To Prove It - Chapter 3 - 3.3

Proofs involving Quantifiers

1.
Givens
∃x(P(x) → Q(x))

Goal
∀x P(x) → ∃x Q(x)

Revised givens
∃x(P(x) → Q(x))
∀x P(x)

Goals
∃x Q(x)

Let y be an arbitrary value of x, so that
P(y) -> Q(y)
Since P(x) is true for all x, then P(y) must also be true.

Hence, Q(y) must also be true.
So for some arbitrary value of x called y, Q(x) is true. Hence, there exists some x so that Q(x) is true, i.e., ∃x Q(x)

2.
Givens
A and B \ C are disjoint

Goal
A ∩ B ⊆ C

Revised
Givens
x ∈ A -> x ∉ B \ C
x ∈ A
x ∈ B

Goal
x ∈ C

From the givens,
x ∈ A, hence x ∉ B \ C is also true.
Hence, x must be an element of C since it's not an element of (in B but not in C).
Or,
x ∈ C

3.

Givens
A ⊆ B \ C, or
for some arbitrary x,
x ∈ A -> x ∈ B \ C, or
x ∈ A -> (x ∈ B ∧ x ∉ C)

Goal
A and C are disjoint, or
x ∈ A -> x ∉ C

Revised givens
x ∈ A -> (x ∈ B ∧ x ∉ C)
x ∈ A

Revised goals
x ∉ C

From the givens, since x ∈ A is true, so x ∈ B is also true, and so is x ∉ C, which is the desired goal.

6.

(a)
Givens,
x is real
x ≠ 1

Goal
∃y (y+1 / y -2 = x)

Assume that y = -1.
Then, (y+1 / y -2 = x)
=> -1 +1 = x (-3)
=> x= 0

Thus, there exists a real number y so that x ≠ 1 and the equation is satisfied.

(b)
Using contradiction,

Givens,
there is a real number y so that y + 1 / y -2 = x
x = 1

Goal
Contradiction

From the givens,

y + 1 = y - 2
or, 1 = -2, which is a contradiction. Hence, if there is a real number y so that the equation is satisfied, then x cannot be 1.