3
$\begingroup$

Here is my question. There exist a finite set A that equals its own Power Set ? True or False

If Power Set has any elements, since Power Set definitely has empty set , There never exist any finite set which equals its own Power Set.

The only I have considered is that empty set. but since P(∅)={∅, {∅}} so above states is still false. right?

Please if I am doing something wrong, please advice me. Thanks

$\endgroup$
5
  • 1
    $\begingroup$ The power set of $\emptyset$ is just $\{\emptyset\}$. $\endgroup$ – peterwhy Oct 1 '18 at 22:16
  • $\begingroup$ To prove your claim for all finite sets, try to compute the size of the power set of a set of size $n$. Hint: a subset of $A$ is equivalent to a function from $A$ to $\{0,1\}$. (There is also a very elegant argument that works for infinite sets as well as finite ones.) $\endgroup$ – Danny Stoll Oct 1 '18 at 22:16
  • 1
    $\begingroup$ See Cantor's Theorem. I don't know if I'm terribly biased, but it seems natural to me to think about this in terms of cardinality. $\endgroup$ – Git Gud Oct 1 '18 at 22:17
  • $\begingroup$ OK, I found another argument. Use induction and when using the induction hypothesis you can complete the proof with a combinatorial argument. $\endgroup$ – Git Gud Oct 1 '18 at 22:22
  • 1
    $\begingroup$ Correct. A very simple intuitive argument is : for a finite set $A = \{ a_1, \ldots, a_n \}$, its power-set contains for sure the following subsets of $A$ : $\{ a_1 \}, \ldots \{ a_n \}$. Thus in the power-set of $A$ there are at least so much elements as in $A$. But we have more : $\emptyset, A$ and more. $\endgroup$ – Mauro ALLEGRANZA Oct 2 '18 at 9:33
2
$\begingroup$

There exists a finite set A that equals its own Power Set. True or False?

False!

This answer will be written for someone just beginning their explorations of set theory. If this is not you: feel free to peruse the other answers.

Welcome to the exploration of sets! You're in for a wild ride if you stick with it...

Claim: No finite set is equal to her powerset.

Proof

Left to the asker... but here are some hopefully helpful hints.

As is noted in the comments: $P(\emptyset) =\{ \emptyset\}$

Note that $\emptyset=\{\}$ has cardinality zero: It has no elements. Whereas $P(\emptyset)$ has cardinality 1. That is, $P(\emptyset)$ is a set with one element in it. That one element is $\emptyset$.

Symbolically we may write $0=|\emptyset|\neq |P(\emptyset)|=1$ where $|S|$ is the number of elements in a set. We can argue that $\emptyset \neq P(\emptyset)$ because they have different cardinalities.

Foreshadowing: We may continue (ad infinitum) arguing that $A \neq P(A)$ because $|A| \neq |P(A)|$ for $ A \neq \emptyset$.

Taking $A= \{1,2,3 \}$ you should find that $3=|A|\neq |P(A)|=8$. This can be seen here. For any finite set you should be able to find a formula for $|P(A)|$. I leave it to you to try this for all finite sets $A$. Yes! All of them! You can do this for all finite sets! It really shouldn't take you to long to find out the size of of every single finite powerset. You start by making an equivalence class so you don't have to deal with $\{1,2,3\}$ and $\{red,blue,green\}$ as separate cases.

Then look at some small $n$ to derive $|P(\{ 1,2,3 \dots, n \})|$.

Good luck. Have fun.

$\endgroup$
2
$\begingroup$

There is no set $A$, finite or infinite, such that $\mathcal P(A)\subseteq A$; in other words, given any set $A$, we can find a set $R$ such that $R\in\mathcal P(A)$ and $R\notin A$.

If we assume that no set can be an element of itself, this is obvious: $A\in\mathcal P(A)$ but $A\notin A$.

If we allow the possibility of a set being an element of itself, we can still give a (slightly more complicated) proof, due to Bertrand Russell: Let $R=\{x\in A:x\notin x\}$. (This is a direct generalization of the previous case, since $R=A$ if sets never contain themselves as elements.) Clearly $R\in\mathcal P(A)$. We have to show that $R\notin A$, i.e., that $R\ne a$ for any $a\in A$.

Consider any $a\in A$. By definition, $a\in R$ if and only if $a\notin a$. Thus $R\cap\{a\}\ne a\cap\{a\}$, which shows that $R\ne a$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.