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

# Math stuff

Working through problems in stats, probability and other math disciplines as part of my self-study plan.

## Sunday, August 21, 2011

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

n

-->

We'll prove by contradiction.

Givens

n

n is odd

Goal

Contradiction

n

n

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

Hence, (2k)

or,

2.4k

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

<---

Given

n is even

n

Goal

Contradiction

n is even, so n = 2k, k being an integer

n

Hence, (2k)

=> 2(4.k

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

Hence, n

Combining the two, n

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

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

^{3}is even iff n is even-->

We'll prove by contradiction.

Givens

n

^{3}is evenn is odd

Goal

Contradiction

n

^{3}is even, son

^{3}= 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.4k

^{3}= 2(4m^{3}+ 6m^{2}+ 3m) + 1which 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

^{3}is odd.<---

Given

n is even

n

^{3}is oddGoal

Contradiction

n is even, so n = 2k, k being an integer

n

^{3}is odd, so n^{3}= 2m + 1, m being an integerHence, (2k)

^{3}= 2m + 1=> 2(4.k

^{3}) = 2m + 1Which is impossible, as the left expression evaluates to an even integer, while the right one to an odd integer.

Hence, n

^{3}is even when n is even.Combining the two, n

^{3}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

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.

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.

Subscribe to:
Posts (Atom)