Discrete Mathematics Homework #2 Solution

1. (5 points.) Prove that B ⊂ A where

A = {(a, b) | |a + b| < 21} and B = {(a, b) | |a − 1| < 10 and |b − 1| < 9}.




A = {(a, b) | −21 < a + b < 21}

B = {(a, b) | −9 < a < 11 and −8 < b < 10}







Rearrange B :

B = {(a, b) | (−9 < a < 11) + (−8 < b < 10)}

B = {(a, b) | (−17 < a + b < 21)}




A has every pair of B has.(Not vice versa. ∴ B * A) ∴ B ⊂ A




2. (10 points.) Write the expressions which represent the sets, given the Venn diagrams in Figure 1.










Figure 1:




1) (A \ (B ∪ C )) ∪ (D ∪ E)

2) (B \ C ) ∪ (F ∩ E) ∪ D

3) (E ∩ (G ∪ F )) ∪ (H ∩ (G ∪ F )) \ (G ∩ F ) ∪ (B \ (A ∪ C )) ∪ (C \ (B ∪ E ∪ D))

3. (10 points.) Let R be the relation on R2, defined by:

(a1, b1) R (a2 , b2) if and only if either a1 < a2 or both a1 = a2 and b1 ≤ b2. Prove that R is a partial order on R2 .

R is Reflexive: for all (a, b) ∈ R2 , we have [(a, b), (a, b)] ∈ R Since a = a and b ≤ b.

R is Transitive: Whenever [(a1 , b1), (a2, b2)] ∈ R and [(a2, b2 ), (a3 , b3)] ∈ R, we have [(a1, b1 ), (a3 , b3)] ∈ R. Since, if a1 < a2 and a2 < a3 , therefore a1 < a3 holds; or if a1 = a2 and b1 ≤ b2, a2 = a3 and b2 ≤ b3, therefore a1 = a3 and b1 ≤ b3 holds.

R is Antisymmetric: Whenever (a1, b1 ) = (a2, b2 ) and [(a1, b1), (a2, b2 )] ∈ R, we have

[(a2, b2 ), (a1 , b1)] ∈/ R. Since, if a1 < a2 , then a2 ≮ a1, so there is no such element. Or,

when a1 = a2 and b1 ≤ b2 , if a2 = a1 and b2 ≤ b1. Therefore a2 = a1 and b2 = b1,

(a1, b1) = (a2, b2). Which conflicts with our assumption, therefore [(a2 , b2), (a1, b1)] ∈/

R.

4. (15 points.) Let a partial order relation R on X = {n ∈ Z : 2 ≤ n ≤ 12}, defined by:

xRy if and only if either (x is prime and x < y) or (x divides y).




Draw a Hasse diagram for R, and identify the least element and the maximal elements.







12




11 9 10

8

7

6




5




4 3




2







Maximal Elements: 12, 9, 10, 8




Least Element: 2




5. (10 points.) Examine all Boolean lattices with cardinalities 1 − 5. Explain these lattice structures in detail.




6. (10 points.) Determine whether each of the following functions is injective, surjective, both or neither.




(a) f : Z → Z, f (n) = n + (−1)n

(b) f : R → R, f (n) = 2x

(c) f : R → R+ ∪ {0}, f (n) = x + |x|

(a) Let x, y, k, l ∈ Z

Every image has preimage. It is surjective.

Say x = 2k and y = 2l. x + 1 = y + 1 ∴ x = y.

Say x = 2k + 1 and y = 2l + 1. x − 1 = y − 1 ∴ x = y. It is injective.

(b) Let x, y ∈ R

There is no image x such that f (x) = 0. It is not surjective.

2x = 2y ∴ x = y It is injective. (c) Let x, y ∈ R

Every image has a preimage. It is surjective.

If x, y < 0 then, f (x) = f (y) = 0. It is not injective.




7. (15 points.) Let f : X → Y be a function.

Show that function f is bijective if and only if f (X − Z ) = Y − f (Z ), for every subset

Z of X .




Let X = X + Z

f (X + Z − Z ) = f (X ) + f (Z ) − f (Z )

f (X ) = f (X )

∴ f is bijective.




8. (15 points.) Let S denote the set of real 2 × 2 matrices of the form




a b

−b a
where a and b are not both zero. Show that S is a group under the operation of matrix multiplication.




To be able to be a group, one must satisfy these things: (a) Must be closed under the operation .




(b) Must be Associativitive.




(c) Must have identity element. (d) Must have inverse element.




Proofs has ben made due to this order, in below.




(a) It is closed, under operation of matrix multiplication. a, b ∈ R. Thus, a2 + b2 ∈ R.



(b)







(c)

1 2

−2 1




1 0

0 1

3 4

× ( −4 3 ×

5 1

−1 5




) = (

1 2

−2 1 ×

3 4

×

)

−4 3

5 1

−1 5
(d) An element exists in that group such that, a, b ∈ R.
a2 +b2

( 1

Thus, a2 + b2 ∈ R and 1

∈ R.
a2 +b2 is the inverse element.)




9. (10 points.) Define the ring Zn . Show that Zn is a field if and only if n is a prime number.




A ring is a set S with two defined binary operators satisfying the following conditions:
(a) Additive associativity. (b) Additive commutativity. (c) Additive identity.

(d) Additive inverse.




(e) Left and right distributivity. (f ) Multiplicative associativity.

For a ring to be a field, also four operations must be defined. n=5 case:(n is a prime number)






1
2
3
4
1
1
2
3
4
2
2
4
1
3
3
3
1
4
2
4
4
3
2
1
n=6 case:(n is not a prime number)






1
2
3
4
5
1
1
2
3
4
5
2
2
4
0
2
4
3
3
0
4
0
3
4
4
3
0
4
2
5
5
4
3
2
1
Some of the element has no inverse element.

∴ This is not a field. Besides, having 0 in the table causing this ring not to become field anymore, since this is against the identity element 1.