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.
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
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
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.
\(\exists\) x ∈ S, P(x)
Also means:
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 |
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.
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)