## Sunday, August 21, 2011

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

## Tuesday, August 9, 2011

### 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.

n3 is even iff n is even

-->

Givens
n3 is even
n is odd

Goal

n3 is even, so
n3 = 2k, where k is an integer.

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

Hence, (2k)3 = (2m + 1)3
or,
2.4k3 = 2(4m3 + 6m2 + 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 n3 is odd.

<---

Given
n is even
n3 is odd

Goal

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

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

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

Hence, n3 is even when n is even.

Combining the two, n3 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

## Monday, August 8, 2011

### 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)