CP 3 Relations 1 Flashcards
what is a relation
a relation (R) from A to B is a subset of AxB when (a,b) are elements of R
- we say a is related to b (aRb)
an example of a relation
M=set of mothers
S= set of sons
R={(m,s)|m is the mother of s}
TF every relation is a function but not every function is a relation
T
What the key difference between a relation and a function
In a function every element in A is assigned to an element in B
- in a relation each element in A can be related to zero, one, or many elements in B
statement
given set S we say that R is a relation on S if R is a subset of SxS
what is reflexive
something is related to itself
what is a symmetric relation
if for all a,b∈ S, then
(a,b)∈R implies (b,a)∈R
what is antisymetric
if for all a,b∈ S, then
(a,b)∈R implies (b,a)∉ R
what is a transitive relation
if a,b,c∈S
(a,b)∈R and (b,c)∈R
implies
(a,c)∈R
TF if theres no arrows for you to apply then the definition stands
T, If there exists no arrows from a–>b–>c then there is no need for an arrow from a–>c thus it is transitive
Tf for something to be symmetric or antisymmetric not all elements must be affected
F, all elements must be affected properly in order for the relation to apply (but if nothing is touching that element its not included)
what is the criteria for a partial order
it must be reflexive, antisym. and transitive
(divisors or 42 graph)
what is the criteria for a graph
it must be antireflexive and symmetric
what is the only transitive graph
an empty set
what is the criteria for an equivalence relation
it must be reflexive, symmetric and transitive
