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 had as a question on an assignment the question in the subject. I'll write it properly here: $$A\subset B\leftrightarrow 2^A\subset 2^B$$

How can I go about proving this? I had a few ideas how to start, but I don't know if I'm anywhere on the right track.

  1. $A\subset B\leftrightarrow \forall w\in A\{w\in B\}\wedge A\ne B$
  2. $2^A\leftrightarrow \forall x\{x\subseteq A\}$
  3. $2^B\leftrightarrow \forall y\{y\subseteq B\}$
  4. $2^A\subset 2^B\leftrightarrow \exists z\in 2^B\{z\notin 2^A\}$

I feel like I have a few good points, but it just doesn't feel complete. I wonder if anybody can help me along.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

I think that you’re getting lost in symbols and not really thinking clearly about the idea.

Suppose that $x\in 2^A$; then then $x\subseteq A\subseteq B$, so $x\subseteq B$, and therefore $x\in 2^B$. Since $x$ was an arbitrary member of $2^A$, it follows that $2^A\subseteq 2^B$. To show that the inclusion is strict, just look at $B$: clearly $B\in 2^B$, but is $B\in 2^A$?

Your points (2) and (3) don’t make sense: $\leftrightarrow$ is a connective between statements, and $2^A$ isn’t a statement. What you mean, I think, is that $2^A=\{x:x\subseteq A\}$, and similarly for $B$.

share|improve this answer
    
I had indeed considered that $B\in 2^B\wedge B\notin 2^A$... I just wasn't sure how to use it in some coherent proof from start to end. –  agent154 Nov 8 '12 at 23:50
1  
@agent154: It could stand a few more words, but $B\in 2^B\wedge B\notin 2^A$ is a coherent proof that $2^B\nsubseteq 2^A$ if $A\subsetneqq B$; all you have to do to finish the job is show that $2^A\subseteq 2^B$, as I did above. –  Brian M. Scott Nov 9 '12 at 0:04

To show that if $A\subsetneq B$ then $P(A)\subsetneq P(B)$ you have to show inclusion, and inequality. The inclusion is quite simple, since $X\subseteq A\subseteq B$ implies $X\subseteq B$. The inequality can be deduced through the singletons in $P(A)$ and in $P(B)$ (you have to use the fact that $A\neq B$, of course).

In the other direction, if $P(A)\subsetneq P(B)$ you also have to show inclusion and inequality. Again the singletons in $P(A)$ are in $P(B)$ which should be enough to conclude $A\subseteq B$, and you can argue that if $A=B$ then $P(A)=P(B)$, which is a contradiction to the assumption.

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.