Week 5 and 6 - Relations and Functions Flashcards
What is a relation?
A subset of tuples containing elements from different sets
What does it mean if R is a subset of A x B?
R is a set made up of tuples containing one element from set A and another from set B
A binary relation if reflexive if…
it contains all pairs where the two values are the same
A Binary relation is irreflexive if…
It contains no pairs where the values are the same
A binary relation is symmetric if…
for every pair, the reverse pair is also in the relation.
R^-1 is the set that contains…
The inverse of every pair in set R.
A binary relation is transitive if…
Whenever the set contains (x, y) and (y, z) it also contains (x, z)
What is an order relation?
A relation that is reflexive, anti-symmetric and transitive
What is an equivalence relation?
A relation that is reflexive, symmetric and transitive.
What conditions must a relation satisfy to qualify as a function?
Definedness
Single valuedness
What is definedness?
For every argument(input) there is a value(output)
What is single valuedness?
Only one value(output) for every argument(input)
If R⊆A×B is a functional relation then A and B are…
The domain and co-domain of the function
What does it mean if a function is injective?
The function gives a different output for every input.
What does it mean if a function is surjective?
The range is equal to the co-domain.
