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

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

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

Писать $\kappa ,\lambda$ для ординалов, $m$ для кардинального числа (конечного или бесконечного) и $n$ для натурального числа. Эрдеш и Радо (1956) ввели обозначения

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

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

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

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

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

Еще одним вариантом является обозначение

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

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

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

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

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

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

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

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

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

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

Сильные окраски

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

Писать $\kappa ,\lambda$ для ординалов, $m$ для кардинального числа (конечного или бесконечного) и $n$ для натурального числа. Затем

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

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

Еще одним вариантом является обозначение

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

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

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

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

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

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

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

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

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

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

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

несколько крупных кардинальных Используя это обозначение, можно определить свойств. В частности:

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

Ссылки

• Душник, Бен; Миллер, EW (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. Симпозиумы. Чистая математика, том. XIII Часть I, Провиденс, Род-Айленд: Амер. Математика. Соц., стр. 17–48, МР   0280381.
• Эрдеш, Пол ; Хайнал, Андраш ; Мате, Аттила; Радо, Ричард (1984), Комбинаторная теория множеств: отношения разделения для кардиналов , Исследования по логике и основам математики, том. 106, Амстердам: Издательство Северной Голландии, ISBN  0-444-86157-2 , МР   0795592
• Эрдеш, П .; Радо, Р. (1956), «Исчисление разделов в теории множеств» (PDF) , Bull. амер. Соц. , 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