For numerical answers, if it is finite, give a number. If it is infinite, state whether is is countable (has the same cardinality as the integers), or uncountable (which we define here as "the same cardinality as the reals").

You are welcome to use online resources to learn or remind yourself what are equivalence relations and equivalence classes or what steps you must undertake to prove a relation has some property. I've looked, and don't believe that any problem below has an answer online, but if you do find such a solution, copy it, and turn it in, that would constitute a violation of academic integrity.

Problems:

1. You reach, blindly, into a bin with 2 red m&m's, 5 green m&m's, and
    7 blue m&m's.  

  a) You pull out 2 m&m's.  What is the probability they are the same color?



let's pretend that all the M&M's are numbered (that is, the red m&m's
are distinct.).  Since we are computing a probability, this is ok (as
long as we are consistent in computing both how many total solutions there are, and how many satisfy our criteria.

So.  Total number of ways to pull out two m&m's, from a group of 14:  (14 choose 2).

Total number of ways to have a pair of the same color = 
  total number of was that are red + ways that are green + ways that are blue = 
  (2 choose 2)                     + (5 choose 2)        + (7 choose 2)

so the probability is:

(  (2 choose 2) + (5 choose 2) + (7 choose 2) ) / (14 choose 2)

If you copy and paste the above line exactly into google, it gives you
the results (!):

0.352....


  b) How many must you take out to be sure that you have at least 3
     colors?
 you need 13.  In the worst case, you could get all of the blues and all of the greens as your first 12.
  c) if a "handful" of m&m's depends only what colors the handful has,
     and not, for instance, what order they were picked on or their
     arrangement on your palm, how many different handfuls can you
     grab from the bin?
 

This question goes back to trying to count sets by finding simple ways
of constructing them.  Since the m&m's are indistinct, and it only
matters how many of each type, you can "construct a handful" by
choosing:  how many reds,  how many greens, and how many blues.

You can have 0,1, or 2 reds, (for a total of 3 choices of how many reds),
and 6 choices for how many green, and 8 for how many blue, so the solution is:

3*6*8 = 144


  d) Generalize your answer to (c) for the case where there are "r"
     red m&m's, "g" green m&m's, and "b" blue m&m's.
 
(r+1)(g+1)(b+1)


2. Let A be the set {1, 2, 3, 4, 5, 6, 7, 8, 9}

  Let R be the relation { (1,2), (1,1), (3,4), (4,5), (3,9), (6,9),
  (7,8) }

  a) Is R: reflexive?  anti-reflexive?  symmetric? anti-symmetric?

This is anti-symmetric (and none of the other properties.

  b) List the pairs that are in the transitive closure of R that are
  not in R.

(3,5)

3. we define the relation ~ on the set of integers to be x ~ y if
        x2 = y2.

  a) (1,1) is an element of this relation, as is (-1,1).  List at
      least 5 other elements of this relation.

   (0,0),  (-2,2), (2,2), (1181,-1181), (1,1)

  b) Describe the set of all equivalence classes for this relation.
      How many are there?  If it is finite, give a number.

  the equivalence classes are {-a,a} for all integers a.  This is
  infinite, the same cardinality as the set of integers.


4. Prove: For any 5 points on the plane, where each point has integer
   coordinates, that the midpoint of at least one of the lines
   connecting pairs of points also has integer coordinates.



this is a pigeonhole problem.  The question to start with is: if a
line segment goes from one point (x1,y1) to another (x2,y2), where all
the coordinates of the points are integers, when is that midpoint also
an integer?

Well, the midpoint = (x1 + x2) / 2.  When is this an integer?  well,
when both x1, and x2 are even or both are odd.  So that is the
x-coordinate of the midpoint, the same holds true for the
y-coordinate.  So if the "even-oddness" (the parity) of both
coordinates of the point are the same, then the midpoint  also has
integer coordinates.  Now, how can we argue that the segment
connecting some pair of points has endpoints with the same parity? 

Lets make four pigeonholes:

(even, even)
(even,odd)
(odd, even)
(odd,odd)

Since there are five points, two must land in the same pigeonhole.
The segment connecting these points must have integer coordinates.


5. Let R be any symmetric relation on set A.  Show that Rn
   is symmetric.


this proof almost has to be done recursively.

Assume R1 is symmetric
  Prove for n >=1 that Rn is symmetric.
  Proof by induction: P(k): "Rk is symmetric."
    Base case: P(1): "R1 is symmetric."
         R1 = R which is assumed to be symmetric. 
  Proof by induction: P(k): "Rk is symmetric."
    Base case: P(1): "R1 is symmetric."
         R1 = R which is assumed to be symmetric. 
    Induction, assume P(k): "Rk is symmetric."
         Prove P(k+1): "Rk+1 is symmetric."
            let (a,b) in Rk+1 
              then there exists an x such that
                 (a,x) in Rk and
                 (x,b) in R1 and
              but
                  Rk and R1 are both symmetric, so
                  (b,x) in R1.
                  (x,a) in Rk and 
              so
	          (b,a) in Rk+1
          so Rk+1 is symmetric.
   so for all n Rn is symmetric.
so R is symmetric implies for all n Rn is symmetric.


6. Let R be a relation on Real numbers such that 
       R = { (a,b) |  for some k, a = b + 2 * k * pi }.
 show that R is an equivalence relation.

we need to show that R is reflexive, symmetric and transitive.

1. reflexive.
prove (a,a) is an element of R

  (a,a) is in R if there is a k such that:
       a = a + 2 * k * pi. 

  if we choose k = 0, this reduces to:
       a = a + 0 * k * pi.    
       a = a.

  thus, R is reflexive.


2. symmetric
prove (a,b) is an element of R -> (b,a) is an element of R

  Assume (a,b) is in R
    Prove (b,a) is in R

    since (a,b) is in R (by assumption), then there is some k such that:
      a = b + 2 * k * pi. 

    with a little algebra, we can re-write this as:
      a - 2 * k * pi = b 
      b = a - 2 * k * pi
      b = a + 2 * (-k) * pi

    thus, since there is a number (-k) such that,
       b = a + 2 * (-k) * pi
    (b,a) is an element of R.

  thus (a,b) in R -> (b,a) in R
thus, R is reflexive.

3. transitive.
prove ((a,b) in R and (b,c) in R) -> (a,c) in R

  Assume: ((a,b) in R and (b,c) in R)

    Then there is a k and an m such that:
      a = b + 2 * k * pi.       
      b = c + 2 * m * pi.

    with a little algebra (plug 2nd equation for b into the first one), we get:
      a = c + 2 * m * pi + 2 * k * pi.       
      a = c + 2 * (m + k) * pi.

    thus, since there is a number (m+k) such that,
       b = a + 2 * (m+k) * pi
    (a,c) is an element of R.
  Therefore ((a,b) in R and (b,c) in R) -> (a,c) in R   
Therefore R is transitive.

Since R is reflexive, symmetric and transitive, R is an equivalence relation.

 list 3 elements in the equivalence group [ pi / 2 ]

pi / 2,  3* pi / 2,  131 * pi / 2,

 How many equivalence classes are there?


This depends a little on your interpretation.  I inteded to require
that k is an integer.  Under this interpretation, there is one
equivalence class for every real number between 0 and 2*pi.  This is
an uncountable infinite set.

If there is no restriction on the value of k, then there is a single
equivalence class, that includes all numbers.