5.2-1 Prove that the subset relation \"C\" on all subsets of Z is a partial orde

Question

5.2-1 Prove that the subset relation "C" on all subsets of Z is a partial order but not a total order. 5.2-2 Show that for any positive integer n, the relation "equivalent modulo n" is an equivalence relation on the integers. (We say that a b (mod n) if there exists an integer q such that a-b qn.) Into what equivalence classes does this relation partition the integers? 5.2-3 Give examples of relations that are a. reflexive and symmetric but not transitive, b. reflexive and transitive but not symmetric, c. symmetric and transitive but not reflexive. 5.2-4 Let be a finite set, and let R be an equivalence relation on S S. Show that if in addition R is antisymmetric, then the equivalence classes of S with respect to R are singletons. 5.2-5 Professor Narcissus claims that if a relation R is symmetric and transitive, then it is also reflexive. He offers the following proof. By symmetry,

Explanation / Answer

Answer. 5.2-1 :

The only difference between a partial order and a total order is that we can have incomparable elements in a partial order.

To clarify: such an example will merely show that (P(Z),) is not a total order. You still need to show that it is a partial order. To do this, you need to show that the following properties hold:

is transitive: if ABC, then AC.

is reflexive: AA.

is antisymmetric: if AB and BA, then A=B.

Let us have a look at an example of the proof of transitivity:

Suppose AB and BC. I want to show AC. So let aA; we need to show that aC. Since AB, we know aB. And since BC, every element of B is an element of C; so aC. Hence proved.

Answer. 5.2-3 :

a. Let A = {4, 6, 8}.

Define a relation R on A as:

A = {(4, 4), (6, 6), (8, 8), (4, 6), (6, 4), (6, 8), (8, 6)}

Relation R is reflexive since for every a A, (a, a) R i.e., (4, 4), (6, 6), (8, 8)} R.

Relation R is symmetric since (a, b) R (b, a) R for all a, b R.

Relation R is not transitive since (4, 6), (6, 8) R, but (4, 8) R.

Hence, relation R is reflexive and symmetric but not transitive.

b.

Define a relation R in R as:

R = {a, b): a3 b3}

Clearly (a, a) R as a3 = a3.

R is reflexive.

Now,

(2, 1) R (as 23 13)

But,

(1, 2) R (as 13 < 23)

R is not symmetric.

Now,

Let (a, b), (b, c) R.

a3 b3 and b3 c3

a3 c3

(a, c) R

R is transitive.

Hence, relation R is reflexive and transitive but not symmetric.

c.

Let A = {5, 6}.

Define a relation R on A as:

R = {(5, 6), (6, 5), (5, 5)}

Relation R is not reflexive as (6, 6) R.

Relation R is symmetric as (5, 6) R and (6, 5}R.

It is seen that (5, 6), (6, 5) R. Also, (5, 5) R.

The relation R is transitive.

Hence, relation R is symmetric and transitive but not reflexive.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.