$\mathcal P(X) \cong \mathcal P(X)$ without singletons if the set $X$ is infinite

Question

I did not find this question here though I'm sure that it has already been asked. Sorry for that.

I am looking for an elementary way to show the following: Let $X$ be an infinite set, then there is a bijection \begin{equation} \mathcal P(X) \longrightarrow \{Y \in \mathcal P(X) \mid \#Y \neq 1 \}, \end{equation} i.e. the power set $\mathcal P(X)$ does not change its cardinality when subtracting a set of cardinality $\#X$, the singletons in this case.

Answer 1

Inspired by Mindlack's answer... Take an infinite injective sequence $(x_n)$ from $X$. (Need AoC for that.)

Map every set $A\subseteq X$ as follows:

• $A$ empty or infinite: map to itself
• $A$ finite: add one element from the sequence $(x_n)$; more precisely, add the element with the index $1$ higher than the index of all elements in $(x_n)$ that belong to $A$. (Add $x_1$ if none do.)

For example, if $A$ is a finite set that happens to contain $x_7, x_{12}, x_{19}$, then $A$ is mapped to $A\cup\{x_{20}\}$.

This should provide for an injection of ${\cal P}(X)$ into the set of non-singletons in ${\cal P}(X)$. The opposite injection is trivial, and then the equivalence follows from Cantor-Bernstein theorem.

Answer 2

Take an infinite injective sequence $x_n \in X$, $n \geq 1$.

Define $i_n : X \rightarrow X \backslash \{x_1, \ldots, x_{n-1}\}$ by having $i_n(x_k)=x_{k+n-1}$ and $i_n(y)=y$ if $y$ is not in the sequence.

Define $j_n: X \rightarrow \{F \subset X,\, |F|=n\}$ by $j_n(z)=\{x_1, \ldots, x_{n-1},i_n(z)\}$.

Note that each $j_n$ is well-defined and injective; that $j_1$ is surjective; that the images of the $j_n$ are pairwise disjoint.

Now define the bijection $f: \mathcal{P}(X) \rightarrow \{F \subset X,\, |F| \neq 1\}$ as follows: if $F \subset X$ is not some $j_k(y)$ then $f(F)=F$, else, if $F=j_k(y)$, then $(k,y)$ is well-defined and we set $f(F)=j_{k+1}(y)$.

Answer 3

Thanks for your answers.

By the way, the result follows also from the fact that for infinite sets $X$ we have \begin{equation} |X \times X| = |X| \end{equation} which is a consequence of the well-order theorem.

In fact, given $x\in X$ fixed, a (somewhat heavily built) injection $f: \mathcal P(X) \rightarrow \mathcal P(X) \setminus X \times \mathcal P(X) \setminus X$ is provided by $f(A) = (A,X)$, if $|A|\neq 1$, $f(\{x\}) = \emptyset$, $f(A)=(X,A\cup\{x\})$ if $A$ has exactly one element which is not $x$.

Thus: \begin{equation} |\mathcal P(X) \setminus X| \le |\mathcal P(X)| \le |\mathcal P(X) \setminus X \times \mathcal P(X) \setminus X| = |\mathcal P(X) \setminus X| \end{equation} whence equality. Herein we implicitly make use of the well-order theorem.

Of course, in view of the question pos(t)ed, StB's answer is the better one.