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