5
$\begingroup$

Let $A, B$ subsets of $X$ and $\mathbb P(X)$ the power set, we define the following equivalence relation on $\mathbb P(X)$:

Let $ S\subseteq X$ a fixed subset of $X$ and $A$~$B$ $\iff A△B \subseteq S$

Prove that is is an equivalence relation and find the class of $X$ and $S$

My work:

I have already shown that the relationship satisfies reflexivity and symmetry, all this is justified respectively by the fact that the empty set is a subset of any set and the symmetric difference is commutative.

My problem is with transitivity, I do not know how to do it, that is when I try to use it for the definition of symmetric difference I fall in many cases. There is some way to test transitivity using only operations between sets. And with respect to the equivalence class of $S$, I showed that they are all subsets of $X$ contained in $S$. But with respect to the equivalence class of $X4 I do not see what it is.

Any help would be useful. Thank you!

$\endgroup$
  • $\begingroup$ @EthanBolker You're right, my mistake! $\endgroup$ – Hendrik Matamoros May 23 at 21:54
3
$\begingroup$

Two hints about ways to go.

  • Draw a Venn diagram for $A, B, C, X$ showing $A \Delta B$ and so on.
  • Know or show that $\Delta$ is associative. That and the fact that $B \Delta B$ is empty leads to an algebraic proof.
$\endgroup$
4
$\begingroup$

Hint:

By definition, $A\sim B$ means $A-B$ and $B-A\subset S$. So you have to show that, if $A-B, B-A, B-C, C-B\subset S$, then both $A-C$ and $C-A$ are subsets of $S$.

Consider first an element $x\in A-C$. Either it is in $B$, or it is not in $B$. What can you deduce from the hypotheses in each case?

$\endgroup$
  • 1
    $\begingroup$ Thanks! My problem is now, what is the equivalence class of $X$? $\endgroup$ – Hendrik Matamoros May 23 at 22:01
  • 2
    $\begingroup$ Well, it seems to be made up of the subsets of $X$ which contain $X-S$. $\endgroup$ – Bernard May 23 at 22:16
4
$\begingroup$

We need to show theat $A\sim B$ and $B \sim C$ give $A \sim C$. This can easily be seen by visualising $A, B, C$ in a Venn diagram (try it yourself!) To put the Venn diagram proof formally, consider any element $x$ in $A$ but not in $C$. If $x$ is in $B$, it lies in the symmetric difference of $B$ and $C$ and so is in $S$. If $x$ is not in $B$, it lies in the symmetric difference of $A$ and $B$ and so is in $S$. By symmetry any element in $C$ but not $A$ is in $S$, completing the proof.

$\endgroup$
2
$\begingroup$

If $A \Delta B \subseteq S$ and $B \Delta C \subseteq S$, then

$A \Delta C= (A \Delta B) \Delta (B \Delta C) \subseteq S$ as well.

$\endgroup$
  • $\begingroup$ Must be, subset of $S$. Any help about the equivalence class of $X$? $\endgroup$ – Hendrik Matamoros May 23 at 21:59
  • 1
    $\begingroup$ @HendrikMatamoros: if $A$ is a subset of $X$, then $A\Delta X=A^c$, the complement of $A$ in $X$. This should help $\endgroup$ – Taladris May 24 at 12:13
1
$\begingroup$

Below, a proof using the fact that (1) symmetrixc difference can be defined using exclusive OR ( w) (2) that exclusive OR is the negation of the biconditional operator, and (3) that the biconditional operator is transitive

Below, please read " we'll " instead of " will".

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.