Теорема Кёнига (теория множеств)

В теории множеств теорема Кёнига утверждает, что если выполняется аксиома выбора , I — множество , а — кардинальные числа для каждого i из I и для каждого i из I , то ${\displaystyle \kappa _{i}}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle \kappa _{i}<\lambda _{i}}$

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

Сумма здесь есть мощность непересекающегося объединения множеств m _i , а произведение — мощность декартова произведения . Однако без использования аксиомы выбора сумма и произведение не могут быть определены как кардинальные числа, а значение знака неравенства необходимо было бы прояснить.

Теорема Кёнига была введена Кёнигом  (1904) в несколько более слабой форме, согласно которой сумма строго возрастающей последовательности ненулевых кардинальных чисел меньше их произведения.

Подробности

Точное выражение результата: если I — множество , A _i и B _i — множества для каждого i из I , и для каждого i из I , то ${\displaystyle A_{i}<B_{i}}$

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

где < означает строго меньше, чем по мощности , т.е. существует инъективная функция из A _i в B _i , но не существует функции, идущей в обратном направлении. Объединение, о котором идет речь, не обязательно должно быть непересекающимся (непересекающееся объединение не может быть больше непересекающейся версии, также предполагая аксиому выбора ). В этой формулировке теорема Кёнига эквивалентна аксиоме выбора . ^[1]

(Разумеется, теорема Кёнига тривиальна, если кардинальные числа m _i и n _i конечны , а множество индексов I конечно. Если I пусто , то левая сумма является пустой суммой и, следовательно, равна 0, тогда как правое произведение является пустым произведением и , следовательно, равно 1).

Теорема Кёнига замечательна строгим неравенством в заключении. Существует много простых правил для арифметики бесконечных сумм и произведений кардиналов, в которых можно заключить только слабое неравенство ≤, например: если для всех i из I , то можно заключить только ${\displaystyle m_{i}<n_{i}}$

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

поскольку, например, установка и , где индексный набор I — натуральные числа, дает сумму для обеих сторон, и мы имеем равенство. ${\displaystyle m_{i}=1}$ ${\displaystyle n_{i}=2}$ ${\displaystyle \aleph _{0}}$

Следствия теоремы Кёнига

• Если — кардинальное число, то . ${\displaystyle \kappa }$ ${\displaystyle \kappa <2^{\kappa }}$

Если мы возьмем m _i = 1, и n _i = 2 для каждого i из κ, то левая часть приведенного выше неравенства будет просто κ, в то время как правая часть будет 2 ^κ , мощность функций от κ до {0, 1}, то есть мощность множества мощности κ. Таким образом, теорема Кёнига дает нам альтернативное доказательство теоремы Кантора . (Исторически, конечно, теорема Кантора была доказана гораздо раньше.)

Аксиома выбора

Один из способов сформулировать аксиому выбора — «произвольное декартово произведение непустых множеств непусто». Пусть B _i — непустое множество для каждого i из I . Пусть A _i = {} для каждого i из I . Таким образом, по теореме Кёнига имеем:

• Если , то . ${\displaystyle \forall i\in I(\{\}<B_{i})}$ ${\displaystyle \{\}<\prod _{i\in I}B_{i}}$

То есть, декартово произведение заданных непустых множеств B _i имеет большую мощность, чем сумма пустых множеств. Таким образом, оно непусто, что и утверждает аксиома выбора. Поскольку аксиома выбора следует из теоремы Кёнига, мы будем свободно и неявно использовать аксиому выбора при обсуждении следствий теоремы.

Теорема Кёнига и конфинальность

Теорема Кёнига также имеет важные следствия для конфинальности кардинальных чисел.

• Если , то . ${\displaystyle \kappa \geq \aleph _{0}}$ ${\displaystyle \kappa <\kappa ^{\operatorname {cf} (\kappa )}}$

Если κ регулярно , то это следует из теоремы Кантора. Если κ сингулярно, то κ является предельным кардиналом. Выберем строго возрастающую cf(κ)-последовательность кардиналов, приближающуюся к κ. Пусть λ будет их суммой. Каждое слагаемое меньше κ, поэтому по теореме Кёнига λ меньше произведения cf(κ) копий κ. Завершим доказательство, показав, что λ = κ. Поскольку каждое слагаемое является нижней границей для λ, λ ≥ κ. Для другого неравенства λ ≤ cf(κ)·κ = κ.

Согласно теореме Истона , следующим следствием теоремы Кёнига является единственное нетривиальное ограничение на функцию континуума для регулярных кардиналов .

• Если и , то . ${\displaystyle \kappa \geq \aleph _{0}}$ ${\displaystyle \lambda \geq 2}$ ${\displaystyle \kappa <\operatorname {cf} (\lambda ^{\kappa })}$

Пусть . Предположим, что вопреки этому следствию, . Тогда, используя предыдущее следствие, , противоречие. ${\displaystyle \mu =\lambda ^{\kappa }}$ ${\displaystyle \kappa \geq \operatorname {cf} (\mu )}$ ${\displaystyle \mu <\mu ^{\operatorname {cf} (\mu )}\leq \mu ^{\kappa }=(\lambda ^{\kappa })^{\kappa }=\lambda ^{\kappa \cdot \kappa }=\lambda ^{\kappa }=\mu }$

Доказательство теоремы Кёнига

Предполагая теорию множеств Цермело–Френкеля , включая особенно аксиому выбора , мы можем доказать теорему. Помните, что нам дано , и мы хотим показать: ${\displaystyle \forall i\in I\quad A_{i}<B_{i}}$ ${\displaystyle \sum _{i\in I}A_{i}<\prod _{i\in I}B_{i}.}$

Аксиома выбора подразумевает, что условие A < B эквивалентно условию, что нет функции из A на B и B непусто. Итак, нам дано, что нет функции из A _i на B _i ≠{}, и мы должны показать, что любая функция f из несвязного объединения A s в произведение B s не является сюръективной и что произведение непусто. То, что произведение непусто, немедленно следует из аксиомы выбора и того факта, что множители непусты. Для каждого i выберем b _i в B _i не в образе A _i при композиции f с проекцией на B _i . Тогда произведение элементов b _i не находится в образе f , поэтому f не отображает несвязное объединение A s в произведение B s.

Примечания

1. Рубин, Х.; Рубин, Дж. Э. (1985). Эквиваленты аксиомы выбора, II . Нью-Йорк, Нью-Йорк: Северная Голландия . С. 185. ISBN 0-444-87708-8.

Ссылки

• M. Holz, K. Steffens и E. Weitz (1999). Введение в кардинальную арифметику . Биркхойзер. ISBN 3-7643-6124-7.
• Кениг, Дж. (1904), «Zum Continuum-Problem», в книге Кразер, Адольф (редактор), Verhandlungen des dritten Internationalen Mathematik-Kongresses in Heidelberg vom 8. bis 13. August 1904 , стр. 144–147, заархивировано из оригинал 04 января 2015 г. , получено 14 июня 2014 г., перепечатано как Кениг, Дж. (1905), «Zum Continuum-Problem», Mathematische Annalen , 60 (2): 177–180, doi : 10.1007/BF01677263, S2CID  177788074