How To Prove It - Chapter 4 - 4.1

Relations - Ordered Pairs and Cartesian Products

1.

(a) T = {(a, b) ∈ P x P | a is a parent of b).
(b) T = {(c, u) ∈ C x U | there is someone who lives in c and attends u}

2.

(a) T = {(p, c) ∈ P x C | p lives in c}
(b) T = {(p, n) ∈ C x N | the population of p is n}

3.
(a) Samples (x, y) = (0, -2), (1, -2), (-1, 0)
(b) Samples (x, y) = (1, 0), (2, 1), (1000, 100)
(c) Samples (x, y) = (0, -2), (1, 1)
(d) Samples (x, y) = (0, -2), (6, 4)

4.
A = {1, 2, 3}, B = {1, 4}, C = {3, 4}, and D = {5}
(1)
A × (B ∩ C) = {(1,1), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,3), (3,4) }
(A × B) ∩ (A × C) = {(1,1), (2,1), (3,1), (1,3), (1,4), (2,3), (2,4), (3,3), (3,4)}

A × (B ∩ C) = (A × B) ∩ (A × C)

(5)
A×∅= ∅×A = ∅
A×∅ = {}
∅×A = {}

Both are = ∅



6.

Proof given for (A ∪ C) × (B ∪ D) ⊆ (A × B) ∪ (C × D)

The cases are not exhaustive. Missing cases are
(3) x ∈ A and y ∈ D
(4) x ∈ C and y ∈ B


7. m

8.
To prove A×(B \C) = (A× B)\(A×C)
-->

Given
For arbitrary x, y
(x, y) ∈ A x (B\C)
x ∈ A
y ∈ B\C

or,
Givens
x ∈ A
y ∈ B
y ∉ C

From the first 2 givens,
(x, y) ∈ A x B
From the 1st and 3rd givens,

(x, y) ∉ A x C

Combining these two,
the Cartesian product (x, y) for arbitrary x and y must is an element of A x B, but not of A x C. Hence,
(x, y) ∈ (A× B)\(A×C)

or,
(x, y) ∈ A x (B\C) -> (x, y) ∈ (A× B)\(A×C)
This completes the forward proof.

<--
Given,
for arbitrary x, y
suppose (x, y) ∈ (A× B)\(A×C)

or,
(x, y) ∈ (A× B)
(x, y) ∉ (A x C)

or,
x ∈ A
y ∈ B
Since we already have x ∈ A, so it's only possible when
y ∉ C (second given above)

Revised givens,
x ∈ A
y ∈ B
y ∉ C

From the 2nd and 3rd givens,
y ∈ B\C

Hence,
(x, y) ∈ A x (B\C)

Or, (x, y) ∈ (A× B)\(A×C) -> (x, y) ∈ A x (B\C)
This completes the reverse proof.

10.
(A x B) ∩ (C x D) = ∅

To prove,
A ∩ C = ∅ ∨B ∩ D = ∅
or,
(x ∈ A -> x ∉ C) ∨ (y ∈ B -> y ∉ D)

Suppose x ∈ A, y ∈ B
Then,
(x, y) ∈ A x B -> (x, y) ∉ C x D

The RHS can be expressed as
(x ∉ C ∧ y ∉ D) ∨ (x ∈ C ∧ y ∉ D) ∨ (x ∉ C ∧ y ∈ D)

Or,
(x ∈ A ∧ y ∈ B) -> (x ∉ C ∧ y ∉ D) ∨ (x ∈ C ∧ y ∉ D) ∨ (x ∉ C ∧ y ∈ D)

Taking the 3 cases -
1.
x ∈ A
y ∈ B
x ∉ C
y ∉ D

This implies A ∩ C = ∅ and B ∩ D = ∅
Since both are true, this is an inclusive case of the required proof.

2.
x ∈ A
y ∈ B
x ∈ C
y ∉ D

This implies A ∩ C ≠ ∅ and B ∩ D = ∅, or one of them is true. Hence,
A ∩ C = ∅ ∨B ∩ D = ∅

3.
x ∈ A
y ∈ B
x ∉ C
y ∈ D

This implies A ∩ C = ∅ and B ∩ D ≠ ∅, or one of them is true. Hence,
A ∩ C = ∅ ∨B ∩ D = ∅

From the 3 cases, A ∩ C = ∅ ∨B ∩ D = ∅

How To Prove It - Chapter 3 - 3.4

Proofs involving Conjunctions and Biconditionals

Note: A lot of the first few problems are of the same type. Skipped the similar ones.

1.
-->
Given
∀x(P(x) ∧ Q(x))

Goal
∀x P(x) ∧ ∀x Q(x)

Let ∀x(P(x) ∧ Q(x))
So for an arbitrary y, P(y) ∧ Q(y).
Hence, P(y). So ∀x P(x) is true. So is ∀x Q(x)

So, for arbitrary x, P(x) and Q(x) are true.
Hence,
∀x P(x) ∧ ∀x Q(x)

<--
Given
∀x P(x) ∧ ∀x Q(x)

Goal
∀x(P(x) ∧ Q(x))

Let ∀x P(x) ∧ ∀x Q(x)
For arbitrary y, ∀y P(y) ∧ ∀y Q(y)

Since P(y), and also Q(y), hence P(y) ∧ Q(y) is also true.
Since y was arbitrary, P(x) ∧ Q(x) is true for any value of x.
Hence, ∀x(P(x) ∧ Q(x))

2.

Givens
A ⊆ B
A ⊆ C

Goal
A ⊆ B ∩ C

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

Goal
x ∈ B
x ∈ C

From the givens, x ∈ A is true. Hence, so is x ∈ B (first goal) and x ∈ C (second goal)

3.

Givens
x ∈ A -> x ∈ B

Goal
x ∈ C \ B ⊆ x ∈ C \ A

Let x be an arbitrary element of an arbitrary set C.

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

Goal
x ∈ C \ A

The first given can be expressed as (modus tollens)
x ∉ B -> x ∉ A
x ∈ C
x ∉ B

Goals
x ∈ C
x ∉ A

From the givens,
x ∉ B, hence x ∉ A as well, which is one of the goals
From the second given, x ∈ C, which is the second goal.

9.

Given
x and y are odd integers

Goal
xy is odd

Since x and y are odd integers, they can be expressed as
x = 2k +1
y = 2m + 1,

where k and m are integers

Hence, xy = (2k + 1) (2m + 1)
= 2(2km + k + m) + 1

2km + k + m is an integers, and 2(2km + k + m) is even. Hence, 2(2km + k + m) + 1 is odd.

10.

n³ is even iff n is even

-->
We'll prove by contradiction.

Givens
n³ is even
n is odd

Goal
Contradiction

n³ is even, so
n³ = 2k, where k is an integer.

n is odd, so n = 2m + 1, m being an integer.

Hence, (2k)³ = (2m + 1)³
or,
2.4k³ = 2(4m³ + 6m² + 3m) + 1

which is impossible as the number of the left is even, while the one on the right is odd.

Hence, n has to be even if n³ is odd.

<---

Given
n is even
n³ is odd

Goal
Contradiction

n is even, so n = 2k, k being an integer
n³ is odd, so n³ = 2m + 1, m being an integer

Hence, (2k)³ = 2m + 1
=> 2(4.k³) = 2m + 1

Which is impossible, as the left expression evaluates to an even integer, while the right one to an odd integer.

Hence, n³ is even when n is even.

Combining the two, n³ is even iff n is even.

11.

(a) The same 'k' cannot be chosen, as it translates that m = n+1, which is not an assumption that is given.

(b) The theorem is incorrect.
Counterexample - m = 4, n =7

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.

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