Discrete Mathematical Structures by Pearson

2-12 Discrete Mathematical Structures

Hence,

[b] ⊆ [a] (2.1)

Again, x ∈ [a] ⇒ x R a

 ⇒ x R a and a R b [Since R is symmetric]

 ⇒ x R b

 ⇒ x ∈ [b]

Hence,

[a] ⊆ [b] (2.2)

From (2.1) and (2.2), we have [a] = [b]

Conversely: Suppose [b] = [a]

Since R is reflexive b R b ⇒ b ∈ [b]

 ⇒ b ∈ [a] (since [b] = [a])

3. Let [a] ∩ [b] ≠ j, then we have to prove that [a] = [b]

Let x ∈ [a] ∩ [b] ⇒ x ∈ [a] and x ∈ [b]

⇒ (x R a) and (x R b)

⇒ (a R x) and (x R b) (since R is symmetric x R a ⇒ a R x)

⇒ a R b

⇒ [a] = [b]

Thus,

[a] ∩ [b] ≠ f ⇒ [a] = [b]

But, if [a] ≠ [b] ⇒ [a] ∩ [b] = f

2.4 PARTITION OF A SET

Let S be a given non-empty set. A partition P of S is a collection of ...