If and Only If

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.

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)