Equivalence Relations of Power Sets

817 Views Asked by At

I am trying to understand how $\mathrm W$ is an equivalence relation.

Let $A = \{1,2,3,4,5,6,7\}$ and $B = \{1,2,3,4\}$.

Let $\mathrm W$ be the relation on $P(A)$ defined by: \begin{equation} \forall X, Y \in P(A), X \mathrm R Y \Leftrightarrow |X \cap B| = |Y \cap B| \end{equation}

2

There are 2 best solutions below

6
On BEST ANSWER

$$\forall X\in \mathcal P(A),\forall Y\in\mathcal P(A): \Big[X\operatorname R Y \iff \lvert X\cap B\rvert = \lvert Y\cap B\rvert\Big]$$

In English: "Any two subsets of $A$, are said to be $\operatorname R$ related if their intersections with $B$ have the same cardinality."

The relation $\operatorname R$ is an equivalence relation if it is reflexive, symmetric, and transitive.   You have gotten that far, but don't seem to know what these properties are.

Yes, I was trying to prove that it is reflexive. I was thinking that it is not reflexive since, $X = \{1,2,3,4,5\}$ and $Y = \{1,2,3,4\}$ then $|X \cap B| = 4 = |Y \cap B|$. But element 5 in X cannot point to itself. However, that contradicts from the question that is claiming it is an equivalence relation. Am I missing something?

I'm not entirely sure what you mean by "element 5 in X cannot point to itself".   We are discussing relations between subsets of $A$, not betwixt elements of those subsets.

Reflexivity means that identity always infers a relationship, $\forall X\,\forall Y:(X=Y)\to (X\operatorname R Y)$, however the converse is not necessary; a relationship need not imply an identity.   It is possible for two distinct sets to be in a reflexive relation.   (Or an equivalence relation for that matter; equivalence is not necessarily identity.)

In short, the following means that $\operatorname R$ is reflexive:$$\forall X\in\mathcal P(A): X\operatorname R X$$

So to ascertain that $\operatorname R$ is reflexive you must assess whether all subsets of $A$ (aka elements of $\mathcal P(A)$) are related to themselves.   Does the following hold?$$\forall X\in\mathcal P(A): \lvert X\cap B\rvert =\lvert X\cap B\rvert$$

Similarly symmetry is ascertained by $$\begin{align}\forall X\in\mathcal P(A)~\forall Y\in\mathcal P(A) &: (\lvert X\cap B\rvert = \lvert Y\cap B\rvert) \to (\lvert Y\cap B\rvert = \lvert X\cap B\rvert)\\ &\Updownarrow\\ \forall X\in\mathcal P(A)~\forall Y\in\mathcal P(A) &: (X\operatorname R Y) \to (Y\operatorname R X)\end{align}$$

And then there is transitivity. $$\begin{align}\forall X\in\mathcal P(A)~\forall Y\in\mathcal P(A)~\forall Z\in\mathcal P(A) &: \Big(\big((\lvert X\cap B\rvert = \lvert Y\cap B\rvert) \wedge (\lvert Y\cap B\rvert = \lvert Z\cap B\rvert)\big)~\to~ (\lvert X\cap B\rvert = \lvert Z\cap B\rvert)\Big)\\ &\Updownarrow\\ \forall X\in\mathcal P(A)~\forall Y\in\mathcal P(A)~\forall Z\in\mathcal P(A) &: \Big(\big((X\operatorname R Y)\wedge(Y\operatorname R Z)\big)~ \to ~(X\operatorname R Z)\Big)\end{align}$$

0
On

(Answering your comment.) Yes, you are missing something. What you are missing is that this is a relation between sets, not between individual elements. So the statement $$X\ {\rm R}\ Y$$ only makes sense (whether true or false) if $X$ and $Y$ are sets. It does not make sense, and is irrelevant to the question, if you try to take $X$ as a single element such as $5$.

But (at the risk of further confusion) it does make sense if $X$ is a set containing a single element such as $\{5\}$. Note that $\{5\}$ is not the same as $5$!!!