# Logika - ćwiczenia 9

### Definiowalność

K klasy struktur "definiowalne" za pomocą jednej formuły pierwszego rzędu $\phi$.

$\mathfrak{K} = \{{\cal A} \mid {\cal A} \vDash \phi\}$

* czy ważne jest czy \phi jest zdaniem (czyli formułą bez zmiennych wolnych)?
Nie, bo $\{{\cal A} $\mid {\cal A} \vDash \phi\} = \{{\cal A} \mid {\cal A} \vDash \overline{\forall}\phi\}$, gdzie $\overline{\forall}\phi$ to domknięcie wszystkich wolnych zmiennych $\phi$ kwantyfikatorami ogólnymi.

* a może w definicji powinna być \phi jest spełnialna w A

$\mathfrak{K} = \{{\cal A} \mid \phi \textrm{ jest spełnialna w } {\cal A}\}$

No podobnie jak wyżej, wystarczy domknąć \phi kwantyfikatorami szczegółowymi.

### Twierdzenie o zwartości
(Nieskończony) zbiór formuł $\Gamma$ jest spełnialny wtw gdy jest skończenie-spełnialny (czyli każdy jego skończony podzbiór jest spełnialny).

Warianty:

(Nieskończony) zbiór formuł $\Gamma$ jest niespełnialny wtw gdy ma skończony niespełnialny podzbiór.

Formuła \psi jest konsekwencją (nieskończonego) zbioru formuł $\Gamma$ wtw, gdy jest konsekwencją jego skończonego podzbioru.

Powiemy, że klasa $\mathfrak{K}$ jest definiowalna (jedną formuł logiki I rzędu), wtw gdy istnieje $\phi$, t. że $\mathfrak{K} = \{{\cal A} \mid {\cal A} \vDash \phi\}$.

Powiemy, że klasa $\mathfrak{K}$ jest aksjomatyzowalna (zbiorem formuł logiki I rzędu), wtw gdy istnieje $\Gamma$, t. że $\mathfrak{K} = \{{\cal A} \mid {\cal A} \vDash \Gamma\}$.

### Problem 2.9.6
"Skończoność" nie jest aksjomatyzowalna za pomocą zbioru formuł I rzędu.

Załóżmy, że jest aksjomatyzowalna za pomocą zbioru $\Delta$.

Napiszmy nieskończony zbiór formuł $\Gamma$, który mówi, że ew. struktura, która miałaby go spełniać jest nieskończona.

$\gamma_n = \exists x_1\dots \exists x_n. x_1 \neq x_2 ∧ \dots ∧ x_{n-1} \neq x_n$

$\Gamma = \{\gamma_n \mid n > 0\}$.

Bierzemy sobie zbiór $\Gamma \cup \Delta$ i... okazuje się, że cały zbiór jest sprzeczny, ale każdy jego skończony podzbiór jest niesprzeczny.

Istotnie, jesli weźmiemy $\Xi \subseteq \Gamma \cup \Delta$, to $\Xi = \Gamma_0 \cup \Delta_0$, gdzie $\Gamma_0 \subseteq \Gamma$ i $\Delta_0 \subseteq \Delta$. Ponieważ $\Gamma_0$ jest skończona, więc istnieje $\gamma_m \in \Gamma_0$, gdzie $m$ to najwyższy numer formuły $\gamma_i$ w $\Gamma_0$. Wtedy dowolna struktura o $m$ elementach spełnia zarówno $\Gamma_0$ jak i $\Delta_0$, bo jest to struktura skończona, a każda struktura skończona spełnia $\Delta$. A zatem $\Xi$ niesprzeczny.

Dostaliśmy więc sprzeczność z tw. o zwartości.

### Aksjomatyzowalność to naprawdę nie to samo, co definiowalność

Teza: klasa struktur nieskończonych nie jest definiowalna (za pomocą 1 formuły), ale jest aksjomatyzowalna (za pomocą zbioru formuł).

Jest aksjomatyzowalna, bo możemy wziąć zbiór formuł $\Gamma$ z poprzedniego zadania.

Nie jest definiowalna za pomocą jednej formuły $\phi$. No bo gdyby była, to za pomocą formuły $¬\phi$ byłaby definiowalna klasa struktur skończonych, a pokazaliśmy że ona nawet nie jest aksjomatyzowalna.

### 2.9.4 Jeśli Klasa i jej dopełnienie są aksjomatyzowalne, to są definiowalne.

$\Delta$ aksjomatyzuje $\mathfrak{K}$
$\Gamma$ aksjomatyzuje dopełnienie $\mathfrak{K}$

Zbiór $\Delta \cup \Gamma$ jest sprzeczny. Stąd, z tw. o zwartości, istnieje skończony podzbiór $\Delta_0 \cup \Gamma_0$ $(\Delta_0 \subseteq \Delta$, $\Gamma_0 \subseteq \Gamma)$.

Rozważmy $\delta = \delta_1 ∧ ... ∧ \delta_n$, gdzie $\Delta_0 = \{\delta_1, ..., \delta_n\}$.

Zbiór $\Gamma \cup \{ \delta \}$ też jest sprzeczyny.

Czy może istnieć ${\cal A} \in -\mathfrak{K}$ (dopełnienie), takie że ${\cal A} \vDash \delta$ ?
NIE, bo $\Gamma \cup \{ \delta \}$ jest sprzeczyny.

A jeśli ${\cal A} \in \mathfrak{K}$, czy ${\cal A} \vDash \delta$ ?
TAK, bo ${\cal A} \vDash \Delta$, a $\delta$ jest koniunkcją podzbioru $\Delta$.

A zatem ${\cal A} \in \mathfrak{K}$ wtw ${\cal A} \vDash \delta$.
Czyli $\delta$ definiuje klasę $\mathfrak{K}$ (a $¬\delta$ definiuje jej dopełnienie.)

### Możliwości:

* klasa i jej dopełnienie są definiowalne 1 formułą
* klasa jest aksjomatyzowalna, a jej dopełnienie nie
* ani klasa ani jej dopełnienie nie są aksjomatyzowalne

### 2.9.10
Czy jest aksjomatyzowalna klasa $\mathfrak{K}$ relacji równoważności z samymi skończonymi klasami abstrakcji?

$\Sigma=\{\sim\}$ - jeden symbol binarny

Załóżmy, że $\mathfrak{K}$ jest aksjomatyzowalna za pomocą zbioru zdań $\Gamma$.

------------------
>* istnieje klasa abstrakcji, która ma co najmniej dwa elementy
>
>$\delta_2 = \exists{x_1 x_2}. x_1 \neq x_2 \land x_1 \sim x_2$
>
>$\delta_n$ - istnieje klasa abstrakcji o co najmniej $n$ elementach
>
>$\Delta = \{ \delta_n \mid n \in N\}$.
>
>Czy teraz $\Gamma \cup \Delta$ jest sprzeczny? NIE, bo relacja na N zbudowana z podziału:
>
>{0},{1,2},{3,4,5},{6,7,8,9}...
>
>będzie należeć do klasy $\mathfrak{K}$ (czyli będzie spełniać $\Gamma$), ale będzie też spełniać każdą formułę $\delta_n$.
>
------------------

Gdyby taki zbiór zdań istniał, to byłby on również dobry dla struktur nad dowolnym rozszerzeniem sygnatury $\Sigma$.

Wprowadźmy zatem nową stałą c, a zatem rozważmy sygnaturę $\Sigma'=\Sigma \cup \{c\}$.

Zróbmy teraz zdania mówiące:
klasa abstrakcji elementu c ma co najmniej n elementów:

$\alpha_2 = \exists{x_1 x_2}. c = x_1 \land x_1 \neq x_2 \land x_1 \sim x_2$

Weźmy $\Xi = \{\alpha_n \mid n \in N\}$.

I teraz $\Gamma \cup \Xi$ będzie naprawdę sprzecznyn zbiorem formuł.
Ale dowolny skończony podzbiór $\Gamma_0 \cup \Xi_0$ jest spełnialny, bo wystarczy wziąć n będące maksymalnym "indeksem" formuły z $\Xi_0$ i strukture o klasach abstrakcji rozmiaru $n+1$, ustalając stałą $c$ dowolnie.
Zgodnie z tw o zwartości to jest niemożliwe.

Czyli nie może istnieć taki zbiór formuł $\Gamma$, czyli klasa relacji równoważności o skończonych klasach abstrakcji nie jest aksjomatyzowalna.

### Tw Skolema-Löwenheima
Jeśli $\Gamma$ ma model nieskończony, to ma model dowolnych mocy $\mathfrak{m} ≥ max(\aleph_0, |\Sigma|)$.

### 2.10.9
Czy klasa struktur ${\cal A} = \langle A, f^{\cal A} \rangle$ nad sygnaturą z jedną funkcją 1-argumentową $f$, w których $|f^{\cal A}(A)| < |A|$ jest aksjomatyzowalna?

Załóżmy, że takie $\Gamma$ istnieje.

$\Delta=\{ \delta_n \mid n \in N \}$

$\delta_n = \exists x_1...x_n. f(x_1) \neq f(x_2) ∧ ... ∧ f(x_{n-1}) \neq f(x_n)$ ($n^2$ formuł atomowych)

Weźmy zbiór $\Gamma \cup \Delta$. Ten zbiór formuł ma model nieskończony, bo wystarczy rozważyć $\langle R, \lfloor \cdot \rfloor \rangle$), ale nie ma modelu mocy $\aleph_0$. Sprzeczność z tw. Skolema-Löwenheima.

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