Misplaced Pages

In set theory, Kőnig's theorem states that if the axiom of choice holds, I is a set, ${\displaystyle \kappa _{i}}$ and ${\displaystyle \lambda _{i}}$ are cardinal numbers for every i in I, and ${\displaystyle \kappa _{i}<\lambda _{i}}$ for every i in I, then

$${\displaystyle \sum _{i\in I}\kappa _{i}<\prod _{i\in I}\lambda _{i}.}$$

The sum here is the cardinality of the disjoint union of the sets m_i, and the product is the cardinality of the Cartesian product. However, without the use of the axiom of choice, the sum and the product cannot be defined as cardinal numbers, and the meaning of the inequality sign would need to be clarified.

Kőnig's theorem was introduced by Kőnig (1904) in the slightly weaker form that the sum of a strictly increasing sequence of nonzero cardinal numbers is less than their product.

Details

The precise statement of the result: if I is a set, A_i and B_i are sets for every i in I, and ${\displaystyle A_{i}<B_{i}}$ for every i in I, then

$${\displaystyle \sum _{i\in I}A_{i}<\prod _{i\in I}B_{i},}$$

where < means strictly less than in cardinality, i.e. there is an injective function from A_i to B_i, but not one going the other way. The union involved need not be disjoint (a non-disjoint union can't be any bigger than the disjoint version, also assuming the axiom of choice). In this formulation, Kőnig's theorem is equivalent to the axiom of choice.

(Of course, Kőnig's theorem is trivial if the cardinal numbers m_i and n_i are finite and the index set I is finite. If I is empty, then the left sum is the empty sum and therefore 0, while the right product is the empty product and therefore 1.)

Kőnig's theorem is remarkable because of the strict inequality in the conclusion. There are many easy rules for the arithmetic of infinite sums and products of cardinals in which one can only conclude a weak inequality ≤, for example: if ${\displaystyle m_{i}<n_{i}}$ for all i in I, then one can only conclude

$${\displaystyle \sum _{i\in I}m_{i}\leq \sum _{i\in I}n_{i},}$$

since, for example, setting ${\displaystyle m_{i}=1}$ and ${\displaystyle n_{i}=2}$, where the index set I is the natural numbers, yields the sum ${\displaystyle \aleph _{0}}$ for both sides, and we have an equality.

Corollaries of Kőnig's theorem

• If ${\displaystyle \kappa }$ is a cardinal, then ${\displaystyle \kappa <2^{\kappa }}$.

If we take ${\displaystyle m_{i}=1}$, and ${\displaystyle n_{i}=2}$ for each ${\displaystyle i}$ in ${\displaystyle \kappa }$, then the left side of the above inequality is just ${\displaystyle \kappa }$, while the right side is ${\displaystyle 2^{\kappa }}$, the cardinality of functions from ${\displaystyle \kappa }$ to ${\displaystyle \{0,1\}}$, that is, the cardinality of the power set of ${\displaystyle \kappa }$. Thus, Kőnig's theorem gives us an alternate proof of Cantor's theorem. (Historically of course Cantor's theorem was proved much earlier.)

Axiom of choice

One way of stating the axiom of choice is "an arbitrary Cartesian product of non-empty sets is non-empty". Let B_i be a non-empty set for each i in I. Let A_i = {} for each i in I. Thus by Kőnig's theorem, we have:

• If ${\displaystyle \forall i\in I(\{\}<B_{i})}$, then ${\displaystyle \{\}<\prod _{i\in I}B_{i}}$.

That is, the Cartesian product of the given non-empty sets B_i has a larger cardinality than the sum of empty sets. Thus it is non-empty, which is just what the axiom of choice states. Since the axiom of choice follows from Kőnig's theorem, we will use the axiom of choice freely and implicitly when discussing consequences of the theorem.

Kőnig's theorem and cofinality

Kőnig's theorem has also important consequences for cofinality of cardinal numbers.

• If ${\displaystyle \kappa \geq \aleph _{0}}$, then ${\displaystyle \kappa <\kappa ^{\operatorname {cf} (\kappa )}}$.

If κ is regular, then this follows from Cantor's theorem. If κ is singular, then κ is a limit cardinal. Choose a strictly increasing cf(κ)-sequence of cardinals approaching κ. Let λ be their sum. Each summand is less than κ, so, by Kőnig's theorem, λ is less than the product of cf(κ) copies of κ. We finish the proof by showing that λ = κ. Since each summand is a lower bound for λ, λ ≥ κ. For the other inequality, λ ≤ cf(κ)·κ = κ.

According to Easton's theorem, the next consequence of Kőnig's theorem is the only nontrivial constraint on the continuum function for regular cardinals.

• If ${\displaystyle \kappa \geq \aleph _{0}}$ and ${\displaystyle \lambda \geq 2}$, then ${\displaystyle \kappa <\operatorname {cf} (\lambda ^{\kappa })}$.

Let ${\displaystyle \mu =\lambda ^{\kappa }}$. Suppose that, contrary to this corollary, ${\displaystyle \kappa \geq \operatorname {cf} (\mu )}$. Then using the previous corollary, ${\displaystyle \mu <\mu ^{\operatorname {cf} (\mu )}\leq \mu ^{\kappa }=(\lambda ^{\kappa })^{\kappa }=\lambda ^{\kappa \cdot \kappa }=\lambda ^{\kappa }=\mu }$, a contradiction.

A proof of Kőnig's theorem

Assuming Zermelo–Fraenkel set theory, including especially the axiom of choice, we can prove the theorem. Remember that we are given ${\displaystyle \forall i\in I.A_{i}<B_{i}}$, and we want to show ${\textstyle \sum _{i\in I}A_{i}<\prod _{i\in I}B_{i}.}$

The axiom of choice implies that the condition A < B is equivalent to the condition that there is no function from A onto B and B is nonempty. So we are given that there is no function from A_i onto B_i≠{}, and we have to show that any function f from the disjoint union of the As to the product of the Bs is not surjective and that the product is nonempty. That the product is nonempty follows immediately from the axiom of choice and the fact that the factors are nonempty. For each i choose a b_i in B_i not in the image of A_i under the composition of f with the projection to B_i. Then the product of the elements b_i is not in the image of f, so f does not map the disjoint union of the As onto the product of the Bs.

Notes

1. Rubin, H.; Rubin, J. E. (1985). Equivalents of the Axiom of Choice, II. New York City: North Holland. pp. 185. ISBN 0-444-87708-8.

References

• M. Holz, K. Steffens and E. Weitz (1999). Introduction to Cardinal Arithmetic. Birkhäuser. ISBN 3-7643-6124-7.
• Kőnig, J. (1904), "Zum Kontinuum-Problem", in Krazer, Adolf (ed.), Verhandlungen des dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904, pp. 144–147, archived from the original on 2015-01-04, retrieved 2014-06-14, reprinted as Kőnig, J. (1905), "Zum Kontinuum-Problem", Mathematische Annalen, 60 (2): 177–180, doi:10.1007/BF01677263, S2CID 177788074

v t e Mathematical logic
General	Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory
Theorems (list)  and paradoxes	Gödel's completeness and incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem, paradox and diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox
Logics	Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus
Set theory	Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps and cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Set theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive
Formal systems (list), language and syntax	Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of arithmetic: Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry: Euclidean: Elements Hilbert's Tarski's non-Euclidean Principia Mathematica
Proof theory	Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories
Model theory	Interpretation function of models Model equivalence finite saturated spectrum submodel Non-standard model of arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity
Computability theory	Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory
Related	Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask
Mathematics portal

• Axiom of choice
• Cardinal numbers
• Mathematical logic
• Theorems in the foundations of mathematics