Exam 3 Discrete Math

relation R from set A to set B

subset of AxB

reflexive

∀a∈A, (a,a) ∈ R

how to prove reflexive

assume that a∈A and prove (a,a) ∈ R

reflexive simple terms

for any a in A, it will be related to itself. for example if the relation is x-y=0, then prove that x-x is in the relation aka that x-x=0

symmetric

∀a,b∈A, (a,b)∈R → (b,a)∈R

how to prove symmetric

assume (a,b)∈R and prove (b,a)∈R. think, if 2x=y then we need to prove that 2y=x.

symmetric simple terms

if x is related to y, then y is related to x. a valid example would be an inequality, if 4≠3 then 3≠4

antisymmetric

∀a,b∈A, [(a,b)∈R ∧ (b,a)∈R] → a=b

antisymmetric simple terms

if aRb and bRa, then a=b

something can be symmetric and not anti symmetric and/or vice versa

true, for example relation y=2x is not symmetric but is antisymmetric. y=2x and x=2y only holds true when y and x are 0.

how to prove antisymmetric

assume that xRy and yRx, does this only occur when y=x? think about the relation y=2x. xRy and yRx is only true when x and y are 0, therefore it’s asymmetric

transitive

∀a,b,c∈A, [(a,b)∈R ∧ (b,c)∈R] → a=c

transitive simple terms

if x is related to y and y is related to z, then x is related to z.

how to prove transitive

assume that xRy and yRz is true, prove xRz

induction steps

prove base case, let k>=n, assume p(k), prove k+1, conclude that p(k) implies p(k+1)

equivalence relation

symmetric, transitive, and reflexive

a|b

a divides b, b=ak, (b/a)=k

a mod b = c

a divided by b leaves remainder 2

5|15

15/5 or 3

4 mod 3 =?

1, 4/3 leaves remainder 1

product rule

if a task can be split into smaller, subsequent tasks A and B and there are x ways to do A and y ways to do B, then there are xy ways to do A then B

sum rule

if there are separate tasks A and B, and A can be done x ways and B can be done y ways, then A and B can be done x+y ways

(n!)/(n-k)!

permutation

(n!)/(n-k)!

represents the number of permutations of length k from a list of n elements without repetition

when to use permutation

when order matters, like strings or sequences

(n!)/(k!(n-k)!)

combination

when to use combination

when order doesn’t matter, (like sets? double check)

subtraction rule

if a task can be done x ways or y ways, then you can add those ways and subtract the common

subtraction rule is similar to...

addition probability rule: AorB=A+B-(AandB)

subtraction rule written out

x + y - (common ways)

division rule

add

pigeonhole principle theorem

if k+1 items are placed into k boxes, one box will have more than one item

generalized pigeonhole principle

if n objects are places into k boxes, there at least one box containing [n/k] items (ceiling function!)

note to self

review pigeonhole principle and how it’s applied, do all answers need the theorem listed?

review division rule

note to self

review permutation vs combination

when to use each self study note to self

induction, practice concluding things for strong induction like in hw problem 12

note to self