K-хроматические графы

[gurukamu]

Всем привет!
С мат. логикой голова абсолютно не дружит, но задания на дом никто не отменял.

Цитата:

Теорема (де Брейн, Эрдеш). Если множество вершин графа G может быть вполне упорядочено, а всякий его подграф k-хроматический, то и сам граф G - k-хроматический.
Доказать, построив теории I порядка с равенством (см. Э. Мендельсон. Введение в мат. лог. М., 1971.: гл.2 «Теории I порядка»; § 12 ; с. 109). Привести обычное мат. доказательство (см. О. Оре. Теория графов. М. 2009.: Гл. 14 «Хроматические графы»; Теорема 14.1.3.; с. 294).

С обычным мат. доказательством вроде как разобрался, а с теориями I порядка - нет.
В мендельсоне указан список аксиом для обобщенной теории K первого порядка с равенством, но как на их основе построить частные теории с равенством - не понимаю. И сколько их должно быть и какие именно тоже тайна.

Некоторая информация из мендельсона:

Всякий граф можно рассматривать как множество, частично упорядоченной некоторым бинарным симметричным отношением R (т.е. отношением, выполненным для любых двух вершин тогда и только тогда, когда эти вершины соединены ребром)
Назовем граф k-хроматическим, если он может быть разбит на k попарно непрекращающихся множеств так, чтобы никакие 2 элемента из одного и того же множества не были связаны отношением R. Для доказательства построим обобщенную теорему K первого порядка с равенством.

В этой теории будут иметься:
1) две двуместные предикатные буквы
$A_1^2$ (=)
$A_1^2$ - отношение R на J
2) k одноместных предикатных букв (соответствующих тем k множествам, на которые стремимся разбить J)
$A_1^1...A_k^1$
3) предметные константы, по одной для каждого элемента c графа J
$a_c$

Если множество множеств вершин J может быть вполне упорядочено, а всякий его конечный подграф k-хроматическим, то и сам граф J является k-хроматическим.

В качестве собственных аксиом возьмем обычные аксиомы равенства:
1) $\exists$xB(x)
2) $\forall$x(A(x)$\to$B(x)), $\exists$xA(x)$\mapsto_c$$\exists$xB(x)
(Правило C("choice"), позволяющее переходить от $\exists$xA(x) к $A(b)$)
+ следующие формулы
1) $\neg$$A_2^2(x,x)$ - иррефлексивность R
2) $A_2^2(x,y)$\to$A_2^2(y,x)$ - симметричность R
3) $\forall$$x(A_1^1(x)V...VA_k^1(x))$ - разбиение на k классов
4) $\forall$$\neg$$(A_i^1(x)&A_j^1(x))$ - для 1$\leqslant$i<j$\leqslant$k (попарно не пересекаются)
5) $\forall$x$\forall$$y$($A_i^1(x)\bigwedge A_i^1(y)\to \neg A_2^2(x,y)) - для 1$\leqslant$i$\leqslant$k никакие два элемента одного и того же класса не связаны отношением R
6) $a_b \neq a_c$- для любых 2-х различных элементов b, c из графа J
7) $A_2^2(a_b, a_c)$- для любых 2-х различных элементов b, c из графа J, для которых R(b,c)

Рассмотрим произведение конечного множества этих аксиом. Поэтому соответствующий подграф {c_1...c_n} конечен и, по предположению, к-хроматический. Означает, что данное конечное множество аксиом имеет модель и поэтому непротиворечиво. Из непротиворечивости всякого конечного множества аксиом т. К $\to$ непротиворечивость теории K. Видим, что т. К удовлетворяет всем условиям следствия 2.35(1) и поэтому имеет нормальную модель, мощность которой меньше или равна мощности графа J. Эта модель является k-хроматическим графом, в силу 6-7 содержит граф J в качестве подграфа.

[zhoraster]

Тема перемещена из Помогите решить/разобраться (М) в Карантин по следующим причинам:
- формулы надо набирать в нотации $\TeX$. Как это делать, можно посмотреть в теме Краткий ФАК по тегу [math];
- не допускается выкладывать картинки, которые можно заменить текстом или формулами.

Исправьте все свои ошибки и сообщите об этом в теме Сообщение в карантине исправлено.

Также в качестве полезного чтения рекомендую Правила научного форума.

[zhoraster]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»