2
$\begingroup$

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.

2 Answers 2

3

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

  • 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.2012-11-09
2

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.