$2^\kappa-\kappa=2^\kappa$ for infinite $\kappa$ without the AC

Question

Without using the AC, show that if $\kappa \geq \aleph_0$ then $2^{\kappa}-\kappa=2^{\kappa}$. That is to say, for such $\kappa$ there is a unique cardinal $\mu$ such that $\kappa+\mu=2^{\kappa}$, and this $\mu$ equals $2^{\kappa}$.

In Rubin & Rubin, "Equivalents of the Axiom of Choice", 2nd edition, 1985, this is mentioned as a well-known property of cardinals (cf. Theorem 0.14.f in the book), but sadly they do not provide a proof.

Found a proof for the case $\kappa=2\kappa$.

Lemma: for any cardinals $\kappa,\mu,\lambda$, if $\kappa+\mu=\lambda=\lambda^{2}$ then either there is a surjection of $\kappa$ onto $\lambda$, or we have $\mu=\lambda$.

Proof: if $f:\kappa\sqcup\mu\to\lambda^{2}$ is a bijection (with $\sqcup$ denoting disjoint union), let $g:\kappa\to\lambda$ be the map $\pi_1\circ (f\upharpoonright\kappa)$, where $\pi_{1}:\lambda^{2}\to\lambda$ is the projection on the first factor (i.e. $\pi_{1}(x,y)=x$ for $x,y\in\lambda$). If $g$ is surjective, we are done. If not, $\exists{z\in\lambda}$ such that $(\{z\}\times\lambda)\cap f[\kappa]=\varnothing$. But then we have $\{z\}\times\lambda\subseteq f[\mu]$, since f is a surjection, and so $\lambda\leq\mu$; since $\mu\leq\lambda$ also holds, we find $\mu=\lambda$, q.e.d.

Now if $\kappa+\mu=2^{\kappa}$, for a $\kappa$ with $\kappa=2\kappa$, apply the Lemma with $\lambda=2^{\kappa}$; one has $\lambda=\lambda^{2}$ in view of $\kappa=2\kappa$, and a surjection of $\kappa$ onto $\lambda=2^{\kappa}$ cannot exist (Cantor). It follows that $\mu=2^{\kappa}$.

Answer 1

The most difficult part would be to show that $2^\kappa \leq \mu$ if $\kappa + \mu = 2^\kappa =2 \times 2^\kappa$. It can be easily reduced to the following lemma:

Lemma Let $X$ be a set and $f \colon X \rightarrowtail 2 \times \mathcal{P}(X)$ be an injection, where $2 = \{0, 1\}$. Then there exists an injection $g \colon \mathcal{P}(X) \rightarrowtail 2 \times \mathcal{P}(X)$ such that $\mathop{\mathrm{Im}}f$ and $\mathop{\mathrm{Im}}g$ are disjoint.

(Injectivity of $f$ is not necessary)

Proof Let $\pi_2 \colon 2 \times \mathcal{P}(X) \to \mathcal{P}(X)$ be the right projection.

Define $g$ by $$ g(A) = \begin{cases} (1,A) & \text{if}\; (1, A) \notin \mathop{\mathrm{Im}} f \\ (0,\{ x \in X : x \notin \pi_2(f(x)) \;\text{xor}\; f(x)=(1,A) \}) & \text{if}\; (1, A) \in \mathop{\mathrm{Im}} f. \end{cases} $$

Here $P \;\text{xor}\; Q$ means that $P$ but not $Q$, or $Q$ but not $P$.

(The intuition here is that we basically want to define $g(A) = (1, A)$. When it's impossible, then we want somewhere in $(0, -)$ to escape to. The existence of such a place is guaranteed by the diagonal argument, but we have to choose a different place for each collision. Xor-ing with $f(x)=(1, A)$ is the trick here: it embeds information about $y$ such that $f(y)=(1, A)$, while not disturbing the diagonal argument.)

$\mathop{\mathrm{Im}}f$ and $\mathop{\mathrm{Im}}g$ are disjoint. To show this, assume that $f(y) = g(A)$. If $(1, A) \notin \mathop{\mathrm{Im}} f$, then $f(y) = g(A) = (1, A)$. It contradicts with $(1, A) \notin \mathop{\mathrm{Im}} f$. If $(1, A) \in \mathop{\mathrm{Im}} f$, then $f(y) = (0, \mathop{-}) \neq (1, A)$. Thus \begin{align*} y \in \pi_2(f(y)) & \iff y \in \pi_2(g(A)) \\ & \iff y \in \pi_2((0,\{ x \in X : x \notin \pi_2(f(x)) \;\text{xor}\; f(x)=(1,A) \})) \\ & \iff y \in \{ x \in X : x \notin \pi_2(f(x)) \;\text{xor}\; f(x)=(1,A) \} \\ & \iff y \notin \pi_2(f(y)) \;\text{xor}\; f(y)=(1,A) \\ & \iff y \notin \pi_2(f(y)) \end{align*} leads to contradiction. Therefore we never have $f(y) = g(A)$.

$g$ is injective. To show this, assume that $g(A) = g(A')$. Then either $(1, A), (1, A') \notin \mathrm{\mathop{Im}} f$ or $(1, A), (1, A') \in \mathrm{\mathop{Im}} f$. In the former case, we have $(1, A) = g(A) = g(A') = (1, A')$ and thus $A = A'$. In the latter case, take $y$ such that $f(y) = (1, A)$. Expanding $y \in \pi_2(g(A)) \iff y \in \pi_2(g(A'))$, we obtain $$ y \notin \pi_2(f(y)) \;\text{xor}\; f(y) = (1, A) \iff y \notin \pi_2(f(y)) \;\text{xor}\; f(y) = (1, A')$$ and, since $\text{xor}$ is cancellative, we have $$ f(y) = (1, A) \iff f(y) = (1, A'). $$ Since the left hand side is true, the right hand side is. Since $(1, A) = f(y) = (1, A')$, we have $A = A'$.

□

Thanks to alg_d (the author of the famous Japanese website about AC) for letting me know this interesting problem.

Answer 2

A proof of this theorem

THEOREM $1$. We are able to prove without the aid of the axiom of choice that if $\mathfrak m$ is a cardinal number $\ge\aleph_0,$ then $$2^\mathfrak m-\mathfrak m=2^\mathfrak m.$$

takes up most of pp. 172–173 in W. Sierpiński's book Cardinal and Ordinal Numbers, Second Edition Revised, 1963. Sierpiński uses the following lemma:

LEMMA. If $\mathfrak m,\mathfrak p,\mathfrak s$ are cardinal numbers such that $2^\mathfrak m=\mathfrak m+\mathfrak p$ and $\mathfrak m=\mathfrak m+\mathfrak s,$ then $\mathfrak p\ge2^\mathfrak s.$

According to Sierpiński the theorem is due to A. Tarski, who stated it without proof in 1926; a proof was published by Sierpiński in: W. Sierpiński, Démonstration de l'égalité $2^\mathfrak m-\mathfrak m=2^\mathfrak m$ pour les nombres cardinaux transfinis, Fund. Math. 34 (1947), 113—118.

Answer 3

You can prove it this way : $2^\kappa \leq 2^\kappa + \kappa \leq 2^\kappa + 2^\kappa \leq 2^\kappa \times 2 \leq 2^{\kappa+1}\leq 2^\kappa$

The first inequality comes from the natural injection, The second as well,where there is an injection $\kappa \to 2^\kappa$, sending $x\to \{x\}$ The third one comes from identifying the disjoint union of $A$ and $B$ as $A\times\{0\}\cup B\times\{1\}$ The fourth one is the natural injection, And the last one is simply that, $\kappa$ being infinite, $\kappa +1 \leq \kappa$.

By Cantor-Bernstein's theorem, all these inequalities of cardinals (i.e. injections) can be turned into equalities of cardinals, that is, bijections.

Therefore $2^\kappa +\kappa \sim 2^\kappa$

Now if you take $A$ to be a subset of $2^\kappa$ of cardinality $\kappa$, then you can use this bijection to produce a bijection $2^\kappa \setminus A\to 2^\kappa$.

EDIT : It seems Noah Schweber was quicker

Second edit: The last sentence of this answer is there to show the uniqueness of $\mu$: assume $\kappa + \mu = 2^\kappa$. Then the image of $\kappa$ under a bijection $\kappa + \mu \to 2^\kappa$ is a subset $A\subset 2^\kappa$ of cardinality $\kappa$. But $2^\kappa\setminus A$ is the image of $\mu$ o has cardinality $\mu$. But according to my last sentence it also has cardinality $2^\kappa$, which proves that $2^\kappa \sim \mu$. I'm adding this to my answer because Matthé Van der Lee commented on Noah's answer saying that the uniqueness of $\mu$ hadn't been established.

Answer 4

By contradiction: $2^\kappa-\kappa=[\kappa,2^\kappa)$. If $|[\kappa,2^\kappa)|<2^\kappa$ then, because $2^\kappa=[0,2^\kappa)=[0,\kappa)\cup[\kappa,2^\kappa)$, we must have $2^\kappa=|[0,\kappa)|=|\kappa|=\kappa$.