Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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? –  Stavros Mekesis 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

2 Answers 2

up vote 4 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|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|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.