# Logika - ćwiczenia 6 i 7

### $(∀x∃y.P(x) ∨ Q(y)) → ∀x.P(x) ∨ Q(f(x))$

sygnatura: dwa symb. rel. 1-arg P i Q, jeden symb. funkc. 1-arg f

Przykład struktury, w której ta formuł będzie spełniona:
${\cal A} = \langle A, P^{\cal A}, Q^{\cal A}, f^{\cal A} \rangle$, gdzie
$A = \{1\}$,
$P^{\cal A}=\emptyset$,
$Q^{\cal A}=\emptyset$,
$f^{\cal A}(x)=1$.

W tej strukturze nie zachodzi poprzednik tej implikacji (dla żadnego wartściowania), czyli jeśli $\rho$ jest wartościowaniem, to
${\cal A}, \rho \not \vDash ∀x∃y.P(x)∨Q(y)$, czyli cała implikacja zachodzi, co zapisujemy ${\cal A}, \rho \vDash (∀x∃y.P(x)∨Q(y))→∀x.P(x)∨Q(f(x))$

Inna struktura:

B = {1,2}
P^B = \epmtyset
Q^B = {1}
f^B(x)=1

Poprzednik spełniony, następnik też, więc cała formuła spełniona w tej strukturze.

Jeszcze inna struktura:

C = {1,2}
P^C = \epmtyset
Q^C = {1}
f^C(x)=2
W niej jest spełniony poprzednik, ale nie spełniony następnik, czyli formuła nie jest tautologią.

### $(∀x.P(x) ∨ Q(f(x))) → ∀x∃y.P(x) ∨ Q(y)$

Ta formuła jest tautologią. Istotnie, weźmy dowolną strukturę ${\cal A} = \langle A, P^{\cal A}, Q^{\cal A}, f^{\cal A} \rangle$ i dowolne wartościowanie $\rho$ i pokażmy, że
${\cal A}, \rho \vDash (∀x.P(x) ∨ Q(f(x))) → ∀x∃y.P(x) ∨ Q(y)$.

Założmy, że spełniony jest poprzednik tej implikacji, czyli
${\cal A}, \rho \vDash ∀x.P(x) ∨ Q(f(x))$
To znaczy, że dla dowolnego $a \in A$
${\cal A}, \rho' \vDash P(x) ∨ Q(f(x))$, gdzie $\rho'=\rho[x:=a]$
Mamy pokazać, że zachodzi następnik, czyli że dla dowolnego $a \in A$ zachodzi
${\cal A}, \rho' \vDash \exists y.P(x) ∨ Q(y)$, gdzie $\rho'=\rho[x:=a]$
co oznacza, że musimy wskazać takie $b \in A$, że
${\cal A}, \rho'' \vDash P(x) ∨ Q(y)$, gdzie $\rho''=\rho'[y:=b]$.

Szukanym b będzie $f^{\cal A}(a)$. Istotnie, z zachodzenia poprzednika wiemy, że $a \in P^{\cal A}$ lub $f^{\cal A}(a) \in Q^{\cal A}$, co oznacza,że $a \in P^{\cal A}$ lub $b \in Q^{\cal A}$, a więc ${\cal A}, \rho'' \vDash P(x) ∨ Q(y)$.

Tak więc następnik implikacji zachodzi, czyli cała implikacja też.

## 2.3.4
Pokazać, że ta formuła ma tylko nieskończone modele:
$(∀x.∃y.R(x,y)) ∧ (∀x.¬R(x,x)) ∧ (∀x,y,z.R(x,y)∧R(y,z)→R(x,z))$

Model (z definicji modeli) jest niepusty, więc jak weźmiemy dowolny element $a_0$, to (z I częsci) istnieje $a_1$ i tak dalej $a_2, a_3, ...$, no i z III część oraz II części wszystkie te elementy muszą być parami różne (bo nie może być cykli). Czyli musi być nieskończenie wiele różnych elementów.

## 2.6

A, \rho |= \phi

{\psi_1, \psi_2} |= \phi

|= \psi_1 ∧ \psi_2 → \phi

$\{ \forall x. f^n(x) = x \;|\; \textrm{dla } n=3, 5, 7, 9, 11, ...\} \vDash \forall x. f^{16}(x) = x$

komentarz: \forall x.f(f(f(x)))=x f(f(f(f(f(x)))))=x to są zwykłe formuły

Tak, bo $f^{16}(x) = f^5(f^{11}(x)) = x$ (tak naprawdę należałoby to semantycznie rozpisać podobnie do zad 2 powyżej).

# 2.8

Spec($\psi$) = $\{n \in \mathbb{N} \;|\; \textrm{istnieje model mocy n formuły } \psi\}$
(modele nieskończone nas tu nie interesują; mogą być, mogą nie być, wszystko jedno)

### 2.8.2

Czy dowolny zbiór jednoelementowy liczb naturalnych może być spectrum jakiejś formuły?
$\{n\} = Spec(\phi_n)$,
gdzie $\phi_n = \exists x_1...x_n. x_1 \neq x_2 ∧ ... x_{n-1} \neq x_n ∧ \forall y. y = x_1 ∨ ...∨ y = x_n$

Czy dowolny zbiór skończony liczb naturalnych jest spectrum jakiejś formuły?

Dla dowolnego zbioru skończonego $B = \{n_1,...,n_k\}$, mamy $B=Spec(\phi_{n_1} ∨ ... ∨ \phi_{n_k})$.

Czy dowolny zbiór koskończony liczb naturalnych (czyli taki, który ma skończone dopełnienie) jest spectrum jakiejś formuły?

Tak. Dla dowolnego zbioru koskończonego $C = \mathbb{N}-\{n_1,...,n_k\}$, mamy $C=Spec(¬\phi_{n_1} ∧ ... ∧ ¬\phi_{n_k})$.

### Dopełnienie?

Jeśli B = Spec(\phi), to czy N-B = Spec(¬\phi) ?
Nie, bo może być tak, że ta sama liczba $k \in Spec(\phi)$ oraz $k \in Spec(¬\phi)$

Niech $\psi = \forall x, \exists y, R(x,y)$. Mamy $1 \in Spec(\psi)$, bo jednoelementowy model w którym $R=\{(1,1)\}$ spełnia $\psi$.
Ale mamy też $1 \in Spec(¬\psi)$, bo jednoelementowy model w którym $R=\emptyset$ spełnia $¬\psi$.

### 2.8.3 Czy zbiór niezerowych liczb parzystych to spectrum?

Niech $\psi=\forall x. x \neq f(x) \land f(f(x)) = x$, wtedy $Spec(\psi)$=zbiór liczb parzystych niezerowych

### 2.8.4 Czy zbiór kwadratów liczb całkowitych dodatnich jest spectrum?

U symbol relacyjny 1-argumentowy - pewne elementy (zwane indeksami) będą to U spełniać

x <--> (i_1,i_2)

U×U -> A

f: A×A -> A, która jest bijekcją z U×U w A

------------------------
na przykład:
A = {0,...,24}
f(x,y) = (5*x+y) mod 25
U = {0,...,4}

0, 1, 2, 3, 4, ?, ?, dalej wszystko jedno
5, 6, 7, 8, 9 ... j.w.
10,11,12,13,14
15,16,17,18,19
20,21,22,23,24
....
.....
------------------------

1-1
$\forall a_1, a_2, a_3, a_4 . U(a_1) ∧ U(a_2) ∧ U(a_3) ∧ U(a_4)
∧ (a_1 \neq a_3 ∨ a_2 \neq a_4) →
f(a_1, a_2) \neq f(a_3, a_4)$

na
$\forall x, \exists i_1, i_2. U(i_1) ∧ U(i_2) ∧ f(i_1,i_2) = x$

### 2.8.5 Czy zbiór złożonych (nie-pierwszych) jest spectrum?

n×n - poprzednio

n×m - teraz n>1, m>1

sygnatura:
U,V - symbole predykatów 1-arg
f - symbol funkcyjny 2-arg

struktura:
${\cal A} = \langle A, U^{\cal A}, V^{\cal A}, f^{\cal A} \rangle$, gdzie
$A$ - jakiś zbiór,
$U^{\cal A} - podzbiór A$,
$V^{\cal A} - podzbiór A$,
$f^{\cal A} - funkcja A×A -> A$.

co ma mówić nasza formuła:
$|U^{\cal A}|>1, |V^{\cal A}|>1 \ \ i\ \ f^{\cal A}|_{U×V}$ jest bijekcją z U×V -> A

$\exists u_1, u_2, U(u_1) \land U(u_2) \land u_1 \neq u_2$
∧
$\exists v_1, v_2, V(v_1) \land V(v_2) \land v_1 \neq v_2$
∧
f jest bijekcją z U×V -> A (prawie jak poprzednio)

### 2.8.6 Udowodnij, że zbiór potęg dwójki jest spectrum.

U - "zbiór"
V

A ~ P(U)

a \in A ~~~~ {u_1,u_2,...,u_k}

"u \in a" ... I(u,a)

każde dwa "zbiory" a b się różnią
$\forall a b. a \neq b → \exists u. U(u) ∧ ((I(u,a) ∧ ¬I(u,b)) ∨ (¬I(u,a) ∧ I(u,b)))$
∧
istnieje zbiór pusty (nie piszemu U(u)→ bo jak nic nie ma w I, to nie ma)
$\exists p. \forall u. ¬I(u,p)$
∧
dla każdego a i $u \not \in a$ istnieje $a\cup\{u\}$
$\forall a. \forall u. (U(u) ∧ ¬I(u,a)) → \exists b. \forall v. (I(v, b) ↔ (I(v, a) ∨ v = u))$

I   a b c d e f .... 
u_1   *       *
u_2     *     *
u_3       *
u_4         *

### Zbiór liczb pierwszych jest spectrum

Negacja 2.8.5 jest zła bo może istnieć struktura o mocy np. 12, ale o "złej" funkcji f oraz U V

Można spróbować takiej formuły
jeśli (f jest bijekcja z U×V → A), to |U|=1 lub |V|=1
Tutaj możemy mieć podział liczby 12 na 1×12 i też źle

Rozwiązanie:
wiadomo, że skończone ciała mają charakterystykę (najmniejsza liczba jedynek, których suma to zero 1+...+1=0), która jest liczbą pierwszą. I wtedy liczba elementów ciała to $p^n$, gdzie $p$ jest liczbą pierwszą. Czyli
$\phi$ = aksjomaty ciała
$Spec(\phi)$ = zbiór potęg liczb pierwszych

Jak z tego zrobić po prostu liczby pierwsze? Podpowiedź: zadbać, żeby charakterystyka ciała była również jego mocą... Może w tym pomóc liniowy porządek...

0 < 1 < 1+1 < 1+1+1 < ... < 1+...+1 (p-1 jedynek)

* 0 jest najmniejsze wzgl ≤
$\forall x. 0≤x$
* jeśli x ma następnik, to jest nim x+1
"jesli x ma coś większego od siebie, to istnieje taki y, że jeśli coś jest większe do x to jest większe-równe od y i y = x+1"

Jesli ciało ma $p^k$ (dla k>1) elementów to rozważmy x=1+..+1 (p-1 jedynek)
$x$ ma następnika w porządku, ale x+1=0, czyli ten następnik to nie jest jest x+1.

Przykład ciała 4-elementowego (wiki: ciała Galois)
(0,0): 0 (1,0):1
(0,1) (1,1)

### 2.8.8 Zbiór silni

U - predykat 1-arg
P - f 2-arg

P(a) : U -> U

forall a, P(a) jest bijekcją z U w U

P jest 1-1
forall a b. a <> b -> P(a) <> P(b),
czyli forall b. a!=b -> \exist x. U(x) -> P(a,x) <> P(b,x)

P jest na
i tu może być problem, bo nie możemy kwantyfikować po funkcjach
ale może go obejdziemy :)
istnieje identyczność
$\exists i \forall x. U(x) → P(i,x)=x$
dla każdej permutacji jak zamienimy miejscami dowolne dwa elementy to będzie dobrze
$\forall a .\forall x y. U(x) \land U(y) → \exists b. "b=a[x↔y]"$
$\forall a .\forall x y. U(x) \land U(y) → \exists b. P(b,x)=P(a,y) ∧ P(b,y)=P(a,x) ∧ \forall z. U(z) → z\neq x ∧ z \neq y → P(a,z)=P(b,z)$

W sumie P jes bijekcją z A w "Bijekcje z U w U"

### 2.8.10 czy spectra są zamknięte zwn sumę?

Jeśli A=Spec(\phi), B=Spec(\psi), to czy istnieje \beta taka,
że A\cup B = Spec(\beta) ?

Możemy założyć, że \phi i \psi to zdania (czyli że nie mają zmiennych wolnych)

\beta = \phi ∨ \psi

$M \vDash \phi ∨ \psi$ to znaczy, że $M \vDash \phi$ lub $M \vDash \psi$, to znaczy, że
$|M| \in A$ lub $|M| \in B$, czyli $|M| \in A \cup B$.

W drugą stronę też działa: każdy model \phi możemy przerobić na model \beta.

### 2.8.11 czy spectra są zamknięte zwn przecięcia?

Jeśli A=Spec(\phi), B=Spec(\psi), to czy istnieje \beta taka,
że A\cap B = Spec(\beta) ?

Możemy założyć, że \phi i \psi to zdania (czyli że nie mają zmiennych wolnych)

\beta = \phi ∧ \psi

$M \vDash \phi ∧ \psi$ to znaczy, że $M \vDash \phi$ i $M \vDash \psi$, to znaczy, że
$|M| \in A$ i $|M| \in B$, czyli $|M| \in A \cup B$.
(czyli $Spec(\beta) \subseteq Spec(\phi) \cap Spec(\psi)$ )

Czy w drugą stronę to będzie działać? NIE

$\psi=P(c)$ $Spec(\psi) = N$
$\phi=~P(c)$ $Spec(\phi) = N$
ale $\psi ∧ \phi = P(c) ∧ ¬P(c)$, a zatem $Spec(\psi ∧ \phi)=\emptyset$.

Trzeba "urozłącznić" sygnatury, czyli:

$\beta = P(c) ∧ ¬Q(d)$

Wtedy na "część psi" struktury spełnia $\psi$, a to co jest potrzebne, żeby spełniać $\phi$ jest zrobiona dla kopii symboli $\phi$ i w związku z tym struktura spełnia też $\phi'$, które jest poprawionym $\phi$.

Na przykład: