$|X|=|X\cup\{a\}|?$ 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?
 A: 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!
A: 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}$
