Let N = {0, 1, 2, 3,...} be the set of natural numbers. Define a relation...

 

Transcribed Image Text:

Let N = {0, 1, 2, 3,...} be the set of natural numbers. Define a relation R on N × N by (a, b) R(c, d) a+d=c+b. (a) Use only the laws of commutativity (a+b=b+a), associativity (a + (b+c) = (a+b)+c) and cancellation (a+c=b+ca = b) of addition on N to prove that R is an equivalence relation on N > N. (b) Denote by Z the set of equivalence classes {[(a,b)] R a, b = N}. Define the operations of addition and subtraction in Z by [(a, b) Rz [(c, d)] R = [(a+c, b+d)]R, -2 [(a, b)]R —z [(c, d)]R = [(a+d, c+b)]R. Prove that these operation are well-defined, that is, independent of the choices of representatives of the equivalence classes. (c) Prove that, for all a, b, c, d, e, f = N, [(a, b)] Rz [(c, d)] R = [(e, f)]R ↔ [(a,b)]R = [(c, d)] R +z [(e, f)]R· (d) Prove that the functions : N → Z and : N → Z defined as 4(n) = [(n,0)]R, v(n) = [(0,n)] are injective, Z=4(N) U (N), and (N) (N) = {[(0,0)] R}. (e) Prove that, for all m, n = N, (m) +z 4(n) = x(m + n), v(m) +z v(n) = v(m + [(0,0)] R. and (n) +z (n) = From now on, we shall identify the set N with the subset (N) of Z, and write n for (n) in Z. We shall also write n for (n). Let N = {0, 1, 2, 3,...} be the set of natural numbers. Define a relation R on N × N by (a, b) R(c, d) a+d=c+b. (a) Use only the laws of commutativity (a+b=b+a), associativity (a + (b+c) = (a+b)+c) and cancellation (a+c=b+ca = b) of addition on N to prove that R is an equivalence relation on N > N. (b) Denote by Z the set of equivalence classes {[(a,b)] R a, b = N}. Define the operations of addition and subtraction in Z by [(a, b) Rz [(c, d)] R = [(a+c, b+d)]R, -2 [(a, b)]R —z [(c, d)]R = [(a+d, c+b)]R. Prove that these operation are well-defined, that is, independent of the choices of representatives of the equivalence classes. (c) Prove that, for all a, b, c, d, e, f = N, [(a, b)] Rz [(c, d)] R = [(e, f)]R ↔ [(a,b)]R = [(c, d)] R +z [(e, f)]R· (d) Prove that the functions : N → Z and : N → Z defined as 4(n) = [(n,0)]R, v(n) = [(0,n)] are injective, Z=4(N) U (N), and (N) (N) = {[(0,0)] R}. (e) Prove that, for all m, n = N, (m) +z 4(n) = x(m + n), v(m) +z v(n) = v(m + [(0,0)] R. and (n) +z (n) = From now on, we shall identify the set N with the subset (N) of Z, and write n for (n) in Z. We shall also write n for (n).