# Logika - ćwiczenia 13

## Logika drugiego rzędu

$∃R^{(k)} \forall x, R(x,c,t(x,c))$

R - symbol relacyjny (arności k)

### 3.1.1 skończoność jest def. w SO

Skończoność jest niedefiniowalna w FO

nie można napisać formułu FO, która byłaby spełniona <=> model ma skończenie wiele elementów

czy da się napisać formułę (nad jakąś sygnaturą), która miałaby tylko modele nieskończone?

Tak. Dla Σ={f} f - symbol funkcyjny 1-argumentowy

φ = "f jest 1-1" ∧ ¬"f jest na"

ta formuła FO ma tylko modele nieskończone, ale nie wszystkie nieskończone struktury ją spełniają.

A jak to będzie w SO?

ψ = ∀f ("f jest 1-1" -> "f jest na")

ta formuła mówi to samo, co "model jest skończony".

$\psi_S(X)$ - "X jest zbiorem skończonym"

X(a) to to samo co $a \in X$

$\psi_S(X) = \forall F^{(2)}. \psi_F(F,X,X) \land \psi_{11}(F,X,X) \to \psi_{\text{na}}(F,X,X)$
"dla każdej relacji $F^{(2)}$, jeśli F jest funkcją z X w X i do tego różnowartościową, to jest na"

$\psi_F(F,X,Y) = \forall a. X(a) → \exists b. Y(b) ∧ F(a, b) ∧ \forall c. Y(c) ∧ F(a,c) \to b = c$
$\psi_F(F,X,Y)$ - F jest funkcją z X w Y

$\psi_{11}(F,X,Y) = \forall a b c. X(a) \to Y(b) \to Y(c) \to F(a,c) \land F(b, c) \to a = b$
$\psi_{11}(F,X,Y)$ - F jest różnowartościowa z X w Y

$\psi_{\text{na}}(F,X,Y) = \forall b. Y(b) → \exists a. X(a) ∧ F(a, b)$
$\psi_{\text{na}}(F,X,Y)$ - F jest z X na Y
(wszystkie kwantyfikatory powyżej działają "tak daleko jak się da")

### 3.1.2 przeliczalność jest def. w SO

$\psi_C = \exists Y. (\forall a. Y(a)) ∧ \forall X. \neg \psi_S(X) \to \exists F^{(2)}. \psi_F(F, Y, X) \land \psi_{11}(F, Y, X)$

$\psi_C$ - każdy podzbiór nieskończony ma moc niemniejszą niż cały zbiór
(\exists Y potrzebne tylko po to, żeby użyć formułek zdef. wcześniej)

### 3.2.2 tw. (?) S-L nie zachodzi dla logiki SO

"jeśli zbiór formuł ma model nieskończony o mocy nie mniejszej niż moc sygnatury, to ma model dowolnych mocy (nie mniejszych niż moc sygnatury)"

To twierdzenie nie zachodzi, bo formuła $\psi_C$ ma model mocy $\aleph_0$ a nie ma modeli wyższych mocy.

### 3.2.1 tw. (?) o zwartości nie zachodzi dla logiki SO

Ten nieskónczony zbiór formuł:

$\exists Y. (\forall a. Y(a)) ∧ \psi_S(Y)$
"istnieją co najmniej 2 elementy"
...
"istnieje co najmniej n elementów"
...

jest sprzeczny (nie ma modelu), ale każdy jego skończony podzbiór jest niesprzeczny (ma model).

### 3.1.5 domknięcie przechodnie relacji E
$\phi(R)$ - jest domknięciem przechodnim E

$(\forall x y. E(x, y) \to R(x,y)) \land (\forall x y z. R(x,y) \land R(y,z) \to R(x,z))$
$\land (\forall S^{(2)}. (\forall x y. E(x, y) \to S(x,y)) \land (\forall x y z. S(x,y) \land S(y,z) \to S(x,z))$
$\quad \to (\forall x y. R(x,y) \to S(x,y)))$

R zawiera E i R jest przechodnia
i dla każdej S jeśli S zawiera E i S jest przechodnie
&nbsp;&nbsp; to R zawiera się w S

$\alpha(a,b)$ - "z $a$ do $b$ da się dojść w skończonej liczbie kroków po E"

$\alpha(a,b) = \forall R. (\text{R jest domknięciem przechodnim E (formuła powyżej)}) \to R(a,b)$

można by tez napisać "zachodzi R(a,b) dla każdej relacji R zawierającej E i przechodniej"

Czy dałoby się to samo powiedzieć za pomocą jednego kwantyfikatora ogólnego monadycznego drugiego rzędu (czyli kwantyfikatora po podzbiorach, a nie relacjach)?

Tak. Można powiedzieć "b należy do każdego zbioru zawierającego a i zamkniętego zwn krawędzie". ∀MSO

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