Showing that (A⊕B)⊕B is equal to A

Question

I found this solution somewhat incomplete in a video I was watching. Here's the image and video (solution starts at ~2:11).

Here's what he wrote:

(A⊕B)⊕B=A

⇒ x∈(A⊕B)⊕B

= x∈(A⊕B) xor x∈B

= (x∈A xor x∈B) xor x∈B

x∈B → x∉A or x∉B (contradiction)

x∈A → x∉B or x∉B (works)

I find this incomplete as we only show that x∈A works, and there's no explanation of what happens to disjoint elements. What are your thoughts on this solution? And why or why not this is okay?

I came up with this solution and would like to know if it's correct or if there's a better way of writing it:

We want to show that: (A⊕B)⊕B=A

Let A=a∪c and B=b∪c, a is disjoint from b, a is disjoint from c

(A⊕B)⊕B

= ((a∪c)⊕(b∪c))⊕(b∪c)

= (a∪b)⊕(b∪c)

= (a∪c)

= A

QED

Answer 1

I agree with neither solution. Showing associativity of $\oplus$ is the best way to go IMHO, as @egreg suggested. This thread (and others) shows that $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ for all subsets and then just use that to move the braces and apply $B \oplus B = \emptyset$ and $A \oplus \emptyset = A$.

But as an ad-hoc proof: Suppose $x \in A$.

If $x \in B$ then $x \in A \cap B$ so $x \notin A \oplus B$ but still $x \in B$ so $x \in (A \oplus B) \oplus B$ by definition.

If $x \notin B$ then $x \in A \oplus B$ by definition and as $x \notin B$, $x \in (A \oplus B) \oplus B$ again.

So $A \subseteq (A \oplus B) \oplus B$.

If on the other hand $x \in (A \oplus B) \oplus B$ then either $x \in A \oplus B$ and $x \notin B$ which can only happen if $x \in A$,

or $x \notin A \oplus B$ and $x \in B$. In that case $x \notin A$ is ruled out too, as that would mean $x \in A \oplus B$, quod non. So $x \in A$ and so these two cases imply

$(A \oplus B) \oplus B \subseteq A$ and we are done.

Answer 2

An alternate solution: $I_{A\oplus B}=|I_A -I_B|$. So we have to show $||I_A (x)-I_B(x)|-I_B(x)|=I_A(x)$ which is obvious if you consider the cases $I_A(x) \geq I_B(x)$ and $I_A (x)\leq I_B(x)$.

Answer 3

The proof in the video is not just incomplete, it's just plain wrong.

The narrator states that if $x \in B$, then given that we have $x \in A \oplus x \in B$, we must have that $x \not \in A$, and, more importantly, since we have $(x \in A \oplus x \in B) \oplus x \in B$, we must have $x \not \in B$.

But the mistake is that it's not a given at all that $x \in A \oplus x \in B$. I think the narrator thinks something like this. "OK, we have $x \in B$. Well, then $x \in A \oplus x \in B$, because one of the two sides is true. OK, but then the other side must be false." The mistake is that while from $x \in B$ you can infer the inclusive disjunction (i.e. you can infer $x \in A \lor x \in B$), you cannot infer the exclusive disjunction $x \in A \oplus x \in B$

The narrator is likewise wrong to think that you can infer that $x \not \in B$ from the assumption that $x \in A$. Again the narrator thinks that by setting $x \in A$ to true, you thereby satisfy the exclusive disjunction $x \in A \oplus x \in B$. Not true!

Your proof is a lot better, though you may want to be clear what your $a$, $b$, and $c$ are. Now, I am sure you mean:

$a = A \setminus B$ (or: $A \cap B^C$)

$b = B\setminus A$ (or: $B \cap A^C$)

$c = A \cap B$

Also, you say that $a$ and $c$ are disjoint, and that $a$ and $b$ are disjoint, but you also want that $b$ and $b$ are disjoint, i.e. that they are all disjoint. But, once you do that, your proof works very nicely!