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 = ∅