НГУ

Форумы НГУ
Текущее время: Пн май 20, 2019 7:20 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Теорема Гёделя о неполноте
СообщениеДобавлено: Вт апр 17, 2007 6:12 pm 
Не в сети
Частый гость

Зарегистрирован: Вс май 21, 2006 2:30 am
Сообщения: 41
Откуда: Дорин Александр
Здравствуйте !
Можно ли теорему Гёделя о неполноте сформулировать как утверждение :
никакая конечно аксиоматизируемая система не может быть полной. ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 17, 2007 6:41 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Это вопиюще неверное утверждение.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 17, 2007 6:51 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
К тому же в вопросе не прозвучало, что речь идёт об арифметике. :)
А конечно аксиоматизируемую систему можно истолковать как алгебраическую систему. Возьмём одноэлементную систему с пустой сигнатурой и напишем единственную аксиому (\forall x)(\forall y) (x=y)

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 4:56 am 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Pavel E. Alaev писал(а):
Один из вариантов: что конечная система аксиом, позволяющая моделировать арифметику натуральных чисел, не может быть полной.

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

У меня к Вам вопрос: а что такое та арифметика которую мы собираемся моделировать? Это что некая содержательная
теория? Или она сама по себе уже представляет формальную теорию?
Если же эта теория содержательна, то как мы узнаём, что тот или
иной вопрос относится именно к арифметике а не например к мореплаванию? Каков критерий? Просто если мы строим формализацию теории чисел, и говорим, что всякая такая формализация неполна, то должно быть и то, что мы собственно
формализуем. Так что это такое? [/quote]Вот здесь
я предпринял попытку это выяснить. Но никто из авторитетных участников нечего не подтвердил, впрочем как и не опроверг.
Посмотрите пожалуйста.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 3:40 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Pavel E. Alaev писал(а):
конечность множества аксиом может быть заменена на более слабое условие, говорящее, что множество аксиом может быть перечислено с помощью некоторого алгоритма.

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

Amigo писал(а):
что такое та арифметика которую мы собираемся моделировать?

Я бы сильно не удивлялся отсутствию четких ответов на этот вопрос, так как он скорее философский, нежели математический. Например, можно считать, что арифметика -- это совокупность всех истинных утверждений о натуральных числах. Предвосхищая вопрос о том, что именно в данном контексте означают слова "совокупность", "истинность", "утверждение" и "число", могу сказать, что все это -- тоже своего рода философия. Чтобы избежать бесконечной цепи переходов от совсем неформального к тому, что выглядит чуть менее неформальным, можно считать, что нам изначально известны все эти понятия, и мы оперируем ими на наивном уровне -- исходя из интуиции и здравого смысла. (P.S.: Все, как всегда, IMHO.)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 4:53 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
AGu писал(а):
Pavel E. Alaev писал(а):
конечность множества аксиом может быть заменена на более слабое условие, говорящее, что множество аксиом может быть перечислено с помощью некоторого алгоритма.

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


Вы не правы. Перечислимости достаточно.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 5:20 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Коба писал(а):
AGu писал(а):
должен существовать алгоритм, способный для любой формулы выяснять, является ли она аксиомой.


Вы не правы. Перечислимости достаточно.

Видимо, это вопрос вкуса -- что именно считать "достаточным".
Мне всегда казалось естественным желание иметь алгоритм, который по данной конечной последовательности формул выясняет, является ли она доказательством. А отсюда тривиальным образом вытекает разрешимость аксиоматики.

Добавление: Если имелась в виду теорема Крейга, то в ней идет речь о перечислимости множества теорем, а не аксиом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 6:40 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
При чём здесь теорема Крейга?

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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 7:31 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Коба писал(а):
Павел сформулировал теорему о неполноте. Вы его зачем-то поправили, будто он неверно написал.

А, понял. Виноват. Я нечаянно выпал из контекста.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 9:11 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
AGu писал(а):
Например, можно считать, что арифметика -- это совокупность всех истинных утверждений о натуральных числах. Предвосхищая вопрос о том, что именно в данном контексте означают слова "совокупность", "истинность", "утверждение" и "число", могу сказать, что все это -- тоже своего рода философия. Чтобы избежать бесконечной цепи переходов от совсем неформального к тому, что выглядит чуть менее неформальным, можно считать, что нам изначально известны все эти понятия, и мы оперируем ими на наивном уровне -- исходя из интуиции и здравого смысла.

Отлично! Именно в таком виде я хотел получить ответ.
Пойдём теперь дальше, два вопроса:
1. Подтвердите или опровергните следующее предложение:
в формальной аксиоматической теории (далее ФАТ)присутствуют только знаки, которые напрочь лишены какого - либо содержательного смысла.Цепочки символов которые получаются в результате "сцепки" этих знаков, сами по себе абсолютно бессодержательны и не являются ни истинными ни ложными. А становятся таковыми, и преобретают содержательный смысл, только в результате какой либо интерпритации?
2. Как работают правила вывода в ФАТ? Точнее: эти правила целиком пренадлежат самой ФАТ, задаются только формулами, которые строятся исключительно из символов алфавита теории и работают чисто механически? Или мы можем нагромоздить любые правила, для которых быть может вообще нет ни какой последовательности знаков формулируемых в терминах ФАТ.
Т.е. допускается ли например в ФАТ следующее правило: если строка
оканчивается на символ "t" - то возьми предыдущие два символа (если таковые имеются) переведи их в код таблицы ASCII - посчитай их сумму кодов, расмотри по модулю 256, полученное число переведи
обратно в букву, получившуюся букву вставь на первое место исходной строки.
То есть какие ограничения наклыдываются на правила к ФАТ?
или нет ограничений?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 9:57 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
1. Подтвердите или опровергните следующее предложение:
в формальной аксиоматической теории (далее ФАТ)присутствуют только знаки, которые напрочь лишены какого - либо содержательного смысла.Цепочки символов которые получаются в результате "сцепки" этих знаков, сами по себе абсолютно бессодержательны и не являются ни истинными ни ложными. А становятся таковыми, и преобретают содержательный смысл, только в результате какой либо интерпритации?

Я лично не берусь ни подтверждать, ни опровергать это суждение. Скажу лишь, что (по моему мнению, естессно), так можно считать.

Amigo писал(а):
2. Как работают правила вывода в ФАТ? Точнее: эти правила целиком пренадлежат самой ФАТ, задаются только формулами, которые строятся исключительно из символов алфавита теории и работают чисто механически?

Я бы только заменил "задаются только формулами" на "в них участвуют только формулы". С остальным готов согласиться.

На мой взгляд, достаточно общим (и, кстати, очень тупым, тавтологичным) определением совокупности правил вывода может сослужить следующее: множество правил вывода -- это произвольное разрешимое множество R пар вида (F,f), где F -- непустое конечное множество формул, а f -- формула. Множеством R правил вывода определяется понятие выводимости формул: говорят, что формула f выводима из формул f1,...,fn, и пишут f1,...,fn |- f, если ({f1,...,fn},f) принадлежит R. (Все и впрямь тупо, не правда ли?) Ясно, что разрешимость R нужна для того, чтобы выводимость f1,...,fn |- f была алгоритмически проверяемой. Кстати, если в приведенном определении опустить требование непустоты F, то можно отказаться от понятия аксиом и ограничиться одними лишь правилами вывода: роль аксиом в этом случае будут играть такие формулы f, что 0 |- f, где 0 -- пустое множество.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 11, 2008 10:24 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Спасибо за ясность изложения. Следующий вопрос(Вы извините за назойливость, но спрашивать то особо не у кого...):
1. Когда говорят -" в данной формальной аксиоматической теории
данный предикат ввести можно/нельзя" - то что имеют ввиду?
Если в формальной теории все символы абсолютно бессодержательны,
то как можно хоть что то туда не ввести? -бери да интерпритируй как угодно цепочки символов - какие собственно проблемы?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 13, 2008 6:34 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
Когда говорят -" в данной формальной аксиоматической теории
данный предикат ввести можно/нельзя" - то что имеют ввиду?
Если в формальной теории все символы абсолютно бессодержательны,
то как можно хоть что то туда не ввести? -бери да интерпритируй как угодно цепочки символов - какие собственно проблемы?

Поскольку фраза вырвана из контекста, о ее смысле можно лишь догадываться.

Для простоты ограничимся рассмотрением лишь одноместных предикатов.
Обозначим обсуждаемую теорию символом T, а ее сигнатуру -- символом S.
Коль скоро речь идет о "данном предикате", этот предикат как-то нам "дан".
Тут видятся разные возможности. Для примера рассмотрим парочку.

1. Предикат интерпретирован в виде конкретного отношения P
на некоторой особо любимой нами модели M теории T.

Возможное осмысление фразы "нельзя ввести данный предикат":
нет такой формулы ф сигнатуры S с одной свободной переменной,
что P = { m из M : M |= ф(m) }.

2. Указаны желаемые свойства предиката p
в виде формально не противоречащего теории T
набора предложений F сигнатуры S+{p}.

В этом случае можно предложить два естественных осмысления
фразы "нельзя ввести данный предикат".

2a. Нет такой формулы ф сигнатуры S с одной свободной переменной,
что T+F |- (Ax)( p(x) <=> ф(x) ).

2b. Имеются две модели теории T+F с совпадающими носителями
и совпадающими интерпретациями сигнатуры S,
но различными интерпретациями предиката p.

Впрочем, согласно теореме Бета об определимости
утверждения 2a и 2b эквивалентны.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 14, 2008 8:39 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
AGu писал(а):
Поскольку фраза вырвана из контекста, о ее смысле можно лишь догадываться.


Я извиняюсь, что забыл сообщить про контекст.
Речь идёт о следующем предикате:
Изображение
Этот предикат взят из лекции профессора Алексея Брониславовича Сосинского http://www.math.ru/media/cat/dubna.
Там он проводит доказательство т.Гёделя, но отмечает тот факт,
что для полного его завершения нужно доказать, что в нашей формальной теории этот предикат действительно можно ввести.

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 14, 2008 10:07 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
Речь идёт о следующем предикате:
...

Прямо скажем, очень схематичная запись.
Видимо, ее следует расшифровывать так:
Doc(x,y) равносильно тому, что y является номером какого-либо
доказательства формулы, имеющей номер x.
(Кстати, эта расшифровка не соответствует Вашему пояснению
того, что такое Г, но, скорее всего, тут просто описка,
так что не будем отвлекаться от сути вопроса.)

Тут в принципе применим подход 1 из моего предыдущего поста --
за тем исключением, что предикат не одноместный, а двухместный.
Здесь T -- это арифметика,
M -- стандартная модель арифметики
(с множеством натуральных чисел в качестве носителя)
и P = {(x,y) из M^2 : Doc(x,y)}.

Но если вспомнить классическое доказательство теоремы Гёделя,
то, скорее всего, тут все же имеется в виду
некий весьма страшненький случай подхода 2 --
с арифметикой Пеано в качестве T
и следующим набором свойств F:
{p([m],[n]) : Doc(m,n)} + {~p([m],[n]) : не Doc(m,n)},
где [n] = 0''...' с n штрихами.
(Ну, может, и не совсем так, но как-то так. :-))


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

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB