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
A and B = finite sets, R = binary relation between two sets
elements of these two sets are
vertices of a graph
(a,b) ∈ R, arrow linking related elements ==>
Directed Graph (digraph) of R
R ⊆ A x B
a,b
R = subset of A x B
(a,b) are elements in a binary relation
Binary relation on A
binary relation between a set A and itself
V ⊆ AxA
A = {1,2,3,4,5}
V = {(1,2), (3,3), (5,5), (1,4), (4,1), (4,5)}
1 and 2 are V related
3 and 3 are V related
(they have this binary relation)
Cartesian Product = ordered Pair
