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
Antisymmetric via Matrix
IF m(i,j) = 1, THEN m(j,i) = 0
Reflexive via Digraph
Loop on every vertice
Symmetry via Digraph
IF (x, y) is an edge, THEN (y, x) is an edge
Antisymmetry via Digraph
IF (x, y) is an edge, THEN (y, x) is NOT an edge
Transitivity via Digraph
IF (x, y) is an edge, and (y, z) is an edge, THEN (x, z) is an edge.
Reflexive Closure
R ∪ △
R = Relation
△ = Diagonal relation (a, a) for each a in A
Symmetric Closure
R ∪ R^-1
Transitive Closure
The unity of transitive relations on a set, until subsequent relations are redundant.
ie: (1, 2), (2, 1) -> (1, 2), (2, 1), (1, 1)
