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.

Informatyka MIMUW