1
$\begingroup$

I am working on basic set theory, more precisely, I am learning about the concepts of inclusion and power sets. I know that a power set $\mathcal P(A)$ of the set $A$ is the set of all subsets of $A$ and that a proper subset $X$ of a set $Y$ is such that $X \subset Y$ and $X \neq Y$.

If $X$ is a proper subset of the power set $\mathcal P(A)$ and $\mathcal P(A)$ is a proper subset of $Y$ such that $X$ contains exactly $2$ elements, how do I show the minimum number of elements that are in $Y$?

$$X\subset \mathcal P(A)\subset Y : |X|=2$$ $$X=\lbrace x_1, x_2 \rbrace, \; \text{find} \;|Y|$$ Basically what I am seeing is that if $X$ is a proper subset of $\mathcal P(A)$, then $\mathcal P(X)$ is also a proper subset of $\mathcal P(A)$ and $|\mathcal P(A)| \gt |\mathcal P(X)|\gt |X|$ so $|\mathcal P(A)|$ contains at least $|\mathcal P(X)|+1 = $ $2^{|X|}+1$ elements. $$X\subset \mathcal P(A) \implies \mathcal P(A) = \lbrace \,\ldots,\underbrace{ X, \lbrace x_1\rbrace, \lbrace x_2 \rbrace, \emptyset }_{\mathcal P(X)}\; \rbrace $$ Then, $$X\subset \mathcal P(A)\subset Y \implies X\subset Y$$ Since $X$ is already in $Y$ I do not count it twice and so we only know $ \lbrace x_1 \rbrace , \lbrace x_2 \rbrace$ and the empty set $\emptyset$ from $\mathcal P(A)$ that are included in $Y$, all the other elements of $\mathcal P(A)$ but $X$ are also included in $Y$ but they are unknown hence, $$Y=\lbrace\ldots, X, \lbrace x_1 \rbrace, \lbrace x_2 \rbrace, \emptyset \, \rbrace $$ Therefore I would claim that $$|Y| \ge 2^{|X|}+1$$ Is this a correct reasoning and does it apply to any $|X|$ in such conditions?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Suppose $A$ is a $2$-element set, say $A=\{1,2\}.$ Then the $3$-element set $X=\{\emptyset,\{1\},\{2\}\}$ is a proper subset of $\mathcal P(A),$ so $Y$ can have $5$ elements, say $Y=\mathcal P(A)\cup\{3\},$ while $2^{|X|}+1=9.$ $\endgroup$ – bof Feb 5 '17 at 23:49
  • 5
    $\begingroup$ Your mistake is saying "if $X$ is a proper subset of $\mathcal P(A),$ then $\mathcal P(X)$ is also a proper subset of $\mathcal P(A)$ and $|\mathcal P(A)|\gt|\mathcal P(X)|$". $\endgroup$ – bof Feb 5 '17 at 23:56
  • 1
    $\begingroup$ Correctly: $|X|\lt|\mathcal P(A)| \implies 2^|A|\gt|X| \implies 2^|A|\ge|X|+1 \implies |A|\ge\log_2(|X|+1)$ $ \implies |A|\ge\lceil\log_2(|X|+1)\rceil$ $\endgroup$ – bof Feb 6 '17 at 0:04
  • 1
    $\begingroup$ Note that, if $X=A=\emptyset,$ then $X$ is a proper subset of $\mathcal P(A),$ but $\mathcal P(X)$ is not a proper subset of $\mathcal P(A).$ $\endgroup$ – bof Feb 6 '17 at 0:09
  • 1
    $\begingroup$ That's true as far as it goes. If $|X|=4$ then $|A|\ge3$ so $|\mathcal P(A)|\ge2^3=8\ge5=|X|+1.$ $\endgroup$ – bof Feb 6 '17 at 1:34
3
$\begingroup$

It is not true that if $X\subset\mathcal{P}(A)$ then $\mathcal{P}(X)\subset\mathcal{P}(A)$. For example, consider $A=\{0,1\}$ and $X=\{\{0\},\{1\}\}$. Then, for instance, $\{\{1\}\}$ is an element of $\mathcal{P}(X)$ but is not an element of $\mathcal{P}(A)$. Really, there is no reason at all for $\mathcal{P}(X)$ to be a subset of $\mathcal{P}(A)$ in general: an element of $\mathcal{P}(X)$ is a set of subsets of $A$, rather than a set of elements of $A$.

Instead, all you know from $X\subset\mathcal{P}(A)$ is that $2<|\mathcal{P}(A)|$, since $\mathcal{P}(A)$ contains the two elements of $X$ and also at least one more element (or in general, all you know is that $|X|+1\leq|\mathcal{P}(A)|$). Given this, what is the smallest cardinality that $\mathcal{P}(A)$ could have (keeping in mind that the cardinality of a power set can't be just any number)? And then given that $\mathcal{P}(A)\subset Y$, what is the smallest cardinality $Y$ could have?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Unless there is something I am not seeing, I would be tempted to answer that given all we know about $|\mathcal P(A)|$ from $X \subset \mathcal P(A)$, we can only deduce that $|\mathcal P(A)|$ is at the very least $3 = |X|+1$. Then, since we know $\mathcal P(A) \subset Y$ and $|\mathcal P(A)| \ge 3$, I would say that the cardinality of $Y$ has to be at the very least $4 = |\mathcal P(A)| +1 = |X| + 2$, for example if $|X| = 5$ the least possible cardinality of $Y$ is $7$, correct? $\endgroup$ – user409521 Feb 6 '17 at 17:45
  • 1
    $\begingroup$ Almost, but not quite. Remember that the cardinality of a power set must be a power of $2$. So it is not possible for $\mathcal{P}(A)$ to have exactly $3$ elements. $\endgroup$ – Eric Wofsey Feb 6 '17 at 17:47
  • $\begingroup$ Now I see! I should have understood that is was what you meant by "keeping in mind that the cardinality of a power set can't be just any number". That number has to be a power of $2$ by definition of the cardinality of the power set. Hence, if $|X| = n$ then, $|\mathcal P(A)|$ is at least the smallest power $p$ of $2$ that is greater than or equal to $|X|+1$ namely, $|\mathcal P(A)| = 2^p \ge n + 1$. So if $X \subset \mathcal P(A) \subset Y$ and $|X| = 2$ then $|Y|$ can not be $4$ and is at least $5$... $\endgroup$ – user409521 Feb 6 '17 at 18:03
  • 1
    $\begingroup$ Yep, that's right! $\endgroup$ – Eric Wofsey Feb 6 '17 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy