Lpu9

Упражнение 9


страницата се нуждае от дописване/преглеждане


Ще порешаваме още малко задачи за определимост (виж това).

Още задачи за определимост

Задача 1

Кои множества са определими в $\langle \mathbb{Z}, \cdot, \dot= \rangle$.
Ще покажем за $\{ 0 \}, \{ 1 \}, \{ -1 \}$:

  1. $\{ 0 \}$ : Ще използваме че произволно число по нула е нула (и няма други с това свойство): $\forall x(x \cdot y \dot= y)$;
  2. $\{ 1 \}$ : Ще иползваме, че произволно число по едно е самото число (и няма други с това свойство) : $\forall x (x \cdot y \dot= x)$;
  3. $\{ -1 \}$ : Ще използваме, че $-1 * -1 == 1$ и няма друго с това свойство. Разбира трябва да си дефинираме и 1 вътре (защото не може да #include-нем горното :)) $\exists y(\forall x(x \cdot y \dot= x) \And z \cdot z \dot= y \And \lnot z \dot= y)$ - тук $y$ ще бъде 1, а $z$ е удовлетворено само от $-1$.

Сега ще покажем, че всички други синглетони (множества от по едно число) не са определими: Ще покажем как се прави за $\{ 2 \}$ за другите аналогично. Нека дефинираме автоморфизъм $h$ който размества 2 и 3 (2 прости числа). С други думи $h(a) = 2^x 3^y \dots = 2^y 3^x \dots$1 - просто виждаме на кои степени участват 2 и 3 в каноничното разлагане на $a$ и ги променяме (степента на 2 става степен на 3 и обратно). По този начин не е трудно да се убедим, че това наистина е хомоморфизъм (трябва да запазва операцията), именно $h(a) \cdot h(b) = h(a \cdot b)$. С този автоморфизъм $\{ 2 \}$ отива в $\{ 3 \}$ следователно $\{ 2 \}$ не е определимо.

Задача 2

Кои са определими в $\langle \mathbb{Q}, + \rangle$?
По аналогични разсъждения намираме, че $\{ 0 \}$ е определимо, а всички други числа могат да бъдат разместени с автоморфизма $h(x) = 2x$.

Задача 3

Кои са определими в $\langle \mathbb{Q}, \cdot \rangle$?
Аналогично показваме, за $\{ 0 \}, \{ -1 \}, \{ 1 \}$. За да покажем за останалите може да използваме 2 подхода:

  • разместване на две прости - в този случай обаче трябва да разместваме и в числителя и в знаменателя (едновременно) да не вземе да се изпосъкрати нещо;
  • $h(x) = \begin{cases} 0 & x = 0 \\ \frac{1}{x} & x \ne 0 \end{cases}$ - това размества всички синглетони с изключение на вече определените.

Задача 4

Кои са определими в $\langle \mathbb{N}, < \rangle$.
На лекции е показвано, че:

  • всички крайни множества са определими - дефинираме си първо 0, после 1, итн - всяко естествено, след което лесно образуваме обединение на произволен брой (но краен) естествени.
  • всички безкрайни, които са допълнение на крайни (например $\mathbb{N} \setminus \{ 0, 2, 5, 1321 \}$) - това става просто като сложим едно отрицание пред горните - показвано е.
  • за останалите (чудите се дали има още ли - ами примерно простите - безкрайно е и допълнението му не е крайно :-/) се доказва (сложно) че не може. Не ни е работа сега да го правим :)

Задача 5

Кои са определими в $\langle \mathbb{R}, + \rangle$.
Като при $\mathbb{Q}$.

Задача 6

Може ли да се определи $\mathbb{Q}$ в $\langle \mathbb{R}, \cdot \rangle$.
Ами не - използваме биекцията $h(x) = x^3$ наобратно :) (самата биекция не размества $\mathbb{Q}$ но обратната функция на $h$ - т.е $h^{-1}$ го размества, с други думи казано корен трети върши работа). Просто обръщам внимание, че може да вземем явна фукция и да я обърнем (може обърнатата да не е well-known) - важното е да върши работа.

Задача 7

Може ли да се определи $\{ \frac{1}{2} \}$ в $\langle \mathbb{Q}, 0, 1, < \rangle$.
Ще покажем, че не може.
Тук трябва да подходим малко по-различно. Някак е очевидно, че ако разместим числата в интервала $(0, 1)$ така, че относителния им ред да не се промени (т.е биекцията трябва да запази $<$), но от друга страна да се посбият леко числата към единия или другия край - т.е да станат 'по-гъсти' - така ще може да разместим $\{ \frac{1}{2} \}$. За да опишем процеса формално е достатъчно да си изберем точно две рационални числа от $(0, 1)$ - нека ги кръстим с $p, q$. Ще опитаме да направим биекцията, така че $h(p) = q$, и всички числа преди $p$ отиват преди $q$, всички числа след $p$ отиват след $q$:

(1)
\begin{align} h(a) = \begin{cases} \frac{a}{p} \cdot q & a < p \\ q & a = p \\ \frac{a-p}{1-p} \cdot (1-q) + q & a > p \\ \end{cases} \end{align}

Лесно се проверява,че това е биекция и запазва знака.
Друг вариант да се опише (по-нагледно) е геометрично:
sq
Това е графиката на гореописаната функция за $p = \frac{1}{2}, q = \frac{1}{4}$. (който не вярва да си я начертае сам с математика ;)).

Задача 8

Да разгледаме Език с един двуместен предикат $p$ и структура с универсум всички затворени кръгове в реалната равнина, като предиката определя дали две кръгчета имат обща точка.
Да се определят:
(1) съвпадение на кръгчета;
(2) включване на кръгче в друго;
(3) вътрешно допиране на описаните окръжности на кръгчетата;
(4) външно допиране на описаните окръжности на кръгчетата;
(5) включване на кръгче в друго без окръжностите им да се допират;

Решение: Ще си кръщаваме формулите които дефинираме за всяка точка, за да може да ги ползваме в следващите точки:
(1) Двете кръгчета са еднакви относно предиката.

(2)
\begin{align} \mathrm{Eq}(x, y) \rightleftharpoons \forall z(p(x, z) \iff p(y, z)) \end{align}

(2) За всяко кръгче което пресича вътрешното трябва да пресича и външното.

(3)
\begin{align} \mathrm{In}(x, y) \rightleftharpoons \forall z(p(x, z) \Rightarrow p(y, z)) \end{align}

(3) Тук е малко по-усукано: Трябва първото да е във второто, да съществува такова, което пресича и двете (но е външно за второто) такова че всяко негово вътрешно или пресича и 2те начални или не ги пресича и 2те. Един вид $z$ е такова, което се допира външно до 2те, а $t$ е вътрешно за $z$, което или не допира и 2те, или ако допира едното трябва да допира и другото( в същата точка).

(4)
\begin{align} \mathrm{InT}(x, y) \rightleftharpoons \mathrm{In}(x, y) \And \exists z\bigg(\lnot \mathrm{In}(z, y) \And p(x, z) \And p(y, z) \And \forall t\Big(\mathrm{In}(t, z) \Rightarrow \big(p(t, x) \And p(t, y)\big) \lor \big(\lnot p(t, x) \And \lnot p(t, y)\big)\Big)\bigg) \end{align}

(4) Сега ще използваме горното:

(5)
\begin{align} \mathrm{OutT}(x, y) \rightleftharpoons p(x, y) \And \forall z(\mathrm{In}(z, x) \And p(z, y) \Rightarrow \mathrm{InT}(z, x)) \end{align}

(5)

(6)
\begin{align} \mathrm{InR}(x, y) \rightleftharpoons \mathrm{In}(x, y) \And \lnot \mathrm{InT}(x, y) \end{align}

Задачи за изпълнимост

Тук задачата е по дадена формула да кажем структура, в която да е изпълнена. В долната задача асистента казваше формули, ние структури, като всяка следваща формула не си противоречеше с горната (т.е съществуваха структури, които удовлетворяваха и двете), но чупеше нашата последно избрана структура (за да измислим нова):

(1) $\forall x \forall y \forall z(p(x, y) \And p(y, z) \Rightarrow p(x, z))$ - с други думи има транзитивен предикат.
(отговор): $\langle \mathbb{N}, < \rangle$
(2) $\forall x \exists y (p(y, x))$.
(отговор): $\langle \mathbb{Z}, < \rangle$
(3) $\exists x p(x, x)$
(отговор): $\langle \mathbb{Z}, \le \rangle$
(4) $\exists x \lnot p(x, x)$
(отговор): $\langle \mathbb{Z}, \{ \langle x, y \rangle | x < y \lor (x = y \And \mathrm{Even}(x)) \} \rangle$ - с други думи само четните числа са по-малки или равни от тях самите.
(5) $\exists x \forall y \lnot p(x, y)$
(отговор): $\langle \mathbb{Z}, \{ \langle x, y \rangle | (x < y \lor (x = y \And \mathrm{Even}(x))) \And x \ne 0 \} \rangle$.
(6) $\forall x \forall y \exists z (p(x, y) \Rightarrow p(x, z) \And p(z, y))$
(отговор): $\langle \mathbb{Z}, \{ \langle x, y \rangle | (x < y \lor (x = y \And \mathrm{Even}(x))) \And x \ne 1 \} \rangle$.
Оказа се, че има и малко по просто решение (:
gr1
(7) $\exists x (\lnot p(x , x) \And \exists y p(x, y))$ - този пример чупи само графа.
Ето и малко усложнения граф, който хваща 7:
gr2

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License