## If and Only If

A | B | A \(\leftrightarrow\) B |
---|---|---|

T | T | T |

T | F | F |

F | T | F |

F | F | T |

When A = B, A \(\leftrightarrow\) B is True.

## Proof

If S = T, then S ∪ T and S ∩ T

**(“\(\rightarrow\)”)**

Assume S = T

Let x ∈ S ∩ T, then (x ∈ S) ∧ (x ∈ T)

Hence (x ∈ S) ∧ (x ∈ T)

Therefore (x ∈ S) v (x ∈ T)

Therefore x ∈ S ∪ T, so S ∩ T ⊆ S ∪ T

On the other hand, let y ∈ S ∪ T

Then (y ∈ S) v (y ∈ T)

At least one of y ∈ S or y ∈ T is a true statement.
Without loss of generality (WLOG), assume y ∈ S

From assumption S = T, so when y ∈ S, then y ∈ T

Thus S ∪ T ⊆ S ∩ T

**(“\(\leftarrow\)”)**

S ∪ T = S ∩ T then S = T

Assume S ∪ T = S ∩ T

let (x ∈ S) then (x ∈ S) v (x ∈ T)

Thus x ∈ S ∪ T.

Since S ∪ T = S ∩ T, x ∈ S ∩ T

Hence (x ∈ S) ∧ (x ∈ T)

Thus x ∈ T. Therefore S ⊆ T

Similarly, T ⊆ S

Therefore S = T

## Quantifiers

quantifier, variable, domain, open sentence

For all x ∈ \(\mathbb{R}\), \(x^2\) + 1 \(\ge\) 2x

**Universal Quantifer:** “For all”

**Variable:** x

**Domain:** “\(\mathbb{R}\)”

**Open Sentence:** \(x^2\) + 1 \(\ge\) 2x

**For every natural number n, 2\(n^2\) + 11n + 15 is composite**

**Proof:**

Let n ∈ \(\mathbb{N}\)

2\(n^2\) + 11n + 15 = (2n + 5)(n + 3)

Since n \(\ge\) 1, 2n + 5 \(\ge\) 2 and (n + 3) \(\ge\) 2

Also: n ∤ 3 \(\ne\) (2\(n^2\) + 11n + 15) as 2n + 5 \(\ne\) 1

as 2n + 5 ∈ \(\mathbb{Z}\), (n + 3) | (2\(n^2\) + 11n + 15)

So 2\(n^2\) + 11n + 15 is composite

**\(\forall\) x ∈ \(\mathbb{Z}\), a | (bx + c)**

**Proof:**

Pick x = 1

a | (b(1) + c)

a | b + c

**In this case we use the substitution method**

## The Select Method

**Used to Prove \(\forall\) x ∈ S, P(x):**

Select a representative mathematical object x ∈ S. This cannot be a specific object. It has to be a placeholder, (a variable) that the argument would work for any specific member of S.

Then show that the open sentence P would work for any representative x.

**For each x ∈ \(\mathbb{R}\), x < x + 1**

**Proof:**

Let x be a real number.

Therefore (x + 1) - (x) = 1

Since (x + 1) - (x) > 0

x < x + 1 is true

Thus, by **select method**, x ∈ \(\mathbb{R}\), x < x + 1 is a true statement

**For every natural number n, n \(\le\) \(n^2\)**

**Proof:**

Let P(x): x \(\le\) \(n^2\). We know that the set of natural numbers is given by

\(\mathbb{N}\) = {1, 2, 3, 4, 5, …}

Let n ∈ \(\mathbb{N}\).

Since n is a natural number, n \(\ge\) 1
Multiply both sides of the inequality by n (note: n is positive) to generality

n * n \(\ge\) n * 1

\(n^2\) \(\ge\) n

Thus, P(n) is true. Therefore, by the select method, \(\forall\) n ∈ \(\mathbb{N}\), P(n) is a true statement.

## Existential Quantifier

\(\exists\) x ∈ S, P(x)

Also means:

- There is an x ∈ S such that P(x) is true
- P(x) is true for some x ∈ S
- At least one x ∈ S satisfies P(x)
- S has an element x such that P(x) is satisfied

## The Construct Method

**Used to prove \(\exists\) x ∈ S, P(x)**

**\(\exists\) x ∈ {1,2,3,4}, such that x is even**

**Proof:**

Consider x = 2. Since 2 is an element of the given domain, and 2 is even, therefore the above statement is true.

Quantified statement | When True? | When False |
---|---|---|

\(\forall\) x ∈ S, P(x) | P(x) is true for every element in S | P(x) is false for at least one element in S |

\(\exists\) x ∈ S, P(x) | P(x) is true for at least one element in S | P(x) is false for every element in S |

# Assuming a Quantified Statement is True

## The Substitution Method

**Used to prove \(\forall\) x ∈ S, P(x)**

Substitute an appropriate value of x from S into the open sentence P, and use the fact that P(x) must be true to arrive at the desired conclusion.

**If \(\forall\) x ∈ \(\mathbb{N}\), n | x then n = 1**

The trick here is to use an appropriate value of x from \(\mathbb{N}\) that helps give the conclusion of n = 1.

**Proof:**

Assume \(\forall\) x ∈ \(\mathbb{N}\), n | x.

Since x ∈ \(\mathbb{N}\), consider x = 1. By our own assumption n | 1.

We know that the only positive divisor of 1 is 1 itself. Therefore n = 1.

## The Object Method

**Used to prove \(\exists\) x ∈ S, P(x), it true**

Use a symbol such as s to denote an element of S for which P(x) is true. Since we do not know exactly which element of S satisfies P, we cannot assign a specific value to x. Instead we use x as a variable.

**Let n be an integer. Prove the following statement about n:**

If n is of the form 4l + 1 for some positive integer l, then 8 | (\(n^2\) -1)

\(\exists\) l ∈ \(\mathbb{Z}\), such that n = 4l + 1

Our goal is to prove 8 | (\(n^2\) - 1),

which is equivalent to proving that k ∈ \(\mathbb{Z}\), 8k = (\(n^2\) - 1)

**Proof:**
Assume, by the **object method**, that we can write n = 4l + 1 for some integer l.

let k = \(2l^2\) + l. Since l is an integer, therefore k must be also an integer.

In that case, \(n^2\) - 1 = \((4l + 1)^2\) - 1 = \(16l^2\) + 8l + 1 - 1

\(16l^2\) + 8l = 8(\(2l^2\) + l) = 8k

Thus according to the **construct method**, we have shown that k ∈ \(\mathbb{Z}\), 8k = (\(n^2\) - 1)

Therefore 8 | (\(n^2\) -1)