How to prove the associative law of symmetric difference?

[cleaf]

I'm trying to prove the associative law of symmetric difference (AΔ(BΔc) = (AΔB)ΔC ) with other relations of sets.

A naive way is to compare the truth table of two sides. However, I think the symmetric difference is not a basic one, it is constructed form other relations, that is AΔB = (A\B)∪(B\A). Is it possible to prove the associative law from other relations (i.e. ∩,∪,\ )?

 

[fresh_42]

I'm trying to prove the associative law of symmetric difference (AΔ(BΔc) = (AΔB)ΔC ) with other relations of sets.

A naive way is to compare the truth table of two sides. However, I think the symmetric difference is not a basic one, it is constructed form other relations, that is AΔB = (A\B)∪(B\A). Is it possible to prove the associative law from other relations (i.e. ∩,∪,\ )?

This should be the case, so yes. It is an equation in a Boolean algebra.

 

[Stephen Tashi]

A naive way is to compare the truth table of two sides.

Technically, it isn't correct to speak of a truth table for a side of an equation involving sets. What you probabily mean is that an equation involving sets can be interpreted as the equivalence of two propositional functions preceeded by the quantifier $\forall$. So the equation for sets $A = B$ can be interpreted as $\forall x: x \in A \iff x \in B$. Pretending that "$x$" represents a specific thing instead of a quantified variable, we may be able to speak of a truth table for each side of the logical equivalence. And you are correct that this point of view can form the basis for proofs about sets.

One way is show the logical equivalence of $x \in A\triangle (B \triangle C) \equiv x \in (A \triangle B) \triangle C$ is to write each side using on the relation $\in$, the logical connectives "and" and "or" ($\land, \lor$) and the logical operator "not" ($\lnot$). As an intermediate step you can express the two sides of the set equation using only $\cup, \cap,$ and the operation of taking the complement of a set. Statements involving $\cap,\cup$ can be interpreted as propositions involving the connectives $\land,\lor$. (For example $x \in A \cap B$ is interpreted to mean $(x \in A) \land (x \in B)$ .)

Since it's possible to prove equivalence of two propositions in propositional logic using theorems instead of writing truth-tables, it is, in theory, possible to prove the equation you asked about in that manner.

However, your question didn't deal with breaking down both sides into pure propositional logic. You asked if the proof can be done in a more elegant manner , employing only set equations with the connectives $\cap, \cup, \setminus$ I don't know. My suggestion is to not to insist that "$\setminus$ " be used. Instead, try to write set equations using only $\cap,\cup$ and the operation of taking a complement of a set.