2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Разобраться с формальными системами
Сообщение03.07.2012, 13:01 
Заблокирован
Аватара пользователя


07/08/06

3474
Разбираю такое предложение:
Цитата:
Предложение $\varphi$ является следствием теории $T$, если в любой модели теории $T$ предложение $\varphi$ истинно. Теория $T$ в рекурсивном языке рекурсивно аксиоматизируема тогда и только тогда, когда множество всех следствий теории $T$ рекурсивно перечислимо.


Допустим у нас есть рекурсивно аксиоматизируемая теория и в ней присутствуют предложения, которые могут быть истинными или ложными в зависимости от интерпретации. Если задать интерпретацию для теории, часть из этих предложений станут истинными, т.е. множество истинных предложений возрастёт. Останется ли оно рекурсивно перечислимым?

По-моему - не всегда, т.к. добавив все эти предложения в качестве аксиом, получили бы полную и непротиворечивую теорию. Насколько я прав?

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 14:08 
Заслуженный участник
Аватара пользователя


28/09/06
10414
По-моему, можно взять любое нерекурсивное подмножество предложений языка, дополнить его множеством следствий теории и вычесть из него множество отрицаний следствий теории. В итоге получим нерекурсивную интерпретацию теории.

А вот идея с добавлением ВСЕХ этих предложений в качестве аксиом, насколько я понимаю, не годится, поскольку у нас тогда получится нерекурсивное множество аксиом, чего в осмысленных теориях не бывает.

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 14:21 
Заблокирован
Аватара пользователя


07/08/06

3474
epros в сообщении #591594 писал(а):
поскольку у нас тогда получится нерекурсивное множество аксиом

Почему? По-моему, это так не всегда. И как раз в этом и состояло моё предположение, которое я хотел проверить (в силу цитаты в первом сообщении).

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 14:25 
Заслуженный участник
Аватара пользователя


28/09/06
10414
AlexDem в сообщении #591600 писал(а):
Почему? По-моему, это так не всегда.
Что почему? Разумеется, теоретически мы имеем право рассматривать и нерекурсивно аксиоматизируемые теории. Но для такой теории невозможно проверить, является ли предложение аксиомой, так что на практике от такой теории мало проку - вряд ли в ней что-либо удастся реально доказать.

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 14:28 
Заблокирован
Аватара пользователя


07/08/06

3474
epros в сообщении #591602 писал(а):
Что почему?

Почему вдруг сразу получится нерекурсивное множество аксиом?

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 14:43 
Заслуженный участник
Аватара пользователя


28/09/06
10414
AlexDem в сообщении #591605 писал(а):
Почему вдруг сразу получится нерекурсивное множество аксиом?
Если я правильно понял Вашу идею, у Вас было рекурсивно перечислимое множество следствий теории, и Вы хотели дополнить его до нерекурсивного множества? Причём дополнение - это и есть множество новых аксиом?

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 15:28 
Заблокирован
Аватара пользователя


07/08/06

3474
Нет. У меня была рекурсивная система аксиом теории. Из них по правилам вывода получаются все следствия теории, пусть это будет множество $D$. Дополнение $U \setminus D$ этого множества до множества всех формул $U$, насколько я понимаю, - это ещё не множество ложных формул, там есть как ложные, так и те, которые могут быть либо истинными, либо ложными в зависимости от интерпретации.

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

PS: Занятно... Вот ещё из другого источника:
Цитата:
В любой формальной системе $F$ совокупность слов, выводимых из произвольного рекурсивно перечислимого множества слов $U$, является рекурсивно перечислимой.

С учётом цитаты в первом сообщении получается, что рекурсивной перечислимости множества аксиом достаточно для его рекурсивности?

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 16:10 
Заслуженный участник
Аватара пользователя


28/09/06
10414
AlexDem в сообщении #591630 писал(а):
Ставится вопрос о рекурсивной перечислимости множества истинных формул в заданной интерпретации.
А что мешает выбрать нерекурсивную интерпретацию? Например, вот так:
epros в сообщении #591594 писал(а):
взять любое нерекурсивное подмножество предложений языка, дополнить его множеством следствий теории и вычесть из него множество отрицаний следствий теории


AlexDem в сообщении #591630 писал(а):
получается, что рекурсивной перечислимости множества аксиом достаточно для его рекурсивности?
Его - это множества аксиом? Рекурсивность (разрешимость) = перечислимость + перечислимость дополнения. Поэтому перечислимости, вообще говоря, недостаточно для рекурсивности.

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение03.07.2012, 17:45 
Заблокирован
Аватара пользователя


07/08/06

3474
epros в сообщении #591644 писал(а):
А что мешает выбрать нерекурсивную интерпретацию? Например, вот так:
epros в сообщении #591594 писал(а):
взять любое нерекурсивное подмножество предложений языка, дополнить его множеством следствий теории и вычесть из него множество отрицаний следствий теории

Разность множеств здесь может оказаться рекурсивной.

-- Вт июл 03, 2012 18:46:41 --

epros в сообщении #591644 писал(а):
Поэтому перечислимости, вообще говоря, недостаточно для рекурсивности.

Это понятно, но я же рассмотрел частный случай.

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение04.07.2012, 10:00 
Заслуженный участник


09/05/08
1155
Новосибирск
AlexDem в сообщении #591630 писал(а):
С учётом цитаты в первом сообщении получается, что рекурсивной перечислимости множества аксиом достаточно для его рекурсивности?
У одной и той же теории есть куча разных множеств аксиом. (Каждое из этих множеств аксиом порождает одно и то же множество следствий -- множество следствий данной теории.) Так вот, упомянутые Вами факты говорят о том, что из существования рекурсивно перечислимого множества аксиом следует существование (возможно, какого-то другого) рекурсивного множества аксиом.

 Профиль  
                  
 
 Re: Разобраться с формальными системами
Сообщение04.07.2012, 12:11 
Заблокирован
Аватара пользователя


07/08/06

3474
Да, скорей всего - так, если в этих двух книгах нет расхождения в понятиях. Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

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



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

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


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

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