Discrete Mathematics

Note that “iff” stands for “if and only if”. Also, to show “whether or not” means to give a proof for it if it is true and to give a counter example if it is false. Finally a R b means “a is related to b“, i.e. (a,b)∈R.

1. Let R be the relation on socks in your drawer defined by the following property: 
   a R b iff a and b have the same number of stripes 
   1. Show whether or not R is reflexive.
   2. Show whether or not R is symmetric.
   3. Show whether or not R is transitive.
   4. Is R an equivalent relation? If it is, how may equivalence classes does it have?
2. Let R be the relation on natural numbers defined by the following property: 
   a R b iff a+b is even 
   1. Show whether or not R is reflexive.
   2. Show whether or not R is symmetric.
   3. Show whether or not R is transitive.
   4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
3. Let R be the relation on natural numbers defined by the following property: 
   a R b iff f(a)=f(b), where f(n) is the number of 1’s in the binary representation of n 
   1. Show whether or not R is reflexive.
   2. Show whether or not R is symmetric.
   3. Show whether or not R is transitive.
   4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
4. Let R be the relation on functions that map natural numbers to natural numbers defined by the following property: 
   fRg iff for all natural numbers n, f(n)≤g(n) 
   1. Show whether or not R is reflexive.
   2. Show whether or not R is symmetric.
   3. Show whether or not R is transitive.
   4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
5. Let R be the relation on natural numbers defined by the following property: 
   a R b iff a%7=b%7 (where % is the C++ remainder operation) 
   1. Show whether or not R is reflexive.
   2. Show whether or not R is symmetric.
   3. Show whether or not R is transitive.
   4. Is R an equivalent relation? If it is, how many equivalence classes does it have?