Структурная теория Рамсея - Structural Ramsey theory

В математике структурная теория Рамсея это категоричный обобщение Теория Рамсея, основанный на идее, что многие важные результаты теории Рамсея имеют «подобную» логическую структуру. Ключевое наблюдение состоит в том, что эти теоремы типа Рамсея могут быть выражены как утверждение, что определенная категория (или класс конечных структур) имеет Ramsey собственности (определено ниже).

Структурная теория Рамсея зародилась в 1970-х годах.^[1] с работой Nešetřil и Rödl, и тесно связан с Теория Фраиссе. Интерес к нему возобновился в середине 2000-х годов из-за открытия Кехрис – Пестов – Тодорчевич переписка, который связал структурную теорию Рамсея с топологическая динамика.

История

Leeb [де ] дан кредит^[2] за изобретение идеи свойства Рамсея в начале 70-х, и первая публикация этой идеи, по-видимому, Грэм, Либ и Ротшильд Статья 1972 года по этому поводу.^[3] Ключевое развитие этих идей было сделано Nešetřil и Rödl в своей серии 1977 г.^[4] и 1983 г.^[5] статьи, в том числе знаменитую теорему Нешетржила – Рёдля. Этот результат был независимо осужден Абрамсоном и Харрингтон^[6], и далее обобщается Prömel [де ]^[7]. Совсем недавно Машулович^[8]^[9]^[10] и Солецкий^[11]^[12]^[13] проделали новаторскую работу в этой области.

Мотивация

В этой статье будет использоваться соглашение теории множеств, согласно которому каждое натуральное число ${ Displaystyle п в mathbb {N}}$ можно рассматривать как множество всех натуральных чисел, меньших его: т.е. ${ Displaystyle п = {0,1, ldots, п-1 }}$ . Для любого набора ${ displaystyle A}$ , ${ displaystyle r}$ -крашивание ${ displaystyle A}$ это задание одного из ${ displaystyle r}$ метки к каждому элементу ${ displaystyle A}$ . Это можно представить как функцию ${ displaystyle Delta: от A до r}$ отображение каждого элемента на его метку в ${ Displaystyle г = {0,1, ldots, г-1 }}$ (который будет использоваться в этой статье), или, что эквивалентно, как раздел ${ Displaystyle A = A_ {0} sqcup cdots sqcup A_ {r-1}}$ в ${ displaystyle r}$ шт.

Вот некоторые из классических результатов теории Рамсея:

(Конечное) Теорема Рамсея: для каждого ${ Displaystyle к Leq м, г в mathbb {N}}$ , Существует ${ Displaystyle п в mathbb {N}}$ так что для каждого ${ displaystyle r}$ -крашивание ${ displaystyle Delta: [n] ^ {(k)} to r}$ из всех ${ displaystyle k}$ -элементные подмножества ${ Displaystyle п = {0,1, ldots, п-1 }}$ , существует подмножество ${ Displaystyle A substeq п}$ , с ${ displaystyle | A | = m}$ , так что ${ Displaystyle [А] ^ {(к)}}$ является ${ displaystyle Delta}$ -монохроматический.
(Конечное) Теорема ван дер Вардена: для каждого ${ displaystyle m, r in mathbb {N}}$ , Существует ${ Displaystyle п в mathbb {N}}$ так что для каждого ${ displaystyle r}$ -крашивание ${ displaystyle Delta: n to r}$ из ${ displaystyle n}$ , существует ${ displaystyle Delta}$ -монохроматическая арифметическая прогрессия ${ displaystyle {a, a + d, a + 2d, ldots, a + (m-1) d } substeq n}$ длины ${ displaystyle m}$ .
Теорема Грэма – Ротшильда.: исправить конечный алфавит ${ Displaystyle L = {a_ {0}, a_ {1}, ldots, a_ {d-1} }}$ . А ${ displaystyle k}$ -слово параметра длины ${ displaystyle n}$ над ${ displaystyle L}$ это элемент ${ Displaystyle ш в (L чашка {x_ {0}, x_ {1}, ldots, x_ {k-1} }) ^ {n}}$ , так что все ${ displaystyle x_ {i}}$ появляются, и их первые появления находятся в порядке возрастания. Набор всех ${ displaystyle k}$ -параметрические слова длины ${ displaystyle n}$ над ${ displaystyle L}$ обозначается ${ Displaystyle textstyle [L] { binom {п} {к}}}$ . Данный ${ displaystyle textstyle w in [L] { binom {n} {m}}}$ и ${ displaystyle textstyle v in [L] { binom {m} {k}}}$ , мы формируем их сочинение ${ displaystyle textstyle w circ v in [L] { binom {n} {k}}}$ заменяя каждое вхождение ${ displaystyle x_ {i}}$ в ${ displaystyle w}$ с ${ displaystyle i}$ -я запись ${ displaystyle v}$ .
Затем теорема Грэма – Ротшильда утверждает, что для каждого ${ Displaystyle к Leq м, г в mathbb {N}}$ , Существует ${ Displaystyle п в mathbb {N}}$ так что для каждого ${ displaystyle r}$ -крашивание ${ displaystyle textstyle Delta: [L] { binom {n} {k}} to r}$ из всех ${ displaystyle k}$ -параметрические слова длины ${ displaystyle n}$ , Существует ${ displaystyle textstyle w in [L] { binom {n} {m}}}$ , так что ${ displaystyle textstyle w circ [L] { binom {m} {k}} = {w circ v: v in [L] { binom {m} {k}} }}$ (т.е. все ${ displaystyle k}$ -параметрические подслова ${ displaystyle w}$ ) является ${ displaystyle Delta}$ -монохроматический.
(Конечное) Теорема Фолкмана: для каждого ${ displaystyle m, r in mathbb {N}}$ , Существует ${ Displaystyle п в mathbb {N}}$ так что для каждого ${ displaystyle r}$ -крашивание ${ displaystyle Delta: n to r}$ из ${ displaystyle n}$ , существует подмножество ${ Displaystyle A substeq п}$ , с ${ displaystyle | A | = m}$ , так что ${ displaystyle textstyle { big (} sum _ {k in A} k { big)} <п}$ , и ${ displaystyle textstyle operatorname {FS} (A) = { sum _ {k in B} k: B in { mathcal {P}} (A) setminus varnothing }}$ является ${ displaystyle Delta}$ -монохроматический.

Все эти теоремы типа Рамсея имеют схожую идею: мы фиксируем два целых числа ${ displaystyle k}$ и ${ displaystyle m}$ , и набор цветов ${ displaystyle r}$ . Затем мы хотим показать, что есть ${ displaystyle n}$ достаточно большой, чтобы для каждого ${ displaystyle r}$ -окрашивание «каркасов» размеров ${ displaystyle k}$ внутри ${ displaystyle n}$ , мы можем найти подходящую «структуру» ${ displaystyle A}$ внутри ${ displaystyle n}$ , размером ${ displaystyle m}$ , так что все "подструктуры" ${ displaystyle B}$ из ${ displaystyle A}$ с размером ${ displaystyle k}$ иметь такой же цвет.

Какие типы структур разрешены, зависит от рассматриваемой теоремы, и это оказывается практически единственной разницей между ними. Эта идея «теоремы типа Рамсея» приводит к более точному понятию свойства Рамсея (см. Ниже).

Свойство Рэмси

Позволять ${ displaystyle mathbf {C}}$ быть категория. ${ displaystyle mathbf {C}}$ имеет Ramsey собственности если для каждого натурального числа ${ displaystyle r}$ , и все объекты ${ displaystyle A, B}$ в ${ displaystyle mathbf {C}}$ , существует другой объект ${ displaystyle D}$ в ${ displaystyle mathbf {C}}$ , так что для каждого ${ displaystyle r}$ -крашивание ${ displaystyle Delta: operatorname {Hom} (A, D) to r}$ , существует морфизм ${ displaystyle f: B to D}$ который ${ displaystyle Delta}$ -монохроматический, т.е. множество

{ displaystyle f circ operatorname {Hom} (A, B) = { big {} f circ g: g in operatorname {Hom} (A, B) { big }}}

является ${ displaystyle Delta}$ -монохроматический.^[14]

Часто, ${ displaystyle mathbf {C}}$ рассматривается как класс конечных ${ Displaystyle { mathcal {L}}}$ -структуры над некоторыми фиксированными язык ${ Displaystyle { mathcal {L}}}$ , с вложения как морфизмы. В этом случае вместо раскраски морфизмов можно думать о раскраске «копий» ${ displaystyle A}$ в ${ displaystyle D}$ , а затем найти копию ${ displaystyle B}$ в ${ displaystyle D}$ , так что все копии ${ displaystyle A}$ в этой копии ${ displaystyle B}$ однотонные. Это может более интуитивно подойти к более ранней идее «теоремы типа Рамсея».

Существует также понятие двойственного свойства Рамсея; ${ displaystyle mathbf {C}}$ обладает двойственным свойством Рамсея, если его двойная категория ${ displaystyle mathbf {C} ^ { mathrm {op}}}$ имеет свойство Рамсея, как указано выше. Более конкретно, ${ displaystyle mathbf {C}}$ имеет двойное свойство Рамсея если для каждого натурального числа ${ displaystyle r}$ , и все объекты ${ displaystyle A, B}$ в ${ displaystyle mathbf {C}}$ , существует другой объект ${ displaystyle D}$ в ${ displaystyle mathbf {C}}$ , так что для каждого ${ displaystyle r}$ -крашивание ${ displaystyle Delta: operatorname {Hom} (D, A) to r}$ , существует морфизм ${ displaystyle f: D to B}$ для которого ${ displaystyle operatorname {Hom} (B, A) circ f}$ является ${ displaystyle Delta}$ -монохроматический.

Примеры

Теорема Рамсея: класс всех конечных цепи, с сохраняющими порядок отображениями в качестве морфизмов, обладает свойством Рамсея.
Теорема ван дер Вардена: в категории, объекты которой конечные ординалы, а морфизмы аффинные карты ${ displaystyle x mapsto a + dx}$ за ${ displaystyle a, d in mathbb {N}}$ , ${ displaystyle d neq 0}$ , свойство Рамсея выполнено для ${ displaystyle A = 1}$ .
Теорема Хейлза – Джеветта: позволять ${ displaystyle L}$ - конечный алфавит, и для каждого ${ Displaystyle к в mathbb {N}}$ , позволять ${ Displaystyle X_ {к} = {x_ {0}, ldots, x_ {k-1} }}$ быть набором ${ displaystyle k}$ переменные. Позволять ${ displaystyle mathbf {GR}}$ быть категорией, объекты которой ${ Displaystyle A_ {k} = L чашка X_ {k}}$ для каждого ${ Displaystyle к в mathbb {N}}$ , и чьи морфизмы ${ displaystyle A_ {n} to A_ {k}}$ , за ${ Displaystyle п geq k}$ , являются функциями ${ displaystyle f: X_ {n} to A_ {k}}$ которые жесткий и сюръективный на ${ displaystyle X_ {k} substeq A_ {k} = operatorname {codom} f}$ . Потом, ${ displaystyle mathbf {GR}}$ обладает двойственным свойством Рамсея для ${ displaystyle A = A_ {0}}$ (и ${ displaystyle B = A_ {1}}$ , в зависимости от рецептуры).
Теорема Грэма – Ротшильда: категория ${ displaystyle mathbf {GR}}$ определенный выше обладает двойственным свойством Рамсея.

Переписка Кехриса – Пестова – Тодорчевича

В 2005 году, Кехрис, Пестов и Тодорчевич^[15] обнаружил следующую корреспонденцию (далее именуемую КПТ переписка) между структурной теорией Рамсея, теорией Фраиссе и идеями топологической динамики.

Позволять ${ displaystyle G}$ быть топологическая группа. Для топологического пространства ${ displaystyle X}$ , а ${ displaystyle G}$ -поток (обозначено ${ Displaystyle G curvearrowright X}$ ) это непрерывное действие из ${ displaystyle G}$ на ${ displaystyle X}$ . Мы говорим что ${ displaystyle G}$ является чрезвычайно податливый если есть ${ displaystyle G}$ -поток ${ Displaystyle G curvearrowright X}$ на компактном пространстве ${ displaystyle X}$ признает фиксированная точка ${ displaystyle x in X}$ , т.е. стабилизатор из ${ displaystyle x}$ является ${ displaystyle G}$ сам.

Для Структура Fraïssé ${ displaystyle mathbf {F}}$ , это автоморфизм группа ${ Displaystyle OperatorName {Aut} ( mathbf {F})}$ можно рассматривать как топологическую группу, учитывая топологию поточечная сходимость, или, что то же самое, топология подпространства наведен на ${ Displaystyle OperatorName {Aut} ( mathbf {F})}$ по пространству ${ Displaystyle mathbf {F} ^ { mathbf {F}} = {е: mathbf {F} to mathbf {F} }}$ с топология продукта. Следующая теорема иллюстрирует соответствие КПТ:

Теорема (КПТ). Для структуры Фраиссе ${ displaystyle mathbf {F}}$ , следующие эквиваленты:
Группа ${ displaystyle operatorname {Aut} ( mathbf {F})}$ автоморфизмов ${ displaystyle mathbf {F}}$ чрезвычайно податлив.
Класс ${ displaystyle operatorname {Возраст} ( mathbf {F})}$ обладает свойством Рэмси.

Смотрите также

Рекомендации

^ Ван Те, Лионель Нгуен (10 декабря 2014 г.). «Обзор структурной теории Рамсея и топологической динамики с учетом соответствия Кехриса – Пестова – Тодорцевича». arXiv:1412.3254 [math.CO ].
^ Ларсон, Джин А. (01.01.2012), «Бесконечная комбинаторика», в Габбай, Дов М .; Канамори, Акихиро; Вудс, Джон (ред.), Справочник по истории логики, Наборы и расширения в двадцатом веке, 6, Северная Голландия, стр. 145–357, Дои:10.1016 / b978-0-444-51621-3.50003-7, ISBN 9780444516213, получено 2019-11-30
^ Graham, R.L; Leeb, K; Ротшильд, Б. Л. (1972-06-01). «Теорема Рамсея для класса категорий». Успехи в математике. 8 (3): 417–433. Bibcode:1972ПНАС ... 69..119Г. Дои:10.1016/0001-8708(72)90005-9. ISSN 0001-8708.
^ Нешетржил, Ярослав; Рёдль, Войтех (май 1977 г.). «Разбиения конечных реляционных и множественных систем». Журнал комбинаторной теории, серия А. 22 (3): 289–312. Дои:10.1016/0097-3165(77)90004-8. ISSN 0097-3165.
^ Нешетржил, Ярослав; Рёдль, Войтех (1983-03-01). «Классы Рамсея систем множеств». Журнал комбинаторной теории, серия А. 34 (2): 183–201. Дои:10.1016/0097-3165(83)90055-9. ISSN 0097-3165.
^ Abramson, Fred G .; Харрингтон, Лео А. (сентябрь 1978 г.). «Модели без неотличимых». Журнал символической логики. 43 (3): 572. Дои:10.2307/2273534. ISSN 0022-4812. JSTOR 2273534.
^ Prömel, Ханс Юрген (июль 1985 г.). «Свойства индуцированного разбиения комбинаторных кубов». Журнал комбинаторной теории, серия А. 39 (2): 177–208. Дои:10.1016/0097-3165(85)90036-6. ISSN 0097-3165.
^ Масулович, Драган; Scow, Линн (2015-06-02). «Категориальные конструкции и свойство Рамсея». arXiv:1506.01221 [math.CT ].
^ Масулович, Драган (22.09.2016). «Предварительные присоединения и свойство Рэмси». arXiv:1609.06832 [math.CO ].
^ Машулович, Драган (29.07.2017). «Двойственные теоремы Рамсея для реляционных структур». arXiv:1707.09544 [math.CO ].
^ Солецкий, Славомир (август 2010 г.). «Теорема Рамсея для структур с отношениями и функциями». Журнал комбинаторной теории, серия А. 117 (6): 704–714. Дои:10.1016 / j.jcta.2009.12.004. ISSN 0097-3165.
^ Солецкий, Славомир (20.04.2011). "Абстрактный подход к конечной теории Рамсея и самодвойственной теореме Рамсея". arXiv:1104.3950 [math.CO ].
^ Солецкий, Славомир (16 февраля 2015 г.). «Двойственная теорема Рамсея для деревьев». arXiv:1502.04442 [math.CO ].
^ Машулович, Драган (29.07.2017). «Двойственные теоремы Рамсея для реляционных структур». arXiv:1707.09544 [math.CO ].
^ Kechris, A. S .; Пестов, В.Г .; Тодорцевич, С. (февраль 2005 г.). "Пределы Фраисе, теория Рамсея и топологическая динамика групп автоморфизмов" (PDF). Геометрический и функциональный анализ. 15 (1): 106–189. Дои:10.1007 / s00039-005-0503-1. ISSN 1016-443X.

[1] Ван Те, Лионель Нгуен (10 декабря 2014 г.). «Обзор структурной теории Рамсея и топологической динамики с учетом соответствия Кехриса – Пестова – Тодорцевича». arXiv:1412.3254 [math.CO ].

[2] Ларсон, Джин А. (01.01.2012), «Бесконечная комбинаторика», в Габбай, Дов М .; Канамори, Акихиро; Вудс, Джон (ред.), Справочник по истории логики, Наборы и расширения в двадцатом веке, 6, Северная Голландия, стр. 145–357, Дои:10.1016 / b978-0-444-51621-3.50003-7, ISBN 9780444516213, получено 2019-11-30

[3] Graham, R.L; Leeb, K; Ротшильд, Б. Л. (1972-06-01). «Теорема Рамсея для класса категорий». Успехи в математике. 8 (3): 417–433. Bibcode:1972ПНАС ... 69..119Г. Дои:10.1016/0001-8708(72)90005-9. ISSN 0001-8708.

[4] Нешетржил, Ярослав; Рёдль, Войтех (май 1977 г.). «Разбиения конечных реляционных и множественных систем». Журнал комбинаторной теории, серия А. 22 (3): 289–312. Дои:10.1016/0097-3165(77)90004-8. ISSN 0097-3165.

[5] Нешетржил, Ярослав; Рёдль, Войтех (1983-03-01). «Классы Рамсея систем множеств». Журнал комбинаторной теории, серия А. 34 (2): 183–201. Дои:10.1016/0097-3165(83)90055-9. ISSN 0097-3165.

[6] Abramson, Fred G .; Харрингтон, Лео А. (сентябрь 1978 г.). «Модели без неотличимых». Журнал символической логики. 43 (3): 572. Дои:10.2307/2273534. ISSN 0022-4812. JSTOR 2273534.

[7] Prömel, Ханс Юрген (июль 1985 г.). «Свойства индуцированного разбиения комбинаторных кубов». Журнал комбинаторной теории, серия А. 39 (2): 177–208. Дои:10.1016/0097-3165(85)90036-6. ISSN 0097-3165.

[8] Масулович, Драган; Scow, Линн (2015-06-02). «Категориальные конструкции и свойство Рамсея». arXiv:1506.01221 [math.CT ].

[9] Масулович, Драган (22.09.2016). «Предварительные присоединения и свойство Рэмси». arXiv:1609.06832 [math.CO ].

[10] Машулович, Драган (29.07.2017). «Двойственные теоремы Рамсея для реляционных структур». arXiv:1707.09544 [math.CO ].

[11] Солецкий, Славомир (август 2010 г.). «Теорема Рамсея для структур с отношениями и функциями». Журнал комбинаторной теории, серия А. 117 (6): 704–714. Дои:10.1016 / j.jcta.2009.12.004. ISSN 0097-3165.

[12] Солецкий, Славомир (20.04.2011). "Абстрактный подход к конечной теории Рамсея и самодвойственной теореме Рамсея". arXiv:1104.3950 [math.CO ].

[13] Солецкий, Славомир (16 февраля 2015 г.). «Двойственная теорема Рамсея для деревьев». arXiv:1502.04442 [math.CO ].

[14] Машулович, Драган (29.07.2017). «Двойственные теоремы Рамсея для реляционных структур». arXiv:1707.09544 [math.CO ].

[15] Kechris, A. S .; Пестов, В.Г .; Тодорцевич, С. (февраль 2005 г.). "Пределы Фраисе, теория Рамсея и топологическая динамика групп автоморфизмов" (PDF). Геометрический и функциональный анализ. 15 (1): 106–189. Дои:10.1007 / s00039-005-0503-1. ISSN 1016-443X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]