Mathematical Induction Flashcards
Steps of Mathematical Induction
- Show that P(1) is true
- Show that P(k) -> P(k + 1)
Weak induction
IF we assume P(k) is true, then P(k + 1) must also be true.
Strong Induction
IF we assume P(1)∧P(2)∧. . .∧P(k)
is true, THEN P(k + 1) must also be true.
Recursive Definition
- Basis Step: Specify initial collection of element(s).
- Recursive Step: Give rule(s) for forming newer elements in the set using those elements already present in the set.
Binary Relation
from A to B
R ⊆ A × B
A = {a, b}
B = {1, 2}
A x B = {(a, 1), (a, 2), (b, 1), (b, 2)}
Binary Relation
on sole set A
R ⊆ A × A
A = {a, b}
A x A = {(a, a), (a, b), (b, a), (b, b)}
Reflexive Relation
: ∀ a [a ∈ A → (a, a) ∈ R]
Symmetric Relation
∀ a ∀ b [(a, b) ∈ R → (b, a) ∈ R]
Asymmetric
∀ a ∀ b [(a, b) ∈ R → (b, a) !∈ R]
Anti-symmetric
∀ a ∀ b [((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b)]
Transitive Relation
∀a∀b∀c
[((a, b) ∈ R ∧ (b, c) ∈ R) →
(a, c) ∈ R]
Composite/Composition
IF (x, y) is a member of R1 and (y, z) is a member of R2 THEN (x, z) is a member of R1 ◦ R2.
Matrix Representation
R = {(a, b) : a > b}
A = {1, 2}
B = {1, 2, 3}
1 = True; 0 = False;
(1, 1) -> False -> 0
(1, 2) -> False -> 0
(1, 3) -> False -> 0
(2, 1) -> True -> 1
(2, 2) -> False -> 0
(2, 3) -> False -> 0
0 0 0
1 0 0
Reflexive via Matrix
Matrix diagonals are all 1
Symmetric via Matrix
IF m(i,j) = 1, THEN m(j,i) = 1
