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

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

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

Писать $\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}$ . Такие окраски известны как сильные окраски. ^[3] и изучал теорию множеств. Эрдеш, Хайнал и Радо (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 }$

Примечания

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

Ссылки

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

[1] Андреас Бласс , Комбинаторные кардинальные характеристики континуума , Глава 6 в Справочнике по теории множеств, под редакцией Мэтью Формана и Акихиро Канамори , Springer, 2010

[2] Тодд Эйсворт, Преемники сингулярных кардиналов. Глава 15 в Справочнике по теории множеств, под редакцией Мэтью Формана и Акихиро Канамори, Springer, 2010.

[3] Ринот, Ассаф, Учебное пособие по сильным раскраскам и их применениям, 6-я Европейская конференция по теории множеств , получено 10 декабря 2023 г.

[1]

[2]

[3]