0
$\begingroup$

I'm trying to prove the following exercise of How to Prove it: A structured Approach (Section 3.4, exercise 19):

Suppose A, B and C are sets. Prove that A $\triangle$ B and C are disjoint iff A $\cap$ B = B $\cap$ C.

The answer to the proof goes like this:

($\Rightarrow$) Suppose that A $\triangle$ B and C are disjoint. Let x be an arbitrary element of A $\cap$ C. Then x $\in$ A and x $\in$ C. If x $\not\in$ B, then since x $\in$ A, x $\in$ A \ B, and therefore x $\in$ A $\triangle$ B. But also x ∈ C, so this contradicts our assumption that A $\triangle$ B and C are disjoint. Therefore x $\in$ B. Since we also know x $\in$ C, we have x $\in$ B $\cap$ C. Since x was an arbitrary element of A $\cap$ C, this shows that A $\cap$ C $\subseteq$ B $\cap$ C. A similar argument shows that B $\cap$ C $\subseteq$ A $\cap$ C.

($\Leftarrow$) Suppose that A $\cap$ C = B $\cap$ C. Suppose that A $\triangle$ B and C are not disjoint. Then we can choose some x such that x $\in$ A $\triangle$ B and x $\in$ C. Since x $\in$ A $\triangle$ B, either x $\in$ A \ B or x $\in$ B \ A.

Case 1. x $\in$ A and x $\not\in$ B. Since we also know x $\in$ C, we can conclude that x $\in$ A $\cap$ C but x $\not\in$ B $\cap$ C. This contradicts the fact that A $\cap$ B = B $\cap$ C.

Case 2. x $\in$ B \ A. Similarly, this leads to a contradiction.

Thus we can conclude that A $\triangle$ B and C are disjoint.

The first part of the proof is similar to what I've done, however I'm having troubles understanding the second part (the $\Leftarrow$).

In the second part we're trying to prove A $\cap$ B = B $\cap$ C $\Rightarrow$ A $\triangle$ B $\not\subseteq$ C.

The answer supposes A $\cap$ B = B $\cap$ C, thus the goal becomes A $\triangle$ B $\not\subseteq$ C. Then, it assumes the negation of the goal, A $\triangle$ B $\subseteq$ C, attempting to prove a contradiction.

A $\triangle$ B $\subseteq$ C means that $\forall$y(y $\in$ A $\triangle$ B $\Rightarrow$ y $\in$ C).

The proof then continues with:

Then we can choose some x such that x $\in$ A $\triangle$ B and x $\in$ C.

However this doesn't make sense to me. How can we assume that there exists an arbitrary value that makes the condition true if the given is an universally quantified goal?

As far as my understanding goes, we could use existential instantiation if the given was $\exists$y(y $\in$ A $\triangle$ B $\land$ y $\in$ C) instead. Is there anything that I'm missing?

My solution to that part of the proof was the following:

Suppose that A $\cap$ C = B $\cap$ C. It the follows that A = B. Since A = B, A $\triangle$ B = $\emptyset$, therefore A $\triangle$ B $\not\subseteq$ C.

But I believe my answer is wrong, as it assumes C is not an empty set, which is not a given of the theorem:

  • Suppose that A $\cap$ C = B $\cap$ C. It the follows that A = B.

This means A $\cap$ C = B $\cap$ C $\Rightarrow$ A = B, but this is clearly false if C = $\emptyset$, as any values of A and B (even if they are different) make the statement A $\cap$ C = B $\cap$ C true.

What am I missing to understand the book's answer?

$\endgroup$
0
$\begingroup$

CYou write that "In the second part we're trying to prove that $A\cap C = B\cap C \Rightarrow A \triangle B \not\subseteq C$" but that is not correct. Two sets are disjoint is their instersection is the empty set, so what the second part of the exercise is trying to prove is: $A\cap C = B\cap C \Rightarrow (A \triangle B) \cap C=\emptyset$. See if you can follow the proof now.

$\endgroup$
  • $\begingroup$ Thanks for pointing out the issue. I follow the proof now. $\endgroup$ – jviotti Apr 16 '15 at 18:36

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.