Does $2a = 2b$ imply $a = b$ in ZF?

Question

For $a$ and $b$ cardinals, does the statement $2a = 2b \rightarrow a = b$ hold in ZF? Assuming it is false, what are the weakest choice principles that can imply it? (I presume it makes no substantive difference if I said $3a = 3b$ instead)

Answer 1

Yes, it is (I have on good hearsay, not knowing the proof) a theorem of ZF that, if $a,b$ are cardinals and $n$ a nonzero finite cardinal, then $na=nb\implies a=b$. See "Division by three" by Doyle and Conway for a brief discussion of the complicated history (involving Bernstein, Sierpiński, Lindenbaum, and Tarski) and a proof for the case $n=3$. Below is a proof for the comparatively trivial case $n=2$ which I figured out for myself; no doubt it's similar to the published proofs, which I was too lazy to read. (A slight modification, left to the reader, shows that $2a\le2b\implies a\le b$. Of course it follows that $2a\lt2b\implies a\lt b$.)

Suppose $2a=2b$. Imagine a set of $a$ red arrows and a set of $b$ blue arrows. The $a$ red arrows have $a$ heads and $a$ tails, so the set of red arrowheads and "arrowtails" has cardinality $2a$, and is in bijection with the set of blue arrowheads and arrowtails, which has cardinality $2b$. From that bijection we get a digraph in which each arc is colored red or blue, there are $a$ red arcs and $b$ blue arcs, and each node is incident with exactly two arcs, one of each color. We have to establish a choice-free bijection between the red arcs and the blue arcs, thereby proving that $a=b$.

Each connected component of our digraph is a cycle (of even length, since colors alternate) or a path. (The terms connected, cycle, and path are used here in the weak or undirected sense.) Initially, any component which is a path must be a two-way infinite path, since each node has degree $2$; it may turn into a ray or a finite path as the following procedure is carried out.

Step 1. Pair off and remove any arcs that meet head to head.

Step 2. Close up the gaps created by Step 1. Now each node is incident with at most two arcs, which (if there are two) must be of different colors.

Step 3. Reverse all the red arcs.

Step 4. Pair off and remove any arcs that meet head to head.

Step 5. Close up the gaps created by Step 4.

Step 6. Reverse all the blue arcs.

Step 7. Go to Step 1.

Typically, these steps will be iterated an infinite number of times. In the case of a finite component $C$, all arcs in $C$ will be paired off after a finite number of iterations, thus establishing a bijection between the red and blue arcs of $C$.

In the case of an infinite component $P$, all arcs in $P$ will eventually be paired off, with at most one exception. (If more than one arc remained unpaired, consider two such "lonely" arcs at minimal distance, with no other lonely arcs between them. After a finite number of iterations those two arcs will be adjacent, all intervening arcs having been removed; and shortly thereafter those two arcs will meet head to head and be removed, a contradiction.) If all arcs of $P$ have been paired off, we already have a bijection between the red and blue arcs of $P$. Otherwise there is a unique lonely arc, which we use as a base point to define a bijection between the arcs of $P$ and the integers, adjacent arcs corresonding to consecutive integers, and use that to define a bijection between the red and blue arcs of $P$ in a choice-free way.