I know that $\emptyset$ and $\{\emptyset\}$ contain all their proper subsets. I am trying to show that no other set satisfies this property, i.e. there is no set $x$ such that $\forall y \subsetneq x (y \in x)$. Is this true? If so, how can I prove this?
$\begingroup$
$\endgroup$
1
-
7$\begingroup$ Suppose first that $X$ is a finite set and let $N\in\mathbb{N}_0$ denote the cardinality of $X$. Then $X$ has exactly $2^N$ subsets; hence $2^{N}-1$ proper subsets. However, $X$ has only $N$ elements. Thus, if every proper subset $y$ of $X$ is also an element of $x$, then we must have $2^{N}-1\le N$. This is only possible if $N=0$ or $N=1$. To generalize the argument to infinite sets, I would try modifying the argument of Cantor's Theorem. $\endgroup$– QuokaJun 8 at 0:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
No cardinal arithmetic is needed, just the most basic notions and axioms of set theory.
Let $S$ be a set such that every proper subset of $S$ is an element of $S$, and assume for a contradiction that $S\ne\varnothing$ and $S\ne\{\varnothing\}$.
Then $\varnothing$ is a proper subset of $S$, so $\varnothing\in S$; likewise $\{\varnothing\}$ is a proper subset of $S$, so $\{\varnothing\}\in S$.
Let $R=\{x\in S:x\notin x\text{ and }x\ne\varnothing\}$.
Thus $R\in R\iff R\in S\text{ and }R\notin R\text{ and }R\ne\varnothing$.
Now $R\subseteq S$, and $\varnothing\in S\setminus R$, so $R$ is a proper subset of $S$, so $R\in S$. Also $R\ne\varnothing$ since $\{\varnothing\}\in R$. Thus we have $R\in R\iff R\notin R$, a contradiction.
P.S. The proof can be simplified even more if we assume that no set can be an element of itself. In that case, if $S$ is any set other than $\varnothing$ and $\{\varnothing\}$, then either $\varnothing$ or $S\setminus\{\varnothing\}$ is a proper subset of $S$ which is not an element of $S$.
First, since $\varnothing$ is a proper subset of $S$, we may assume that $\varnothing\in S$, or else we're done. Then $S\setminus\{\varnothing\}$ is a proper subset of $S$, so we may assume that $S\setminus\{\varnothing\}\in S$. Since $S\setminus\{\varnothing\}\notin S\setminus\{\varnothing\}$, it follows that $S\setminus\{\varnothing\}=\varnothing$, that is, $S\subseteq\{\varnothing\}$; but this contradicts our assumption that $S\ne\varnothing$ and $S\ne\{\varnothing\}$.
$\begingroup$
$\endgroup$
Your hypothesis is true! If there were a set $X$ such that $\forall Y \subset X, Y \in X$, then it is certainly true that there would be an injection between proper subsets of $X$ and elements of X. Each proper subset $Y$ could simply map to the element $Y$.
Now we are ready to prove your hypothesis. The power set, which is the set of all subsets, of a finite set $X$ with cardinality $k$ has $2^k$ elements. The set of all proper subsets clearly has $2^k-1$ elements. Now one can see by a simple counting argument that, other than for $k=0$ and $k=1$, there can be no injection from a set with cardinality $2^k-1$ to a set with cardinality $k$.
For $k=0$ there is only one set with that cardinality, $\emptyset$. For $k=1$ there are of course many such sets, but we need the set whose proper subsets (which for cardinality $1$ is only $\emptyset$) are its elements. So it must be precisely $\{\emptyset\}$.
Thus we have proved your hypothesis for finite sets.
We, of course, failed to consider the infinite case. You can prove that along similar lines, using Cantor's diagonal argument or similar. The key is that there is no injection from a power set to the set itself, for both finite and infinite sets.
There is one further technicality. We are not concerned with the full power set, but the power set with one element missing. But for an infinite set, this will not change its cardinality, so it is irrelevant here.
