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

1. There is an x ∈ S such that P(x) is true
2. P(x) is true for some x ∈ S
3. At least one x ∈ S satisfies P(x)
4. 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)