Informatyka MIMUW

Ogólna uwaga: Każda klika musi być pokolorowana tyloma kolorami ile ma elementów, żeby każdy trójkąt w niej zawarty był trójkolorowy.

Rozwiązanie I.

Przypuśćmy,że $\Delta$ to żądana aksjomatyzacja. Niech

$\bar\Delta=\Delta\cup\{\exists x_1\ldots\exists x_n\bigwedge_{i,j}E(x_i,x_j)\}$.

Pokazujemy, że $\bar\Delta$ spełnia założenia twierdzenia o zwartości: niech $\Delta_0\subseteq\bar\Delta$ będzie dowolny, skończony.
Niech $N$ to maksymalna liczna kwantyfikatorów w zdaniach z $\Delta_0$ pochodzących spoza $\Delta$. Wówczas klika mocy $N$ spełnia $\Delta_0$, bo daje się pokolorować skończoną liczbą kolorów bez powtarzania kolorów.

Na mocy twierdzenia o zwartości $\bar\Delta$ ma model. Zawiera on kliki każdej skończonej mocy, więc żadna skończona liczba kolorów nie wystarcza do odpowiedniego pokolorowania modelu $\bar\Delta$. Sprzeczność.

Rozwiązanie II.

Niech $\mathfrak{A}$ to struktura składająca się z przeliczalnie wielu przeliczalnych klik jako składowych spójnych.

Pokazujemy, że dla każdego $m$ istnieje struktura $\mathfrak{B}\in\mathcal{A}$ taka, że dla każdego $m$ istnieje struktura $\mathfrak{B}_m$ tkaza, że gracz II ma strategię w grze Ehrenfeuchta-Fraisse o $m$ rundach, granej na $\mathfrak{A}$ i $\mathfrak{B}_m$.

$\mathfrak{B}_m$ to struktura składająca się z przeliczalnie wielu klik mocy $m$ jako składowych spójnych.

Strategia gracza II jest banalna. Jej istnienie wskazuje, że nie istnieje zdanie o randze kwantyfikatorowej $m$ lub mniejszej, które byłoby fałszywe w $\mathfrak{A}$ a jednocześnie prawdziwe w każdej strukturze z $\mathcal{A}$.

Strategia gracza I na trzy rundy:

1. Jeden z wierzchołków o stopniu 2 w $\mathfrak{H}$.
Odpowiedź gracza II dowolna.

2. Wierzchołek w $\mathfrak{G}$ po przeciwnej stronie długiej przekątnej od wierzchołka wybranego przez II w poprzedniej rundzie.
Odpowiedź gracza II dowolna.

3. W $\mathfrak{H}$ pierwszy wybrany wierzchołek ma stopień 2, drugi wybrany wierzchołek ma stopień najwyżej 3. Łącznie wybranych i incydentnych do wybranych jest co najwyżej 7 wierzchołków, podczas gdy wszystkich wierzchołków jest 8. Gracz I wybiera teraz wierzchołek, który nie
był dotąd wybrany ani nie jest incydentny z żadnym z wybranych wierzchołków.
Gracz II nie ma odpowiedzi, bo w $\mathfrak{G}$ wszystkie wierzchołki sa albo wybrane albo incydentne z jednym z wybranych.

Strategia ta przekłada się na zdanie
$\forall x\exists y\forall z (z=x\lor z=y\lor E(z,x) \lor E(z,y)),$
które jest prawdziwe w $\mathfrak{G}$ i fałszywe w $\mathfrak{H}$.

To zdanie nie jest nawet tautologią logiki klasycznej (wartościowanie $r=1, p=0, q=1$), więc tym bardziej nie jest twierdzeniem logiki intuicjonistycznej.