Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The symmetric difference of two sets $A$ and $B$ is the set $A \vartriangle B = (A \setminus B) \cup (B\setminus A) = (A \cup B) \setminus (A \cap B)$. Prove that if $A \vartriangle B \subseteq A$ then $B \subseteq A$.

Proof. Suppose $A \vartriangle B \subseteq A$. Let $x \in B$ be arbitrary. Now suppose $x\notin A$. Then $x \in B \setminus A$, so $x \in A \vartriangle B$. Since $A \vartriangle B \subseteq A$, it follows that $x \in A$. But this contradicts the fact assumption that $x \notin A$. Therefore $x \in A$. Since $x \in B$ was arbitrary, we can conclude that $B \subseteq A$.

I'm saying that $x \notin A$ implies $x \in A$, so $x \in A$ must be true. Is my proof by contradiction correct? If not, why?

share|cite|improve this question
2  
It is (albeit I'd explicitly write "by contradiction, suppose $x\notin A$" at the beginning, to make the overall structure of the proof clear). You assume something, and derive a contradiction; hence the "something" must be false. – Clement C. Jul 24 '13 at 20:16
1  
Yes. This is a valid proof by contradiction. As a purely syntactical remark, when I perform a proof by contradiction, I prefer to say "this contradicts the assumption that..." as opposed to the "fact". But thats only my opinion. – A.E Jul 24 '13 at 20:17
1  
The proof is correct. I agree with Orangutango that assumption (or hypothesis) would be better a better word choice than fact. I disagree with Clement and amWhy: the proof is so short, and its structure so obvious, that I see no need to say explicitly that that the assumption that $x\notin A$ is to derive a contradiction. – Brian M. Scott Jul 24 '13 at 20:32
    
Yes, in this particular case assumption is a better word choice because I assumed that $x \notin A$. Is assumption generally a better word choice than fact? – user21530 Jul 24 '13 at 20:55
1  
The word fact has a timeless quality to it: if someone jumped to a statement of fact in your writing they could on their own verify that statement. E.g. it is a fact that $B\setminus A$ is nonempty if and only if $B\not\subseteq A$. – Karl Kronenfeld Jul 24 '13 at 21:05
up vote 2 down vote accepted

Yes, you've written a valid proof-by-contradiction. I'd only suggest that you write:

"Let $x \in B$ be arbitrary. Now suppose, for the sake of contradiction, $x \notin A$. Then..."

if only to make explicit, at the start, the direction and structure of your proof.

share|cite|improve this answer

It is a valid proof by contradiction. I will point out, however, that you do not need to do it by contradiction. You can instead adapt your proof so that it is by contrapositive.

Start off by assuming $B\not\subseteq A$ whence there is some $x\in B\setminus A$. But $B\setminus A\subseteq A\vartriangle B$; thus, $x$ is an element of $(A\vartriangle B)\setminus A$, proving the contrapositive of the statement.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.