Description: Two sets are equinumerous iff their cardinal numbers are equal. This important theorem expresses the essential concept behind "cardinality" or "size." This theorem appears as Proposition 10.10 of TakeutiZaring p. 85, Theorem 7P of Enderton p. 197, and Theorem 9 of Suppes p. 242 (among others). The Axiom of Choice is required for its proof. Related theorems are hasheni and the finite-set-only hashen .
This theorem is also known as Hume's Principle. Gottlob Frege's two-volumeGrundgesetze der Arithmetik used his Basic Law V to prove this theorem. Unfortunately Basic Law V caused Frege's system to be inconsistent because it was subject to Russell's paradox (see ru ). Later scholars have found that Frege primarily used Basic Law V to Hume's Principle. If Basic Law V is replaced by Hume's Principle in Frege's system, much of Frege's work is restored.Grundgesetze der Arithmetik, once Basic Law V is replaced, proves "Frege's theorem" (the Peano axioms of arithmetic can be derived in second-order logic from Hume's principle). See https://plato.stanford.edu/entries/frege-theorem . We take a different approach, using first-order logic and ZFC, to prove the Peano axioms of arithmetic.
The theory of cardinality can also be developed without AC by introducing "card" as a primitive notion and stating this theorem as an axiom, as is done with the axiom for cardinal numbers in Suppes p. 111. Finally, if we allow the Axiom of Regularity, we can avoid AC by defining the cardinal number of a set as the set of all sets equinumerous to it and having the least possible rank (see karden ). (Contributed by NM, 22-Oct-2003)
| Ref | Expression | ||
|---|---|---|---|
| Assertion | carden | ⊢ ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) → ( ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ↔ 𝐴 ≈ 𝐵 ) ) |
| Step | Hyp | Ref | Expression |
|---|---|---|---|
| 1 | numth3 | ⊢ ( 𝐴 ∈ 𝐶 → 𝐴 ∈ dom card ) | |
| 2 | 1 | ad2antrr | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → 𝐴 ∈ dom card ) |
| 3 | cardid2 | ⊢ ( 𝐴 ∈ dom card → ( card ‘ 𝐴 ) ≈ 𝐴 ) | |
| 4 | ensym | ⊢ ( ( card ‘ 𝐴 ) ≈ 𝐴 → 𝐴 ≈ ( card ‘ 𝐴 ) ) | |
| 5 | 2 3 4 | 3syl | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → 𝐴 ≈ ( card ‘ 𝐴 ) ) |
| 6 | simpr | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) | |
| 7 | numth3 | ⊢ ( 𝐵 ∈ 𝐷 → 𝐵 ∈ dom card ) | |
| 8 | 7 | ad2antlr | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → 𝐵 ∈ dom card ) |
| 9 | 8 | cardidd | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → ( card ‘ 𝐵 ) ≈ 𝐵 ) |
| 10 | 6 9 | eqbrtrd | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → ( card ‘ 𝐴 ) ≈ 𝐵 ) |
| 11 | entr | ⊢ ( ( 𝐴 ≈ ( card ‘ 𝐴 ) ∧ ( card ‘ 𝐴 ) ≈ 𝐵 ) → 𝐴 ≈ 𝐵 ) | |
| 12 | 5 10 11 | syl2anc | ⊢ ( ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) ∧ ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) → 𝐴 ≈ 𝐵 ) |
| 13 | 12 | ex | ⊢ ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) → ( ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) → 𝐴 ≈ 𝐵 ) ) |
| 14 | carden2b | ⊢ ( 𝐴 ≈ 𝐵 → ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ) | |
| 15 | 13 14 | impbid1 | ⊢ ( ( 𝐴 ∈ 𝐶 ∧ 𝐵 ∈ 𝐷 ) → ( ( card ‘ 𝐴 ) = ( card ‘ 𝐵 ) ↔ 𝐴 ≈ 𝐵 ) ) |