6.4: Вираження відносин у структурі

Template:MathJaxZach

Однією з основних формул використання можна поставити, щоб висловити властивості та відносини\(\Struct M\) в структурі з точки зору\(\Lang L\) примітивів мови\(\Struct M\). Під цим ми маємо на увазі наступне: домен\(\Struct M\) - це сукупність об'єктів. Постійні символи, символи функцій та символи предикатів\(\Struct M\) інтерпретуються деякими об'єктами в\(\Domain M\), функціями та відносинами на\(\Domain M\).\(\Domain M\) Наприклад, якщо\(\Obj A^2_0\) знаходиться в\(\Lang L\), то\(\Struct M\) присвоює йому відношення\(R = \Assign{ {\Obj A^2_0} }{M}\). Тоді формула\(\Atom{\Obj A^2_0}{\Obj v_1, \Obj v_2}\) виражає саме те відношення, в наступному сенсі: якщо змінна присвоєння\(s\) карти\(\Obj v_1\) до\(a \in \Domain{M}\) і\(\Obj v_2\) до\(b \in \Domain M\), то\[Rab \quad\text{ iff}\quad \Sat[,s]{M}{\Atom{\Obj A^2_0}{\Obj v_1, \Obj v_2}}.\nonumber\] Зауважте, що тут ми повинні залучати призначення змінних: ми не можемо просто сказати «\(Rab\)iff\(\Sat{M}{\Atom{\Obj A^2_0}{a, b}}\)», тому що\(a\) і не\(b\) є символами нашої мови: вони є елементами\(\Domain{M}\).

Оскільки ми не просто маємо атомні формули, але можемо об'єднати їх за допомогою логічних зв'язків та кванторів, більш складні формули можуть визначати інші відносини, які безпосередньо не вбудовані\(\Struct M\). Ми зацікавлені в тому, як це зробити, і конкретно, які відносини ми можемо визначити в структурі.

Визначення\(\PageIndex{1}\)

\(A(\Obj v_1,\dots, \Obj v_n)\)Дозволяти бути формулою,\(\Lang L\) в якій тільки\(\Obj v_1\),...,\(\Obj v_n\) відбуваються безкоштовно, і нехай\(\Struct M\) буде структура для\(\Lang L\). \(A(\Obj v_1,\dots, \Obj v_n)\)виражає відношення\(R \subseteq \Domain M^n\) iff\[Ra_1\dots a_n \quad\text{ iff}\quad \Sat[,s]{M}{\Atom{A}{\Obj v_1,\dots, \Obj v_n}}\nonumber\] для будь-якої змінної присвоєння\(s\) with\(s(\Obj v_i) = a_i\) (\(i = 1, \dots, n\)).

Приклад\(\PageIndex{1}\)

У стандартній моделі\(\Struct N\) арифметики формула\(\Obj v_1 < \Obj v_2 \lor \eq[\Obj v_1][\Obj v_2]\) виражає\(\le\) відношення на\(\Nat\). Формула\(\eq[\Obj v_2][\Obj v_1']\) виражає відношення спадкоємця, тобто відношення,\(R \subseteq \Nat^2\) де\(Rnm\) утримується якщо\(m\) є спадкоємцем\(n\). Формула\(\eq[\Obj v_1][\Obj v_2']\) виражає відношення попередника. Формули\(\lexists{\Obj v_3}{(\eqN[\Obj v_3][\Obj 0] \land \eq[\Obj v_2][(\Obj v_1 + \Obj v_3)])}\) і\(\lexists{\Obj v_3}{\eq[(\Obj v_1 + {\Obj v_3}')][v_2]}\) обидва виражають\(\Obj <\) відношення. Це означає, що символ\(<\) присудка насправді є зайвим в мові арифметики; його можна визначити.

Ця ідея не просто цікава в конкретних структурах, але, як правило, кожного разу, коли ми використовуємо мову для опису передбачуваної моделі або моделей, тобто, коли ми розглядаємо теорії. Ці теорії часто містять лише кілька символів предикатів як основні символи, але в області вони використовуються для опису часто багато інших відносин відіграють важливу роль. Якщо ці інші відносини можуть систематично виражатися відносинами, які інтерпретують основні присудні символи мови, ми говоримо, що можемо визначити їх в мові.

Проблема\(\PageIndex{1}\)

Знайдіть формули\(\Lang L_A\), в яких визначають наступні відносини:

1. \(n\)знаходиться між\(i\) і\(j\);

2. \(n\)рівномірно ділить\(m\) (\(m\)тобто кратний\(n\));

3. \(n\)є простим числом (тобто, ніяке число, крім\(1\) і\(n\) рівномірно ділиться\(n\)).

Проблема\(\PageIndex{2}\)

Припустимо, формула\(A(\Obj v_1, \Obj v_2)\) виражає відношення\(R \subseteq \Domain M^2\) в структурі\(\Struct M\). Знайдіть формули, що виражають такі відносини:

1. \(R^{-1}\)зворотна\(R\);

2. відносний товар\(R \mid R\);

Чи можете ви знайти спосіб висловити\(R^+\), перехідне закриття\(R\)?

Проблема\(\PageIndex{3}\)

\(\Lang{L}\)Дозволяти мова, що містить\(<\) лише символ предиката 2-місця (ніяких інших постійних символів, символів функцій або предикатів symbols— крім звичайно\(\eq[][]\)). Нехай\(\Struct{N}\) буде будова така\(\Domain{N} = \Nat\), що, і\(\Assign{<}{N} = \Setabs{\tuple{n,m}}{n < m}\). Доведіть наступне:

1. \(\{ 0 \}\)визначається в\(\Struct{N}\);

2. \(\{ 1 \}\)визначається в\(\Struct{N}\);

3. \(\{ 2 \}\)визначається в\(\Struct{N}\);

4. для кожного\(n \in \Nat\) множина\(\{ n \}\) визначена в\(\Struct{N}\);

5. кожне\(\Domain{N}\) скінченне підмножина визначається в\(\Struct{N}\);

6. кожен\(\Domain{N}\) ко-скінченний підмножина визначається в\(\Struct{N}\) (де\(X \subseteq \Nat\) ко-скінченний iff\(\Nat \setminus X\) є кінцевим).