Discrete Mathematics Using a Computer Chapter 10: Relations Notes and Solutions

DiscreteMathComputer10.hs

{- Discrete Mathematics Using a Computer
   Chapter 10: Relations
-}

module Relations where
import List (nub)
import Stdm (setEq, union, isWeakest, isGreatest, isQuasiOrder, isLinearOrder)
import Data.Tuple (swap)

-- =============================================================================
-- 10.1 Binary Relations

{- A binary relation R with the type R :: A * B is a subset of A x B where 
   A is the domain and B is the codomain of R. 

   For x in A and y in B, notation xRy means (x,y) in R

   Note these are ordered pairs so xRy is not necessarily the same as yRx
-}

type Relation a b = [(a,b)] -- these should actually be sets

-- Example: Pets and Pet Owners
data PetOwners = Bill | Sue | Pat
               deriving (Eq, Show)
                        
data PetAnimals = Dog | Cat
                deriving (Eq, Show)
                         
hasPet :: Relation PetOwners PetAnimals
hasPet = [(Bill, Dog), (Sue, Dog), (Sue, Cat), (Pat, Cat)]

-- =============================================================================
-- 10.2 Digraphs

{- Aside: visual representations of relations.
   Draw each item in domain and codomain with a labeled dot.
   Draw arcs if they are connected by the relation.
-}

{- Definition 35: Digraphs
   Let A be a set, and R be a binary relation R :: A x A.
   The Digraph D of R is the ordered pair D = (A, R)
-}

type Digraph a = ([a], Relation a a)

{- Example: A = {1,2,3}, R = {(1,2), (2,3)}
   then the digraph is: D = ({1,2,3}, {(1,2), (2,3)})

   Example: A = {1,2,3,4,5}, R = {(1,2), (2,3)}
   then the digraph is: D = ({1,2,3,4,5}, {(1,2), (2,3)})

-}

{- Definition 36: Directed Path
   A directed path is a set of arcs that can be arranged in a sequence, so that
   the end point of one arc in the sequence is the start point of the next
-}

-- =============================================================================
-- 10.3 Computing with Binary Relations

-- Example:
data Color = Red | Blue | Green | Orange | Yellow | Violet
           deriving (Eq, Show)
                    
colorComplement :: Digraph Color
colorComplement = ([Red, Blue, Green, Orange, Yellow, Violet],
                   [(Red, Green), (Green, Red),
                    (Blue, Orange), (Orange, Blue),
                    (Yellow, Violet), (Violet, Yellow)])
                  
-- to say Red is the colorComplement of Green, we have to write Red colorComplement Green
-- or (Red, Green) in colorComplement
-- note that none of those are actually valid haskell. So i'll define my own function:

related :: (Eq a) => Digraph a -> a -> a -> Bool
related (_, dg) x y = (x, y) `elem` dg

{- *Main> related colorComplement Red Green
True
*Main> related colorComplement Green Red
True
*Main> related colorComplement Green Blue
False
-}

domain :: Relation a b -> [a]
domain = map fst 

codomain :: Relation a b -> [b]
codomain = map snd

{- *Main> domain $ snd colorComplement
[Red,Green,Blue,Orange,Yellow,Violet]

*Main> codomain $ snd colorComplement
[Green,Red,Orange,Blue,Violet,Yellow]
-}

{- Exercise 1:
domain [(1, 100), (2, 200), (3, 300)] => [1,2,3]
codomain [(1,100), (2, 200), (3, 300)] => [100,200,300]
crossproduct [1,2,3] [4] => [(1,4), (2,4), (3,4)]

-}

{- Exercise 2: Relations from List Comprehensions

(a)  [(a,b) | a <- [1,2], b <- [3,4]]
     Pairs: [(1,3),(1,4),(2,3),(2,4)]
     Domain: [1,2] Codomain: [3,4]

(b) [(a,b) | a <- [1,2,3], b <- [1,2,3], a == b]
    Pairs: [(1,1),(2,2),(3,3)]
    Domain: [1,2,3] Codomain: [1,2,3]

(c) [(a,b) | a <- [1,2,3], b <- [1,2,3], a < b]
    Pairs: [(1,2), (1,3), (2,3)]
    Domain: [1,2,3], Codomain: [1,2,3]
    NOTE: even though we don't have a relation to/from 3, it is still a part of domain
          and codomain
-}

-- =============================================================================
-- 10.4 Properties of Relations

--------------------------------------------------------------------------------
-- 10.4.1 Reflexive
-- Definition: A relation R over A is reflexive if xRx for every element x in
--    the domain of A.
-- Note that this means A subset of B.

isReflexive :: (Eq a) => Digraph a -> Bool
isReflexive (dom, rels) = all sameImage dom
  where sameImage x = (x,x) `elem` rels

-- examples
        
eg27 = isReflexive ([1,2], [(1,1),(1,2),(2,2)]) -- True
-- Note: presence of (1,2) in relations doesn't affect reflexiveness

eg28 = isReflexive([1,2,3], [(1,1),(2,2)]) -- False
-- False because (3,3) is not in the relations

-- Eg 29: Suppose x sameFamily y means that you're in the same family as y
-- then this relation is reflexive because you're in the same relation as yourself

-- Eg 30: ==, >=, <= are reflexive

-- Eg 31: >, < , != are not reflexive

--------------------------------------------------------------------------------
-- 10.4.2 Irreflexive

isIrreflexive :: (Eq a) => Digraph a -> Bool
isIrreflexive = not . isReflexive

-- Special Case: Empty Domain
-- The empty relation: R :: NULL x NULL is vacuously reflexive and irreflexive

-- Exercise 3: Verify whether reflexive or irreflexive

ex3a = isReflexive ([1,2,3], [(1,2)]) -- False
-- not reflexive because don't have (1,1), (2,2) and (3,3)

ex3b = isReflexive ([1,2], [(1,2), (2,2), (1,1)]) -- True
-- we have both (1,1) and (2,2)

ex3c = isReflexive ([1,2], [(2,1)]) -- False
-- don't have (1,1) and (2,2)

ex3d = isReflexive ([1,2,3], [(1,2), (1,1)]) -- False
-- don't have (2,2), (3,3)

{- Exercise 4: Are the following relations on real numbers reflexive?
   (this is weird because in the previous page, they talked about these relations
    and whether they were reflexive or irreflexive)

< : irreflexive because a < a is False forall a in R
> : irreflexive for same reason

>=, <=, =: reflexive because a <= a, a >= a, a == a for all a in R

!= : irreflexive because a != a is False for all a in R
-}

--------------------------------------------------------------------------------
-- 10.4.3 Symmetric

-- Definition: if xRy then yRx.

isSymmetric :: (Eq a) => Digraph a -> Bool
isSymmetric (_, rels) = all symCheck rels
  where symCheck (a,b) = (b,a) `elem` rels
        
-- example: equality is symmetric.
-- example: >= is not symmetric. because 1 >= 0 but 0 >= 1 is false
        
eg40 = isSymmetric ([1,2,3], [(1,2),(2,1),(2,3),(3,2)]) -- True
eg41 = isSymmetric ([1,2,3], [(1,2),(1,3),(3,1)]) -- False because don't have (2,1)

egColor = isSymmetric colorComplement -- True

{- exercise 5: is the relation isChildOf symmetric?
   No. If x is the child of y, then y can't be the child of x.
-}

{- exercise 6: have a relation R:: A x A, A is non-empty and reflexive. Only have
   the arcs necessary for the relation to be reflexive. is it symmetric?

   Since only have arcs necessary to be reflexive, all pairs in the relation are
   of the form (x,x) forall x in A.

   So, the relation is symmetric as well.
-}

{- Exercise7: in the definition of a symmetric relation, can the variables x and y
   be instantiated by a single node?

   rephrased: can you just have a single pair in the relation and still be symmetric?

   Yes. Suppose the only pair is (x,x) for some x in A. Then this relation is reflexive.

-}

--------------------------------------------------------------------------------
-- 10.4.4: Antisymmetric

-- Definition: it is never the case that both xRy and yRx if x and y are distinct.
-- Better definition: xRy and yRx => x == y

isAntisymmetric :: (Eq a) => Digraph a -> Bool
isAntisymmetric (_, rels) = not $ any asymCheck rels
  where asymCheck (a,b)
          | a == b = False -- only care about pairs involving distinct elts
          | otherwise = (b,a) `elem` rels


-- *Main Data.Tuple> isAntisymmetric ([1,2,3], [(1,1), (2,2), (3,3)])
-- True
-- *Main Data.Tuple> isAntisymmetric ([1,2,3], [(1,1), (2,1), (3,3), (1,2)])
-- False
-- *Main Data.Tuple> isAntisymmetric ([1,2,3], [(1,1), (2,1), (3,3)])
-- True

-- We can interpret antisymmetric as forbidding cycles of length 2 
-- all other cycles are allowed.

{- Exercise 8: Are the following relations symmetric?

   isSymmetric ([1,2,3],[(1,2),(2,3)]) -- False
   Don't have (2,1) and (3,2)

   isSymmetric ([1,2], [(2,2),(1,1)]) -- True
   
   isAntisymmetric ([1,2,3],[(2,1),(1,2)]) -- False
   False because we have both (1,2) and (2,1) but 1 != 2

   isAntisymmetric ([1,2,3], [(1,2),(2,3),(3,1)]) -- True
   Don't have any 1 length cycles.
-}

{- Exercise 9: Which relations are symmetric? antisymmetric?

a) Empty binary relation over a set of four nodes.
   vacuously symmetric as well as antisymmetric.

b) The = relation
   Is symmetric. if a = b then b = a.

   Is anti-symmetric. Since first and second elements of each tuple are the same.

c) The <= relation
   Not symmetric. E.g. 10 <= 11, but 11 <= 10 is false.

   Is antisymmetric. If we have (a,b), then the only time we have (b, a) is if b == a. 

d) The < relation
   Not symmetric. E.g. 9 < 10 but 10 < 9 is false.

   Is antisymmetric. We never have (b,a) if we have (a,b)
-}

-- =============================================================================
-- 10.4.5 Transitive Relations

-- Definition: R :: A x B is transitive if forall x,y,z in A, xRy and yRz implies
-- xRz
        
isTransitive :: (Eq a) => Digraph a -> Bool
isTransitive (_, rels) = all transitive rels
  where transitive (x,y) = all (\ (y,z) -> (x,z) `elem` rels) [p | p@(a,b) <- rels, a == y] 
        
egTrans1 = ([1,2,3], [(1,2), (2,3), (1,3)]) -- True
egTrans2 = ([1,2,3], [(1,2), (2,3)]) -- False

{- Exercise 10: Are the following transitive?
   
   isTransitive ([1,2], [(1,2), (2,1), (2,2)])
   We have (1,2) and (2,1) but not (1,1) so not transitive.

   isTransitive ([1,2,3], [(1,2)])
   We have (1,2) but not (2,1) so not transitive
-}

{- Exercise 11: Which of the following relations on Real numbers are transitive?
   
   == : If a == b, and b == c, then a == c. So == is transitive
        Transitive

   != : If a != b, and b != c, we can still have a == c. E.g. a = 2, b = 3, c = 2.
        Not Transitive

   < : If a < b and b < c, then a < c.
       Transitive

  <= : Since both < and == are transitive, <= is transitive as well

  >, >= : Transitive for same reasons as < and <=
-}

{- Exercise 12: Which relations are transitive?

a) Empty Relation: Vacuously transitive.

b) isSiblingOf relation: transitive.

c) An irreflexive relation: 
   If irreflexive, we know that for all x in A, not xRx.
   We don't know anything about how distinct elements relate to one another;
    there is no restriction at all about xRy where x != y.
   So, it may or maynot be transitive.
   (If it is irreflexive and symmetric, then not transitive:
     proof: Suppose xRy. Then yRx by symmetry. So, expect xRx by transitivity,
            but due to irreflexivity, can't have that)

d) the isAncestorof relation:
   transitive.

-}

-- =============================================================================
-- 10.5 Relational Composition

{- Definition: Let R1 :: A x B be a relation, and let R2 :: B x C be another relation
   Then, R1;R2 :: A x C is the relational composition of R1 and R2 and is defined:

   {(a in A, c in C) | exists b in B s.t. (a,b) in R1, and exists b in C such that (b,c) in R2}
-}

relationCompose :: (Eq a, Eq b, Eq c) => [(a,b)] -> [(b,c)] -> [(a,c)]
relationCompose xs ys = [(a,c) | (a,x) <- xs, (y,c) <- ys, x == y]

egR1 = [(1,2), (2,3), (3,4)]

{- expect egR1 compose egR1 to be:
   (a,b)   |  (b,c)     | (a,c)
   (1,2)      (2,3)       (1,3)

   (2,3)      (3,4)       (2,4)
   (3,4)      _           _

   ans: [(1,3), (2,4)]
-}

-- *Main Data.Tuple> relationCompose egR1 egR1
-- [(1,3),(2,4)]

-- Exercise 13: Calculate the Relation Composition of
ex13a = relationCompose [(1,2), (2,3)] [(3,4)] -- expect: [(2,4)]
-- *Main Data.Tuple> ex13a
-- [(2,4)]

ex13b = relationCompose [(1,2)] [(1,3)]-- expect : []
-- *Main Data.Tuple> ex13b
-- []

-- Exercise 14: More composition calculations
ex14a = relationCompose [("Alice", "Bernard"), ("Carol", "Daniel")] [("Bernard", "Carol")] -- expect [(alice, carol)]
-- *Main Data.Tuple> ex14a
-- [("Alice","Carol")]

ex14b = relationCompose [("a", "b"), ("aa", "bb")] [("b","c"), ("cc", "bb")] -- expect [(a,c)]
-- *Main Data.Tuple> ex14b
-- [("a","c")]

ex14c = relationCompose r r
  where r = [(1,2), (2,3), (3,4), (4,1)] -- expect: [(1,3), (2,4), (3,1) (4,2)]
-- *Main Data.Tuple> ex14c
-- [(1,3),(2,4),(3,1),(4,2)]
  
ex14d = relationCompose [(1,2)] [(3,4)] -- expect: []
-- *Main Data.Tuple> ex14d
-- []

-- 14e: Empty set and any other relation: empty set.

-- =============================================================================
-- 10.6 Power of Relations

-- Suppose Flight is a relation defining all cities you can get to in 1 flight
-- Then, Flight;Flight is a relation with all cities you can reach in exactly 2 flights
-- Flight^nFlight is a relation with all cities you can reach in exactly n flights

relPower :: (Eq a) => [(a,a)] -> Int -> [(a,a)]
relPower x 0 = [(a,a) | (a,_) <- x]
relPower x 1 = x
relPower x n
  | even n = relPower (nub (relationCompose x x)) (n `div` 2)
  | otherwise = relationCompose (nub (relPower x (n - 1))) x

eg55 = relPower [(2,3), (3,2), (3,3)] 4
{-   = relPower [(2,2), (2,3), (3,3), (3,2)] 2
     = relPower [(2,2), (2,3), (3,3), (3,2)] 1
     = [(2,2), (2,3), (3,3), (3,2)]

Note the interesting behavior of power on cycles.
-} 

-- Exercise 15: "equalityRelation" computations
equalityRelation :: [a] -> [(a,a)]
equalityRelation xs = zip xs xs

ex15a = equalityRelation [1,2,3] -- [(1,1), (2,2), (3,3)]
ex15b = equalityRelation ([] :: [Int]) -- []

-- Exercise 16: relational power computations
ex16a = relPower [(1,2), (2,3), (3,4)] 1 -- expect: [(1,2), (2,3), (3,4)]
ex16b = relPower [(1,2), (2,3), (3,4)] 2 -- expect: [(1,3), (2,4)]
ex16c = relPower [(1,2), (2,3), (3,4)] 3
{- relCompose [(1,2), (2,3), (3,4)] (relPower [(1,2), (2,3), (3,4)] 2)
 = relCompose [(1,2), (2,3), (3,4)] [(1,3), (2,4)]
 = [(1,4)]

*Relations Data.Tuple> ex16c
[(1,4)]
-}
ex16d = relPower [(1,2), (2,3), (3,4)] 4
{- relPower (relPower [(1,2), (2,3), (3,4)] 2) 2
   = relPower [(1,3), (2,4)] 2
   = []

*Relations Data.Tuple> ex16d
[]
-}

{- Exercise 17: Why do we not need to check the ordered pairs in R while calculating
   R^0; R?
   
   R^0 produces a list of pairs that look like (a,a)
   when we compose R^0 with R^1 (which contains pairs that look like (a,b))
   we get back (a,b)

   In other words, R^0 is the identity for composition so we don't even need to evaluate
   the other argument.
-}

{- Exercise 18: Why can we stop calculating powers after finding two successive powers that
   have the same relation?

   Suppose we found that R^m = R^(m + 1)
   TO find the next power, i.e. R^(m + 2), we're going to do:
   R;R^(m + 1)
   = R;R^m
   = R^(m + 1)

   So, once we find that two successive powers have the same relation, we have found the
   fixed point, so we can stop computing.
-}


ex19 = relPower [(2,2), (4,4)] 4 
{- relPower [(2,2), (4,4)] 2 = [(2,2), (4,4)]
   So, the fixed point is [(2,2), (4,4)] which is the answer
-}


{- Exercise 20: What is the relationship between adding new ordered pairs to make a relation
   transitive and taking the power of a relation?

   If the power is 2, then the pairs added are the same.

   e.g. suppose we have [(a,b), (b,c)] 
   to make it transitive, we need to add (a,c)
   this is exactly what relPower [(a,b), (b,c)] 2 would do.
-}

{- Exercise 21: Suppose a set contains n elements. How many possible relations with type
   R :: A * A are there?

   Consider all the pairs that start with a certain element (i.e. [(a,_)])
   There are 2^n such lists.

   There are n choices of the first element of the pair. So the answer is (2^n)^n
   Since (x^y)^z = x^(yz) , we have 2^(n^2) possibilities

   Alternate derivation: it is the powerset of A cross A.
   A cross A has n^2 elements.
   Powerset of that is 2^(n^2)
-}

{- Exercise 22: Given R = {(a,b), (b,c), (c,d), (d,e)}. How many times do we have to compose it with itself
   before we get the empty relation?

   Pow 2: {(a,c), (b,d), (c,e)}
   Pow 3: compose [(a,c), (b,d), (c,e)] [(a,b),(b,c),(c,d),(d,e)]
          = [(a,d), (b,e)]
   Pow 4: compose [(a,d), (b,e)]  [(a,b),(b,c),(c,d),(d,e)]
          = [(a,e)]
   Pow 5: compose [(a,e)]  [(a,b),(b,c),(c,d),(d,e)]
          = []
-}

ex22 = map (relPower [("a","b"), ("b","c"), ("c","d"), ("d","e")]) [1..10]
-- *Relations Data.Tuple> ex22
-- [[("a","b"),("b","c"),("c","d"),("d","e")],[("a","c"),("b","d"),("c","e")],[("a","d"),("b","e")],[("a","e")],[],[],[],[],[],[]]
-- The first empty list is at power 5

{- Exercise 23: A = {1,2,3}, R = {(3,1), (1,2), (2,3)}
   R^2 = compose {(3,1), (1,2), (2,3)} {(3,1), (1,2), (2,3)}
       = [(3,2), (1,3), (2,1)]

   R^3 = compose [(3,2), (1,3), (2,1)] [(3,1), (1,2), (2,3)]
       = [(3,3), (1,1), (2,2)]
-}

ex23 = map (relPower [(3,1), (1,2), (2,3)]) [2,3]

-- =============================================================================
-- 10.7 Closure Properties of Relations

{- Scenario: Want a relation to have some special properties (e.g. transitive, symmetric)
   But might have to add a large number of pairs to the relation.

   So, have a "basic" relation with just the info specified.
   Derive a larger relation by adding the required ordered pairs.

   [this by itself made no sense, but the following example was helpful]
   Scenario: airline has a relation Flight. (a,b) in Flight means there is a direct flight from a to b.
   but customer asks if he can go from x to z using the airline.
   so the airline needs a transitive relation of the form (x, y), (y, z) to answer this query.

   Note: the above is correct only when the customer asked for destinations at most one stop away.

   ------------------ DEFINITION --------------
   Closure of a relation R with respect to a property is the smallest relation
   that contains R and has the property.
-}

--------------------------------------------------------------------------------
-- 10.7.1 Reflexive Closure

containsPrimaryColor :: Digraph Color
containsPrimaryColor = ([Red, Blue, Green, Orange, Yellow, Violet],
                        [(Violet, Blue), (Violet, Red),
                         (Green, Blue), (Green, Yellow),
                         (Orange, Red), (Orange, Yellow),
                         (Blue, Blue), (Red, Red), (Yellow, Yellow)])
                       
-- This relation is not reflexive because Violet, Green, Orange don't have reflexive arcs.
-- The following Relation, which is containsPrimaryColor plus those reflexive arcs is reflexive
-- Hence, containsColor is the reflexive closure of containsPrimaryColor

containsColor :: Digraph Color
containsColor = ([Red, Blue, Green, Orange, Yellow, Violet],
                 [(Violet, Blue), (Violet, Red),
                  (Green, Blue), (Green, Yellow),
                  (Orange, Red), (Orange, Yellow),
                  (Blue, Blue), (Red, Red), (Yellow, Yellow),
                  (Violet, Violet), (Green, Green), (Orange, Orange)])
                
-- *Relations> isReflexive containsPrimaryColor
-- False
-- *Relations> isReflexive containsColor
-- True                

{- Definition: REFLEXIVE CLOSURE
   Let A be a Set.
   Suppose R :: A x A is a binary relation over A.

   The reflexive closure of R, is the relation R' such that:
     1. R' is a superset of R
     2. Any reflexive relation R'' that is a superset of R is also a superset of R'

   Notation: r(R) denotes the reflexive closure of R

   Interpretation
   1. says that the reflexive closure is atleast as large as the base relation
      if they're the same size, the original is already reflexive.
      otherwise, you're only allowed to ADD relations to make it reflexive.

   2. says that the reflexive closure is the smallest relation


   THEOREM 73: r(R) = R U E where E is the equality relation over the domain of R
   Proof: 
    Part 1: R U E is reflexive
    Consider arbitrary  x in A. 
    Since x == x, (x,x) is in E. 
    So, (x,x) is in R U E. 
    Hence, R U E is a reflexive

    Part 2: R U E is the smallest superset of R that is reflexive.
    Proof: Suppose R U E contains an extraneous (a,b) pair.
    Either a == b or a != b.
    If a == b, we can't omit it without losing the reflexivity property.

    If a != b, it wasn't added by E, so it must have been in R. 
    If we remove (a,b), the new relation is no longer a superset of the old one.

    So, R U E is reflexive and is the smallest superset possible.
    In other words, it is the reflexive closure.
-}

reflexiveClosure :: (Eq a) => Digraph a -> Digraph a
reflexiveClosure (dom, rels) = (dom, nub $ (zip dom dom) ++ rels)

isReflexiveClosure :: (Eq a, Show a) => Digraph a -> Digraph a -> Bool
isReflexiveClosure base derived = samedom base derived && sameRels derived (reflexiveClosure base)
  where samedom (d1, _) (d2, _) = setEq d1 d2
        sameRels (_, r1) (_, r2) = setEq r1 r2
        

eg57 = isReflexiveClosure ([1,2,3], [(1,2),(2,3)]) ([1,2,3], [(1,1), (2,2), (3,3), (1,2), (2,3)]) -- True

eg58 = isReflexiveClosure ([1,2,3], [(1,2), (2,3)]) ([1,2,3], [(1,1), (2,2), (3,3)]) -- False: missing arcs

eg59 = isReflexiveClosure ([1,2,3], [(1,2),(2,3)]) ([1,2,3], [(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)])
-- False: has extra arcs.

{- Exercise 24: Find the Reflexive closures of:

   reflexiveClosure ([1,2,3], [(1,2),(2,3)])
   => answer: ([1,2,3], [(1,2), (2,3), (1,1), (2,2), (3,3)]) by adding the pairs from E.

   reflexiveClosure ([1,2], [(1,2), (2,1)]
   => answer: ([1,2], [(1,2), (2,1), (1,1), (2,2)])
-}

{- Exercise 25: What is the reflexive closure of [(1,2), (2,1)]?
   Don't know the domain so can't tell.

   Assuming domain is [1,2], the answer is [(1,1), (2,2), (1,2), (2,1)]
-}

--------------------------------------------------------------------------------
-- 10.7.2 Symmetric Closure

{- DEFINITION
   Suppose A is a set, and R :: A x A. Then, the symmetric closure of R is the relation R':
   1. R' is symmetric
   2. If R'' is a symmetric relation that is a superset of R, R'' is a superset of R'

   i.e. R' is the smallest superset of R that is symmetric

   THEOREM:
   R' = R U Rc where Rc is the converse of R
    Definition: Converse of a relation R :: A x B is Rc = [(b,a) | (a,b) in R]

   Lemma: R U Rc is symmetric.
   Proof: Consider a  pair (a,b) in R U Rc.
   Either it came from R or it came from Rc (or it's present in both).
   If it is present in R, then (b,a) is in Rc so this pair doesn't cause loss of symmetry.
   If it is present in both, a == b, so it is its own symmetric counterpart.
   Thus, every pair in the relation has a symmetric counterpart, so the relation is symmetric.

   Lemma: R U Rc is the smallest symmetric superset of R
   Proof is by contradiction.
   Suppose R U Rc contains a pair (a,b) that is extraneous.
   
   If (a,b) came from R, excluding it would result in a loss of the superset property.
   If it came from Rc, (b,a) must be present in R, so not adding (a,b) results in a loss
   of symmetry.

   So, we can't remove any pair without losing the desired properties.

   Theorem: R U Rc is the symmetric closure of R
   Proof: By lemma 1, R U Rc is symmetric and by lemma 2 any symmetric superset of R must
   contain R U Rc. Thus, R U Rc is the symmetric closure of R. 
-}

converse :: [(a,b)] -> [(b,a)]
converse = map swap

symmetricClosure :: (Eq a) => Digraph a -> Digraph a
symmetricClosure (dom, rel) = (dom, nub (converse rel ++ rel))

{- Exercise 26: Calculate symmetric closures by hand:
   
symmetricClosure ([1,2], [(1,1), (1,2)])
 => ([1,2], [(1,1), (1,2), (2,1)])

symmetricClosure ([1,2,3], [(1,2), (2,3)])
=> ([1,2,3], [(1,2), (2,1), (2,3), (3,2)])

-}

{- Exercise 27: What is the symmetric reflexive closure of {(a,b), (b,c)}
Assuming domain is [a,b,c]

need to add (a,a), (b,b), (c,c) to make it reflexive
need to add (b,a), (c,b) to make it symmetric

so, [(a,b), (b,c), (a,a), (b,b), (c,c), (b,a), (c,b)] is the answer

*Relations> symmetricClosure (reflexiveClosure (['a', 'b', 'c'], [('a', 'b'), ('b', 'c')]))
("abc",[('a','a'),('b','b'),('c','c'),('b','a'),('c','b'),('a','b'),('b','c')])
-}

--------------------------------------------------------------------------------
-- 10.7.3 Transitive Closure

{- DEFINITION
   Let A be a set of n elements, and R :: A x A be a binary relation over R

   The transitive closure of R is defined as the set of all pairs (a,b) where
   you can "reach" b from a. 

   Formally: t(R) = UNION_{i = 1}^n R^i 

   The limit is $n$ because the largest possible chain is n.

   But, we can use the following facts about power to stop early:
   1. If we get [] for some i, we can ignore all i +1, ..., n
   2. If we get R^i = R^i + 1, we can stop because we've reached the fixed point.

-}

-- Note: doesn't use the optimizations i talked about above
transitiveClosure :: (Eq a) => Digraph a -> Digraph a
transitiveClosure (dom, rel) = (dom, grandUnion [relPower rel i | i <- [1.. length dom]])
  where grandUnion = foldr union []

-- Book's example:
-- *Relations> transitiveClosure ([1,2,3,4], [(1,2), (2,3), (3,2), (3,4), (4,4)])
-- ([1,2,3,4],[(1,2),(2,3),(3,2),(3,4),(4,4),(1,3),(2,2),(2,4),(3,3),(1,4)])

{- exercise 29: calculate the following transitive powers by  hand

transitiveClosure ([1,2,3], [(1,2), (2,3)])
 power1 : [(1,2), (2,3)]
 power2 : [(1,3)]
 power3 : []
 So: ([1,2,3], [(1,2), (2,3), (1,3)])

-- *Relations> transitiveClosure ([1,2,3], [(1,2), (2,3)])
-- ([1,2,3],[(1,2),(2,3),(1,3)])

transitiveClosure ([1,2,3], [(1,2), (2,1)])
 power2 : [(1,1), (2,2)]
 power3 : [(1,2), (2,2)]
 So: ([1,2,3], [(1,2), (2,1), (1,1), (2,2)])

-- *Relations> transitiveClosure ([1,2,3], [(1,2), (2,1)])
-- ([1,2,3],[(1,2),(2,1),(1,1),(2,2)])

-}


{- Exercise 30: how to speed up transition closure algorithm?
   as discussed before: stop at fixpoint and empty.
-}

{- Exercise 31: Find symmetric closure and symmetric transitive closure of:
[(a,b), (a,c)]
  power2: []
  so transitive closure is just [(a,b), (a,c)]
  after making it symmetric: [(a,b), (a,c), (b,a), (c,a)]

*Relations> symmetricClosure $ transitiveClosure ("abc", [('a','b'), ('a','c')])
("abc",[('b','a'),('c','a'),('a','b'),('a','c')])

--------------------
[(a,b)]
  transitive closure is itself
  to make it symmetric: [(a,b), (b,a)]

*Relations> symmetricClosure $ transitiveClosure ("ab", [('a','b')])
("ab",[('b','a'),('a','b')])

--------------------
[(1,1), (1,2), (1,3), (2,3)]
 transitive closure:
   power2: [(1,1), (1,2), (1,3)]
   power3: [(1,1), (1,2), (1,3), (2,3)]
   so: [(1,1), (1,2), (1,3), (2,3)]

  to make it symmetric:
   [(1,1), (1,2), (1,3), (2,3), (2,1), (3,1), (3,2)]

--------------------
[(1,2), (2,1), (1,3)]
 transitive closure:
  power2: [(1,1), (2,2), (2,3)]
  power3: [(1,2), (1,3), (2,1)]
  so: [(1,2), (2,1), (1,3), (1,1), (2,2), (2,3)]

 to make it symmetric:
  [(1,2), (2,1), (1,3), (3,1), (1,1), (2,2), (2,3), (3,2)]
-}

-- =============================================================================
-- 10.8 Order Relations

-- an order relation specifies an ordering that can be used to create a sequence
-- from the elements in the domain.
-- e.g. < , <= etc.

--------------------------------------------------------------------------------
-- 10.8.1 Partial Order

{-
puts atleast some of the elements in its domain into a sequence
e.g. sorting a database by name: if people have the same name, they can't be 
     ordered.

e.g. ordering points (x,y) using the formula: (x1,y1) <= (x2,y2) 
     iff (x1 <= x2) && (y1 <= y2)
     Can't compare (1,4) vs (2,3)

-}

{- Definition: Partial Order
   A relation is a partial order over a set if it is reflexive, antisymmetric and transitive.

   Why are each of the conditions necessary?
   1. Suppose not transitive:
      Then if a LT b and b LT c, a not LT c for some a,b,c
      So, it's not an order even for the items where it defines an order.

   2. Suppose not antisymmetric
      Then, we have both a LT b, and b LT a for some a != b
      a LT b would say that we need to put a in front of b
      but b LT a would say that we need to put b in front of a

   3. Suppose not reflexive
      If we don't have this then we don't have equality (can't compare an item with itself)
      Probably not a good idea. (NOTE: later we talk about quasi order which don't have reflexivity)
-}

isPartialOrder :: (Eq a) => Digraph a -> Bool
isPartialOrder xs = and [f xs | f <- [isReflexive, isTransitive, isAntisymmetric]]

-- poset diagram: remove all reflexive and transitive edges from the normal graph

{- DEFINITION: weaker
   If x precedes y in the partial order, then x is weaker than y. 
   

   DEFINITION: incomparable
   If there is no directed path from x to y and no path from y to x, the two are incomparable

   DEFINITION: least elements
   the set of least elements of a poset p is:
   {x in P | forall y in P. (x weaker y or (x notweaker y and y notweaker x))}

   DEFINITION: greatest elements
   {x in P | forall y in P. (y weaker x or (x notweaker y and y notweaker x))}
-}


{- Exercise 32: Are the digraphs partial orders?

   isPartialOrder ([1,2,3], [(1,2), (2,3)])
=> Not reflexive (don't have (1,1), (2,2)) so not partial order

   isPartialOrder ([1,2,3], [(1,2), (2,3), (1,3), (1,1), (2,2), (3,3)])
=> Is reflexive (has (1,1), (2,2), (3,3))
   Is transitive (has (1,2), (2,3) => (1,3))
   Is antisymmetric so this is a partial order.

-}


{- Exercise 33 : weakest/greatest calculations
   Hint: drawing the poset diagram makes this exercise really easy.

(a) isWeakest [(1,2), (2,3), (1,3), (1,1), (2,2), (3,3)] 2
    No because we have 1R2 so 1 is weaker than 2.
    Note: 1 is the weakest 

(b) isWeakest [(1,2), (1,3), (1,1), (2,2), (3,3)] 3
    No because we have 1R3.
    Note: weakest set is {1,2}

(c) isGreatest [(1,2), (2,3), (1,3), (1,1), (2,2), (3,3)] 3
    Yes. The only time we have (3,_) is with 3 itself.
    Note: greatest set is {3}

(d) isGreatest [(1,2), (1,3), (1,1), (2,2), (3,3)] 1
    No. we have (1,2), (1,3) so 2 and 3 are already stronger than 1.
    Note: greatest set is {2,3)}

-}

{- Exercise 34: weakest and greatest set calculations
   Again, drawing poset diagram makes it really easy.

(a) weakestSet ([1,2,3,4], [(1,4), (1,3), (1,2), (1,1),
                        (2,3), (2,4), (2,2),
                        (3,4), (3,3),
                        (4,4)])

    Poset diagram: 1 <- 2 <- 3 <- 4
    So weakest set: {1}, greatest set: {4}

(b) weakestSet ([1,2,3,4], [(1,4), (1,2), (1,1),
                        (2,4), (2,2),
                        (3,4), (3,3),
                        (4,4)])
    
    Poset diagram: 1 <- 2 < - 4
                        3 <---|
    So, weakest set: {1,3}, greatest set: {4}

(c) greatestSet ([1,2,3,4], [(1,2), (3,4), (1,1), (2,2), (3,3), (4,4)])
    
    Poset diagram: 1 <- 2; 3 <- 4
    Weakest set: {1,3}, greatest set: {2,4}

(d) greatestSet ([1,2,3,4], [(2,3), (3,4), (2,4), (1,1), (2,2), (3,3), (4,4)])
    
    Poset diagram: 1; 2 <- 3 <- 4
    Weakest set: {1,2}, Greatest set: {1,4}
-}

{- Exercise 35: greatest and weakest elements again

(a) {(a,b), (a,c)}
    Poset diagram: c -> a <- b
 
    greatest: {b,c}, weakest: {a}

(b) {(a,b), (c,d)}
    Poset diagram: a <- b; c <- d
    greatest: {b,d}, weakest: {a,c}

(c) {(a,b), (a,d), (b,c)}
    Poset diagram: d ->  a <- b <- c
                   
    Weakest: {a}, greatest: {c,d}

-}

--------------------------------------------------------------------------------
-- 10.8.2 Quasi Order

{- DEFINITION: Quasi Order
   A relation is a quasi order if it is irreflexive and transitive.
   e.g. < is a quasi order, <= is a partial order.

   THEOREM: A Quasi Order is not symmetric
   Proof: If it is symmetric, we have both (a,b) and (b,a)
          But: by transitivity, we'd require (a,a) which makes it reflexive.

   THEOREM: A quasi order is antisymmetric
   Proof: Since irreflexive, we don't have xRx
          By previous theorem, we don't simultaneously have xRy and yRx with x&y distinct
          So vacuously true.
-}
   
{- Exercise 36: quasi order.
  
(a) isQuasiOrder ([1,2,3,4], [(1,2), (2,3), (3,4)])
    1. not reflexive: good
    2. not transitive: have (1,2) and (2,3) but not (1,3): bad!
    so not quasi order.

(b) isQuasiOrder ([1,2,3,4], [(1,2)])
    1. not reflexive: good
    2. transitive.
    quasi order.

*Relations> isQuasiOrder ([1,2,3,4], [(1,2), (2,3), (3,4)])
False
*Relations> isQuasiOrder ([1,2,3,4], [(1,2)])
True
-}

--------------------------------------------------------------------------------
-- 10.8.3 Linear Order / Total Order

{- DEFINITION: Linear Order or Total Order

   A linear order is a partial order with the additional requirement that
   for each a,b in the set, either a WEAKER b or b WEAKER a

   basically all elements are comparable.

-}


{- Exercise 37: total order
   
(a) isLinearOrder ([1,2,3], [(1,2), (2,3), (1,3), (1,1), (2,2), (3,3)])
    True. the chain is: 1 <- 2 <- 3. every node is comparable to another.

(b) isLinearOrder ([1,2,3], [(1,2), (1,3), (1,1), (2,2), (3,3)])
    False. Can't compare 2 and 3

*Relations> isLinearOrder ([1,2,3], [(1,2), (2,3), (1,3), (1,1), (2,2), (3,3)])
True
*Relations> isLinearOrder ([1,2,3], [(1,2), (1,3), (1,1), (2,2), (3,3)])
False
-}

--------------------------------------------------------------------------------
-- 10.8.4 Well Order

{- DEFINITION : Well Order
   Well Order = Total Order + has a least element.
                Also, every subset must have a least element.

   e.g. Naturals with (<) is a well order because least elt is 0
   e.g. Integers with (<) is a total order but not a well order because it doesn't
        have a smallest element.
-}

{- Exercise 38: we are watching the people who come in and use the terminal.
                Is this a total order?
   Since only one person can use it at a time, we have an ordering with startingTime as
   our relation.

   Furthermore, the first person we saw is the "least" element. So this is a well order.
-}

{- Exercise 39: Is it always possible to count elements of a linear order?
   No. Counterexample: Reals between [0,1]
   This is a total order with < as the ordering function.
   The least element is 0 so we have a well order.
   But the reals are not countable.
-}

{- Exercise 40: Can a set that is not well order be countable?
   Yes. Consider the set of nominals {cats, dogs} with no ordering function.
   Since there is no ordering, it isn't a well order.

   But it is countable (2 elements).
-}

--------------------------------------------------------------------------------
-- 10.8.5 Topological Sort

-- Convert a partial order into total order by breaking "ties" among the incomparable
-- elements in an arbitrary manner.

{- Exercise 41: the book's exercise wants us to use the functions and watch what happens
   Instead, I'll compute the topological sort.

(a) topsort [(1,2), (1,3), (2,3), (1,4), (2,4), (1,1), (2,2), (3,3), (4,4)]
   
    the poset diagram is: 1 <- 2 <- {3,4}
    So a topological sort is: 1 <- 2 <- 3 <- 4

(b) topsort [(1,2), (1,3), (1,4), (1,1), (2,2), (3,3)]
   
    the poset diagram is: 1 <- {2,3,4}
    So, a topological sort is: 1 <- 2 <- 3 <- 4
-}

-- =============================================================================
-- 10.9 Equivalence Relations

{- DEFINITION: Equivalence Relation
   it is: reflexive, symmetric and transitive.

   e.g. < is not an equivalence relation because it is not reflexive
        <= is reflexive and transitive but not symmetric.

        = is reflexive, symmetric and transitive. so it is an equivalence relation

   DEFINITION: Partition 
   A partition P of a non-empty set is a set of nonempty subsets of A such that:
     1. for each subset S1, S2 either S1 == S2 or S1 intersect S2 = NULL
     2. A = GrandUNION S

   basically, send each element of the set A into only one subset S
-}

{- Example: Congruence Relation
   
   Let k be a positive integer
   Let a and b be integers.

   If there is an integer n such that: (a - b) = n * k, 
   we say that a is congruent to b (modulo k)

   e.g. things modulo 3
    4 and 1 are congruent modulo 3: (4 - 1) = 3 = 1 * 3.
    5 and 2 are congruent modulo 3: (5 - 2) = 3 = 1 * 3
    basically, things that give the same remainder when divided by k.

   --------------------
   DEFINITION: define aCb iff a == b (mod k). 

   THEOREM: C is an equivalence relation
   PROOF:
     Lemma 1: C is reflexive
     Proof: Consider an arbitrary natural x. 
            Then x - x = 0 and 0 = 0 * k for any k
            So, x is congruent to x (modulo k)
            Thus, C is reflexive.

     Lemma 2: C is symmetric.
     Proof: Suppose a == b (mod k). We'll show that b == a (mod k)
       Since a == b (mod k), there exists an n such that (a - b) = n * k

       So, (b - a) = -n * k. 
       This means that b == a (mod k) (using -n as the required number).

     Lemma 3: C is transitive
     Proof: Suppose a == b (mod k) and b == c (mod k)
     Then, we have m such that (a - b) = m * k
           we have n such that (b - c) = n * k
           Adding, we have (a - c) = (m + n) * k

           Hence, a == c (mod k) (using (m + n) as the required number).

   Proof: Since C is reflexive, symmetric and transitive, it is an equivalence relation.
-}


{- Exercise 42: Finding smallest equivalence relations

(a) equivalenceRelation ([1,2], [(1,1), (2,2), (1,2), (2,1)])
    => the partition is: {[1,2]}

(b) equivalenceRelation ([1,2,3], [(1,1), (2,2)])
    => the partition is: {[1],[2]}

(c) isEquivalenceReltion ([1,2], [(1,1), (2,2), (1,2), (2,1)])
    => is reflexive, transitive and symmetric. Hence equivalence.

(d) isEquivalenceRelation ([1], [])
    => not reflexive. so not equivalence.
-}

{- Exercise 43: Does the topological sort require that the relation is a partial order?
   Yes? A Topological sort is just a total order. and a total order is a partial order.
-}

{- Exercise 44: Can we give a cyclic graph to a topological sort?
   No. Suppose we have a cycle a <- b <- c <- d <- a in a larger graph

   Then, this particular subset doesn't have a smallest element.
   Hence, we can't make a total order out of it. 
   So, no topological sort.
-}

-- =============================================================================
-- 10.10 Further Reading

-- Discrete Mathematics in Computer Science by Stanat and McAllister
-- Discrete Mathematics by Ross and Wright

-- =============================================================================
-- Review Exercises Begin here

--------------------------------------------------------------------------------
{- Exercise 45: Which are equivalence relations?

(a) InTheSameRoomAs
    - clearly reflexive, symmetric and transitive.
    - so equivalence.

(b) IsARelativeOf
    - equivalence

(c) IsBiggerThan
    - not symmetric. not equivalence

(d) The equality relation
    - equivalence.

-}

--------------------------------------------------------------------------------
{- Exercise 46: Given a non-empty antisymmetric relation, does its transition
   closure ever contain symmetric arcs?

   First of all, antisymmetric doesn't preclude reflexivity. So, we could already
   have symmetric arcs.

   Suppose we don't have self arcs to begin with. Here's an example that shows
   that we can introduce self arcs:
   [(1,2), (2,3), (3,1)]  <- this is antisymmetric
   power 2: [(1,3), (2,1), (3,2)] <- *
   power 3 : [(1,1), (2,2), (3,3)] <- symmetric arcs introduced.

   * actually we now have (3,1) from original, (1,3) from this. so already have symmetric arcs.
-}

--------------------------------------------------------------------------------
{- Exercise 47: Write a relation that is both quasi order and an equivalence.
  
   This relation has to be: 
   1. quasi order: irreflexive and transitive
   2. equivalence: symmetric, reflexive, transitive.

   Can't satisfy both reflexive and irreflexive at the same time with nonzero elements
   So, R = []
-}

--------------------------------------------------------------------------------
{- Exercise 48: Write a function that takes a relation and returns True if 
   that relation has a power that is the given relation.
-}

isFixedPoint :: (Show a, Eq a) => Digraph a -> Bool
isFixedPoint (dom, rel) = any (setEq rel) $  map (relPower rel) [1.. length dom]

--------------------------------------------------------------------------------
{- Exercise 49: A quasi order is transitive and irreflexive. Can it have any symmetric loops?
   
   No. By transitivity, we could reduce the cycle length of the loop until it became a 
   self loop. This would break irreflexivity.
-}

--------------------------------------------------------------------------------
{- Exercise 50: Given an antisymmetric, irreflexive relation, can its transitive closure
   have reflexive arcs?

   Yes: the example from 46 is anti-symmetric and irreflexive but it gets a reflexive arc.
-}

--------------------------------------------------------------------------------
{- Exercise 51: Function that takes in a relation and returns True if all its powers
   have fewer arcs than it.
-}

powersAreSmaller :: (Eq a) => Digraph a -> Bool
powersAreSmaller (dom, rel) = all ((> lrel) . length) (map (relPower rel) [1.. ldom])
  where ldom = length dom
        lrel = length rel

--------------------------------------------------------------------------------
{- Exercise 52: function that takes a relation and returns true if relation is 
   smaller than its symmetric closure.

   If a rel is already a symmetric closure, then obviously false.
   If it isn't, the symmetric closure is a superset. 
   So, just return not of symmetric
-}

symmetricClosureSmaller :: (Eq a) => Digraph a -> Bool
symmetricClosureSmaller d = not $ isSymmetric d

--------------------------------------------------------------------------------
{- Exercise 53: Given a partial order {(a,b), (b,c), (a,d)}
   which of the following is not a topological sort.

   (poset diagram is: a <- b <- c; a <- d)

(1) [d,c,b,a]
is a topological sort. because we respect the chains in poset diagram.

(2) [c,b,d,a]
is a top sort.

(3) [d,c,a,b]
a is before b so not a top sort.

-}

--------------------------------------------------------------------------------
{- Exercise 54: Is a reflexive and symmetric relation ever antisymmetric?

   Reflexive => have xRx for all x
   Symmetric => xRy means yRx for all x,y
   Antisymmetric: either xRy or yRx but not both (when x and y distinct)

   So a relation that contains only reflexive arcs is both symmetric and antisymmetric.
-}

--------------------------------------------------------------------------------
{- Exercise 55: A relation has a single path of length n.
   How many arcs can be added by its symmetric transitive closure?

   suppose we have 1 -> 2 -> ... -> n
   Transitive closure will add paths 1 -> 3, 1 -> 4, ... 1 -> n  i.e (n - 2) paths
                                             2 -> 4, ... 2 -> n  i.e. (n - 3 paths 
                                    n - 2 -> n is also added (1 path)
   So we have 1 + 2 + ... + (n - 2) = (n - 2) (n - 1) / 2 paths added by transitive closure

   VERIFICATION: N = 5 and path is 1 -> 2 -> 3 -> 4 -> 5
   Predicted: 6 paths added.
   Paths added: (1,3), (1,4), (1,5), (2,4), (2,5), (3,5) = 6
   Works for this particular example.

   Now symmetric closure will add reflections of each of those paths.
   We had n -1 original paths => (n - 1) new paths
   Also, (n -2) (n - 1)/2 new paths => (n -2) (n -1) newer paths.


   Grand total: (n - 1) + (n - 2) (n - 1) + (n - 2) (n -1)/2 paths added.

   book claims only 2 (1 + 2 + ... + n - 1) but it's calculations are more handwavy than mine:
   "transitive closure adds the 1 + 2 + ... n -1, symmetric doubles it."
   they're ignoring the symmetries to existing paths.

-}

--------------------------------------------------------------------------------
{- Exercise 56: Given a relation containing only a cycle of length n containing all nodes
   in domain, which power will be reflexive?

   experiment: N = 2: [(1,2), (2,1)] next power is [(1,1), (2,2)] so n - 1?
               N = 3: [(1,2), (2,3), (3,1)]. next power is [(1,3), (3,2), (2,1)]
                                             next is: [(1,1), (2,2), (3,3). so n -1.

   Theoretical reason: If there's a cycle of length n, it takes n hops to get back to
   starting point. Each power is equivalent to traveling a hop.
-}

--------------------------------------------------------------------------------
{- Exercise 57: Can we write a function that determines whether the equality relation over positive
   integers is reflexive?
   
   Yes. const True :P

   Actually unless we wrote a function that did proof by induction, it'd have to examine
   infinite arcs. thus it'd never terminate.
-}

--------------------------------------------------------------------------------
{- Exercise 58: Why can't partial orders have cycles of length greater than 1?
   
   We could use transitivity to violate the antisymmetric assumption.

-}

--------------------------------------------------------------------------------
{- Exercise 59: Is the last power of a relation always the empty set?
   
   No. Any relation that has a nonempty fixpoint e.g. [(1,2), (2,1)] is a counterexample.
-}

--------------------------------------------------------------------------------
{- Exercise 60: What order given by: [(a, a + 1) | a <- [1..]]

   Characteristics: 
   1. not reflexive (don't have (a,a))
   2. not transitive (don't have (a, a + 2))
   3. not symmetric (don't have (a + 1, a))
   4. but we do have a minimal element 1

   So not any order we know of. Book claims it is a linear order, but it's not even
   a partial order (no transitivity!)
-}

--------------------------------------------------------------------------------
{- Exercise 61: Is the composition of a relation containing only a single cycle with its 
   converse the equality relation?

   Yes. e.g. [(a,b), (b,c), (c,a)].
        it's converse is [(b,a), (c,b), (a,c)]
        composition gives: [(a,a), (b,b), (c,c)]

   CAVEAT: The single cycle touches all elements in the domain.

   Rigorous Proof?
   1) I have to show that I have (a,a) for all a in domain.
   2) I have to show that there is no other pair (a,b) in the resulting relation.

   Proof of 1:
   Since the relation contains a single cycle touches all elements of the domain,
   we have a pair (x,y) x != y in the relation.

   The converse is (y,x).

   Composition of (x,y) and (y,x) gives (x,x).
   So for every element in the domain, i have a reflexive pair.

   Proof of 2:
   Since the relation contains only a single cycle, each element x is in exactly two 
   ordered pairs: One as (x,y), and the other as (z, x) where y and z are its neighbors.

   So, it appears in two places in the converse: as (y,x) and (x,z).

   Thus, the only thing that (x,y) can consume is (y,x) giving (x,x)
         the only thing that (z,x) can consume is (x,z) giving (z,z)

   So for any arbitrary element, we never produce a non-reflexive ordered pair.

   Thus the new relation contains only reflexive pairs, hence is an equivalence relation.
-}

--------------------------------------------------------------------------------
{- Exercise 62: Give examples of partial orders where set of greatest is same as set of weakest

   Example: [(1,1), (2,2)] then the poset diagram is 1; 2

   This means that weakest is {1,2}, strongest is {1,2}

   Basically, none of the elements were comparable.
-}