Всем привет!
С мат. логикой голова абсолютно не дружит, но задания на дом никто не отменял.
Цитата:
Теорема (де Брейн, Эрдеш). Если множество вершин графа 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$ (=)](https://dxdy-01.korotkov.co.uk/f/8/f/5/8f5d3fbd71bbe53858b4dcf4ed79c26882.png)
![$A_1^2$ - отношение R на J $A_1^2$ - отношение R на J](https://dxdy-01.korotkov.co.uk/f/8/1/8/818c472f1b0325292f268e81dbab47d782.png)
2) k одноместных предикатных букв (соответствующих тем k множествам, на которые стремимся разбить J)
![$A_1^1...A_k^1$ $A_1^1...A_k^1$](https://dxdy-01.korotkov.co.uk/f/0/9/e/09ebf82096cf5f6a8cd581b94f3645b382.png)
3) предметные константы, по одной для каждого элемента c графа J
![$a_c$ $a_c$](https://dxdy-02.korotkov.co.uk/f/1/a/9/1a9bef2ea3d734f55b14c3c3c87d791b82.png)
Если множество множеств вершин J может быть вполне упорядочено, а всякий его конечный подграф k-хроматическим, то и сам граф J является k-хроматическим.
В качестве собственных аксиом возьмем обычные аксиомы равенства:
1)
![$\exists$xB(x) $\exists$xB(x)](https://dxdy-04.korotkov.co.uk/f/7/3/c/73cb35a92aec30b8d730d06f4c8b020b82.png)
2)
![$\forall$x(A(x)$\to$B(x)), $\exists$xA(x)$\mapsto_c$$\exists$xB(x) $\forall$x(A(x)$\to$B(x)), $\exists$xA(x)$\mapsto_c$$\exists$xB(x)](https://dxdy-02.korotkov.co.uk/f/9/2/5/92512d1706930cbe04f7192916b953ac82.png)
(Правило C("choice"), позволяющее переходить от
![$\exists$xA(x) $\exists$xA(x)](https://dxdy-02.korotkov.co.uk/f/d/5/c/d5cc2ae705aaf266e15c17e665ee3c3782.png)
к
![$A(b)$ $A(b)$](https://dxdy-03.korotkov.co.uk/f/e/8/6/e86796590e6be2167c801d3505aff7c182.png)
)
![+ +](https://dxdy-03.korotkov.co.uk/f/2/6/b/26b17225b626fb9238849fd60eabdf6082.png)
следующие формулы
1)
![$\neg$$A_2^2(x,x)$ - иррефлексивность R $\neg$$A_2^2(x,x)$ - иррефлексивность R](https://dxdy-03.korotkov.co.uk/f/6/0/9/6090cf0365d4237ae32ea0a5f88f9f4c82.png)
2)
![$A_2^2(x,y)$\to$A_2^2(y,x)$ - симметричность R $A_2^2(x,y)$\to$A_2^2(y,x)$ - симметричность R](https://dxdy-02.korotkov.co.uk/f/d/2/8/d280302f83b8f64f4d778274e7e995a682.png)
3)
![$\forall$$x(A_1^1(x)V...VA_k^1(x))$ - разбиение на k классов $\forall$$x(A_1^1(x)V...VA_k^1(x))$ - разбиение на k классов](https://dxdy-02.korotkov.co.uk/f/5/0/6/506c3315d1f95fe2b6e21138fa91839b82.png)
4)
![$\forall$$\neg$$(A_i^1(x)&A_j^1(x))$ - для 1$\leqslant$i<j$\leqslant$k (попарно не пересекаются) $\forall$$\neg$$(A_i^1(x)&A_j^1(x))$ - для 1$\leqslant$i<j$\leqslant$k (попарно не пересекаются)](https://dxdy-01.korotkov.co.uk/f/c/7/8/c78cca475874803f39554f227ee54e9882.png)
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 $\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](https://dxdy-04.korotkov.co.uk/f/7/2/0/72044f8e6dd7f3a3c715d613268cb24a82.png)
6)
![$a_b \neq a_c$ $a_b \neq a_c$](https://dxdy-04.korotkov.co.uk/f/3/3/8/33894f982f90babc8a2deef6d98ac75382.png)
![- для любых 2-х различных элементов b, c из графа J - для любых 2-х различных элементов b, c из графа J](https://dxdy-02.korotkov.co.uk/f/1/b/7/1b7ef7b56ee4265d7b28019ce94e7a7f82.png)
7)
![$A_2^2(a_b, a_c)$ $A_2^2(a_b, a_c)$](https://dxdy-01.korotkov.co.uk/f/0/9/f/09f2fa146883a8dfea27f4e6f28c298c82.png)
![- для любых 2-х различных элементов b, c из графа J, для которых - для любых 2-х различных элементов b, c из графа J, для которых](https://dxdy-04.korotkov.co.uk/f/b/8/7/b874ed4470e8e31b14cb48099f9ab8c982.png)
R(b,c)
Рассмотрим произведение конечного множества этих аксиом. Поэтому соответствующий подграф
![{c_1...c_n} {c_1...c_n}](https://dxdy-04.korotkov.co.uk/f/f/3/1/f313b213033c23db815f62460e0bb44282.png)
конечен и, по предположению, к-хроматический. Означает, что данное конечное множество аксиом имеет модель и поэтому непротиворечиво. Из непротиворечивости всякого конечного множества аксиом т. К
![$\to$ $\to$](https://dxdy-03.korotkov.co.uk/f/e/4/9/e49c6dac8af82421dba6bed976a80bd982.png)
непротиворечивость теории K. Видим, что т. К удовлетворяет всем условиям следствия 2.35(1) и поэтому имеет нормальную модель, мощность которой меньше или равна мощности графа J. Эта модель является k-хроматическим графом, в силу 6-7 содержит граф J в качестве подграфа.