1
$\begingroup$

$X,Y,Z$ are sets, $X+Y:=(X \cup Y) \setminus (X \cap Y)$.

I need to show that $(X+Y)+Z=X+(Y+Z)$.

Intuitively it is clear that $$(X+Y)+Z=(X \cup Y \cup Z) \setminus ( [X \cap Y] \cup [Y \cap Z] \cup [Z \cap X] \setminus [X \cap Y \cap Z ])$$

Then the claim would follow. Any idea how to prove the intuition in a smart way without considering 8 cases ($x \in X, x \notin Y, x \in Z$, etc.)?

$\endgroup$
6
  • $\begingroup$ You mean $(X\cup Y)\setminus(X\cap Y)$, don't you? $(X\cap Y)\setminus(X\cup Y)$ is always empty no matter what $X$ and $Y$ are (and therefore your relation holds automatically, but not very interestingly) $\endgroup$ Nov 21, 2015 at 21:34
  • $\begingroup$ @NormalHuman: Not really, since working from a definition $(X\cup Y)\setminus(X\cap Y)$ is different from working from the definition $(X\setminus Y)\cup(Y\setminus X)$. One can prove that those definitions are equlvalent, of course, but that does not seem to be significantly simpler than proving associativity directly. $\endgroup$ Nov 21, 2015 at 21:36
  • $\begingroup$ Equivalence of two is immediate, associativity is not. $\endgroup$
    – user147263
    Nov 21, 2015 at 21:38
  • $\begingroup$ @NormalHuman: Equivalence may well not be immediate for someone at the level at which this question is likely to be asked. $\endgroup$ Nov 21, 2015 at 21:43
  • $\begingroup$ You could prove that each side is the set of things belonging to an odd number of the sets $X,Y$, and $Z$. This argument is essentially the same for both expressions. $\endgroup$ Nov 21, 2015 at 22:00

2 Answers 2

2
$\begingroup$

The symmetric difference $(a\cup b)\backslash (a\cap b)$ is usually written $a\Delta b. $ It is worthwhile to observe that $a\Delta b=(a\backslash b)\cup (b\backslash a). $ Now $p\in (a\Delta b)\Delta c$ iff (i) $p\in a$ or $p\in b$ but not both, and also $p\not \in c$, or (ii)$p\in c$ and $p$ doesn't belong to $a$ or $b$ unless it belongs to both of them. In other words, $p\in (a\Delta b)\Delta c$ iff $p$ belongs to one of $a,b,c$ but not to the intersection of any 2 of them,unless $p$ belongs to all of them. What of $a\Delta (b\Delta c)$? We have $a\Delta (b\Delta c)=(b\Delta c)\Delta a.$ And $p\in (b\Delta c)\Delta a)$ iff $p$ belongs to one of $b,c,a$ but not to the intersection of any 2 of them, unless $p$ belongs to all of them. $$(a\Delta b)\Delta c=a\Delta (b\Delta c)=$$ $$=(P\backslash Q)\cup R$$ where $P=a\cup b \cup c$ and $Q= (a\cap b)\cup (b\cap c)\cup (c\cap a)$ and $R=a\cap b \cap c$. It may be helpful to draw a Venn diagram.

$\endgroup$
1
$\begingroup$

Both $A + (B + C)$ and $(A + B) + C$ are exactly those things that are in an odd number of $(A, B, C)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .