Date: Tue, 11 Nov 2003 22:50:32 -0600 (CST)
   From: Mark Jacobson <jacobson@math-cs.cns.uni.edu>
     To: 810-080-01@uni.edu, 810-080-03@uni.edu
Subject: Partition any set making an RST relation on it...

Hi 080 students,                  rst = (reflexive, symmetric, transitive)
                                         -          -          -
     I have just received my 2nd question on how partitions
are related to equivalence relations.

     Please look at the online, interactive self-grading quiz
where question #4 asks what properties does an equivalence
relation have.

     Click the hypertext link in question 4 and you will
see a R, S and T relation on the set of elements

 A =  {5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 17, 18, 19, 21}

     partitions that set into 5 different disjoint subsets.

 R =  {{5, 10}, {6, 16, 21}, {7, 12, 17}, {8, 13, 18}, {9, 14, 19}}
       -------  -----------  -----------  -----------  -----------
          0          1            2           3             4

      R subset of A cross A  or R subset of A X A

                  R = {(x,y} | x mod 5 = y mod 5}

      The URL to get directly to this 14 question quiz with the
      link from question four to a graph of the binary relation
      that is reflexive, symmetric and transitive and thus
      PARTITIONS the set A into the disjoint subsets
      according to whether the x mod 5 remainder is 0, or 1, or 2
                                                 or 3, or 4

      is http://www.cns.uni.edu/~jacobson/js/framesDiscrete080.html

      and gets you the link to

      http://www.cns.uni.edu/~jacobson/080/partitionsToER.gif

      opened up in a new browser window.

      Let me list a set of cities:

      Cities = {Cedar Falls, Le Mars, New York City, Atlanta,
                Waukon, Albany, Chicago, Urbana, Dixon, Boston,
                Waterloo, Cambridge, Brookline, Buffalo, Macon}

      Let us define a binary relation R that is a subset of
      the cartesian or cross product of Cities.

      R subsetOf Cities X Cities

      R = {(x,y) | x isInSameStateAs y}

      Clearly, R is reflexive, symmetric and transitive.

      Clearly, the above cities can be partitioned in many
      different ways, the the binary relation R,
      partitions them as follows:

      Cities = {Cedar Falls, Le Mars, New York City, Atlanta,
                Waukon, Albany, Chicago, Urbana, Dixon, Boston,
                Waterloo, Cambridge, Brookline}



      {  {Cedar Falls, Waterloo, Le Mars, Waukon, Urbana},

         {New York City, Albany, Buffalo},

         {Chicago, Dixon},       {Boston, Brookline, Cambridge}  }

     The cities are partitioned very nicely into IOWA,
                                                 NEW YORK,
                                                 ILLINOIS, and
                                                 MASSACHUSETTS.
     Clearly, it is reflexive, since every
     city is in the same state as itself!

     (Boston, Boston) is one of the ordered pairs, for example.

     Clearly, it is symmetric.

     (Le Mars, Cedar Falls) is an ordered pair, and clearly
     (Cedar Fall, Le Mars) is also present as an ordered pair.

     Clearly it is transitive.

     if city x is in the same state as city y and
        city y is in the same state as city z
     then
        city x will certainly be in the same state as city z

     Mark