mad3105 asgn2

MAD3105 Asgn2 - Closure of Relations

Ex. Set A = {0, 1}. Create a relation such that:
- R is reflexive & symmetric.
-> R = {(0,0), (1,1)}

- R is irreflexive but (R o R) is reflexive.
-> R = {(0,1), (1,0)}
-> This is b/c R^2 will end up with (0,0) and (1,1) as pairs

- R is asymmetric and irreflexive.
-> R = {(1,0)} or R = {(0,1)} both work
-> This is b/c nothing populates the central diagonal

Ex. Add closures to a digraph...
- Reflexive closure: Make sure each node has a loop to itself
- Symmetric closure: Make sure each edge has a return edge
- Transitive closure: Erm... just make it transitive

Proof: Prove that if R is symmetric, its transitive closure (R*) is also symmetric.
- Assume R is symmetric and (a,b) ∈ R*.
- There exists a path from a -> b in R and since R is symmetric, there also exists a path from b -> a.
- Thus there is a path from b -> a in the relation R and also the transitive closure of R.
- Thus we have b -> a ∈ R* whenever a -> b ∈ R*.
- Therefore, if R is symmetric, R* is also symmetric.