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

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

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

Напишите κ, λ для ординалов, m для кардинального числа и n для натурального числа. Erdős & Rado (1956) ввели обозначение

{\ Displaystyle \ каппа \ стрелка вправо (\ лямбда) _ {м} ^ {п}}

сокращенно говоря, что каждое разбиение множества [κ] ⁿ из n -элементных подмножеств на m частей имеет однородное множество порядкового типа λ. В этом случае однородным множеством называется такое подмножество κ, что каждое подмножество из n -элементов находится в одном и том же элементе разбиения. Когда m равно 2, его часто опускают. ${\ Displaystyle \ каппа}$

Принимая аксиому выбора , не существует ординалов κ с κ→(ω) ^ω , поэтому n обычно считается конечным. Расширение, в котором n почти может быть бесконечным, - это обозначение

{\ Displaystyle \ каппа \ стрелка вправо (\ лямбда) _ {м} ^ {<\ омега}}

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

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

{\ Displaystyle \ каппа \ стрелка вправо (\ лямбда, \ му) ^ {п}}

что является сокращенным способом сказать, что каждая раскраска множества [κ] ⁿ из n -элементных подмножеств κ с 2 цветами имеет подмножество типа порядка λ такое, что все элементы [λ] ⁿ имеют первый цвет, или подмножество порядкового типа µ такое, что все элементы из [µ] ⁿ имеют второй цвет.

Некоторые свойства этого включают: (далее - кардинал) ${\ Displaystyle \ каппа}$

{\ Displaystyle \ алеф _ {0} \ стрелка вправо (\ алеф _ {0}) _ {к} ^ {п}}

для всех конечных n и k ( теорема Рамсея ).

{\ Displaystyle \ Бет _ {п} ^ {+} \ стрелка вправо (\ алеф _ {1}) _ {\ алеф _ {0}} ^ {п + 1}}

( Теорема Эрдеша – Радо .)

{\ Displaystyle 2 ^ {\ каппа} \ не \ стрелка вправо (\ каппа ^ {+}) ^ {2}}

(теорема Серпинского)

{\ Displaystyle 2 ^ {\ каппа} \ не \ стрелка вправо (3) _ {\ каппа} ^ {2}}

{\ Displaystyle \ каппа \ rightarrow (\ каппа, \ алеф _ {0}) ^ {2}}

( теорема Эрдёша–Душника–Миллера ).

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

{\ Displaystyle \ алеф _ {1} \ стрелка вправо (\ алеф _ {1}) _ {2} ^ {\ алеф _ {1}}}

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

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

Слабо компактные кардиналы κ — это те, которые удовлетворяют κ→(κ) ²
α- Кардиналы Эрдёша κ наименьшие, удовлетворяющие условию κ→(α) ^<ω
Кардиналы Рамсея κ — это те, которые удовлетворяют κ→(κ) ^<ω

Примечания

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

использованная литература

Душник, Бен; Миллер, 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
Эрдёш, Пол ; Хайнал, Андраш (1971), «Нерешенные проблемы теории множеств», Аксиоматическая теория множеств (Калифорнийский университет, Лос-Анджелес, Калифорния, 1967) , Proc. Симпозиумы Pure Math, XIII Part I, Providence, RI: Amer. Мат. Soc., стр. 17–48, MR 0280381
Эрдёш, Пол ; Хайнал, Андраш ; Мате, Аттила; Радо, Ричард (1984), Комбинаторная теория множеств: отношения разделения для кардиналов , Исследования по логике и основаниям математики, 106 , Амстердам: издательство North-Holland Publishing Co., ISBN 0-444-86157-2, МР 0795592
Эрдёш, П. ; Радо, Р. (1956), «Исчисление разделов в теории множеств» , Bull. амер. Мат. соц. , 62 (5): 427–489, doi : 10.1090/S0002-9904-1956-10036-0 , MR 0081864
Канамори, Акихиро (2000). Высшее Бесконечное (второе изд.). Спрингер. ISBN 3-540-00384-3.
Кунен, Кеннет (1980), Теория множеств: введение в доказательства независимости , Амстердам: Северная Голландия, ISBN 978-0-444-85401-8

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

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

[1]