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.

I have to prove the following question,

Let A and B are subsets of a universal set U. Prove that A is a subset of B iff B' is a subset of A'

Now I don't understand how do I prove this using proof techniques. Please guide me.

Thanks.

share|improve this question
    
What is B'? When you say belong, do you mean $\in$ or $\subseteq$? The former is "a member of" and the latter is "a subset of". –  Asaf Karagila Sep 29 '11 at 21:25
    
The phrase "belongs to" is ambiguous because it is used to mean both $\in$ and $\subseteq$. Presumably you mean "subset" when you say one set belongs to another. (Also you should explain what your ' notation means. I think it means set complement.) –  Srivatsan Sep 29 '11 at 21:25
    
@AsafKaragila,Srivatsan: I have edited it. ' indicates a compliment. –  Fahad Uddin Sep 29 '11 at 21:30
1  
Ok. Since you said "I don't understand how do I prove this using proof techniques.", what proof techniques do you know? –  Jack Sep 29 '11 at 21:32
1  
Just some more questions: Do you know what a subset mean? Do you understand what is iff? Do you understand what are $B'$ and $A'$? –  Jack Sep 29 '11 at 21:36

2 Answers 2

up vote 4 down vote accepted

We want to prove the following:

$$A\subseteq B\iff B^c\subseteq A^c$$

We need, therefore, to prove two implications.

  1. Assume $A\subseteq B$. We want to show that $B^c\subseteq A^c$, that is $x\in B^c$ implies $x\in A^c$. Suppose $x\in B^c$, then $x\notin B$. Since $A\subseteq B$ is to say $x\in A\rightarrow x\in B$, we have that if $x\notin B$ then $x\notin A$. In particular, $x\in A^c$. We therefore proved $\Rightarrow$.

  2. Suppose now that $B^c\subseteq A^c$. Note that $(B^c)^c = B$. By the previous proof we have that $B^c\subseteq A^c\Rightarrow (A^c)^c\subseteq (B^c)^c$. However that means exactly that $A\subseteq B$.


Another approach is to use logical equivalence of $\alpha\rightarrow\beta\iff\lnot\beta\rightarrow\lnot\alpha$.

Since $A\subseteq B$ is $x\in A\rightarrow x\in B$, this as the above equivalence tells us, is the same as $x\notin B\rightarrow x\notin A$, which is precisely to say $B^c\subseteq A^c$.

share|improve this answer

See my formal proof at http://www.dcproof.com/MathSE-2011-09-30.htm

This proof was generated with the aid of my DC Proof software available at

http://www.dcproof.com

Dan

share|improve this answer
1  
I think this isnt helpful for someone trying to learn how to prove things by themselves. –  Shahab Sep 30 '11 at 5:29
1  
The question was about proof techniques -- the rules of logic, etc. It seemed to me that the resulting proof was incidental. –  Dan Christensen Sep 30 '11 at 6:12

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.