2
$\begingroup$

In this question, the most upvoted explanation of the identity in my title is this reply. I don't have the reputation to comment on the existing thread, so I'm asking here, because I am having a hard time following the explanation. I can prove this identity via Venn decomposition as in the checked reply, or simply verbalizing the ideas, but I can't seem to follow it via straight logical equivalencies. This explanation just confuses me further, such as here:

$x \in (A \triangle B)\setminus C$ or $x \in C$. In the first case, $x \in A$ and $x \notin B$ (so $x \in A \cup C $ and $x \notin B\setminus C$) or $x \notin A$ and $x \in B$ and $x \notin C$

Why is it being phrased this way? I can see how individual assertions are technically true, but I can't seem to follow how they're being arrived at, and the treatment of the set $C$ seems arbitrary to me. Why is its exclusion not mentioned in the first possibility, but is in the second? I know what these statements mean taken by themselves, but I can't seem to make sense of how the respondent relates them.

Here's as far as I get with the algebraic logic approach:

$((A \lor B)\land(\lnot A \lor \lnot B))\lor C \equiv ((A \lor C) \lor (B \land \lnot C)) \land ((\lnot A \land \lnot C) \lor (\lnot B \lor C))$

But it's at this point that I run into a wall.

$\endgroup$

2 Answers 2

1
$\begingroup$

In the set algebra explanation replace intersection with and, union with or, difference with 'and not', summetric difference with exclusive or, equality with equivalence and replace every set with the proposition that x belongs to it.

$\endgroup$
3
  • $\begingroup$ I've attempted that a few times; I've gotten as far as the expression I've edited into the original post, but after the expansions necessary to get there, I can't see how I'd begin to move towards the final goal of showing them to be the same thing. $\endgroup$
    – user242007
    Commented Dec 7, 2015 at 16:09
  • 1
    $\begingroup$ In the paragraph you are quoting, the author of the reply starts from the hypothesis that $x$ belongs to the LHS and establishes that is must belong to the RHS. He does that by splitting the analysis in two mutually exclusive cases, one of which must be true. In either case he arrives by a separate reasoning that $x$ must be in the symmetric difference of $A\cup C$ and $B\setminus C.$ Together, all this establishes that the LHS is at least a subset of the RHS, i.e., half of the equality to be proven. $\endgroup$ Commented Dec 7, 2015 at 20:23
  • $\begingroup$ That comment just made everything click. Thank you so much, both for your insight and for your patience. $\endgroup$
    – user242007
    Commented Dec 7, 2015 at 20:53
0
$\begingroup$

The idea behind the reply you have quoted is that to prove that two sets $X$ and $Y$ are equal, you have to show that $X \subseteq Y$ and $Y \subseteq X$.

Let us prove that $(A \triangle B)\cup C \subseteq (A\cup C)\triangle (B\setminus C)$ i.e. all elements of $(A \triangle B)\cup C$ are elements of $ (A\cup C)\triangle (B\setminus C)$. Suppose that $x \in (A \triangle B)\cup C $: since either $x \in C$ or $x \notin C$ (law of excluded middle), your hypothesis means that either $x \in (A \triangle C) \setminus C$ or $x \in C$. Now, following the argument in this reply, you show that $x \in (A\cup C)\triangle (B\setminus C)$. This ends the proof that $(A \triangle B)\cup C \subseteq (A\cup C)\triangle (B\setminus C)$.

$\endgroup$

You must log in to answer this question.

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