Equivalence relation for $X \sim Y \iff X \cap T = Y \cap T$

discrete mathematicsequivalence-relationsrelations

For the question

Let $T$ be a fixed subset of a nonempty set $S$. Define the relation $\sim$ on power set of S by $$X \sim Y \iff X \cap T = Y \cap T$$
Show that $\sim$ is an equivalent relation. In particular let $S = \{1,2,3,4,5\} \text{ and } T = \{1,3\}$

Is $\{1,2,4\} \sim \{1,4,5\}$ and equivalent relationship. What about $\{1,2,4\} \sim \{1,3,4\}$?

The book just gives the answer as true for the first and false for the second. I want to know why my answers are wrong because I get true for both and how to get the right answer.

$\{1, 2, 4\} \sim \{1,4,5\}$ is an equivalence relation because:

  • Reflexive: $X \cap T = X \cap T$ is true
  • Symmetric: $X \cap T = Y \cap T \implies Y \cap T = X \cap T$ is true
  • Transitive: $\{1, 2, 4\} \cap \{1,3\} = \{1,4,5\} \cap \{1,3\} \land \{1,4,5\} \cap \{1,3\} = Z \cap \{1,3\} \implies \{1,2,4\} = Z$ is true

$\{1, 2, 4\} \sim \{1,3,4\}$ is an equivalence relation because:

  1. Reflexive is true (see above)
  2. Symmetric: $\{1, 2, 4\} \cap \{1,3\} = \{1,3,4\}\cap\{1,3\}$ is false since $\{1\} \neq \{1,3\}$ since the premise is false, the implication is true
  3. Transitive: $\{1, 2, 4\} \cap \{1,3\} = \{1,3,4\} \cap \{1,3\} $ is false since $\{1\} \neq \{1,3\}$. Since the premise is false, the implication is true

Best Answer

Honestly, I've been as confused as you are right now when I first saw this stuff. So let's go over it step by step.

First, we need to show the relation $\sim$ satisfies the demands of an equivalence relation. Your reflexivity and symmetricity checks are correct. For transitivity you have, for some reason, replaced $X,Y,T$ with some fixed subsets. To fix this, assume $X\cap T = Y\cap T$ and $Y\cap T = Z\cap T$. Is is then true that $X\cap T = Z\cap T$?

Once we've established that $\sim$ is an equivalence relation, we fix sets $S,T$ and we are asked whether $$\{1,2,4\} \sim \{1,4,5\}\quad\mbox{or}\quad \{1,2,4\}\sim \{1,3,4\}. $$ To check this, we simply check the condition we defined the relation $\sim$ with. Do the following hold? $$\{1,2,4\}\cap \{1,3\} \overset{?}= \{1,4,5\}\cap \{1,3\} \quad (\text{yes}) \\ \{1,2,4\}\cap \{1,3\} \overset{?}= \{1,3,4\}\cap \{1,3\}\quad (\text{no})$$

Can you pick it up from here?

Related Question