Теорема Эрдёша — Радо

Теорема Эрдёша — Радо — обобщение теоремы Рамсея на несчётные множества. Названа в честь Пала Эрдёша и Ричарда Радо. Ранее Джюро Курепа доказал эту теорему в предположении обобщённой Континуум-гипотезы.

Формулировка

Пусть $r$ — конечно и $\kappa$ — бесконечный кардинал. Тогда для любой раскраски $(r+1)$ -точечных подмножеств множества мощности $\exp _{r}(\kappa )^{+}$ , в $\kappa$ цветов существует монохроматическое подмножество мощности $\kappa ^{+}$ .

Замечания

$\kappa ^{+}$ обозначает следующее за $\kappa$ кардинальное число.
$\exp _{r}(\kappa )$ определяется индуктивно $\exp _{0}(\kappa )=\kappa$ и $\exp _{r+1}(\kappa )=2^{\exp _{r}(\kappa )}$ .

Литература

Erdős, P.; Hajnal, A.; Máté, A.; Rado, R. (1984), Combinatorial set theory: partition relations for cardinals, Studies in Logic and the Foundations of Mathematics, vol. 106, Amsterdam: North-Holland Publishing Co., ISBN 0-444-86157-2, MR 0795592
Erdős, P.; Rado, R. (1956), "A partition calculus in set theory.", Bull. Amer. Math. Soc., 62 (5): 427—489, doi:10.1090/S0002-9904-1956-10036-0, MR 0081864

Похожие исследовательские статьи

Мо́щность, или кардина́льное число́, мно́жества — характеристика множеств, обобщающая понятие количества (числа) элементов конечного множества.

Множество всех подмножеств — множество, состоящее из всех подмножеств данного множества $\text{[math]}$ ; обозначается $\text{[math]}$ или $\text{[math]}$ .

Конти́нуум-гипо́теза — выдвинутое в 1877 году Георгом Кантором предположение о том, что любое бесконечное подмножество континуума является либо счётным, либо континуальным. Другими словами, гипотеза предполагает, что мощность континуума — наименьшая, превосходящая мощность счётного множества, и «промежуточных» мощностей между счетным множеством и континуумом нет. В частности, это предположение означает, что для любого бесконечного множества действительных чисел всегда можно установить взаимно-однозначное соответствие либо между элементами этого множества и множеством целых чисел, либо между элементами этого множества и множеством всех действительных чисел.

Пал Э́рдёш — венгерский математик, один из наиболее продуктивных математиков XX века. Работал в самых разных областях современной математики: комбинаторика, теория графов, теория чисел, математический анализ, теория приближений, теория множеств и теория вероятностей. Лауреат множества математических наград, включая премию Вольфа (1983/1984). Основатель премии Эрдёша.

<span class="mw-page-title-main">Теорема Лёвенгейма — Скулема</span>

Теоремы Лёвенгейма — Скулема — несколько теорем теории моделей, утверждающих существование моделей разных мощностей для теорий первого порядка. Различаются следующие теоремы:

Теорема Лёвенгейма — Скулема, слабый вариант — непротиворечивая теория первого порядка в не более чем счётном языке имеет счётную модель.
Теорема Лёвенгейма — Скулема, сильный вариант
- счётная версия — каждая бесконечная модель теории первого порядка в не более чем счётном языке имеет счётную элементарную подмодель.
- несчётная версия — каждая бесконечная модель теории первого порядка в языке $\text{[math]}$ имеет элементарную подмодель мощности меньшей или равной $\text{[math]}$ .
Теорема Лёвенгейма — Скулема о повышении мощности — каждая нормальная бесконечная модель мощности $\text{[math]}$ имеет нормальное элементарное расширение любой мощности, больше $\text{[math]}$ .

Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик.

Теория Рамсея — раздел комбинаторики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.

В математике, в частности в комбинаторике, полиномы Белла — это полиномы вида

\text{[math]}

Гипотеза Эрдёша об арифметических прогрессиях — предположение в аддитивной комбинаторике, сформулированное Палом Эрдёшем, согласно которому в случае, если сумма обратных величин положительных натуральных чисел некоторого множества расходится, то множество содержит сколь угодно длинные арифметические прогрессии.

Теорема Семереди — утверждение комбинаторной теории чисел о наличии длинных арифметических прогрессий в плотных множествах.

Свободное от сумм множество — множество, не включающее суммы своих элементов, используется в аддитивной комбинаторике и аддитивной теории чисел. Формально, подмножество $\text{[math]}$ абелевой группы $\text{[math]}$ является свободным от сумм, если его множество сумм $\text{[math]}$ не пересекается с $\text{[math]}$ . Другими словами, $\text{[math]}$ является свободным от сумм, если уравнение $\text{[math]}$ не имеет решения для $\text{[math]}$ .

В данном списке приводятся математические утверждения и объекты, названные именем венгерского математика Пала Эрдёша.

<span class="mw-page-title-main">Задача со счастливым концом</span>

Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.

Граф Радо — единственный счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов. Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.

Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.

Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа $\text{[math]}$ пусть $\text{[math]}$ является семейством графов, не содержащих $\text{[math]}$ в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа $\text{[math]}$ такая, что графы с $\text{[math]}$ вершинами в $\text{[math]}$ имеют либо клику, либо независимое множество размером $\text{[math]}$ .

Теорема сумм-произведений — теорема арифметической комбинаторики, устанавливающая неструктурированность любого достаточно большого множества относительно хотя бы одной из операций поля. Название обсуловлено тем, что метрикой структурированности относительно той или иной операции является количество различных сумм или произведений, которые можно составить из элементов данного множества.

Множество сумм — концепт аддитивной комбинаторики, соответствующий сумме Минковского конечных множеств.

В теории чисел последовательностью Сидона называется любая последовательность $\text{[math]}$ такая, что все суммы вида $\text{[math]}$ различны. Последовательность может быть конечной или бесконечной — от этого существенно зависит подход к изучению свойств таких последовательностей.

Аддити́вная тео́рия чи́сел — раздел теории чисел, возникший при изучении задач о разложении целых чисел на слагаемые заданного вида.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.