# 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 nf(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?