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

Эта статья включает список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Май 2024 ) ( Узнайте, как и когда удалить это сообщение )

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

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

${\displaystyle \displaystyle \ каппа \rightarrow (\lambda)_{m}^{n}}$

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

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

${\displaystyle \displaystyle \каппа \rightarrow (\lambda)_{m}^{<\omega }}$

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

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

${\displaystyle \displaystyle \ каппа \rightarrow (\lambda,\mu)^{n}}$

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

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

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

${\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 }}$

• Душник, Бен; Миллер, Э. У. (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