Induction and Relations

Question 1

Steps for Induction

Answer 1

1) Identify Predicate
2) Base Case
3) Inductive Hypothesis
4) Prove P(k) -> P(k+1)

Question 2

Identify Predicate

Answer 2

Let P(n) denote ______ (given equation)

Question 3

Base Case

Answer 3

Prove thing right after sum = thing after equals for the lowest ij/j value

Question 4

Inductive Hypothesis

Answer 4

Let k >= ___ (i/j value) be arbitrary and SUPPOSE P(k). ie ______ (restate Predicate with k instead of n/m/whatever

Question 5

Prove P(k) -> (Pk+1)

Answer 5

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)

Question 6

Binary Relation on a set A

Answer 6

a subset of AxA

Question 7

Reflexive

Answer 7

1) Va in A, (a,a) in R
2) aRa
3) all elements point to themselves (loops)

Question 8

Symmetric

Answer 8

1) Va,b in A, (a,b) in R -> (b,a) in R
2) aRb -> bRa
3) all arrows are double arrows

Question 9

Antisymmetric

Answer 9

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

Question 10

Transitive

Answer 10

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)

Question 11

Equivalent Relation

Answer 11

For relations, notation: R
Reflexive, symmetric, transitive

Question 12

Partial Order

Answer 12

For relations, notation: R
Reflexive, antisymmetric, transitive

Question 13

Poset

Answer 13

For sets, notation: (A,R) (set, relation)
Reflexive, antisymmetric, transitive

Question 14

Two elements are Comparable if

Answer 14

If a«b or b«a (they have an arrow somehow connecting them)

Question 15

Total Order

Answer 15

A partial order where everything is comparable

Question 16

x is minimal IFF

Answer 16

Va in A, x«a or x and a are incomparable

It points to everything or is incomparable to everything

Question 17

x is a minimum IFF

Answer 17

Va in A, x«a

it points to EVERYTHING

Question 18

x is maximal IFF

Answer 18

Va in A, a«x or a and x are incomparable

everything points to it or is incomparable to everything

Question 19

x is maximal IFF

Answer 19

Va in A, a«x

EVERYTHING points to it

Question 20

Equivalence relation (set notation)

Answer 20

For sets, notation: (A,~)
Reflexive, symmetric, transitive

Question 21

Equivalence Class

Answer 21

{x in A: a~x} (class of all related)

Question 22

Representative of Equivalence Class

Answer 22

[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)

Question 23

Set of all equivalence classes

Answer 23

A/~ = {[a], [b], [c], …}
A/~ is a partition of A

Question 24

Strong Induction Steps

Answer 24

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)