# Logika - ćwiczenia 12

## Eliminacja kwantyfikatorów

### zad 4.2.6

$Σ=\{f\}$

Consider the following sentence:
$φ \;≡\; ∀x.f(f(x))=x∧f(x)≠x$
Let $Γ=\{φ,φ_{≥1},φ_{≥2},...\}$ be the set of axioms including φ and infinitely many axioms ensuring that Γ has only infinite models. Is the theory Th(Γ) of the logical consequences of Γ (over the signature Σ) decidable? Is it complete?

$\exists x. \phi_1 \land \ldots \land \phi_n$
$\phi_i$ --- formuła atomowa używająca $x$ lub jej zaprzeczenie

Te $\phi_i$ to są tak naprawdę:

f(f(x)) = f(f(f(f(y)))), gdzie y to też może być x
albo
f(f(f(f(x)))) ≠ f(f(y)), gdzie y to też może być x

Możemy usuwać f-y po dwa, więc mamy (równości - najpierw te, gdzie y to nie x)
1) x = y
2) x = f(y)
3) f(x) = y
4) f(x) = f(y)
5) x = x
6) x = f(x)

Jeśli jakikolwiek phi_i jest postaci 1 lub 2, to całą formułę zastępujemy przez "resztę z f(y) wstawionym na x"

Ponieważ f jest bijekcją, więc 3 jest równoważna f(f(x)) = f(y) tj. x = f(y).
A 4 jest równoważna x=y - czyli możemy zastosować to co w 1 lub 2.

Równość 5 nic nie mówi, więc zastępujemy JĄ przez $\top$ (albo usuwamy).

Równość 6 jest sprzeczna w $\Gamma$, więc cała koniunkcja jest sprzeczna, a zatem całą formułę zastępujemy przez $\bot$.

Pozostaje tylko sytuacja gdy są same nie-równości.
f(x) ≠ y <=> f(x) ≠ f(f(y)) <=> x ≠ f(y)
f(x) ≠ f(y) <=> x ≠ y
A zatem mamy nie-równości postaci (w dwóch pierwszych y to nie x)
1) x ≠ y
2) x ≠ f(y)
3) x ≠ x
4) x ≠ f(x)

Jeśli mamy 3) to zastępujemy całość przez $\bot$.

Jeśli mamy nie-równość 4) to zastępujemy JĄ przez $\top$ (albo usuwamy).

Jesli mamy już tylko 1) i 2), to ponieważ model jest nieskończony, więc zawsze znajdziemy x różny od wymienionych elementów, a zatem cała formuła jest równoważna $\top$.

A zatem teoria jest rozstrzygalna, bo dowolne zdanie (czyli formułę bez zmiennych wolnych) doprowadzimy efektywnie do postaci bez kwantyfikatorów czyli $\top$ lub $\bot$.

Z tego również wynika, że teoria jest zupełna (complete), bo każde zdanie lub jego zaprzeczenie da się doprowadzić do $\top$, a zatem będzie ono (lub jego zaprzeczenie) konsekwencją logiczną naszej teorii.

### Pytanie kontrolne:

Jak weźmiemy dowolny model, to każde zdanie $\phi$ albo w nim zachodzi, albo nie. Czyli jest równoważne albo $\top$ albo $\bot$. Czy z tego wynika, że teoria (każdego) pojedynczego modelu jest rozstrzygalna?

Oczywiście NIE, bo co z tego, że wiemy, że nasze zdanie jest albo równoważne $\top$ albo $\bot$, jeśli nie wiemy (i nie potrafimy efektywnie stwierdzić), która z tych opcji zachodzi.

## Twierdzenie Skolema-Lovenheima

### zad 2.10.11

Prove that the class of all structures isomorphic to ${\cal B}=\langle P(A),∪,∩,⊆ \rangle$, where ∪,∩ are the binary operations of union, resp., intersection, and ⊆ is the set containment relation, is not axiomatisable in first-order logic.

First "for a given infinite A".

To jest niemożliwe, bo taki zbiór formuł wyznaczałby dokładnie moc modeli, co jest sprzeczne w tw S-L.

Second "for any A"

$\{ M \mid \text{istnieje A, że M jest izomorficzny z } \langle P(A), ∪,∩,⊆ \rangle\}$

Załóżmy, że mamy zbiór formuł Γ nad sygnaturą $\Sigma=\{∪,∩,⊆\}$ , który aksjomatyzuje w/w klasę, to ponieważ istnieją nieskończone elementy w tej klasie, zgodnie z Tw. S-L istniałby element o mocy $\aleph_0$. A to jest niemożliwe, bo nie ma zbiorów potęgowych o tej mocy.

### nieaksjomatyzowalność $|r^A| = 2^{|A-r^A|}$
Udowodnij, że klasa wszystkich struktur A nad sygnaturą $Σ^R_1=\{r\}$ ($r$ to symbol relacyjny jednoargumentowy), takich że $|r^A| = 2^{|A-r^A|}$ jest nieaksjomatyzowalna za pomocą żadnego zbioru formuł nad sygnaturą $Σ$.

Przykład nieskończonej struktury, która to spełnia: $\langle R, IQ \rangle$ interpretacją $r$ jest zbiór liczb niewymiernych.

To jest niemożliwe w mocy $\aleph_0$, bo jeśli dopełnienie $r^A$ jest skończone, to $2^{|A-r^A|}$ też, a $|r^A|$ nie, a jeśli dopełnienie $r^A$ jest nieskończone, to $2^{|A-r^A|} = \text{continuum} ≠ |r^A|$.

Czyli nie może istnieć zbiór formuł, który aksjomatyzuje tę klasę.

## Gry EF

### zad 2.12.5
Udowodnij, że rozróżnienie cyklu długości $2^n$ od nieskończonej prostej wymaga formuły o randze kwantyfikatorowej $n+1$.

Sygnatura $Σ_2^R=\{E\}$. Chodzi o grafy symetryczne. Cykl to cykl, a przez prostą rozumiemy np zbiór Z z krawędziami od n do n+1.

Formuła o 3 kw. odróżniająca 2²-cykl od prostej:

$\exists x y. \forall z. z = x ∨ z = y ∨ E(z,x) ∨ E(z,y)$

To się tak łatwo nie chce uogólnić... Może tak:

Formuła $\phi_0(x,y)$ mówi, że punkt y jest odległy od x co najwyżej o $2^0=1$.

$\phi_0(x,y) ≈ y = x ∨ E(y,x)$

$\phi_{i+1}(x,y) ≈ \exists z. \phi_i(x,z) ∧ \phi_i(z,y)$

Formuła o randze kw. n+1 odróżniająca $2^n$-cykl od prostej:

$\forall x \forall y. \phi_{n-1}(x,y)$ - każde dwa elementy są odległe od siebie co nawyżej o $2^{n-1}$

Dlaczego ranga kwantyfikatorowa $n$ nie wystarczy?
Jaka byłaby strategia duplikatora w grze o $n$ rundach?
Pierwsza odpowiedź dowolna, a potem:

Duplikator musiałby utrzymywać niezmiennik:
Jeśli dwa kamienie są "blisko" w jednej strukturze, to są w tej samej odległości (i kolejności) w drugiej (a jeśli są "daleko" w jednej, to są "daleko" w drugiej - wtedy wszysko jedno dokładnie w jakiej odległości).

Pojęcie "blisko" zmienia się z każdą rundą: im bliżej do końca tym mniejsze jest "blisko". Jak jest 0 rund do końca, to "blisko" oznacza 1 (czyli jak jest krawędź w jednej strukturze, to jest krawędź w drugiej - i duplikator wygrywa) i odpowiednio:

Jak jest k rund do końca to "blisko" oznacza $≤2^k$.

Zauważmy, że duplikator zawsze może adekwatnie odpowiedzieć: jeśli spoiler wceluje pomiędzy dwa kamienie, które są "daleko" od siebie (na $k$ rund do końca), to może wcelować "blisko" (w sensie gry o $k-1$ rund do końca) tylko jednego kamienia (bo $2^{k-1}+2^{k-1} \not > 2^k$). Więc nawet jeśli te dalekie kamienie nie są koło siebie, to nie ma to znaczenia.

<div style="height: 3000px"></div>