1
$\begingroup$

I want to prove that:

a)

$A \Delta B = \emptyset \Leftrightarrow A = B $

Prove for $\Leftarrow$

Then:

$A \Delta B = (A$ \ $A) \cup (A $\ $A) = \emptyset$

Prove for $\Rightarrow$

Then(proof by contrapositive):

$A = B \rightarrow (A$ \ $B) \cup (A $\ $B) = (A$ \ $B) \cup (A $\ $B)= \emptyset$

b)

$A \Delta B = A \cup B \Leftrightarrow A \cap B = \emptyset$

Prove for $\Leftarrow$

$A \Delta B \rightarrow (A \cup B)$ \ $(A \cap B) = ( A \cup B) \rightarrow ( A \cap B) = \emptyset$

Prove for $\Rightarrow$

Then(proof by contrapositive):

$A \Delta B \rightarrow (A \cup B)$ \ $\emptyset = ( A \cup B) \rightarrow ( A \cap B) = ( A \cap B) $

I am not sure if these two proves are correct. I really appreciate your answer!

$\endgroup$
  • $\begingroup$ On a very formal level, $(A\cup B)\setminus(A\cap B)=A\cup B$ does not immediately give $A\cap B=\emptyset.$ At least $X\setminus Y=X$ does not imply $Y=\emptyset$. So you may want to add some detail there. $\endgroup$ – Hagen von Eitzen Jul 31 '13 at 14:30
  • $\begingroup$ @HagenvonEitzen: Suppose $A \cap B \neq \emptyset$. Then we can choose some $x$ such that $x \in A \cap B$. This means that $x \in A$ and $x \in B$. Since $x \in A$, it follows that $x \in A \cup B$. But then since $A \Delta B = A \cup B$, $x \in A \Delta B$, so $x \in A \cup B$ and $x \notin A \cap B$. This contradicts the fact that $x \in A \cap B$. Therefore $A \cap B = \emptyset$. $\endgroup$ – user21530 Jul 31 '13 at 23:38
1
$\begingroup$

a) ($\rightarrow$) Suppose $A \Delta B = \emptyset$. Let x be an arbitrary element of A. Suppose $x \notin B$. Then since $x \in A$ and $x \notin B$, $x \in B\setminus A$, so $x \in A \Delta B$, and therefore $x \in \emptyset$. But this last statement is clearly a contradiction, so we can conclude that $x \in B$. Since x was an arbitrary element of $A$, $A \subseteq B$. A similar argument shows that $B \subseteq A$. Then since $A \subseteq B$ and $B \subseteq A$, $A = B$.

($\leftarrow$) Suppose $A = B$. Suppose $A \Delta B \neq \emptyset$. Then we can choose some $x$ such that either $x \in A\setminus B$ or $x \in B\setminus A$. We consider these cases separately.
Case 1. $x \in A \setminus B$. Then since $A = B$, $x \in A \setminus A$, so $x \in A$ and $x \notin A$, which is a contradiction.
Case 2. $x \in B \setminus A$. Similarly, this leads to a contradiction.
Thus we can conclude that $A \Delta B = \emptyset$.

b) ($\rightarrow$) Suppose $A \Delta B = A \cup B$. Suppose $A \cap B \neq \emptyset$. Then we can choose some $x$ such that $x \in A \cap B$. This means that $x \in A$ and $x \in B$. Since $x \in A$, it follows that $x \in A \cup B$. But then since $A \Delta B = A \cup B$, $x \in A \Delta B$, so $x \in A \cup B$ and $x \notin A \cap B$. This contradicts the fact that $x \in A \cap B$. Therefore $A \cap B = \emptyset$.

($\leftarrow$) Suppose $A \cap B = \emptyset$. Let $x$ be an arbitrary element of $A \Delta B$. Then $x \in (A \cup B) \setminus (A \cap B)$. This means that $x \in A \cup B$ and $x \notin A \cap B$, so in particular $x \in A \cup B$. Since $x$ was an arbitrary element of $A \Delta B$, $A \Delta B \subseteq A \cup B$.
Now let $x$ be an arbitrary element of $A \cup B$. Then either $x \in A$ or $x \in B$.
Case 1. $x \in A$. Since $A \cap B = \emptyset$, $x \notin B$. Since $x \in A$ and $x \notin B$, $x \in A \setminus B$, so $x \in A \Delta B$.
Case 2. $x \in B$. A similar argument shows that $x \in A \Delta B$.
Since x was an arbitrary element of $A \cup B$, $A \cup B \subseteq A \Delta B$. But then since $A \Delta B \subseteq A \cup B$ and $A \cup B \subseteq A \Delta B$, we can conclude that $A \Delta B = A \cup B$.

$\endgroup$
2
$\begingroup$

Let $X$ be a set. Let $F_2 = \mathbb{Z}/2\mathbb{Z} = \{0, 1\}$ be the field consisting of $2$ elements. Let $F_2^X$ be the set of maps $X \rightarrow F_2$. $F_2^X$ is a ring with pointwise addition and multiplication. Let $A$ be a subset of $X$. Let $\chi_A$ be the characteristic function of $A$. We regard $\chi_A$ as an element of $F_2^X$.

Now let $A, B$ be subsets of $X$. Clearly $\chi_{A\Delta B} = \chi_A + \chi_B$.

Suppose $A\Delta B = \emptyset$. Then $0 = \chi_A + \chi_B$. Hence $\chi_A = -\chi_B = \chi_B$. Hence $A = B$.

Conversely suppose $A = B$. Then $\chi_A = \chi_B$. Hence $\chi_{A\Delta B} = \chi_A + \chi_B = 0$. Hence $A\Delta B = \emptyset$.

$\endgroup$
1
$\begingroup$

For a) $\Rightarrow)$ and since you want use the contrapositive argument you must prove that if $A\neq B$ then $A\Delta B\neq \emptyset$, so suppose that $A\neq B$ then there's $x\in A$ and $x\not\in B$ or there's $x\in B$ and $x\not\in A$ so $A\setminus B\ne\emptyset$ or $B\setminus A\ne\emptyset$ and then $A\Delta B=(A\setminus B)\cup (B\setminus A)\ne\emptyset$.

For b) if $A\Delta B=A\cup B$ then $(A\cup B)\setminus (A\cap B)=(A\cup B)$ so $(A\cap B)\subset(A\cup B)^c $ and since clearly $(A\cap B)\subset(A\cup B) $ then $$(A\cap B)\subset(A\cup B)\cap(A\cup B)^c=\emptyset $$

$\endgroup$
1
$\begingroup$

Here is an alternative, calculational proof which does not have two separate directions, using the fact (an alternative definition, actually) that for all $\;x\;$, $$x \in A \Delta B \equiv x \in A \not\equiv x \in B$$ Now we try to simplify $\;A \Delta B = \emptyset\;$: \begin{align} & A \Delta B = \emptyset \\ \equiv & \;\;\;\;\;\text{"basic property of $\;\emptyset\;$: it contains no elements"} \\ & \langle \forall x :: \lnot(x \in A \Delta B) \rangle \\ \equiv & \;\;\;\;\;\text{"the above definition of $\;\Delta\;$"} \\ & \langle \forall x :: \lnot(x \in A \not\equiv x \in B) \rangle \\ \equiv & \;\;\;\;\;\text{"logic"} \\ & \langle \forall x :: x \in A \equiv x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;=\;$ on sets, i.e., set extensionality"} \\ & A = B \\ \end{align} If you want to use the definition $\;A \Delta B = (A \setminus B) \cup (B \setminus A)\;$, then you can use a similar approach, using \begin{array}\\ x \in A \setminus B & \equiv & x \in A \land \lnot(x \in B) \\ x \in A \cup B & \equiv & x \in A \lor x \in B \\ \end{array} This makes the calculation slightly longer, of course. Hint: use DeMorgan, and the fact that $\;\lnot P \lor Q\;$ is the same as $\;P \Rightarrow Q \;$.

$\endgroup$

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.