diff options
| -rw-r--r-- | 1.8.md | 124 | ||||
| -rw-r--r-- | 2.1.md | 87 | ||||
| -rw-r--r-- | 2.2.md | 185 |
3 files changed, 396 insertions, 0 deletions
@@ -26,3 +26,127 @@ Sometimes, the proofs of multiple cases are essentially the same, so we will say Proof: Let a,b∈ℝ. without loss of generality, assume `a>=b`. Then, LHS (left hand side) = `max(a,b)-min(a,b)` = `a-b`. Note `|x| = x` for `x>0` and `|x| = -x` if `x<=0`. RHS (right hand side) = `|b-a|` = `-(b-a)` = `a-b`. ∴ LHS = RHS as desired. ▣ - We don't need to consider the other case since it would have been identical + +--- + +- To prove `p<->q`, we must show + 1. `p->q` + 2. `q->p` + +- Ex. Let n∈ℤ. Prove `n` is odd iff `n^2` is odd. + +Proof: +- (=>)(implication arrow) "If `n` is odd, then `n^2` is odd" + - We already proved this in [1.7](1.7.md) +- (<=)(implication arrow; reverse direction) "If `n^2` is odd, then `n` is odd" + - **Direct Proof**: + - Ǝk∈ℤ s.t. `n^2 = 2k+1` + - `n = ±sqrt(2k+1)` + - not sure if `±sqrt(2k+1)` is an integer :( + - **Contraposition**: "If `n` is even, then `n^2` is even` + - Let `n` be even. Ǝk∈ℤ s.t. `n = 2k`. + - Then, `n^2 = (2k)^2 = 4k^2 = 2(2k^2)` which is even since `(2k)^2`∈ℤ + - ∴ `n` is odd iff `n^2` is odd. ▣ + +- Definition: A **theorem** is a mathematical statement that can be shown/proven to be true +- Definition: A **proposition** is a "less important" **theorem** +- Definition: A **corollary** is a theorem that is a direct result of another theorem + - Ex. Let n∈ℤ. `n` is even iff `n^2` is even + - Proof Sketch: Both directions are contrapositives of the above example + +--- + +# 1.8 Proof Methods p2 + +- Proposition: `[(p->q)^(q->r)] -> (p->r)` is a tautology. + - Transitive Law + +- Suppose we want to show `p1 <-> p2 <-> p3 <-> ... <-> pn` for `n >= 3`. When this is true we say: + - "the following are equivalent" (TFAE): + 1. `p1` + 2. `p2` + 3. `p3` + n. `pn` + - To prove this, it is sufficient to show: `p1 -> p2 -> p3 -> ... -> pn -> p1` + +- Ex. Let n∈ℤ. Prove TFAE: + 1. `5n+4` is even + 2. `n^2` is even + 3. `n-3` is odd. + +- Proof: (iii) -> (ii) + - Let n∈ℤ s.t. `n-3` is odd + - Then, Ǝk∈ℤ s.t. `n-3 = 2k+1` + - `n^2` = `(2k+4)^2` = `4k^2 + 16k + 16` = `2(2k^2 + 8k + 8)` + - It's **even** since `2k^2 + 8k + 8`∈ℤ +- Proof: (ii) -> (i) + - Let n∈ℤ s.t. `n^2` is even + - We have previously proved that n is even iff n^2 is even. Ǝl∈ℤ s.t. `n = 2l` + - Then, `5n+4` = `5(2l)+4` = `10l+4` + - It's **even** since `5l+4`∈ℤ +- Proof: (i) -> (iii) + - Direct Proof: + - `5n+4 = 2k` + - `n = (2k-4)/5`... too hard, lets use a different strategy + - Contrapositive: "If `n-3` is even, then `5n+4` is odd" + - Let n∈ℤ s.t. `n-3` is even + - Ǝk∈ℤ s.t. `n-3 = 2k` + - Then, `n = 2k+3`, so `5n+4` = `5(2k+3) + 4` = `10k+15+4` = `10k+19` = `10k + 18 + 1` = `2(5k+9) + 1` + - It's **odd** since `5k+9`∈ℤ + +∴ (i), (ii), and (iii) are equivalent. ▣ + +--- + +Ex. Prove that for all nonnegative reals, `x` and `y`, `(x+y)/2 >= sqrt(xy)` +- The left hand is the "Arithmetic Mean" +- The right hand is called the "Geometric Mean +- AM - GM Inequality for `n = 2` +- Direct Proof is hard +- We will use a new method called **Backwards Reasoning** + +### Backward Reasoning + +Show conclusion is **equivalent** to a true statement + +- Proof: + - `(x+y)/2 >= sqrt(xy)` + - <-> `((x+y)/2)^2 >= xy` + - <-> shows that going from the previous step to this step is reversible + - squaring both sides preserves the inequality + - <-> `(x^2 + 2xy + y^2)/4 >= xy` + - <-> `(x^2 + 2xy + y^2) >= 4xy` + - <-> `(x^2 - 2xy + y^2) >= 0` + - <-> `(x-y)^2 >= 0` + - `a^2 >= 0` is a tautology; it's called "Trivial Inequality" + - `≡T` + - Since `(x+y)/2 >= sqrt(xy)` is equivalent to a true statement, this inequality is also true + +- **Note**: For a proof using Backward Reasoning, ensure each step is reversible. Failure to do so could lead to Circular Reasoning + +--- + +Ex: Prove `sqrt(2)` is irrational. + +- Proof: + - Assume for the sake of contradiction that `sqrt(2)`∈ℚ + - Then, `sqrt(2)` = `a/b` for some a,b∈ℤ, `b!=0` + - Suppose `a/b` is written in "lowest terms" + - `(sqrt(2))^2 = (a/b)^2` + - -> `2 = (a^2)/(b^2)` + - -> `2b^2 = a^2` + - This means `a^2` is **even** since `b^2`∈ℤ + - Recall: "`a` is even iff `a^2` is even" + - This implies that `a` is even. + - Ǝk∈ℤ s.t. `a=2k` + - Substituting `a=2k` into `2b^2 = a^2`, we get `2b^2 = (2k)^2` + - -> `2b^2 = 4k^2` + - -> `b^2 = 2k^2` + - This means `b^2` is even since `k^2`∈ℤ + - This implies that `b` is even + - However, `a` and `b` being even **contradicts** the assumption that `a/b` is written in lowest terms + - As a result, `sqrt(2)` is irrational. ▣ + +--- + +[2.1 ->](2.1.md) @@ -0,0 +1,87 @@ +[\<- 1.8](1.8.md) + +--- + +# 2.1 Sets p1 + +- A **Set** consists of elements, and it is **unordered** + - "x∈S" means `x` is an element of 'S' + + - Note: {a,b,c} = {c,b,a} (order doesn't matter) + - Note: {a,b,c} = {a,a,b,b,c,c} (number of occurences doesn't matter) + +- **Definition**: Let 'S', 'T' be sets. We say 'S' is a **subset** of 'T', and write `S <= T`, if each element `x` of 'S' is also an element of 'T' + - To prove `S ≺= T`: + 1. Let `x` be an arbitrary element of 'S' + 2. Show it follows that x∈T + +- **Definition**: The set with no elements is called the **empty set**, denoted by Ø or {} + - For any set 'S', + 1. `Ø ≺= S` (Ø is a subset of 'S') + 2. `S ≺= S` ('S' is a subset of 'S') + +- **Definition**: If a set 'S' has `n` elements with n∈ℤ, `n >= 0`, then 'S' is a **finite set**. We say the **cardinality** of 'S' is `n` and write `|S| = n` + - If 'S' is not a finite set, then 'S' is an **infinite set** + - `(S = Ø) <-> (|S| = 0)` + +--- + +## Power Sets + +**Definition**: The **Power Set** of 'S' is the set of all subsets of 'S' and is denoted `Ꝕ(S)` + +- Ex. Let 'S' = {`a`, `b`, `c`}. Write `Ꝕ(S)` in set notation. + - `Ꝕ(s)` = + - Ø + - {`a`} + - {`b`} + - {`c`} + - {`a`, `b`} + - {`a`, `c`} + - {`b`, `c`} + - {`a`, `b`, `c`} + - Notice: all the elements of `Ꝕ(S)` are sets themselves (i.e. {a}∈Ꝕ(S) instead of just `a`) + - `|Ꝕ(S)| = 8` + - Can create elements of `Ꝕ(S)` with **bit strings** (sequence of 0's and 1's) + +- Ex. `S = {a, b, c}` ... bit string of length 3 (e.g. 011) + - 1st digit: + - 1 if a∈subset + - 0 if !(a∈subset) + - 2nd digit: + - 1 if b∈subset + - 0 if !(b∈subset) + - 3rd digit: + - 1 if c∈subset + - 0 if !(c∈subset) + - **Possible Bit Strings**: + - 000 + - corresponds to Ø + - 100 + - corresponds to {`a`} + - 010 + - 001 + - 110 + - 101 + - 011 + - corresponds to {`b`, `c`} + - 111 + - There are 8 possible bit strings because `2^3` = 8 + - This leads to a theorem + +- **Theorem**: If `|S| = n`, then `|Ꝕ(S)| = 2^n` + +- **Definition**: Let 'S', 'T' be sets. The **product** of 'S' and 'T' is the set `{(s, t) | s∈S, t∈T}` + - (`s`, `t`) = ordered pair + - e.g. Let 'S' = {`a`, `b`, `c`} and 'T' = {1, 2}. Then, + - `S × T = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}` + - Notice: `|S × T|` = `6` = `3 · 2` = `|S| · |T|` + +- **Theorem**: If `|S| = n` and `|T| = m`, then `|S × T| = nm` + +- **Note**: (ℝ × ℝ × ℝ) = `{(a,b,c) | a,b,c∈ℝ}` is denoted ℝ^3 + - we can similarly define ℝ^n for `n>3` + +--- + +[2.2 ->](2.2.md) @@ -0,0 +1,185 @@ +[\<- 2.1](2.1.md) + +--- + +# 2.2 Set Operations p1 + +We can represent sets in a **Venn Diagram** as circles/ellipses that lie inside some **universal set** + +``` ++----------+ +| | +| +--+ u | +| | s| | +| | | | +| +--+ | ++----------+ +``` + +- "rectangle is universal set `u` + +- Ex. + - Let `u` = ℤ + - 'A' = `{2k | k∈ℤ}` + - 'B' = `{3l | l∈ℤ}` + 1. Draw a Venn Diagram and write at least on element in each "region" + +``` ++---------------------+ +| | +| +-------+ u | +| | A | | +| | +-------+ | +| | | | | | +| +----|--+ | | +| | B | | +| +-------+ | ++---------------------+ +``` + +- `u` is representing ℤ +- Examples that belong in each region: + - Inside 'A', outside 'B' + - 2 + - 4 + - Inside 'B', outside 'A' + - 3 + - -9 + - Inside both 'A' and 'B' + - 6 + - 0 + - -18 + - Outside of both 'A' and 'B' (but inside `u`) + - 7 + - 5 + +- **Definitions**: If 'A', 'B' are sets, the + 1. **Intersection** of 'A' and 'B', written `A∩B`, is the set of all elements in 'A' **and** 'B' + 2. **Union** of 'A' and 'B', written `A∪B`, is the set of all elements in 'A' **or** 'B' + - the "or" is inclusive, btw + +### Intersection Venn Diagram + +``` ++---------------------+ +| A↓ | +| +-------+ u | +| | | | +| | +-------+ | +| | |██| | | +| +----|--+ |← | +| | |B | +| +-------+ | ++---------------------+ +``` + +- `A∩B` = shaded + +### Union Venn Diagram + +``` ++---------------------+ +| A↓ | +| +-------+ u | +| |███████| | +| |████+-------+ | +| |████|██|████| | +| +----|--+████|← | +| |███████|B | +| +-------+ | ++---------------------+ +``` + +- `A∪B` = shaded + +|Words|Logic|Sets| +|-----|-----|----| +|and |^ |∩ | +|or |∨ |∪ | + +- Describe `A∩B`, `A∪B` in the earlier example + - `A∩B` = multiples of 2 **and** 3 + - multiples of 6 + - `A∪B` = multiples of 2 **or** 3 + - 2, 3, 4, 6, 8, ... + +--- + +- **Definition**: If `A∩B` = Ø, we say 'A' and 'B' are **disjoint** + +``` ++---------------------+ +| | +| +-------+ u | +| | A | | +| | | | +| | | +----+ | +| +-------+ | B | | +| | | | +| +----+ | ++---------------------+ +``` + +- Notice how 'A' and 'B' don't overlap at all + +- **Definition**: Fix a universal set `u`, and `S ≺= u`. The **complement** of 'S', written s̅ or s^c, is the set of elements `u` not in 'S' + +**complement** + +``` ++---------------------+ +|█████████████████████| +|██+-------+██████u███| +|██| S |██████████| +|██| |██████████| +|██| |██████████| +|██+-------+██████████| +|█████████████████████| +|█████████████████████| ++---------------------+ +``` + +- Everything outside of 'S' and inside `u` is shaded + - the shaded region is s̅ + +- **Definition**: The **difference** of 'A' and 'B', written `A-B` or `A\B`, is the set of elements **in 'A' but not 'B'** + +``` ++---------------------+ +| A↓ | +| +-------+ u | +| |███████| | +| |████+-------+ | +| |████| | | | +| +----|--+ |← | +| | |B | +| +-------+ | ++---------------------+ +``` + +- The shaded region is `A-B` + +- **Note**: `A-B` = `A∩¯(B̄̄̄̄̄̄̄̄̄)` + - (line above 'B' -> complement of B) + +--- + +## Set Identities + +| | | | +|-|-|-| +|**Commutative**|`A∪B` = `B∪A`|`A∩B` = `B∩A`| +|**Associative**|`A∪(B∪C)` = `(A∪B)∪C`|`A∩(B∩C)` = `(A∩B)∩C`| +|**De Morgan (for sets)|`¯(A∩B)` (not in ('A and 'B')) = `¯(A)∪¯(B)`|`¯(A∪B)` (not in ('A or 'B')) = `¯(A)∩¯(B)`| + +--- + +# 2.2 Set Operations p2 + +Ex: Let `A ≺= B`. Prove that `A∪B ≺= B` +- Proof: Let x∈A∪B. Then, x∈A or x∈B. + - Case 1: If x∈A, then x∈B since `A ≺= B` + - Case 2: If x∈B, then we are done + - ∴ x∈B which implies `A∪B ≺= B` ▣ + +- **Theorem**: Let 'A', 'B' be sets. 'A' = 'B' iff `A ≺= B` and `B ≺= A` |