3
$\begingroup$

I would appreciate the insight again for a couple of proofs since I'm learning. These are homework problems in so much as they are problems from the textbook. They are not required by my professor. I'm doing a little extra through spring break.

The objective was to prove the statement or provide counter examples. I'd like to have my work critiqued since I've got to refine my abilities for proofs.

The following applies to both problems: Let $A, B, C$ be sets.

Problem 1

Prove: $A \oplus B = A \oplus C \Rightarrow B = C$.

My objective is to is to show that $B \subseteq C$ and $C \subseteq B$.

Proof:
Case 1: $$ \begin{align} \text{let}\, x \in B \mid x \in A \oplus B \\ \text{so,}\, x \in B \, \text{and} \, x \notin A \text{, by definition} \\ \text{since,}\, A \oplus B = A \oplus C, x \in C \,\square \end{align} $$

Case 2: $$ \begin{align} \text{let}\, x \in C \mid x \in A \oplus C \\ \text{so,}\, x \in C \, \text{and} \, x \notin A \text{, by definition} \\ \text{since,}\, A \oplus C = A \oplus B, x \in B \,\square \end{align} $$

Problem 2

Prove: $A \times B = A \times C \Rightarrow B = C$.
A similar problem and I must show that $B \subseteq C$ and $C \subseteq B$.

Proof:
Case 1: $$ \begin{align} \text{let} (a,b) \in A \times B\, \text{and}\, (a,c) \in A \times C \\ \text{since}\, A \times B = A \times C \text{,}\, \forall (a,b)\text{,} (a,b) = (a,c) \\ \text{so,}\, a = a\, \text{and}\, b=c \\ \text{thus}\, \forall b \in B, b \in C\,\square \end{align} $$

Case 2: $$ \begin{align} \text{let} (a,c) \in A \times C\, \text{and}\, (a,b) \in A \times B \\ \text{since}\, A \times C = A \times B \text{,}\, \forall (a,c)\text{,} (a,c) = (a,b) \\ \text{so,}\, a = a\, \text{and}\, c=b \\ \text{thus}\, \forall c \in C, c \in B\,\square \end{align} $$

I do appreciate the critique.

Thanks,
Andy

$\endgroup$
  • $\begingroup$ Your problem $2$ is right. However, what definition of $\otimes$ are you using? $\endgroup$ – user122283 Mar 30 '14 at 0:24
  • 1
    $\begingroup$ $\oplus$ is associative, $A\oplus A=\varnothing$ and $C\oplus \varnothing =C$ for any $C$. By adding $A$ on the left to $A\oplus C=A\oplus B$ you get what you want. $\endgroup$ – Pedro Tamaroff Mar 30 '14 at 0:51
  • $\begingroup$ @SanathDevalapurkar $\oplus$ is defined as the symmetric difference between sets. $A \oplus B = (A \setminus B) \cup (B \setminus A)$ $\endgroup$ – Andrew Falanga Mar 31 '14 at 13:15
  • $\begingroup$ @PedroTamaroff I'm having a bit of trouble visualizing how this works. We haven't covered addition of sets. I see the two operations you've done for symmetric difference. Is this what you mean: $A \oplus A \oplus C = A \oplus A \oplus B \rightarrow C = B$? $\endgroup$ – Andrew Falanga Mar 31 '14 at 13:25
  • $\begingroup$ @AndrewFalanga Yes. You have addition and inverses. Much like $a+b=a+c\implies b=c$ by adding $-a$ to both sides. $\endgroup$ – Pedro Tamaroff Mar 31 '14 at 13:38
1
$\begingroup$

As pointed out in the comments, your solution to Problem $2$ is correct.

I believe that your solution to Problem $1$ is correct, but (as Pedro Tamaroff pointed out) it's not the "easiest" proof. A more straightforward proof is to say:

Let $A,\;B,\;C$ be sets, and $A\oplus B = A\oplus C$. Adding $A$ on the left gives: $$A\oplus (A \oplus B) = A\oplus(A\oplus C)$$ $$(A\oplus A) \oplus B = (A\oplus A)\oplus C \tag{$\oplus$ is associative}$$ $$\emptyset \oplus B = \emptyset \oplus C \tag{$A \oplus A = \emptyset$ for all $A$}$$ $$B = C \tag{$\emptyset \oplus A = A \oplus \emptyset = A$ for all $A$}$$

$\endgroup$
  • 1
    $\begingroup$ I like this proof. That's great. For the class, we didn't spend much time with the $\oplus$ and my prof would have wanted me to demonstrate that it's associative (i.e. prove it). I know this because of a conversation I had with him about one of the tests. $\endgroup$ – Andrew Falanga Jun 26 '14 at 18:47

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.