1c. Functions, Relations, Binary, Equivalent Flashcards
Functions
∈ ⋂ ⋃ ⊆ ∆ ⊖ ∉ Ø
input output relationship
domain = input, range =
(actual) output (co-domain = all possible outputs)
f: D –> R
f = function with D as domain, R as range
f is SURJECTIVE (onto) if it uses ALL ELEMENTS of range
every y ∈ R there exists x ∈ D with y = f(x)
Injective
one to one, every input has a unique / different output
Not a function
if all inputs DO NOT have outputs
Binary Relation
subset of cross product
if a ∈ A and b ∈ B, then (a,b ∈ R)
this pair is an element of this set
aRb = a is related to b = R(a) contains b
Binary Relation from A to A
= binary relation ON A
Binary Relation as a Function
Domain: A x B
Range: {TRUE, FALSE}
R: AxB –> {TRUE, FALSE}
R(a, b) = TRUE is equivalent to
aRb
if R is a binary relation, aRb means that
aRb = TRUE
R on set A is REFLEXIVE
when xRx for all x ∈ A
every element has to be related to itself
R on set A is SYMMETRIC
when xRy implies yRx for all x, y ∈ A
ex: {1,2} , {2,1}
R on set A is TRANSITIVE
when xRy and yRz imply xRz for all x,y,z ∈ A
Equivalence Relations
binary relation on set A that is reflexive, transitive, and symmetric
Equivalence relation on A partitions elements of A into
disjoint equivalence classes, all elements in that class are related to that class only, no others A1 ⋂ A2 = Ø, no elements in common
Surjective
Think domain = range
