Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals $\alpha ,\beta$ the sets $\alpha \bigsqcup \beta$ and $\alpha \times \beta$ carry explicit well-orders, so their cardinalities exist in ZF

For sets $A$ and $B$ write

$A\bigsqcup B:=(\{0\}\times A)\cup (\{1\}\times B),{}^{B}A:=\{h:h\text{ is a function }B\to A\},$

so $A\bigsqcup B$ is the disjoint union, made disjoint by tagging, and ${}^{B}A$ is the set of all functions from $B$ to $A$. Work in ZF. Then:

(a) Representative independence. If $A\approx A^{\mathrm{\prime }}$ and $B\approx B^{\mathrm{\prime }}$ (Equinumerous sets, $A\approx B$ and $A⪯B$) then

$A\bigsqcup B\approx A^{\mathrm{\prime }}\bigsqcup B^{\mathrm{\prime }},A\times B\approx A^{\mathrm{\prime }}\times B^{\mathrm{\prime }},{}^{B}A\approx {}^{B^{\mathrm{\prime }}}{A}^{\mathrm{\prime }}\mathrm{.}$

(b) Power sets. If $A\approx B$ then $\mathcal{P}(A)\approx \mathcal{P}(B)$.

(c) Two operations are choice-free. For ordinals $\alpha$ and $\beta$ (Ordinal (von Neumann)) the sets $\alpha \bigsqcup \beta$ and $\alpha \times \beta$ carry explicitly defined well-orders (Well-order and well-ordered set), so each is equinumerous with an ordinal and each has a cardinality $\mid \alpha \bigsqcup \beta \mid$, $\mid \alpha \times \beta \mid$ in ZF (A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used).

(d) The third is not. Nothing here well-orders ${}^{\beta }\alpha$, and no argument on this page does. Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem) and ${}^{\beta }\alpha$ has a cardinality like any other set; that is where cardinal exponentiation gets its hypothesis.

Why the disjoint union is tagged. $A\cup B$ is not an invariant of $A\approx A^{\mathrm{\prime }}$ and $B\approx B^{\mathrm{\prime }}$: taking $A=A^{\mathrm{\prime }}=B=\{0\}$ and $B^{\mathrm{\prime }}=\{1\}$ gives $A\cup B=\{0\}$ and $A^{\mathrm{\prime }}\cup B^{\mathrm{\prime }}=\{0,1\}$, which are not equinumerous. Tagging with $0$ and $1$ makes the two blocks disjoint whatever the sets were, and claim (a) is then true as stated. This is why the operation defined on this page is $\bigsqcup$ and never $\cup$.

The lexicographic order is not the order used for Hessenberg's theorem. Step 1.7 well-orders $\alpha \times \beta$, which is everything claim (c) asks for. Its order type is in general much larger than $\alpha$: the lexicographic order on $\omega \times \omega$ has order type $\omega \cdot \omega$. The proof that $\mid \kappa \times \kappa \mid =\kappa$ for infinite $\kappa$ uses a different, cleverer well-order and is Hessenberg: $\kappa \otimes \kappa =\kappa$ for every infinite cardinal $\kappa$, proved in ZF from the canonical well-order of $\kappa \times \kappa$.

Where the asymmetry between $\otimes$ and exponentiation comes from. A product of two well-ordered sets is well-ordered by an order written down from the two given ones. A set of functions between well-ordered sets has no such canonical order: the obvious candidates need a choice at each argument. That is not a defect of this proof but the reason general cardinal exponentiation is stated with the Axiom of Choice on this page; the exponential unit laws (Commutativity, associativity, distributivity and monotonicity of $\oplus$ and $\otimes$, the unit laws, the two exponent laws, and $\kappa \le \lambda$ if and only if $\kappa$ injects into $\lambda$) and the finite case (Every natural number and $\omega$ are cardinals, every infinite cardinal is a limit ordinal, and on the natural numbers the cardinal operations are the published finite counting operations, with $\mid A\mid$ in the finite sense equal to $\mid A\mid$ in the cardinal sense) are choice-free, because the function sets they count carry a canonical well-order.