FUNCTIONS Flashcards
What is a function?
a special case of relation with a specific restriction on it.
where each element of A is related to exactly ONE element of b (assuming f ⊆ A X B)
! Every function is a relation, but not every relation is a function
! Everything in A maps to at most one element of B
What is the annotation for a function?
Arrow
function author =
author : BOOK –> AUTHOR
declares that author is a function from BOOK to AUTHOR
What is the inverse function?
if function age : PERSON -> N (natural number)
then age ^-1 is NOT a function
What is an injective function?
Assuming R ⊆ A X B, R is injective iff each element in B is related by R from at most ONE element from A.
- if f(a) = c and f (b) = c then a = b
What is an example of an injective function?
Each student can only have ONE student_ID number
on a graph, this means that two values from the A set cannot point to the same value in set B
What is surjective?
Assuming R ⊆ A X B, R is surjective iff each element in A involves EVERY element of B.
- if f: A > B is surjective then ran(f) = B (all of B)
What is an example of surjective function?
Every football league team relates to some players
on a graph, this means that all lines from A will connect to a value in B so that no value in B is left alone
What is a bijective function?
Assume f : A > B is bijective iff f is both injective and surjective
Each element of A maps to a different element of B, and every element of B is chosen.
What is an example of a bijective function?
every country has its own national flag
on a graph, this is shown as all values of A pointing to ONE value of B and all values of B being pointed to
What does bijection tell about the inverse?
if f : A > B is a bijection then f^-1 (inverse) : B > A is also a bijection
What does bijection tell about the number of elements ?
If f : A > B then A and B must have the same no. of elements as EVERY ELEMENT is directly mapped to another.
What is a total function?
A function where for all a in A, there exists a b in B such that (a,b) ∈ function.
Assumed that every element in A will map to some element of B
What is a partial function?
Not all elements of A have to relate to an element of B
in a mapping graph, there will be extra values in the A graph
and there will be dom(A) != A
Still a function
What will undefined values in a partial function return when called?
They will be undefined so will not return “undefined”.
How to fix undefined values in a partial function?
Lift the partial function to create a total function by using ⊥ (bottom) which all undefined elements will point to in B
this will create a new set of B⊥ which extends B with function f⊥.
Which values will map to elements ⊥(bottom)?
A \ dom(f) will go to ⊥
(so all undefined elements)
What is a partial injective function?
A function where there remains undefined values for A that still point to only ONE value in B.
What is a partial surjective?
A function where there remains undefined values for A that still point to ALL values in B.
What is a partial bijective?
A function where there remains undefined values for A but still point only to one B and include all values for B.
If f:A > B and g : B > C Are functions and f ; g : A > C is partial surjective what can we assume? what are the minimum restrictions?
f is a partial function (not all in A are used)
f is surjective (every element of b ∈ B there is element a ∈ A such that f(a) = b
g is surjective (every element of c ∈ C there is element b ∈ B where g(b) = c
if f is a partial function and g is a total function, will f ; g be a partial function?
YES, as not all values in A will be used, some will be undefined.
The inverse of a surjective function is a total function?
FALSE
not all B will point to a value in A
