Мат. лог

[Maximum]

Всем привет)))

Есть задачка: пусть $\Phi$ -- предложение сигнатуры $\sigma=\langle +,\cdot,0,1\rangle$ такое, что для любого $n\in\mathbb{N}$ существует поле $F$ характеристики $p>n$ такое, что $F\vDash\Phi$ (то есть $\Phi$ истинно в $F$). Доказать, что существует поле $F_{0}$ характеристики 0, для которго выполняется $F_{0}\vDash\Phi.$

Я вот чего надумал: раз $\Phi$ везде выполняется, то значит, она как бы не знает, что у полей разные характеристики, то есть в $\Phi$ как бы ничего не говорится о характеристике поля. Получается, что в этом $\Phi$ может находиться только то что выводимо из аксиом поля любой характеристики. Но я не знаю, как это строго доказать Плиз, помогите...

[Профессор Снэйп]

Maximum писал(а):

Я вот чего надумал: раз $\Phi$ везде выполняется, то значит, она как бы не знает, что у полей разные характеристики, то есть в $\Phi$ как бы ничего не говорится о характеристике поля. Получается, что в этом $\Phi$ может находиться только то что выводимо из аксиом поля любой характеристики. Но я не знаю, как это строго доказать Плиз, помогите...

Действительно И ещё

Рассмотрите теорию $\{ \Phi \} \cup \{ 1+1 \neq 0, 1+1+1 \neq 0, \ldots\}$. Эта теория локально совместна (каждая конечная подтеория имеет модель). Значит совместна. Значит...

[Maximum]

Профессор Снэйп писал(а):

Значит...

Имеет модель! А то что вы написали в фигурных скобках это и есть поле характеристики ноль, так ведь? Пасибо)), вы реальный профессор)))

А такую не поможете: построить пример невычислимого множества $A\subset\mathbb{N}$ такого, что А m-сводимо к дополнению А, а дополнение А m-сводимо к А.

[Профессор Снэйп]

Maximum писал(а):

А такую не поможете: построить пример невычислимого множества $A\subset\mathbb{N}$ такого, что А m-сводимо к дополнению А, а дополнение А m-сводимо к А.

Рассмотрите множество

\[ B \oplus \overline{B} = \{ 2x : x \in B \} \cup \{ 2x+1 : x \not\in B \} \]

,

где $B$ --- произвольное невычислимое множество (например, множество проблемы остановки).

Добавлено спустя 1 минуту 49 секунд:

Maximum писал(а):

А то что вы написали в фигурных скобках это и есть поле характеристики ноль, так ведь?

Ну, ещё надо аксиомы поля туда дописать, тогда будет в точности поле характеристики ноль

[Maximum]

Спасибо профессор! Плиз, проверте верно ли я думаю:

взял как вы написали $A=\{2x:x\in B\}\cup\{2x+1:x\not\in B\}$, а теперь дополнение $\overline{A}=\{2x:x\not\in B\}\cup\{2x+1:x\in B\}$, я теперь пишу функцию которая сводит А к его дополнению: $f(n)=(2[n/2]+1)\overline{sg}(rest(n,2))+2[(n-1)/2]sg(rest(n,2))$ и она рекурсивная.

вы клёвый проф))

помогите с такой задачкой: пусть линейные порядки $M=\langle A,\le_{1}\rangle$ и $N=\langle B,\le_{2}\rangle$ упорядочены по типу $\omega^{*}\cdot(\lambda+2+\eta)$ и $\omega^{*}\cdot(\eta+3+\eta)$ соответственно. Доказать, что $Th M\neq Th N.$ здесь $\omega,\lambda,\eta$ это порядковые типы натуральных, действительных и рациональных чисел. надо наверно найти такую формулу, что она верна в М, но неверна в N или наоборот. А как ее построить, тут же только в счетности и несчетности отличие, а я не могу это формулами написать

[Профессор Снэйп]

Maximum писал(а):

...пишу функцию которая сводит А к его дополнению: $f(n)=(2[n/2]+1)\overline{sg}(rest(n,2))+2[(n-1)/2]sg(rest(n,2))$ и она рекурсивная.

Ну да, всё верно. Непонятно только, зачем было чётное число сначала делить на 2, а потом на 2 умножать Проще было бы

\[ f(n) = (n+1) \overline{\mathrm{sg}}(\mathrm{rest}(n,2)) + (n-1) \mathrm{rest}(n,2) \]

Для завершения решения надо ещё обосновать, что множество $A$ невычислимо, но это как раз не проблема.

Maximum писал(а):

помогите с такой задачкой: пусть линейные порядки $M=\langle A,\le_{1}\rangle$ и $N=\langle B,\le_{2}\rangle$ упорядочены по типу $\omega^{*}\cdot(\lambda+2+\eta)$ и $\omega^{*}\cdot(\eta+3+\eta)$ соответственно. Доказать, что $Th M\neq Th N.$ здесь $\omega,\lambda,\eta$ это порядковые типы натуральных, действительных и рациональных чисел. надо наверно найти такую формулу, что она верна в М, но неверна в N или наоборот. А как ее построить, тут же только в счетности и несчетности отличие, а я не могу это формулами написать

Насколько я понял, $\omega^\ast$ --- это "перевёрнутый" порядок $\omega$, то есть порядок по типу отрицательных целых чисел.

Разница здесь не в счётности/несчётности (это действительно ничего не даёт), а в том, что в одном месте стоит двойка, а в другом --- тройка. Этот факт позволяет нам элементарно различить два этих порядка.

Начнём.

\[ \Phi(x) = (\forall y)(x \leqslant y \mathbin{\&} \neg(x=y) \rightarrow \exists z(x \leqslant z \mathbin{\&} \neg (x=z) \mathbin{\&} z \leqslant y \mathbin{\&} \neg(z=y))) \]

\[ \Psi(a) = \Phi(a) \mathbin{\&} \exists b(\Phi(b) \mathbin{\&} a \leqslant b \mathbin{\&} \mathbin \neg(a=b) \mathbin{\&} \forall c(a \leqslant c \mathbin{\&} c \leqslant b \mathbin{\&} \Phi(c) \rightarrow c=a \mathbin{\&} c=b)) \]

\[ \Delta = \exists a_1 \exists a_2(\Psi(a_1) \mathbin{\&} \Psi(a_2) \mathbin{\&} \neg(a_1=a_2)) \]

В какой из моделей предложение $\Delta$ истинно, а в какой нет --- сами разберётесь

Добавлено спустя 14 минут 35 секунд:

P. S. Хорошо у вас мат. логику преподают, на нормальном уровне. У москвичей, по-моему, такие задачки редко увидишь. Откуда Вы? Новосибирск, Казань, Санкт-Петербург?

[Maximum]

Круто Надо ж как вы в логике шарите!

Такая есть: выписать систему аксиом в сигнатуре $\sigma=\langle{\sim}^{2}\rangle$ для класса $K$ всех систем вида $M=\langle A,\sim\rangle$ таких, что ~ - эквивалентность на A, фактор-множество A/~ бесконечно, и каждый класс эквивалентности а/~ из данного фактор-множества тоже бесконечен. Доказать, что теория $Th(K)$ полна.

Мне кажется что в первой части надо выписать только аксиомы рефлексивности, симметричности и транзитивности и написать еще, что есть сколько угодно разных элементов, только как отдельно выписать, что и фактор-множество тоже бесконечно? А во втором вопросе надо наверно доказать что теория омега-категорична. Помогите сделать это. Я из КГУ

[Профессор Снэйп]

Надо записать:

1) Рефлексивность, симметричность, транзитивность.

2) Бесконечный список аксиом: $n$-ая аксиома утверждает, что в каждом классе эквивалентности не менее чем $n$ элементов.
3) Ещё один список аксиом: $n$-ая аксиома утверждает, что существует $n$ попарно не эквивалентных элементов.

Теория получается не более чем счётной сигнатуры и не имеющая конечных моделей, так что полнота действительно следует из $\omega$-категоричности. Тут Вы абсолютно правильно рассуждаете. Доказать же оную категоричность очень просто, так что не буду тут ничего подсказывать. Сами справитесь.

Я эту задачу давал студентам в ноябре на домашку. Правда, там был ещё один пункт: доказать, что теория не является конечно аксиоматизируемой. Сможете это доказать?

P.S. КГУ --- это Казанский ГУ?

[Maximum]

Пасибки! Я в правильном направлении думал. Это супер! А то что она не конечно аксиоматизируема - так это потому что уже во втором пункте надо выписать бесконечно много аксиом

Кстати, вы напомнили мне, что аксиоматизируемые классы надо тоже порешать: говорят, что чум имеет бесконечную ширину, если для любого $n\in\omega$ в данном множестве существует антицепь длины $n$. Доказать, что класс всех чумов бесконечной ширины не является конечно аксиоматизируемым в сигнатуре $sigma$=$\langle \le\rangle$


И есть еще задачки, которые почти по алгоритму решаются, но мне нужен пример такого решения: построить прф $f(t,x,y)$, удовлетворяющую условию: если $t=\lambda(T),$ $x=\nu(M)$, где $M$ - машинное слово в алфавите машины $T,$ то $f(t,x,y)$ равно общему количеству сдвигов головки на одну ячейку влево в процессе переработки слова $M$ в слово $M^{(y)}_T$

[Профессор Снэйп]

Maximum писал(а):

А то что она не конечно аксиоматизируема - так это потому что уже во втором пункте надо выписать бесконечно много аксиом

Ну!.. Вы меня сильно разочаровываете.

Что с того, что наш список аксиом бесконечен? Где гарантия того, что мы не можем написать какой-нибудь совершенно другой список аксиом, который будет конечен и при этом будем задавать тот же самый класс моделей?

[Brukvalub]

Профессор Снэйп писал(а):

Что с того, что наш список аксиом бесконечен?

Это позволяет быстро прийти к правильному ответу (использован Ваш метод)

[Профессор Снэйп]

Brukvalub писал(а):

Профессор Снэйп писал(а):

Что с того, что наш список аксиом бесконечен?

Это позволяет быстро прийти к правильному ответу (использован Ваш метод)

Позоляет и позволяет, прекрасно. Я же не говорю, что аксиомы нельзя задавать бесконечным списком. А прошу доказать, что в данном, конкретном случае этот список нельзя заменить конечным.

Добавлено спустя 5 минут 51 секунду:

Maximum писал(а):

Кстати, вы напомнили мне, что аксиоматизируемые классы надо тоже порешать: говорят, что чум имеет бесконечную ширину, если для любого $n\in\omega$ в данном множестве существует антицепь длины $n$. Доказать, что класс всех чумов бесконечной ширины не является конечно аксиоматизируемым в сигнатуре $sigma$=$\langle \le\rangle$

Чувствуется, что у Вас есть некоторые пробелы в связи с этой темой.

Для начала сформулируйте критерий конечной аксиоматизируемости класса.

Maximum писал(а):

И есть еще задачки, которые почти по алгоритму решаются, но мне нужен пример такого решения: построить прф $f(t,x,y)$, удовлетворяющую условию: если $t=\lambda(T),$ $x=\nu(M)$, где $M$ - машинное слово в алфавите машины $T,$ то $f(t,x,y)$ равно общему количеству сдвигов головки на одну ячейку влево в процессе переработки слова $M$ в слово $M^{(y)}_T$

Тут я Вам ничем помочь не могу, поскольку не знаю конкретики Вашего курса. Различных модификаций машины Тьюринга известно очень много, какую именно вводил Ваш лектор --- мне неведомо. Я не понимаю, что такое $\nu$, что такое $\lambda$, что такое "машинное слово". Если хотите помощи --- дайте ссылку на ваши лекции.

P. S. "Длина" --- это у цепей Для антицепей обычно используют термин "ширина" А лучше всего в обоих случаях говорить "мощность".

[Maximum]

Проф, вы на меня не обиделись? похоже мне надо реабилитироваться. Для этого решу до конца задачку с эквивалентностями.

Профессор Снэйп писал(а):

1) Рефлексивность, симметричность, транзитивность.

1)$\forall x(x\sim x)$
2)$\forall x\forall y(x\sim y\to y\sim x)$
3)$\forall x\forall y\forall z(x\sim y\& y\sim z\to x\sim z)$

Профессор Снэйп писал(а):

2) Бесконечный список аксиом: $n$-ая аксиома утверждает, что в каждом классе эквивалентности не менее чем $n$ элементов.

$n$-я аксома такая:

$$\forall y\exists x_{1}\ldots\exists x_{n}((x_{1}\sim y\&\ldots x_{n}\sim y\&\neg(x_{1}=x_{2}\&\ldots\neg(x_{1}=x_{n})\&\ldots\&\neg(x_{n}= x_{1})\&\ldots\&\neg(x_{n}=x_{n-1}))$$

Профессор Снэйп писал(а):

Ещё один список аксиом: $n$-ая аксиома утверждает, что существует $n$ попарно не эквивалентных элементов.

$n$-я аксиома:
$\exists x_{1}\ldots\exists x_{n}(\neg(x_{1}\sim x_{2})\&\ldots\&\neg(x_{1}\sim x_{n})\&\ldots\&\neg(x_{n-1}\sim x_{n}))$

Профессор Снэйп писал(а):

Теория получается не более чем счётной сигнатуры и не имеющая конечных моделей, так что полнота действительно следует из $\omega$-категоричности. Тут Вы абсолютно правильно рассуждаете. Доказать же оную категоричность очень просто, так что не буду тут ничего подсказывать. Сами справитесь.

Тогда проверяйте. По определению, теория омега-категорична, если все ее модели мощности $\omega$ изоморфны.
Возьмем две модели $M$ и $N$ нашей теории с носителями $A$ и $B$ cоотв. Занумеруем элементы носителей двумя индексами: первый идекс указывает на номер класса эквивалентности а второй на положение в этом классе. короче, чё я парюсь:

$A=\{a_{11},\ldots,a_{1n},\ldots,a_{21},\ldots, a_{2n},\ldots,a_{n1},\ldots\}$ и $B=\{b_{11},\ldots,b_{1n},\ldots,b_{21},\ldots, b_{2n},\ldots,b_{n1},\ldots\}$
и $a_{ij}\sim a_{kl}\quad\Leftrightarrow \quad i=k$, так же для $B$
Иззоморфизм $f\colon M\to N$ такой: $f(a_{ij})=b_{ij}$. тогда понятно, что
$M\vDash a_{ij}\sim a_{kl}\quad \Leftrightarrow\quad N\vDash f(a_{ij})\sim f(a_{kl})$
Да и всё кажись.

Добавлено спустя 45 минут 28 секунд:

Профессор Снэйп писал(а):

Чувствуется, что у Вас есть некоторые пробелы в связи с этой темой.

Для начала сформулируйте критерий конечной аксиоматизируемости класса.

Эт точно. пробелы есть. а какой это критерий? Я знаю типа такого: K конечно акисоматизируем <--> класс $K_{\Sigma}\K$ аксиоматизируем ($K_{\Sigma}$ - это класс всех систем сигнатуры сигма). Но этим тут не воспользоваться!! Я вобще думаю, что в задачке про антицепи надо теорему Мальцева использовать. Проф, помогите её решить.

Цитата:

Тут я Вам ничем помочь не могу, поскольку не знаю конкретики Вашего курса. Различных модификаций машины Тьюринга известно очень много, какую именно вводил Ваш лектор --- мне неведомо.

Сейчас поведую Лента имеет справа конец, а слева - бесконечна (т.е. слева скока хошь можешь ячеек достраивать и записывать в них 0). Команды такие: $q_{i}a_{j}\to q_{k}a_{l}S,$ где $q_{i}$ - состояние, в котором считывающая головка находилась и при этом она указывала на $a_{j},$ $S$ - это влево (L), вправо (R) или головке не смещаться ($\Lambda$). Когда команда выполнилась, состояние становится $q_{k}$, а в ячейку, где было $a_{j}$ записывается $a_{l}.$ Алфавит внешний состоит из 0 и 1. Начальное состояние $q_{1}$, конечное $q_{0}.$ Машинное слово $M=Aq_{i}a_{j}B$ описывает мгновенное состояние машины в состоянии $q_{i},$ когда головка указывает на ячейку, в котрой записано $a_{j}$. $A$ - это слово перед $a_{j}$, $B$ - после. $\lambda$ и $\nu$ - коды машины и слова соотв. Формулы: если $M=Aq_{i}a_{j}B$
$\nu(M)=2^{k_{l}(A)}\cdot 3^{i}\cdot 5^{j}\cdot 7^{k_{r}(B)},$ где
если $A=a_{s_{0}}\ldots a_{s_{k}}, $ то

$$ k_{l}(A)=\prod\limits_{n=0}^{k}p_{n}^{s_{k-n}} $$

$$ k_{r}(A)=\prod\limits_{n=0}^{k}p_{n}^{s_{n}} $$

где $p_{n}$ - n-е простое число ($p_{0}=2,p_{1}=3,\ldots$)

Номер команды $T(i,j)$ :

$$ \mu(T(i,j))=p_{c(i,j)}^{p_{0}^{k}\cdot p_{1}^{l}\cdot p_{2}^{s}}, $$

где $s=0 $ при $T(i,j)=q_{i}a_{j}\to q_{k}a_{l};s=1,$ при $T(i,j)=q_{i}a_{j}\to q_{k}a_{l}L;s=2$ при $T(i,j)=q_{i}a_{j}\to q_{k}a_{l}R$
$c(i,j)$ - канторовская нумерация.
Номер машины $\lambda(T)$ - это произведение всех номеров команд $T_{ij}$ машины $T$.

[Профессор Снэйп]

Всё правильно Вы решили.

С чего Вы взяли, что я на Вас обиделся? Делать мне больше нечего. Только что Вы от меня хотите? На все предыдущие вопросы я ответил,новых Вы не задавали.

Добавлено спустя 11 минут 25 секунд:

Maximum писал(а):

Профессор Снэйп писал(а):

Чувствуется, что у Вас есть некоторые пробелы в связи с этой темой.

Для начала сформулируйте критерий конечной аксиоматизируемости класса.

Эт точно. пробелы есть. а какой это критерий? Я знаю типа такого: K конечно акисоматизируем <--> класс $K_{\Sigma}\K$ аксиоматизируем ($K_{\Sigma}$ - это класс всех систем сигнатуры сигма). Но этим тут не воспользоваться!! Я вобще думаю, что в задачке про антицепи надо теорему Мальцева использовать. Проф, помогите её решить.

Ерунду какую-то Вы написали.

Для начала докажите, что класс $K$ конечно аксиоматизируем тогда и только тогда, когда классы $K$ и $K_\Sigma \setminus K$ аксиоматизируемы. Это и есть тот критерий, который я просил Вас вспомнить. Если Вы занимаетесь по задачнику Лаврова-Максимовой, то это задача 2.9.13 из этого задачника

Добавлено спустя 38 минут 12 секунд:

Maximum писал(а):

И есть еще задачки, которые почти по алгоритму решаются, но мне нужен пример такого решения: построить прф $f(t,x,y)$, удовлетворяющую условию: если $t=\lambda(T),$ $x=\nu(M)$, где $M$ - машинное слово в алфавите машины $T,$ то $f(t,x,y)$ равно общему количеству сдвигов головки на одну ячейку влево в процессе переработки слова $M$ в слово $M^{(y)}_T$

Ага. С $\nu$ и $\lambda$ вроде бы понятно. А $M_T^{(y)}$, если я правильно понял, это слово, описывающее состояние машины после $y$ шагов работы по программе $T$ из состояния, задаваемого словом $M$.

Ну если так, то давайте попробуем.

Пусть $e(i,n)$ --- примитивно рекурсивная функция, такая что если $n>0$, то значение этой функции --- максимальное число $y$, для которого $n$ делится на $p_i^y$. У Вас в курсе наверняка должна быть такая. Правда не знаю, как она у Вас там обозначается. Далее, вводим

\[ g(x) = c(e(1,x),e(2,x)), \]

\[ h(t,x) = \mathrm{rest}(e(2,e(g(x),t)),2). \]

Пусть также $d(t,x,y)$ --- такая примитивно рекурсивная функция, что если $t=\lambda(T)$ и $x=\nu(M)$, то $d(t,x,y) = \nu(M_T^{(y)})$ (наверняка эта функция должна где-то появляться в курсе, правда, не знаю, как она у вас обозначается).

Теперь запишем схему примитивной рекурсии:

\[ \left[\begin{array}{lcl} f(t,x,0) &=& 0 \\ f(t,x,y+1) &=& f(t,x,y) + h(t,d(t,x,y)) \end{array}\right. \]

Так как $f$ получается примитивной рекурсией из примитивно рекурсивных функций, то она примитивно рекурсивна. Проверку того, что она обладает требуемым в задаче свойством (даёт число сдвигов головки влево) оставляю для самостоятельного разбора.

[Maximum]

Функция $d$ обозначается у нас $w.$

Насчет функции $h$ - введена как двухместная, а в схеме примитивной рекурсии получилась трехместной. Это как?

Насчет критерия конечной аксиоматизируемости. Блин, я протупил малец, конечно, $K$ и $K_{\Sigma}\setminus K$ должны быть аксиоматизируемы. В лекциях у нас это доказывалось в обе стороны: в одну - вообще легко, а в другую с помощью теоермы Мальцева. Чёт я не пойму как этот критерий применить к данной задаче. Просто в дополнении к К находится что попало - и чумы и не чумы. Ну да в этом дополнении например есть вумы, а они не аксиоматизируемы. Но из этого же не следует, что и всё дополнение не аксиоматизируемо! аксиоматизируемость она же ведь не наследуется от подмножества на всё множество.