Discrete Math: Unary and binary predicates?

For natural number x and y, define x mod y to be the remainder obtained upon dividing x by y. Allowing the variables x and y to range over the domain of natural numbers, let P(x,y) denote the binary predicate "x mod 2 = y mod 2" and let Q(x,y) denote the binary predicate "x mod 3= y mod 3."





(a) Is P(x,y) an equivalence relation? Justify your answer.


(b) Fix a natural number n. If P(n,2) holds, what must be true of n? What about if P(n,1) holds? For a fixed natural number n, must at least one of P(n,2) or P(n,1) hold? Can both P(n,2) and P(n,1) hold for a single natural number n?


(c)List the natural number n for which Q(n,1) holds, list the natural which Q(n,3) holds. Do the three lists have any natural numbers in common? Does every natural number appear in at least one of the three lists? For each of the lists, the collection of numbers appearing in that list is said to be an equivalence class of the equivalence relation Q(x,y). What are the equivalence classes of the equivalence relation P(x,y)?|||(A) An equivalence relation requires reflexivity, symmetry, and transitivity. If x,y,z are natural numbers, we check


x mod 2 = x mod 2


x mod 2 = y mod 2 =%26gt; y mod 2 = x mod 2


x mod 2 = y mod 2 and y mod 2 = z mod 2 =%26gt; x mod 2 = z mod 2


So we conclude it is an equivalence relation.





(B) P(n,2) simply says x mod 2 = 2 mod 2. But 2 mod 2 = 0 mod 2. So, by transitivity, we can conclude that n is even. On the other hand, if P(n,1) holds then n is odd. Obviously, every natural number is either even or odd, but not both.





(C) { n | Q(n,1)} = {1,4,7,10,13,...}


{ n | Q(n,2)} = {2,5,8,11,14,...}


{ n | Q(n,3)} = {0,3,6,9,12,...}


These are disjoint, i.e. they don't share anything, and they are the equivalence classes mod 3. The equivalence classes for P(x,y) are simply the even natural numbers and odd natural numbers.