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.
Commutativity, associativity, distributivity and monotonicity of and , the unit laws, the two exponent laws, and if and only if injects into
Statement
Let , , be cardinals (Cardinal (initial ordinal) and cardinality) and let , , be as in Cardinal sum , product and exponentiation , and why they are written apart from the ordinal operations. Clauses (a) to (e) are theorems of ZF; the clauses naming an exponential hold whenever those exponentials are defined, in particular under the Axiom of Choice (The Axiom of Choice).
(a) Comparison. if and only if , that is, if and only if there is an injection (Equinumerous sets, and ). More generally, if and are well-orderable and then .
(b) Commutativity and associativity. , , and .
(c) Distributivity. .
(d) Units. , , , and , , , together with for . The four exponential unit laws need no choice principle, because the function sets they count are empty, a singleton, or a copy of .
(e) Monotonicity. If then and ; and , and provided .
(f) The two exponent laws. and .
Each clause is an equality or an inequality of cardinals, not merely of sizes: each side is an ordinal, and the claim is that the two ordinals are the same.
Facts & Assumptions
Given: Cardinals , in ZF; the Axiom of Choice is assumed only where an exponential is written and is not one of the four unit cases.
For a well-orderable , is the least ordinal equinumerous with , it satisfies , it is a cardinal, equinumerous sets receive the same one, and exactly when is a cardinal (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).
, and respect in both arguments (Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals the sets and carry explicit well-orders, so their cardinalities exist in ZF, claim (a)).
, , , and these may be computed from any equinumerous representatives (Cardinal sum , product and exponentiation , and why they are written apart from the ordinal operations).
If and then (The Schröder-Bernstein theorem).
Ordinals are comparable, exactly one of , , holds, if and only if or , and (Trichotomy and well-ordering of the ordinals, Basic closure properties of ordinals).
A composition of bijections is a bijection, a map with a two-sided inverse is a bijection, and a subset inclusion is an injection (Injection, surjection, bijection, Equinumerous sets, and ).
An ordinal is a cardinal when no has (Cardinal (initial ordinal) and cardinality).
Assuming the Axiom of Choice every set is well-orderable, so every exponential written below is defined (The Axiom of Choice, The well-ordering theorem).
Proof
First half of (a): if then by [L5] and the inclusion is an injection, so ; conversely, if and then gives , so by [L4], contradicting [L7] since ; trichotomy then leaves .
The maps , and are their own inverses up to relabelling, hence bijections and .
The maps , , and have evident two-sided inverses, hence are bijections and .
The map , is a bijection .
Unit computations: ; ; ; has the empty function as its only element, so ; by ; has the constant function as its only element, so ; and for there is no function , so .
Two bijections of function spaces: is a bijection , with inverse gluing a pair back into one function; and is a bijection , with inverse .
Monotonicity injections, for : and and are inclusions; and for , extending a function by the constant value on is an injection , injective because restricting back to recovers the original function.
Second half of (a): if with both well-orderable then by [L1], so by [L6], and step 1.1 applied to these two cardinals gives .
Claims (b) and (c): by [L1] the sets and are equinumerous, and likewise for , so [L2] lets every outer operation be computed on the untagged representatives; steps 1.2, 1.3 and 1.4 then equate the two underlying sets up to , and [L1] gives the same least ordinal on both sides.
Claim (d) is step 1.5 read through [L3] and [L1]: each computed set is equinumerous with , with , or with , and its cardinality is the corresponding cardinal by [L1].
Claim (f): and by [L1], so [L2] and step 1.6 give and ; taking cardinalities through [L1] and [L3] yields and .
Claim (e): each map of step 1.7 is an injection between the underlying sets, so step 2.1 applied to it gives the corresponding inequality of cardinalities, which by [L3] is the stated inequality of cardinals.
All six claims are established, in ZF except for the exponentials of clauses (e) and (f), which are read under the Axiom of Choice by [L8].
Remarks
Why clause (a) is the workhorse. Every other clause is proved by writing down a bijection or an injection between two concrete sets; clause (a) is what converts such a map into a statement about the ordinals and , and it is the only clause whose proof uses The Schröder-Bernstein theorem. Note the direction of the work there: is the trivial half, and the converse is where being a cardinal rather than an arbitrary ordinal is spent.
No cancellation, and no strict monotonicity. Clause (e) gives and not , and that is not a weakness of the proof. The false statements FALSE: implies and FALSE: implies , on this page, show that does not force and that does not force ; both failures are already visible at .
The exponent laws hold at every value, including the degenerate ones. With the first law reads , that is , and with and the second reads , both correct from clause (d). Nothing in the proof of clause (f) case-splits on whether an exponent is zero, because the bijections of step 1.6 are between sets of functions and remain bijections when one of the domains is empty.
Depends on
Cardinal sum , product and exponentiation , and why they are written apart from the ordinal operations
Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals the sets and carry explicit well-orders, so their cardinalities exist 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
Equinumerous sets, and
Injection, surjection, bijection
Cardinal (initial ordinal) and cardinality
Trichotomy and well-ordering of the ordinals
Basic closure properties of ordinals
The Schröder-Bernstein theorem
The Axiom of Choice
The well-ordering theorem