Set theory

Question

Consider the sets $A_1,  A_2,  A_3  \dots  A_m$. Prove that the number of distinct sets of the form $A_i \oplus A_j$ is at least $m$.

Comments

Here I think the sets A₁,A₂,A₃,..........A_m should be non-equal.

because if they are equal that is A₁ = A₂ = A₃ = ............= A_m

then the XOR of any two sets A_i and A_j would be Ø.

But the condition given in the question is , there are at least m  A_i ⊕ A_j

Can u please check your question.@ Debashis

---

generally sets means distinct. You can assume them as distinct and check for  the required answer.

---

Ok.....

Answer 1

Here I am assuming that the sets A₁,A₂,A₃,......,Am are all distinct

THE QUESTION IS WRONG

 The number of distinct sets of the form A_i ⊕ A_j should be at least m-1.

Take the example

A₁ = {1,2,3}  A₂ ={3}  A₃ = {1} and A₄ = {2}

TRY TO FIND 4 distinct sets of the form A_i ⊕ Aj. YOU CANT FIND IT  THERE IS ONLY 3. 

So, I am proving that.

Now, let us assume for arbitrary i,j ∈ { 1,2,3,.....,m}

we have A₁ ⊕ A_i = A₁ ⊕ Aj 

=> A₁ ⊕ (A₁ ⊕ A_i) = A₁ ⊕ (A₁ ⊕ A_j)

=> (A₁ ⊕ A₁) ⊕ A_i = ( A₁ ⊕ A₁ ) ⊕ A_j  ( Assosiative property XOR)

=> A_i = A_j

But we know that all the Ai 's are distinct.

So, our assumption was wrong

Thus (A₁ ⊕ A_i ) !=  (A₁ ⊕ A_j)

Thus (A₁ ⊕ A₂) , (A₁ ⊕ A₃) , (A₁ ⊕ A₄) , ..................., (A₁ ⊕ A_m) are all distinct sets.

So, we have got m-1 distinct sets of the form A_i ⊕ A_j 

Thus there are at least m-1 distinct sets of the form Ai ⊕ Aj (proved)