Question

Let S be a finite set and let P(S) denote the set of all subsets of S. Define a relation on P(S) by declaring that two subsets A and B are related if A and B have the same number of elements.

(a) Prove that this is an equivalence relation.

b) Determine the equivalence classes.

c) Determine the number of elements in each equivalence class.

Answer 1

S be finite set and P(S) is the set of all subsets of S i.e. P(S) is power set of S

Define a relation on P(S) that two subsets A and B are related if A and B have same number of elements.

(a) prove this is a equivalence relation

For this we have to prove this relation is reflexive , symmetric and transitive.

sol. Reflexive- A is related with A i.e.since relatiom is defined of no of elements so A is related with A. Hence reflexive.

symmetric- Since A is related to B as both have same no of elements so B is related to A as both same no elements also. Hence B relates A.

or Let A has m elements and B has n elements so When A and B are related then m=n or n=m so A and B are related.

Hence symmetric.

Transitive- In this if A related to B and B related to C then A is related to C

Since A related to B. so both have A and B same no of elements and B related to C so both B and C have same of elements.From these we get A and C have same no of elements.Hence A is related with C. so Transitive.

or Let A has m elements and B has n elements and C has l elements. Since A and B related and B and C are related. so we get m=n and n=l from these we get m=l. Hence A and C are related

Hence given relation is equivalence relation.

(b) equativalence class is defined by subset of S which includes all elements that are equivalent to each other.

[A]={X: A~X}

(c)No of elements in each equivalent class

Since P(S) is the set of all subjects of.Since S is finite and let S has n elements then

No of elements in each equivalence is 2^n

where n is the no. of elements of S