Solutions of Homework 1 Fall 03

SOLUTIONS OF HOMEWORK 4 FALL 03

DUE DATE: 31st Oct 2003

Solution 1:(Exercise 33, part (f) page 267)

Let A, B, and C be any sets with A  C = B  C.

A  B: Suppose x  A. Either x  C or x  C. If x  C, then x  A and x  C and so by the definition of , x  A  C. But A  C = B  C. Thus x  B  C either. So, again by the definition of , since x  C and x  B  C, then x  B. On the other hand, if x  C, then by the definition of , since x  A, x  A  C. But A  C = B  C. So, again by the definition of , since x  C and x  B  C, then x  B. Hence in either case, x  B as was to be shown.

B  A: The proof is exactly the same as for A  B with letter A and B reversed.

Since A  B and B  A, by definition of set equality A = B.

Solution 2:(Exercise 44 page 268)

S0 = Ø,

S1 = {{a}, {b}, {c}},

S2 = {{a, b}, {a, c}, {b, c}},

S3 = {{a, b, c}}.

Yes, {S0,S1, S2,S3} is a partition of P(S) because the sets S0,S1, S2 and S3 are mutually disjoint and their union is P(S).

Solution 3:(Exercise 28 Part (b) page 546)

466581 Mary Lazars

778400 Jamal Baskers

SELECT admission_date, primary_diagnosis

FROM S WHERE

patient_name = ‘John Schmidt’

Solution 4:(Exercise 17 Page 554)

O is not reflexive: O is reflexive  for all integers m, m O m. By definition of O this means that for all integer m, m – m is odd. But this is false. As a counterexample, take any integer m. Then m – m = 0, which is even, not odd.

O is symmetric: Suppose m and n are any integers such that m O n. By definition of O this means that m – n is odd, and so by definition of odd m – n = 2k + 1 for some integer k. Now n – m = – (m – n). Hence by substitution, n – m = -(2k +1) = -2k –1 = -2k –1-1 +1 = -2k – 2 + 1 = 2(-k-1) + 1. It follows that n – m is odd by definition of odd (since(- k –1) is an integer), and thus n O m by definition of O.

O is not transitive: O is transitive  for all integers m, n, and p, if m O n and n O p then m O p. By definition of O this means that for all integers m, n, and p, if m – n is odd and n – p is odd then m – p is odd. But this is false. As a counterexample, take m = 1, n = 0 and p = 1 them m – n = 1 – 0 = 1 is odd and n – p = 0 –1 = -1 is also odd, but m – p = 1 –1 = 0 is not odd. Hence m O n and n O p but m Ø p.

Solution 5:(Exercise 29 Page 554)

R if reflexive: [We must show that for all set X in P(A), X R X] Suppose X is a set in P(A). By definition of subset, we know that X  X. By definition of R, then, X R X.

R is symmetric: [We must show that for all sets X and Y in P(A), if X R Y then Y R X]

Suppose X and Y are sets in P(A) and X R Y. By definition of R, this means that X  Y or Y  X. In case X  Y, then the statement “ Y  X or X  Y” is true, and so by definition of R, Y R X. In case Y  X then statement “ Y  X or X  Y” is also true, and so by definition of R, Y R X. Therefore in either case Y R X.

If A has at least two elements, then R is not transitive: R is transitive  for all set X, Y, and Z in P(A), if X R Y and Y R Z then X R Z. By definition of R this means that for all sets X, Y and Z in P(A), if either X  Y or Y  X and either Y  Z or Z  Y, then either X  Z or Z  X. However this is false, as the following counterexample shows. Since A has at least two elements, there exist elements x and y in A with x  y. Let X = {x}, Y = A, and Z = {y}. Then X  Y and so X R Y and Z  Y and so Y R Z. But X  Z and Z  X because x  y. Hence X is not related to Z by R.

If A has a single element, then R is transitive: In this case, given any two subsets of A, either one is a subset of the other or the other is a subset of the one. Hence regardless of the choice of X, Y and Z, it must be the case that X  Z or Z  X and so X R Z.

Solution 6:(Exercise 44 Page 555)

a)R U S is reflexive: Suppose R and S are reflexive. [To show that R U S is reflexive, we must show that x A, (x, x)  R U S.] So suppose x  A. Since R is reflexive, (x, x)  R, and since S is reflexive, (x, x)  S Thus by definition of union (x, x)  R U S (as was to be shown.

b)R U S is not necessarily transitive: As a counterexample, Let R = {(0,1)} and S =

{(1,2)} where the set is defined as {0, 1, 2}. Then both R and S are transitive (by default), but R U S = {(0,1), (1,2)} is not transitive because (0,1)  R U S and (1,2)  R U S but (0,2)  R U S. As another counterexample, let R = {(x, y)  R  R | x < y} and let S = {(x, y)  R  R | x > y} (set of real numbers). Then both R and S are transitive because of the transitivity of order for the real numbers. But R U S= {(x, y)  R  R | x  y} is not transitive because, for instance, (1,2)  R U S and (2,1)  R U S but (1,1)  R U S.

Solution 7:(Exercise 9 Page 570)

Distinct equivalences classes: {0, 3, - 3}, {1, 4, -2, 2, -5, 5, -1, -4}.

Solution 8:(Exercise 35 b, c, e, f Page 572)

b)Let (a, b) and (c, d) be any elements of A = Z+ Z+, and suppose (a, b) R (c, d). [We must show that (c, d) R (a, b)]. By definition of R, a + d = c + b, and so by the symmetry property of equality, c + b = a + d. But then by definition of R, (c, d) R (a, b) [as was to be shown].

c)Proof: Let (a, b), (c, d) , and (e, f) be any elements of A = Z+ Z+, and suppose (a, b) R (c, d) and (c, d) R (e, f). [We must show that (a, b) R (e, f)]. By definition of R, a + d = c + b(*) and c + f = e + d(**) . Adding (*) and (**) together gives a + d + c + f = c + b + e + d, and subtracting c + d from both sides gives a + f = b + e. Then by definition of R, (a, b) R (e, f) [as was to be shown].

d)One possible answer: (4, 2), (5, 3), (6, 4), (7, 5), (8, 6).

e)One possible answer: (2, 3), (3, 4), (4, 5), (5, 6), (6, 7).

Solution 9:(Exercise 36 Page 572)

The given argument assumes that from the fact that the statement, “x A, if x R y then y R x” is true, it follows that given any element x in R, there must exist an element y is R such that x R y and y R x. This is false. For instance, consider the following binary relation R defined on A = {1, 2}: R = {(1, 1)}. This relation is symmetric and transitive, but it is not reflexive. Given 2  A, there is no element y in A such that (2, y)  R. Thus we cannot go on to use symmetry to say that (y, 2)  R and transitivity to conclude that (2, 2)  R.

Solution 10:(Exercise 37 Page 572)

Proof: Suppose R is a binary relation on a set A, R is symmetric and transitive, and for every x in A there is a y in A such that x R y. Suppose x is any particular but arbitrarily chosen element of A. By hypothesis, there is ay in A such that x R y. By symmetry, y R x, and so by transitivity x R x. Therefore, R is reflexive. Since we already know that R is symmetric and transitive, we conclude that R is an equivalence relation.