$|X|=|X\cup\{a\}|?$

Question

Let $X$ be an infinite set and $a\notin X$. Prove

$$|X|=|X\cup\{a\}|$$

This is so intuitively obvious but upon inspection it appears quite non-obvious. How might one prove this? Do I need the axiom of choice?

Answer 1

Via Cantor-Bernstein we just need an injective function from $X$ to $X\cup \{a\}$ and an injective function from $X\cup\{a\}$ to $X$.

an example of the first is clear, as for the second show $X$ contains a countable subset $A=\{a_1,a_2\dots a_n\dots \}$ and define the injective map $f:X\cup\{a\}\rightarrow X$ as follows:

$f(x)=x$ if $x\not\in A$, $f(a)=a_1, f(a_i)=a_{i+1}$

Answer 2

To answer the second question: yes, the axiom of choice (or rather, a weak form of it) is necessary.

It is consistent with ZF (= set theory without choice) that there is a set $X$ which is

• infinite, but

• cannot be put in bijection with any of its proper subsets. That is, $X$ is Dedekind-finite.

(That is, infinite but Dedekind-finite.) If $X$ is such a set, then for $a\not\in X$ we can't have $\vert X\cup\{a\}\vert=\vert X\vert$ - otherwise we'd have a bijection $f$ from $X$ to $X\cup\{a\}$, which we could turn around and restrict to a bijective map from $X$ to a proper subset of $X$ (specifically, $f^{-1}(X)$).

---

In fact, we can do even better (or worse :P): it is consistent with ZF that there is a set $X$ which is

• infinite, but

• whenever I partition $X$ into two sets ($X=Y\sqcup Z$), one piece or the other is finite!

Such sets are called amorphous, and are quite weird.

---

Here's an interesting further comment:

• On the one hand, even without choice a couple powersets fix everything: if $X$ is infinite, then $P(P(X))$ has a countably infinite subset (equivalently, $P(P(X))$ is Dedekind-infinite).

• On the other hand, sometimes one powerset isn't enough: if $X$ is amorphous, then $P(X)$ will not be amorphous, but also will not have a countably infinite subset.

These are nice exercises!