TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-05 (gpt-5.6-sol-codex-subscription)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Tarski: the Axiom of Choice is equivalent to the statement that $A \times A \approx A$ for every infinite set $A$ , so extending Hessenberg's theorem from the alephs to arbitrary sets is exactly as strong as choice

Statement

Over ZF the following two statements are equivalent.

(1) The Axiom of Choice (The Axiom of Choice).

(2) Tarski's square law. $A \times A \approx A$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ) for every infinite set $A$ , that is, for every $A$ that is not equinumerous with a natural number (Finite, countably infinite, countable, uncountable).

Hessenberg: $κ \otimes κ = κ$ for every infinite cardinal $κ$ , proved in ZF from the canonical well-order of $κ \times κ$ proves the same equation for every infinite cardinal, without any choice principle. This theorem says that the gap between "every infinite cardinal" and "every infinite set" is precisely the Axiom of Choice: the square law for arbitrary sets is not a mild strengthening of Hessenberg's theorem, it is choice itself.

Facts & Assumptions

Given: ZF. Neither statement is assumed; the theorem asserts their equivalence. For a set $A$ and an ordinal $κ$ write $A ⊔ κ = ({0} \times A) \cup ({1} \times κ)$ , and inside it write $a^{'} = (0, a)$ for $a \in A$ and $ξ^{'} = (1, ξ)$ for $ξ \in κ$ ; these tagged copies are disjoint and $a \mapsto a^{'}$ , $ξ \mapsto ξ^{'}$ are injective.

[L1]

$κ \otimes κ = κ$ , that is $κ \times κ \approx κ$ , for every infinite cardinal $κ$ , in ZF (Hessenberg: $κ \otimes κ = κ$ for every infinite cardinal $κ$ , proved in ZF from the canonical well-order of $κ \times κ$ , Cardinal sum $κ \oplus λ$ , product $κ \otimes λ$ and exponentiation $κ^{λ}$ , and why they are written apart from the ordinal operations).

[L2]

For every set $A$ the Hartogs number $ℵ (A)$ is an ordinal admitting no injection into $A$ (Hartogs: an ordinal that does not inject into a given set), and it is a cardinal (For every set $A$ the Hartogs number $ℵ (A)$ is a cardinal, and for every cardinal $κ$ it is the least cardinal strictly above $κ$ ; this is a theorem of ZF, Cardinal (initial ordinal) and cardinality).

[L3]

Over ZF the Axiom of Choice is equivalent to the well-ordering theorem (Choice, Zorn and well-ordering are equivalent, Well-order and well-ordered set); and assuming the Axiom of Choice every set carries a well-order (The well-ordering theorem).

[L4]

For a well-orderable $X$ : $X \approx ∣ X ∣$ , the value is a cardinal, equinumerous sets receive the same one (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); a cardinal $κ$ is finite when $κ \in ω$ and infinite when $ω \subseteq κ$ , that is $ω \leq κ$ (Cardinal sum $κ \oplus λ$ , product $κ \otimes λ$ and exponentiation $κ^{λ}$ , and why they are written apart from the ordinal operations).

[L5]

$\times$ respects $\approx$ (Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals $α, β$ the sets $α ⊔ β$ and $α \times β$ carry explicit well-orders, so their cardinalities exist in ZF); and for cardinals $κ \leq λ$ iff $κ ⪯ λ$ (Commutativity, associativity, distributivity and monotonicity of $\oplus$ and $\otimes$ , the unit laws, the two exponent laws, and $κ \leq λ$ if and only if $κ$ injects into $λ$ ).

[L6]

Ordinals: elements of ordinals are ordinals, trichotomy holds, $α \subseteq β$ iff $α \in β$ or $α = β$ , and every nonempty set of ordinals has an $\in$ -least element (Basic closure properties of ordinals, Trichotomy and well-ordering of the ordinals, Ordinal (von Neumann)).

[L7]

There is no injection $n \cup {n} \to n$ for $n \in ω$ (claim 1 of The pigeonhole principle on $N$ ); a set is finite when it is equinumerous with a natural number (Finite, countably infinite, countable, uncountable, The cardinality $∣ A ∣$ of a finite set).

[L8]

Induction on $N$ (The principle of mathematical induction); a composition of injections is an injection and the inverse of a bijection is a bijection (Injection, surjection, bijection).

Proof

technique · direct

1.1

If $A$ is infinite then every $n \in ω$ injects into $A$ : by induction along [L8] on the statement "there exists an injection $n \to A$ ", the empty function serving at $n = 0$ , and an injection $f : n \to A$ never being surjective, since $A \approx n$ would make $A$ finite, so that some $a \in A ∖ f [n]$ exists and $f \cup {(n, a)}$ injects $n \cup {n}$ into $A$ ; the statement carried through the induction is an existence statement, so no family of injections is selected.

L7L8

1.2

Assume (1) and let $A$ be infinite; then $A$ is well-orderable by [L3], $κ = ∣ A ∣$ is a cardinal with $A \approx κ$ by [L4], and $κ$ is infinite, since $κ \in ω$ would make $A$ finite; so $A \times A \approx κ \times κ \approx κ \approx A$ by [L5], [L1] and [L4], which is (2).

L1L3L4L5L7

2.1

Assume (2) from here on, let $A$ be infinite and put $κ = ℵ (A)$ ; then $κ$ is a cardinal by [L2], and $ω \leq κ$ , because $κ \in ω$ would make $κ$ a natural number, which injects into $A$ by step 1.1 and contradicts [L2]; so $κ$ is an infinite cardinal.

step 1.1L2L4L6

3.1

The set $B = A ⊔ κ$ is infinite: $ξ \mapsto ξ^{'}$ injects $κ$ , hence also $ω \subseteq κ$ , into $B$ by step 2.1, so $B \approx n$ for some $n \in ω$ would inject $n \cup {n} \subseteq ω$ into $n$ , which [L7] forbids; therefore (2) applies to $B$ and we may fix a bijection $f : B \times B \to B$ .

step 2.1L6L7L8

4.1

Then $A$ is well-orderable. Exactly one of two situations holds. If some $a \in A$ has $f (a^{'}, ξ^{'}) \in {b^{'} : b \in A}$ for every $ξ \in κ$ , then sending $ξ$ to the unique $b \in A$ with $f (a^{'}, ξ^{'}) = b^{'}$ is an injection $κ \to A$ , which [L2] forbids. Otherwise every $a \in A$ admits some $ξ \in κ$ with $f (a^{'}, ξ^{'}) \in {η^{'} : η \in κ}$ ; let $ξ_{a}$ be the $\in$ -least such $ξ$ , which is determined and not chosen by [L6], and let $η_{a} \in κ$ be given by $f (a^{'}, ξ_{a}^{'}) = η_{a}^{'}$ . The map $a \mapsto (ξ_{a}, η_{a})$ is then an injection $A \to κ \times κ$ , since $(ξ_{a}, η_{a}) = (ξ_{b}, η_{b})$ gives $f (a^{'}, ξ_{a}^{'}) = f (b^{'}, ξ_{b}^{'})$ and hence $a^{'} = b^{'}$ by injectivity of $f$ ; composing with a bijection $κ \times κ \to κ$ from step 2.1 and [L1] injects $A$ into $κ$ , and transporting the ordinal well-order of $κ$ back along that injection well-orders $A$ , a nonempty subset of $A$ receiving the preimage of the $\in$ -least element of its image.

step 2.1step 3.1L1L2L6L8

5.1

A finite $A$ is well-orderable outright, being equinumerous with a natural number by [L7], so under (2) every set can be well ordered by step 4.1, and (1) follows by [L3]; with step 1.2 the two statements are equivalent over ZF.

step 1.2step 4.1L3L7∎

Remarks

Where a choice would have crept in, and why it does not. The tempting move in step 4.1 is "for each $a \in A$ choose some $ξ$ with $f (a^{'}, ξ^{'}) \in κ$ ", which is a genuine use of choice over the index set $A$ . It is avoided because $κ$ is an ordinal: the set of admissible $ξ$ is a nonempty set of ordinals and has a least element, so $ξ_{a}$ is a definable function of $a$ . That is the same device that keeps Hartogs: an ordinal that does not inject into a given set choice free, and it is the reason the Hartogs number rather than some arbitrary large set is the right object to adjoin to $A$ .

Why $A$ is enlarged to $A ⊔ ℵ (A)$ . The hypothesis (2) is applied to $B$ , not to $A$ , because the argument needs the bijection $f$ to be able to send a pair with one coordinate in $A$ into the ordinal part. If $κ$ were not present inside $B$ , the second situation of step 4.1 could not arise and nothing would be gained.

What the equivalence does and does not settle. It gives, over ZF, an exact measure of the square law: it is neither weaker nor stronger than the Axiom of Choice. It does not say whether ZF alone refutes the square law, and this page asserts nothing of that kind. The choice ledger at the end of the page records which results here are theorems of ZF and which carry a choice hypothesis.

Depends on

Used by

What each result on this page costs in choice, and where the continuum escapes what ZFC can decide Remark

Dependency tree · two levels

61 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

A. Tarski, Sur quelques théorèmes qui équivalent à l'axiome du choix (1924) (standard reference, not scraped)
Tarski's theorem about choice (Wikipedia) (standard reference, not scraped)
Hartogs number (Wikipedia) (standard reference, not scraped)

Tarski: the Axiom of Choice is equivalent to the statement that A×A≈AA×A≈A for every infinite set AA, so extending Hessenberg's theorem from the alephs to arbitrary sets is exactly as strong as choice