Бесконечная комбинаторика

Распространение идей комбинаторики на бесконечные множества

В математике бесконечная комбинаторика или комбинаторная теория множеств — это расширение идей комбинаторики на бесконечные множества . Некоторые изучаемые вещи включают непрерывные графы и деревья , расширения теоремы Рамсея и аксиомы Мартина . Недавние разработки касаются комбинаторики континуума [ ^1] и комбинаторики на преемниках сингулярных кардиналов. ^[2]

Теория Рамсея для бесконечных множеств

Запишите для ординалов, для кардинальных чисел (конечных или бесконечных) и для натуральных чисел. Эрдёш и Радо (1956) ввели обозначение ${\displaystyle \kappa ,\lambda }$ ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$

как сокращенный способ сказать, что каждое разбиение множества -элементных подмножеств на части имеет однородное множество типа порядка . Однородное множество в этом случае является подмножеством такого, что каждое -элементное подмножество находится в одном и том же элементе разбиения. Когда равно 2, оно часто опускается. Такие утверждения известны как отношения разбиения. ${\displaystyle [\kappa ]^{n}}$ ${\displaystyle n}$ ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle \lambda }$ ${\displaystyle \kappa }$ ${\displaystyle n}$ ${\displaystyle m}$

Предполагая аксиому выбора , нет ординалов с , поэтому обычно считается конечным. Расширение, где почти разрешено быть бесконечным, — это обозначение ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\omega )^{\omega }}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{<\omega }}$

что является сокращенным способом сказать, что каждое разбиение множества конечных подмножеств на части имеет подмножество типа порядка, такое что для любого конечного , все подмножества размера находятся в одном и том же элементе разбиения. Когда равно 2, это часто опускается. ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle \lambda }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle m}$

Другим вариантом является обозначение

${\displaystyle \displaystyle \kappa \rightarrow (\lambda ,\mu )^{n}}$

что является сокращенным способом сказать, что каждая раскраска множества -элементных подмножеств из в 2 цвета имеет подмножество типа порядка , такое что все элементы из имеют первый цвет, или подмножество типа порядка, такое что все элементы из имеют второй цвет. ${\displaystyle [\kappa ]^{n}}$ ${\displaystyle n}$ ${\displaystyle \kappa }$ ${\displaystyle \lambda }$ ${\displaystyle [\lambda ]^{n}}$ ${\displaystyle \mu }$ ${\displaystyle [\mu ]^{n}}$

Некоторые свойства этого включают в себя: (далее — кардинальное число) ${\displaystyle \kappa }$

${\displaystyle \displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$для всех конечных и ( теорема Рамсея ). ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle \displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}$( теорема Эрдёша–Радо .)

${\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}$(теорема Серпинского)

${\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}}$

${\displaystyle \displaystyle \kappa \rightarrow (\kappa ,\aleph _{0})^{2}}$( теорема Эрдеша–Душника–Миллера )

В невыборочных вселенных могут сохраняться свойства разбиения с бесконечными показателями, и некоторые из них получаются как следствия аксиомы детерминированности (AD). Например, Дональд А. Мартин доказал, что AD подразумевает

${\displaystyle \displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{2}^{\aleph _{1}}}$

Яркие цвета

Вацлав Серпинский показал, что теорема Рамсея не распространяется на множества размера , показав, что . То есть Серпинский построил раскраску пар действительных чисел в два цвета, такую, что для любого несчетного подмножества действительных чисел , принимает оба цвета. Взяв любой набор действительных чисел размера и применив к нему раскраску Серпинского, мы получаем, что . Такие раскраски известны как сильные раскраски ^[3] и изучаются в теории множеств. Эрдёш, Хайнал и Радо (1965) ввели для этого обозначения, аналогичные приведенным выше. ${\displaystyle \aleph _{1}}$ ${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$ ${\displaystyle X}$ ${\displaystyle [X]^{2}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}\not \rightarrow (\aleph _{1})_{2}^{2}}$

Запишите для ординалов, для кардинальных чисел (конечных или бесконечных) и для натуральных чисел. Затем ${\displaystyle \kappa ,\lambda }$ ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle \displaystyle \kappa \nrightarrow [\lambda ]_{m}^{n}}$

— это сокращенный способ сказать, что существует раскраска множества -элементных подмножеств на части, такая, что каждое множество типа порядка является радужным множеством. Радужный набор в этом случае — это подмножество такое , которое принимает все цвета. Когда равно 2, его часто опускают. Такие утверждения известны как отрицательные квадратные скобочные отношения разбиения. ${\displaystyle [\kappa ]^{n}}$ ${\displaystyle n}$ ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle \lambda }$ ${\displaystyle A}$ ${\displaystyle \kappa }$ ${\displaystyle [A]^{n}}$ ${\displaystyle m}$ ${\displaystyle m}$

Другим вариантом является обозначение

${\displaystyle \kappa \nrightarrow [\lambda ;\mu ]_{m}^{2}}$

что является сокращенным способом сказать, что существует раскраска множества 2-элементных подмножеств цветами такая, что для каждого подмножества типа заказа и каждого подмножества типа заказа набор принимает все цвета. ${\displaystyle [\kappa ]^{2}}$ ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle \lambda }$ ${\displaystyle B}$ ${\displaystyle \mu }$ ${\displaystyle A\times B}$ ${\displaystyle m}$

Некоторые свойства этого включают в себя: (далее — кардинальное число) ${\displaystyle \kappa }$

${\displaystyle \displaystyle 2^{\kappa }\nrightarrow [\kappa ^{+}]^{2}}$(Серпинский)

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]^{2}}$(Серпинский)

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{3}^{2}}$( Лейвер , Бласс )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{4}^{2}}$( Галвин и Шела )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}$( Тодорчевич )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1};\aleph _{1}]_{\aleph _{1}}^{2}}$( Мур )

${\displaystyle \displaystyle 2^{\aleph _{0}}\nrightarrow [2^{\aleph _{0}}]_{\aleph _{0}}^{2}}$( Галвин и Шела )

Большие кардиналы

Несколько больших кардинальных свойств можно определить с помощью этой нотации. В частности:

• Слабо компактные кардиналы — это те, которые удовлетворяют ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\kappa )^{2}}$
• α- Кардиналы Эрдёша являются наименьшими, которые удовлетворяют ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\alpha )^{<\,\omega }}$
• Кардиналы Рэмси — это те, которые удовлетворяют ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\kappa )^{<\,\omega }}$

Примечания

1. Андреас Бласс , Комбинаторные кардинальные характеристики континуума , Глава 6 в Справочнике по теории множеств, под редакцией Мэтью Формана и Акихиро Канамори , Springer, 2010
2. Тодд Эйсворт, Successors of Singular Cardinals, Глава 15 в Handbook of Set Theory, под редакцией Мэтью Формана и Акихиро Канамори, Springer, 2010
3. Рино, Ассаф, Учебник по сильным раскраскам и их применению, 6-я Европейская конференция по теории множеств , получено 10 декабря 2023 г.

Ссылки

• Душник, Бен; Миллер, Э. У. (1941), «Частично упорядоченные множества», American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307/2371374, hdl : 10338.dmlcz/100377 , ISSN  0002-9327, JSTOR  2371374, MR  0004862

• Эрдеш, Пол ; Хайнал, Андраш ; Радо, Ричард (1965), «Отношения разделения кардинальных чисел», Acta Math. акад. наук. Хунг. , 16 (1–2): 93–196, doi :10.1007/BF01886396, MR  0202613

• Эрдёш, Пол ; Хайнал, Андраш (1971), «Нерешённые проблемы теории множеств», Аксиоматическая теория множеств (Университет Калифорнии, Лос-Анджелес, Калифорния, 1967) , Proc. Sympos. Pure Math, т. XIII Часть I, Провиденс, Род-Айленд: Amer. Math. Soc., стр. 17–48, MR  0280381
• Эрдеш, Пол ; Хайнал, Андраш ; Мате, Аттила; Радо, Ричард (1984), Комбинаторная теория множеств: отношения разделения для кардиналов , Исследования по логике и основам математики, том. 106, Амстердам: Издательство Северной Голландии, ISBN 0-444-86157-2, МР  0795592
• Erdős, P. ; Rado, R. (1956), "Исчисление разбиений в теории множеств" (PDF) , Bull. Amer. Math. Soc. , 62 (5): 427–489, doi : 10.1090/S0002-9904-1956-10036-0 , MR  0081864
• Канамори, Акихиро (2000), The Higher Infinite (второе изд.), Springer, ISBN 3-540-00384-3
• Кунен, Кеннет (1980), Теория множеств: Введение в доказательства независимости , Амстердам: Северная Голландия, ISBN 978-0-444-85401-8