Induction and Relations Flashcards
Steps for Induction
1) Identify Predicate
2) Base Case
3) Inductive Hypothesis
4) Prove P(k) -> P(k+1)
Identify Predicate
Let P(n) denote ______ (given equation)
Base Case
Prove thing right after sum = thing after equals for the lowest ij/j value
Inductive Hypothesis
Let k >= ___ (i/j value) be arbitrary and SUPPOSE P(k). ie ______ (restate Predicate with k instead of n/m/whatever
Prove P(k) -> (Pk+1)
Sum k+1 = Sum k + (____) (thing right after sum but replace all k’s with (k+1).
Multiply k+1 = Multiply k * (____) thing right after multiply but replace all k’s with (k+1)
Binary Relation on a set A
a subset of AxA
Reflexive
1) Va in A, (a,a) in R
2) aRa
3) all elements point to themselves (loops)
Symmetric
1) Va,b in A, (a,b) in R -> (b,a) in R
2) aRb -> bRa
3) all arrows are double arrows
Antisymmetric
1) Va,b in A, (a,b) in R ^ (b,a) in R -> a=b
2) aRb ^ bRa -> a=b
3) all arrows are single arrows
Transitive
1) Va,b,c in A, (a,b) in R ^ (b,c) in R -> (a,c) in R
2) aRb ^ bRc -> aRc
3) Triangles everywhere. (One side points opposite direction for single arrows)
Equivalent Relation
For relations, notation: R
Reflexive, symmetric, transitive
Partial Order
For relations, notation: R
Reflexive, antisymmetric, transitive
Poset
For sets, notation: (A,R) (set, relation)
Reflexive, antisymmetric, transitive
Two elements are Comparable if
If a«b or b«a (they have an arrow somehow connecting them)
Total Order
A partial order where everything is comparable
x is minimal IFF
Va in A, x«a or x and a are incomparable
It points to everything or is incomparable to everything
x is a minimum IFF
Va in A, x«a
it points to EVERYTHING
x is maximal IFF
Va in A, a«x or a and x are incomparable
everything points to it or is incomparable to everything
x is maximal IFF
Va in A, a«x
EVERYTHING points to it
Equivalence relation (set notation)
For sets, notation: (A,~)
Reflexive, symmetric, transitive
Equivalence Class
{x in A: a~x} (class of all related)
Representative of Equivalence Class
[a] (any element in an equivalence class can represent the class. Just so we have a short hand and don’t have to list out all elements every time.)
for any a,b in A, either [a] = [b] or [a] n [b] = empty set (either they are the same, or they’re disjoint)
Set of all equivalence classes
A/~ = {[a], [b], [c], …}
A/~ is a partition of A
Strong Induction Steps
1) Identify Predicate
2) Base Case (multiple base cases)
3) Inductive Hypothesis (Let k >= the last (largest) base case you proved. Suppose that P(0), P(1), . . ., P(k − 1), P(k) are all true (or that P(m) is true for all first base <= m <= last base, if your pattern repeats).
4) Show P(k+1)
