3
$\begingroup$

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.

  • 0
    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".2011-09-29
  • 0
    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.)2011-09-29
  • 0
    @AsafKaragila,Srivatsan: I have edited it. ' indicates a compliment.2011-09-29
  • 1
    Ok. Since you said "I don't understand how do I prove this using proof techniques.", what proof techniques do you know?2011-09-29
  • 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'$?2011-09-29

2 Answers 2

4

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$.

-3

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

  • 1
    I think this isnt helpful for someone trying to learn how to prove things by themselves.2011-09-30
  • 1
    The question was about proof techniques -- the rules of logic, etc. It seemed to me that the resulting proof was incidental.2011-09-30