2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Мат. лог
Сообщение24.12.2007, 13:32 


04/12/06
70
Всем привет)))

Есть задачка: пусть $\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$ может находиться только то что выводимо из аксиом поля любой характеристики. Но я не знаю, как это строго доказать :( Плиз, помогите...

 Профиль  
                  
 
 Re: Мат. лог
Сообщение24.12.2007, 18:35 
Заморожен
Аватара пользователя


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


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

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

 Профиль  
                  
 
 
Сообщение24.12.2007, 20:05 


04/12/06
70
Профессор Снэйп писал(а):
Значит...
Имеет модель! А то что вы написали в фигурных скобках это и есть поле характеристики ноль, так ведь? Пасибо)), вы реальный профессор)))

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

 Профиль  
                  
 
 
Сообщение25.12.2007, 06:59 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
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 писал(а):
А то что вы написали в фигурных скобках это и есть поле характеристики ноль, так ведь?


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

 Профиль  
                  
 
 
Сообщение25.12.2007, 16:27 


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

взял как вы написали $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))$ и она рекурсивная.

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

помогите с такой задачкой: пусть линейные порядки $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 или наоборот. А как ее построить, тут же только в счетности и несчетности отличие, а я не могу это формулами написать :cry:

 Профиль  
                  
 
 
Сообщение25.12.2007, 18:12 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
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 или наоборот. А как ее построить, тут же только в счетности и несчетности отличие, а я не могу это формулами написать :cry:


Насколько я понял, $\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. Хорошо у вас мат. логику преподают, на нормальном уровне. У москвичей, по-моему, такие задачки редко увидишь. Откуда Вы? Новосибирск, Казань, Санкт-Петербург?

 Профиль  
                  
 
 
Сообщение25.12.2007, 20:22 


04/12/06
70
Круто :wink: Надо ж как вы в логике шарите! 8-)

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

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

 Профиль  
                  
 
 
Сообщение26.12.2007, 07:08 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Надо записать:

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение26.12.2007, 14:40 


04/12/06
70
Пасибки! :) Я в правильном направлении думал. Это супер! А то что она не конечно аксиоматизируема - так это потому что уже во втором пункте надо выписать бесконечно много аксиом :D

Кстати, вы напомнили мне, что аксиоматизируемые классы надо тоже порешать: говорят, что чум имеет бесконечную ширину, если для любого $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$

 Профиль  
                  
 
 
Сообщение26.12.2007, 15:27 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Maximum писал(а):
А то что она не конечно аксиоматизируема - так это потому что уже во втором пункте надо выписать бесконечно много аксиом :D


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

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

 Профиль  
                  
 
 
Сообщение26.12.2007, 15:32 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Профессор Снэйп писал(а):
Что с того, что наш список аксиом бесконечен?
Это позволяет быстро прийти к правильному ответу (использован Ваш метод) :D

 Профиль  
                  
 
 
Сообщение26.12.2007, 15:45 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Brukvalub писал(а):
Профессор Снэйп писал(а):
Что с того, что наш список аксиом бесконечен?
Это позволяет быстро прийти к правильному ответу (использован Ваш метод) :D


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

Добавлено спустя 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. "Длина" --- это у цепей :) Для антицепей обычно используют термин "ширина" :D А лучше всего в обоих случаях говорить "мощность".

 Профиль  
                  
 
 
Сообщение27.12.2007, 12:36 


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

Профессор Снэйп писал(а):
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$.

 Профиль  
                  
 
 
Сообщение27.12.2007, 13:31 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Всё правильно Вы решили.

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

Добавлено спустя 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$ получается примитивной рекурсией из примитивно рекурсивных функций, то она примитивно рекурсивна. Проверку того, что она обладает требуемым в задаче свойством (даёт число сдвигов головки влево) оставляю для самостоятельного разбора.

 Профиль  
                  
 
 
Сообщение27.12.2007, 14:14 


04/12/06
70
Функция $d$ обозначается у нас $w.$ :D

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group