# Logika - ćwiczenia 10

### Definicje
$A$ i $B$ to struktury nad pewną sygnaturą.

$A \cong B$ oznacza, że $A$ i $B$ izomorficzne

$A \equiv B$ oznacza, że $A$ i $B$ elemetarnie równoważne (prawdziwie są te same zdania logiki pierwszego rzędu)

$A \equiv_m B$ oznacza, że $A$ i $B$ m-elemetarnie równoważne (prawdziwie są te same zdania logiki pierwszego rzędu o randze kwantyfikatorowej nie większej niż m)

### Pytania:

1. Czy jeśli $A \cong B$ to $A \equiv B$ ? TAK
2. Czy jeśli $A \equiv B$ to $A \cong B$ ? NIE, bo $\langle Q, ≤ \rangle$ i $\langle R, ≤ \rangle$ są elementarnie równoważne, ale oczywiście nie są izomorficzne.
3. Czy jeśli $A \equiv B$ oraz $A$ i $B$ są skończone, to $A \cong B$ ? TAK, bo możemy opisać strukturę skończoną z dokładnością do izomorfizmu.

### Czy izomorficzne są struktury $A=\langle R, + \rangle$ i $B=\langle R, * \rangle$ ?

$\Sigma=\{f\}$ - jeden symbol 2-argumentowy
Jego interpretacją w A jest dodawanie, a w B - mnożenie
$f^A(x,y) = x+y$
$f^B(x,y) = x*y$

$\exists a \forall b. f(a,b) = a$
prawdziwa w B i fałszywa w A.
Czyli A i B nie są elementarnie równoważne, a zatem nie są izomorficzne.

### Czy izomorficzne są struktury $A=\langle R, + \rangle$ i $B=\langle R_+, * \rangle$ ?

Szukanym izomorfizmem z A do B będzie funkcja wykładnicza $i(x)=e^x$.
$i(x+y) = i(x)*i(y)$, to jest prawda, bo $e^{x+y} = e^x * e^y$.

## Gry E-F

Od gier E-F ograniczamy się do sygnatur relacyjnych - czyli tylko z symbolami relacyjnymi. Jak są symbole funkcyjne to też się da, ale jest więcej zamieszania - nie ma takich ładnych odpowiedniości...


### Przystawanie modulo 2 i podzielność
Dany jest zbiór $X=\{1,2,3,4...,15\}$ i dwie relacje: przystawanie mod 2 oraz podzielność.
$A = \langle X, \equiv_{(mod\, 2)} \rangle, \quad B = \langle X, \;|\; \rangle$

$\Sigma=\{R\}$ - jeden symbol relacyjny dwuargumentowy

Obie relacje są zwrotne, dlatego Duplikator ma strategię w grze z 1 rundą.

A w 2 rundach?

$\exists a b. R(a,b) ∧ ¬R(b,a)$

Czyli strategię ma Spoiler.

### Przystawanie modulo 2 i domknięcie symetryczne podzielności
Utrudnijmy nieco: A bez zmian, B = <X, r > gdzie r to suma $|$ i $|^{-1}$ (r(x,y) zachodzi wtw gdy x|y lub y|x).
Znów oczywiście Duplikator ma strategię w grze 1 rundowej, ale w grze 2 rundowej strategię ma Spoiler: wybrać 1 w B, a potem "zły" element w A.

$\exists a \forall b. R(a,b)$

To jest prawdziwe w B, bo 1 jest ze wszystkimi w relacji R.

### 4-klika + 2 vs 3-klika + 3

Duplikator ma strategię wygrywającą w 3 rundach.
W 4 rundach wygrywa Spoiler: wskazuje 4 połączone wierzchołki w str. lewej (albo 4 niepołączone w prawej). Oto formuła:

$\exists a, b, c, d. E(a, b) \land E(a, c) \land E(a, d) \land E(b, c) \land E(b, d) \land E(c, d)$

### H3 i H4 (hiperkostka wymiaru 3 i 4)

"istnieje wierzchołek stopnia 4" - 5 kwantyfikatorów

"istnieje 5 wierzchołków niepołączonych żadną krawędzią" - 5 kwant.

"każde 2 wierzchołki są połączone dwoma pośrednikami" - 4 kwant.


"istnieją 2 wierzchołki, że każdy inny jest połączony z którymś z nich"
W H3 to prawda, w H4 nie, bo kążdy wierzchołek ma tylko 4 sąsiadów, czyli łącznie "ogarniamy" tylko 10 wierzchołków, a jest 16...
(3 kwantyfikatory)

$\exists a b \forall c. c=a ∨ c=b ∨ E(c,a) ∨ E(c,b)$

Strategia Duplikatora w grze z 2 rundami jest oczywista: odpowiadamy, żeby zachować połączenie lub jego brak - zawsze się da, bo nie ma wierzchołków izolowanych, ani połączonych ze wszystkimi innymi.

## Nieaksjomatyzowalność klasy struktur ${\cal K}$

Z wykładu:

Fakt 1. Jeśli dla każdego $m \in N$ istnieją $A_m, B_m$, takie że $A_m \in {\cal K}$, $B_m \not \in {\cal K}$ i $A_m \equiv_m B_m$ dla każdego $m$ to klasa ${\cal K}$ nie jest definiowalna jednym zdaniem.

Fakt 2. Jeśli istnieje $B \not \in {\cal K}$ i dla każdego $m \in N$ istnieje $A_m \in {\cal K}$ i $A_m \equiv_m B$ to klasa ${\cal K}$ nie jest aksjomatyzowalna (może tak być, że wszystkie $A_m$ to jedna i ta sama struktura $A \in {\cal K}$ )

### Zadanie
Udowodnij, że klasa ${\cal K}$ wszystkich struktur $\langle A, r^A \rangle$, gdzie $r$ jest symbolem relacyjnym jednoargumentowym, takich że $|r^A|=|A-r^A|$ nie jest aksjomatyzowalna.

Wystarczy wziąć $B = \langle R, Q \rangle$ i $A = \langle N, Parz \rangle$. Strategia Duplikatora polega na wybieraniu elementów spełniających lub nie r -- tak samo jak Spoiler.

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