Logika pierwszego rzędu: gry Ehrenfeuchta-Fraisse'go

Zad. 1

Pokazać, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o tej własności, że dla każdego nieskierowanego (skończonego lub nie) grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw każdy wierzchołek \(\mathfrak{G}\) należy do pewnego (skończonego) cyklu w tym grafie.

Zad. 2

Wykazać, że dla każdego ustalonego skończonego grafu \(\mathfrak{G}\) (ta litera to gotyckie G) i każdego ustalonego \(m\in\mathbb{N}\), następujący problem decyzyjny może zostać rozstrzygnięty przez deterministyczną maszynę Turinga, która obok taśmy z danymi tylko do odczytu ma taśmę roboczą o długości \(O(\log n)\),gdzie \(n\) to rozmiar danych:

Dany: kod skończonego grafu \(\mathfrak{H}\) (gotyckie H) w postaci macierzy incydencji podanej wierszami.
Pytanie: Czy gracz II ma strategię wygrywającą w grze \(G_m(\mathfrak{G},\mathfrak{H})\)?

Rozwiązanie

Należy przejrzeć drzewo gry EF algorytmem min-max.
Jeden wierzchołek drzewa można zapisać używając co najwyżej \(\log n\) bitów - w postaci binarnie napisanego numeru wierzchołka z \( \mathfrak{H}\), bo \(\mathfrak{G}\) jest ustalony i długość zapisu jego wierzchołków jest stała. Głębokośc drzewa wynosi \(2m\), bo jest \(m\) rund po dwa ruchy w każdej.
W liściach sprawdzenie wygranej polega na przetestowaniu, czy pary wierzchołków w węzłach drzewa dają częściowy izomorfizm, co wymaga odliczania pozycji na taśmie wejściowej, do czego wystarczają liczniki o \(\log n\) bitach.
W sumie cały algorytm działa w pamięci \(O(\log n)\).

Zad. 3

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) nie jest aksjomatyzowalna.

Zad. 4

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) nie jest aksjomatyzowalna.

Zad. 5

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest zbiorem skończonym, nie jest definiowalna.

Zad. 6

Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.

Zad. 7

Niech \(\mathfrak{H}^n\) to struktura której uniwersum to hiperkostka \(\{0,1\}^n\), a jednyna relacja dwuargumentowa \(E^{\mathfrak{H}^n}\) będzie zdefiniowana tak:
\(E^{\mathfrak{H}^n}(x,y)\) wtedy i tylko wtedy, gdy \(x\) i \(y\) różnią się dokładnie na jednej pozycji.

Jakie jest maksymalne \(m\) takie, że gracz II ma strategię wygrywającą w grze Ehrenfeuchta-Fraisse'go
\(G_m(\mathfrak{H}^4,\mathfrak{H}^3)\)?

Zad. 8

Pokazać, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o tej własności, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.