If `P` then `Q`
`P` and `Q` are statements. Statements are exclusively `true` or `false`
`P` is the hypothesis and `Q` is the conclusion
Prove: `-3 = 3`
`=> (-3)^2 = 3^2`
`=> 9 = 9`
`-3 = 3`
Wrong because the proof doesn't go `lArr`
`f: S -> T`
`f` is a function, `S` is the domain, `T` is the codomain
If `a in R`, then `|a| = {(a if a >= 0),(-a if a <= 0):}`
Prove: `|a|^2 = a^2`
Let `a in RR`. Then `a >= 0` or `a <= 0`
Proof by cases: Case 1: `a >= 0`; Case 2: `a <= 0`
Case 1: Suppose `a >= 0`. Then `|a| = a`, so `|a|^2 = a^2`
Case 2: Suppose `a <= 0`. Then `|a| = -a`, so `|a|^2 = (-a)^2 = a^2`
Let `b in ZZ`. `5` divides `b` `<=> 5x = b` for some integer `x`
`<=> EE x in ZZ, 5x = b`
Trichotomy: `AA x, y in RR`, exactly one is true:
`x < y`
`x > y`
`x = y`
Proposition (false): `x - y in ZZ^+`, `AA x, y in ZZ^+`
Let `x = 1, y = 2`
`x, y in ZZ^+`, but `x - y = -1 !in ZZ^+`
Def: `a` divides `b` if `EE k in ZZ, ak = b`
`a | b`
Proposition: If `c|a` and `c|b`, then `c|(a + b)`
Suppose `c|a` and `c|b`. By definition, `EE k, l in ZZ` `s.t.` `ck = a` and `cl = b`
So `a + b = ck + cl = c(k + l)`, where `k+l in ZZ`
Proposition: If `n` is even, then `n^2` is even. `n` is even if `2` divides `n`
Suppose `n` is even. Then `EE k in ZZ`, `n = 2k`
`n^2 = (2k)^2 = 2*2k^2`
Since `2k^2 in ZZ`, `n^2` is even
Prove: There does not exist `m, n in ZZ` `s.t.` `51m - 34n = 101`
Suppose for contradiction that `EE m, n in ZZ` `s.t.` `51m - 34n = 101`
`51m - 34n = 101 => 17(3m - 2n) = 101`
Let `k in ZZ`
Case 1: Suppose `k <= 5`. Then `17k <= 17*5 = 85`
Case 2: Suppose `k >= 6`. Then `17k >= 17*6 = 102`
So `AA k in ZZ`, `7k != 101`, which is a contradiction
Template for `P => (Q or R)`
Assume `P` is true
Suppose `Q` is not true
Thus `R` is true
Prove: If `a in RR` satisfies `a^2 >= 7a`, then `a <= 0` or `a >= 7`
Suppose `a^2 >= 7a`
Assume `a cancel(<=) 0`. Then `a > 0`
`a^2 = a*a >= 7a => a >= 7` (because `a > 0`)
Prove: `1 + 2 + ... + n = (n(n+1)) / 2` for each `n in ZZ^+`
Base case (`n = 1`): `1 = (1(1+1)) / 2`. So `P(1)` is true
Inductive step: Suppose `k in ZZ^+` is such that `P(k)` is true
WTS `P(k+1)` is true, `i.e.`, `1 + 2 + ... + k + (k+1) = ((k+1)(k+2)) / 2`
Suppose `1 + 2 + ... + k = (k(k+1)) / 2`
Then `(1 + 2 + ... + k) + (k+1) = ((k(k+1)) / 2) + (k+1)`
`= ((k^2 + k)) / 2 + (2(k+1)) / 2`
`= ((k^2 + k)) / 2 + (2k + 2) / 2`
`= ((k^2 + 3k + 2)) / 2`
`= ((k+1)(k+2)) / 2`
Prove: `n! > 2^n` `AA n >= 4`
Base case (`n= 4`): `4! = 24 > 2^4 = 16`
Suppose `k >= 4` satisfies `k! > 2^k`, `i.e.` `(k!) / 2^k > 1`
Then `((k+1)!) / 2^(k+1) = (k!(k+1)) / (2^k * 2) > (k+1) / 2 > 1`
(Since `k >= 4`, `(k+1) / 2 > 1`, `i.e.` it is a positive integer greater than 1. Since `(k!) / 2^k > 1`, a positive integer greater than `1` multiplied by another positive integer greater than `1` will result in a positive integer greater than `1`)
Division Theorem: Let `b in ZZ^+` and let `a in ZZ`.
Then there exist unique integers `q` and `r` `s.t.` `a = q*b + r`, `0 <= r < b`
Idea: divide `a` by `b` to get the smallest nonnegative remainder `r`
`17 = 3*5 + 2`
`a = q*b + r`
Consider `b = 2`
Given `a in ZZ`, there exist unique `q, r in ZZ` `s.t.` `a = 2q + r`, where `r = 0` or `r = 1`
Proposition: If `r = 1`, `a` is odd.
(from uniqueness of `r`) Assume `r = 1`, `i.e.` `a = 2q + 1`.
Suppose for contradiction that `a` is even
Then `a = 2k` for some `k in ZZ`, so `a` has `0` as a remainder, `i.e.` `a = 2k + 0`
By uniqueness in Division Theorem, `q = k` and `1 = 0`, which is a contradiction
`a` even `<=> EE q in ZZ` `s.t.` `a = 2q`
`a` odd `<=> EE q in ZZ` `s.t.` `a = 2q + 1`
Proposition: Let `a in ZZ`. If `a^2` is even, then `a` is even.
Contrapositive: If `a` is odd, then `a^2` is odd
Suppose `a` is odd. Then `EE q in ZZ` `s.t.` `a = 2q + 1`
`a^2 = (2q + 1)^2 = 4q^2 + 4q + 1`
`= 2(2q^2 + 2q) + 1`
Therefore, `a^2` is odd
Proving ((not `Q`) `=>` (not `P`)) `=>` (`P => Q`)
Suppose `P` is true
Suppose for contradiction not `Q`. Since (not `Q`) `=>` (not `P`), (not `P`) is true, which is a contradiction (since we supposed `P` was true)
Therefore `Q` is true
Proposition: `sqrt 2` is irrational
Assume for contradiction `sqrt 2` is rational
Then `EE a, b in ZZ^+` `s.t.` `sqrt 2 = a / b => 2 = (a / b)^2 = a^2 / b^2` where `a` and `b` have no common factors (so `a` and `b` cannot be even)
`2 = a^2 / b^2 => a^2 = 2b^2`
This means `a^2` is even, so `a` is even
Thus, `EE k in ZZ` `s.t.` `a = 2k`
Therefore, `2b^2 = a^2 = (2k)^2 = 2*2k^2`
So `2b^2 = 2*2k^2 => b^2 = 2k^2`
This means `b^2` is even, so `b` is even
Since `a` and `b` are both even, `2` is a common divisor of `a` and `b`, which contradicts the fact that `sqrt 2 = a / b` is rational
Suppose `X = {T_1, T_2}` and `Y = {1, 2}`
`EE` a function `f: Y -> X` defined by `f(1) = T_2` and `f(2) = T_1`
`Fun(X,Y)`: set of all functions from `X` to `Y`
`RR^2 = RR xx RR = {(x, y) | x, y in RR}` (cartesian product)
Let `A` and `B` be sets.
`A = B` means they have the same elements, `i.e.` `x in A <=> x in B` (`A sube B` and `B sube A`)
`A sube B` means `x in A => x in B`
Proposition: `(A sube B` and `B sube C)` `=> A sube C`
Suppose `A sube B` and `B sube C`
Let `x in A`. Since `x in A` and `A sube B`, `x in B`
Since `x in B` and `B sube C`, `x in C`
So `A sube C`
Proposition: Let `D` and `U` be sets `s.t.` `D sube U` and `D^c sube U`. Then `D uu D^c = U`
`(U sube D uu D^c)`: Suppose `x in U`
If `x in D`, then `x in D uu D^c`
If `x notin D`, then `x in D^c`. Then `x in D uu D^c`
`(D uu D^c sube U)`: Suppose `x in D uu D^c`
Then `x in D` or `x in D^c`
Suppose `x in D`. Since `x in D` and `D sube U`, `x in U`
Suppose `x in D^c`. Since `x in D^c` and `D^c sube U`, `x in U`
`P(U)`: power set of `U` (set of all subsets of `U`)
Let `A` be a set. `A in P(U) <=> A sube U`
`P(O/)` = `{O/}`
`P({1}) = {O/, {1}}`
`P({1, 2}) = {O/, {1}, {2}, {1, 2}}`
Prove: `(A uu B) uu C = A uu (B uu C)`
Let `x in (A uu B) uu C`. Then `x in A uu B` or `x in C`
Case 1: Suppose `x in C`. Then `x in B uu C`. So `x in A uu (B uu C)`
Case 2: Suppose `x in A uu B`. Then `x in A` or `x in B`. So `x in A` or `x in B uu C`. `I.e.` `x in A uu (B uu C)`
Let `x in A uu (B uu C)`. Then `x in A` or `x in B uu C`
Case 1: Suppose `x in A`. Then `x in A uu B`. So `x in (A uu B) uu C`
Case 2: Suppose `x in B uu C`. Then `x in B` or `x in C`. So `x in A uu B` or `x in C`. `I.e.` `x in (A uu B) uu C`
When a function between finite sets has an inverse, the cardinalities of these 2 sets are equal
Let `f: X -> Y` be a function
Injection: `f(x_1) = f(x_2) => x_1 = x_2, AA x_1, x_2 in X`
Surjection: `AA y in Y, EE x in X` `s.t.` `f(x) = y`
Let `X = {(1),(2):}}`, `Y = {a}`
`f` is not an injection since `f(1) = a, f(2) = a` but `1 != 2`
`f` is a surjection since `f(1) = a`
The image map `vec f: P(X) -> P(Y)` is defined by `vec f``(A) = {f(x) | x in A}`
Known informally as the "`y`-values"
Let `X = {1, 2, 3}, Y = {a, b, c}`. Suppose `f(1) = b, f(2) = a, f(3) = b`. Let `A = {1, 3}` be a subset of `X`
`vec f``(A) = {b}`
`vec f``(X) = {a, b} != Y`
`vec f``(X) != Y <=> f` is not surjective. (So `vec f``(X) = Y <=> f` is a surjection)
`(lArr)` Suppose `f` is a surjection. Let `y_0 in Y`.
Since `f` is a surjection, `EE x_0 in X` `s.t.` `f(x_0) = y_0`
Thus, `y_0 in vec f``(X) = {f(x) | x in X}`. So `Y sube vec f``(X)`
By definition, `Y supe vec f``(X)`. So `vec f``(X) = Y`
The pre-image map `hat f: P(Y) -> P(X)` is defined by
`hat f``(B) = {x in X | f(x) in B}` where `B in P(Y)`, `i.e.` `B sube Y`
Known informally as the "`x`-values"
Let `X = {1, 2, 3}, Y = {a, b, c}`. Suppose `f(1) = b, f(2) = a, f(3) = b`
Proposition: `f` is an injection `<=> hat f``({y})` is empty or consists of exactly one point `AA y in Y`
(`lArr`) Suppose `f` satisfies the condition on the right. Suppose `x_1, x_2 in X` are such that `f(x_1) = f(x_2)`
Let `y_0 = f(x_1) = f(x_2)`. By the assumption, |`hat f``({y_0})`| `<= 1`
Well, `x_1 in hat f``({y_0})` so `hat f``({y_0}) != O/`
Thus `hat f``({y_0})` consists of exactly one point, which is `x_1`
But `x_2 in hat f``({y_0})` because `f(x_2) = y_0`
So `x_1 = x_2` (since `hat f``({y_0})` has exactly one point)
So `f` is an injection
Characteristic function of a subset `A` of a set `X` is `chi_A: X -> {0, 1}` defined by `chi_A (x) = {(1 if x in A),(0 if x notin A):}`
`Fun(X,Y) = {f | f` is a function with domain `X` and codomain `Y}`
Let `A sube X`. Then `chi_A in Fun(X, {0,1})`
Conversely, suppose `f in Fun(X, {0,1})`. If we define `A = {x in X | f(x) = 1}`, then `f = chi_A`
Proposition: `f = chi_A`
Case 1: Suppose `x_0 in A`. Then `chi_A (x_0) = 1` since `x_0 in A`
We have `f(x_0) = 1` since `x_0 in {x in X | f(x) = 1}` by definition of `A`
So `f(x_0) = 1 = chi_A (x_0)`
Case 2: Suppose `x notin A`. Then `chi_A (x) = 0` since `x notin A`
We have `f(x) = 0` since x notin {x in X | f(x) = 1}`
So `f(x) = 0 = chi_A (x)`
A set `X` has cardinality n where n is a nonnegative integer if there exists a bijection `f: NN_n -> X`
We write `|X| = n` and say `X` is finite if `|X| = n` for some `n >= 0`
Otherwise `X` is infinite
Addition Principle: If `X` and `Y` are (disjoint) finite, then `X uu Y` is finite and `|X uu Y| = |X| + |Y| (- |X nn Y|)`
Let `|X| = n` and `|Y| = m`. By definition, there exist bijections `f: NN_n -> X` and `g:NN_m -> Y`
Define `h: NN_(n+m) -> X uu Y` by `h(i) = {(f(i) if 1 <= i <= n),(g(i-n) if n+1 <= i <= m+n):}`
It suffices to show that `h` is a bijection
Suppose `i_1, i_2 in NN_(n+m)` satisfy `h(i_1) = h(i_2) = j in X uu Y`
Case 1: Suppose `j in X`. We claim that `1 <= i_1, i_2 <= n`.
For, if `i_1 >= n+1`, then `j = h(i_1) = g(i_1-n) in Y`
This contradicts the fact that `j in X` and `X nn Y = O/`
Thus, `i_1 <= n` and similarly `i_2 <= n`
Since `1 <= i_1, i_2 <= n`, `f(i_1) = h(i_1) = h(i_2) = f(i_2)`
Since `f` is injective, `i_1 = i_2 => h` is injective
Case 2: Suppose `j in Y`. From similar reasoning as above, `g(i_1-n) = h(i_1) = h(i_2) = g(i_2-n)`
Since `g` is an injection, `i_1-n = i_2-n`, so `i_1 = i_2 => h` is an injection
Proof that `h` is a surjection is left to the reader as an exercise xD
Inclusion-Exclusion Principle: If `X` and `Y` are finite, then `X uu Y` is finite and `|X uu Y| = |X| + |Y| - |X nn Y|`
By some propositions from the book (lol), `X uu Y = (X - Y) uu (Y - X) uu (X nn Y)` is a disjoint union
By the Addition Principle, `|X uu Y| = |X - Y| + |Y - X| + |X nn Y|`
`X = (X - Y) uu (X nn Y)` is a disjoint union
So `|X| = |X - Y| + |X nn Y|`
`|X uu Y| = |X| - |X nn Y| + |Y| - |Y nn X| + |X nn Y|`
`= |X| + |Y| - |X nn Y|`
| `B` | `O/` | `{a}` | `{b}` | `{c}` | `{b,c}` | `{a,c}` | `{a,b}` | `{a,b,c}` |
| `hat f``(B)` | `O/` | `{2}` | `{1,3}` | `O/` | `{1,3}` | `{2}` | `{1,2,3}` | `{1,2,3}` |