Lpu8

Упражнение 8

На това въпросно упражнение почнахме да си говорим за определимост.. нещо, което определено трябва да се знае.

И така, нека $\varphi$ е фиксирана формула и $\mathrm{Var}^{free} \subseteq \{x_1, x_2, \dots, x_n \}$.
Казваме, че в структурата $\mathcal{A}$ е вярна формулата $\varphi$, записваме $\mathcal{A} \models \varphi [[a_1, a_2, \dots, a_n]]$, където $\langle a_1, a_2, \dots, a_n \rangle \in |A|^n$, когато съществува оценка $v$, такава, че

(1)

\begin{align} \mathcal{A} \underset{v^{x_1, \dots, x_n}_{a_1, \dots, a_n}}\models \varphi \end{align}

Дефиниция (определимост)

$\varphi$ определя множеството

(2)

\begin{align} \{ \langle a_1, a_2, \dots, a_n \rangle \ |\ \mathcal{A} \models \varphi [[a_1, a_2, \dots, a_n]] \} \end{align}

Едно множество е определимо, ако същестува формула, която да го определя¹

пример

В структурата $\langle \mathbb{Z}, \cdot, \dot= \rangle$
е определимо ${0}$ с формулата $\forall x(x \cdot y \dot= y)$.
Забележете че структурата съдържа множеството на целите числа, умножението и равенство. С тези елементи трябва да потройм нашата формула.

Ако имаме примерно структурата $\langle \mathbb{Q}, \cdot \rangle$
няма да е определимо ${0}$ с формулата $\forall x(x \cdot y \dot= y)$, защото в тази формула има $\doteq$ ако не се лъжа нищо не е определимо в тази структура, защото имаме само рационалните числа и операцията умножение(или каквото и да е операция заложена в $\cdot$)

---

Сега ще разгледаме задачата за това, как може да определим обединението, сечението, произведението и разликата на две определени множества.
Нека формулата $\varphi$ е на свободната променлива $x$ и определя множеството $A$, а формулата $\psi$ е на свободната променлива $y$ и определя множеството $B$.
Тогава е вярно, че
множеството $A \cup B$ се определя от формулата $\varphi [\frac{x}{z}] \lor \psi [\frac{y}{z}]$. Тук трябва трябва да направим замяна с една чисто нова променлива $z$, за да няма колизии ;) понеже$x$ може да участва в $\psi$ примерно.
Аналогично
$A \cap B$ се определя от $\varphi[\frac{x}{z}] \land \psi[\frac{y}{z}]$
$A*B$ се определя от $\varphi \land \psi$
$A \setminus B$ се определя от $\varphi[\frac{x}{z}] \land \lnot \psi [\frac{y}{z}]$

$/* \dots */$²

---

Критерий за неопределимост

Изображението

(3)

\begin{align} h : \mathcal{A} \to \mathcal{B} \end{align}

където $\mathcal{A}$ и $\mathcal{B}$ са структури, е хомоморфизъм, ако:

1. $\langle a_1, a_2, \dots, a_n \rangle \in p^{\mathcal{A}} \iff \langle h(a_1), h(a_2, \dots, h(a_n) \rangle \in p^{\mathcal{B}}$
2. $h(f^{\mathcal{A}}(a_1, a_2, \dots, a_n)) = f^{\mathcal{B}}(h(a_1), h(a_2), \dots, h(a_n))$
3. $h(c^{\mathcal{A}}) = c^{\mathcal{B}}, \ \ c - \mathrm{const}$

Ако $\mathcal{A}$ и $\mathcal{B}$ съвпадат, тогава $h$ е автоморфизъм.

Теорема

Нека множеството $X$ е определимо и $h$ е автоморфизъм
Тогава

(4)

\begin{align} \langle a_1, a_2, \dots, a_n \rangle \in X \iff \langle h(a_1), h(a_2), \dots, h(a_n) \rangle \in X \end{align}

Задача 1

Нека е дадено $\langle \mathbb{R}, .\rangle$. Определимо ли е $\mathbb{N}$?
Решение:
Допускаме, че $\mathbb{N}$ е определимо.
Харесваме си следния автоморфизъм

(5)

\begin{align} h(x) = \begin{cases} 0, \ x = 0 \\ \frac{1}{x}, \ x \neq 0 \end{cases} \end{align}

Надявам се, че е ясно, че $h : \mathbb{R} \to \mathbb{R}$

Сега, тъй като $6 \in \mathbb{N}$, то от горната теорема следва, че $h(6) \in \mathbb{N}$, т.е $\frac{1}{6} \in \mathbb{N}$, което очевидно е противоречие. Следователно допускането е грешно и $\mathbb{N}$ е неопределимо. $\Box$

NB: Цялата идея се корени в това, че едно множество няма как да е определимо, ако същестува автоморфозъм на универсума, който го размества (множеството). А идеята на разместването е, че $\mathbb{R}$ отива в $\mathbb{R}$, но $\mathbb{N}$ не отива в $\mathbb{N}$ при един автоморфизъм, примерно $h$.

Задача 2

Дадено ни е $\langle \mathbb{N}, . \rangle$. Ще покажем, че само $\{ 1 \}$ е определимо.

Решение:
Лесната част е да покажем, че $\{ 1 \}$ е определимо като просто напишем следната формула:
$\forall x (x.y = x)$, която го определя.

По-кофти частта е да докажем, че всички други не са определими.
Ще покажем, че $\{2 \}$ примерно е неопределимо множество в $\langle \mathbb{N}, . \rangle$.

Допускаме, че е определимо.

Дефинираме следния хомоморфизъм:
$h(a) = h(2^{\alpha_1} 3^{\alpha_2} \dots ) = 2^{\alpha_2} 3^{\alpha_1} \dots$,
където $a \in \mathbb{N}$ и $a$ се разлага канонично така $a = 2^{\alpha_1} 3^{\alpha_2} \dots$ и $\alpha_i \in \mathbb{N} \cup \{0\}$.
Очевидно е, че е хомоморфизъм, защото запазва умножението.

Тогава имаме, че:
$h(2) = h(2^1 3^0 \dots) = h(2^0 3^1 \dots) = 3$.
Греда. Противоречие. Допускането е грешно и $\{ 2 \}$ не е определимо

Този хомоморфизъм обаче не ни върши работа, ако искаме да докажем, че $\{ 6 \}$ е неопределимо.. примерно, защото
$h(6) = h(2^1 3^1) = h(2^1 3^1) = 6$
Идеята обаче е ясна, нали ;)

Footnotes

1. дъъ

2. Тук май има някакви работи, които са свързани с примера по-горе