2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Ряд вопросов по формальным аксиоматическим системам
Сообщение02.04.2008, 11:50 


11/03/06
236
Здравствуйте!
Я пытаюсь изучить т. Гедёля, потратил уже много времени, но пока без результатно.
И вот, наконец, я нашел одну книжку, из которой как кажется, я всё таки смогу уразуметь
её смысл. Но всё равно, там много проблем, потому, я хотел бы Вас попросить, так сказать сопровождать меня в самых трудных местах.

В этой книге содержится такая фраза:
Самой природе ЛЮБОЙ формализации теории чисел (далее –ТЧ) свойственно то, что её МЕТА ЯЗЫК содержится в ней самой. (1)
Ну и дела… даже не верится в такое, неужели это можно доказать? Именно в этом я и собираюсь разобраться. Но прежде хочу воспроизвести то, что звучит у меня в сознании когда произносится эта фраза, звучит так:
Существует такая область человеческих знаний, которая обладает тем свойством, что как бы мы её не формализовывали, всякая возможная формализация этой области знаний, в обязательном порядке будет включать в себя способ, при помощи которого мы можем говорить об самой этой ФОРМАЛИЗАЦИИ. Я подчёркиваю слово «формализации» а не область знаний, что может быть и не верно, отсюда первый вопрос: в данном высказывание речь действительно идёт о формализации, или речь идёт о области знаний?
Второй вопрос который у меня возникает следующий: в высказывании (1) сказано о двух разных вещах, а именно о –ТЧ, и о формализации ТЧ (далее –ФТЧ). Таким образом мы должны отличать ТЧ и ФТЧ. Что мне совершенно непонятно, что разве ТЧ не есть ФТЧ?
Что такое вообще ТЧ? Видимо предполагается, что есть некая неформальная ТЧ, т.е. некоторый «круг вопросов» математики, более менее на одну тему, и вот мы этот круг вопросов хотим неким образом формализовать, т.е. представить в неком «типографском» виде, что и называется формализацией ТЧ. Как же мы узнаем, точнее определяем, какой круг вопросов относится к ТЧ а какой нет? У нас, что есть некоторые правила, который позволяют однозначно определить – является ли данный вопрос - вопросом ТЧ? Мне известно, что существует аксиоматика Пеано, которая задаёт свойства натурального ряда.
Можно ли сказать, что эта аксиоматика и есть как раз то, что называется просто ТЧ.
И фактически, когда речь идёт о формализации ТЧ (т.е. об ФТЧ), то мы имеем ввиду не что иное, как перевод аксиоматики Пеано, в определённую «типографскую» форму ?
Если же нет, то что же тогда такое просто ТЧ? Объясните пожалуйста, на мета языке (желательно русском).

Пока всё.

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


18/12/07
8774
Новосибирск
Я думаю, тут всё гораздо проще. Теория чисел занимаетс числами, а любое человеческое рассуждение о чём бы то ни было так или иначе ими оперирует. Например, мы можем взять пару высказываний о числах. Высказывания --- это объекты метатеории. Но их количество есть число два, то есть это уже объект самой теории :) Числа присутствуют во всех языках, хоть мета-, хоть не мета-, и никуда от них не деться. Вот автор книги и отметил этот факт.

А может быть имелось в виду кодирование... Вы, наверное, знаете, как доказыватся теорема Гёделя о неполноте. Вводится некоторая эффективная кодировка, сопоставляющая числам --- объектам теории высказывания --- объекты метатеории. Благодаря наличию этой кодировки появляется возможность строить по высказываниям метаязыка эквивалентные высказывания предметного языка. Далее эта возможность используется для того, чтобы перевести высказывание, утверждающее свою собственную недоказуемость, на предметный язык.

В любом случае высказывание

Цитата:
Самой природе любой формализации теории чисел свойственно то, что её МЕТАЯЗЫК содержится в ней самой.


вырвано из контекста и не обладая полным текстом книги можно лишь строить догадки насчёт того, что хотел сказать автор.

 Профиль  
                  
 
 
Сообщение02.04.2008, 13:52 


11/03/06
236
Это автор делает для того, что бы доказать, что в любой формализации ТЧ, всегда можно найти строчку говорющую о самой
себе т.е. что высказывание: G = "G не теорема ФТЧ" -действительно
является высказывание ФТЧ, а не "внешним" высказыванием об ФТЧ т.е. не высказыванием мета языка об ФТЧ. Иначе у нас не получиться ни какого доказательства т. Гёделя. В этом, как он поясняет центральный момент...

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


18/12/07
8774
Новосибирск
Ну хорошо, а в чём Ваша проблема? Что именно тут Вы не можете понять?

P. S. Первое сообщение не осилил. Попробуйте сформулировать свой вопрос короче :)

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


11/03/06
236
Автор приводит, полную формализацию ТЧ , но это, очень трудный кусок для уяснения, потому я хотел бы вначале, в полноте прояснить для себя вопрос связанный с тем, формализацию чего именно он проводит. Ведь он же "что то" формализует а не ничто. Так я и хочу понять, что же именно. Он же не проводит формализацию, незнаю,
теорию относительности. Он формализует нечто, что называется
теорией чисел. Т.е. это "нечто" спокойно существует и без того,что её кто формализует. Так я и хочу понять, что такое то "нечто". Как мне узнать, что речь идёт о ТЧ а не о башмаках?

 Профиль  
                  
 
 
Сообщение02.04.2008, 15:02 


04/10/05
272
ВМиК МГУ
Порядок освоения теоремы Гёделя о неполноте в слабой форме (чтобы сильно не мучиться).

1) Научиться записывать простейшие утверждения теории чисел на языке формальной арифметики (такие, как, например, "x - простое число" или "любое четное натуральное число > 2 можно представить в виде суммы двух простых чисел"). Речь идёт именно о записи формул, а не доказательств.

2) Придумать какой-нибудь способ кодирования векторов числами и научиться на основе этого способа записывать в языке формальной арифметики утверждения о векторах.

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

4) Найти хороший пример алгоритмически неразрешимой задачи типа распознавания какого-то свойства.

5) Научиться (алгоритмически) для конкретного входа этой задачи строить формулу формальной арифметики, истинность которой эквивалентна данному свойству. Точнее, не научиться, а почувствовать, что это возможно.

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

Примечания.
A) Желательно иметь опыт программирования, чтобы понимать, что такое алгоритм, и как его можно формализовать, что может алгоритм, а что не может.
Б) Не нужно заниматься формальными выводами в какой-то конкретной теории (типа арифметики Пеано).
В) Нужно понять, что теорема Гёделя в этой слабой форме - это утверждение об алгоритмах, и только о них. Т.е. для её понимания совершенно не обязательно знать мат. логику.
Г) Если не охота возиться с формулами формальной арифметики, то можно добавить в её язык много разных новых функторов и предикатов типа x[y] - "y-й элемент массива с кодом x".
Д) Для освоение усиленной теоремы Гёделя, которая накладывает на теорию лишь требование непротиворечивости, придётся более глубоко разобраться в теории алгоритмов, и немного повозиться с логикой и выводами.
Е) Для освоения теоремы о недоказуемости непротиворечивости теории в самой теории придётся конкретно разобраться в логике и построить много формальных выводов в какой-нибудь конкретной теории. Вот это уже требует значительных трудов.

 Профиль  
                  
 
 
Сообщение02.04.2008, 17:37 


11/03/06
236
Думаю, что если следовать вашему методу, то понадобятся годы...
Я хочу лишь понять основные идеи, больше мне нечего ненужно.
Я понимаю, что такое формальная система, но я не понимаю так сказать изоморфизма- между формальной системой и некой иной предметной областью. Если мы говорим, что построили формализацию теории чисел, то прежде должна быть и сама теория чисел. Так что такое теория чисел?

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

Попробую прояснить проблему следуюшим образом:
Рассмотрим формальную аксиоматическую систему (далее - ФАС),
систему "st".
Алфавит определяется двумя буквами A={s,t}
имеется одна аксиома- $stt$
и одно правило вывода -"Если имеется строчка sx то sxx - тоже строчка системы "st", где $x$ -любая последовательность символов нашей системы.
Посмотрим какие теоремы можно получить в этой системе:
ясно, что только такие:
$stt$ - аксиома
$stttt$ - т.1
$stttttttt$ -т.2
$stttttttttttttttt$- т.3
$stttttttttttttttttttttttttttttttt$ - т.4
и т.д.

Что можно сказать об этой системе? Можно заметить, что количество
букв t в любой теореме всегда:
1.Чётно
2.в каждой последующей теореме их количество возрастает в двое.

То утверждение, что количество букв в каждой последующей теореме
возрастает в двое - не является утверждением самой системы "st",
наоборот, это утверждение О системе "st". И сделано на другом языке - на русском, который по отношению к системе "st" - является
мета языком. Если бы мы жили "внутри" системы "st" - то мы бы никогда не смогли даже задаться этим вопросом.

Теперь попробую объяснить, что мне непонятно.
Предположим наша система является формализацией определённой отрасли знаний. Мы видим, что эта отрасль такова, что её формализация не включает в себя способа говорить о ней самой.
Кажется, что именно так обстоит дело со всеми вообще ФАС, которые моделирую определённую отрасль знаний. Но на самом деле, оказывается, что существует такая отрасль знаний, которую
невозможно формализовать таким способом, что бы говорить о ней самой (изнутри) мы не могли. Т.е. всякая формализация этой отрасли обязательно включает в себя средства (мета средства), позволяющие говорить о ней самой. Математики утверждают, что такой отраслю знаний является - ТЧ. Вот тут та я и хочу разобраться с тем - чем же собственно отличается теория чисел от всех других
теорий. И что такое вообще ТЧ? Ведь если мы признаём, что помимо
ФТЧ, существует ещё собственно и сама теория чисел, то мы должны хотя бы вкратце её описать. То есть описать так, как она представляется во вне формализованном виде. Как же это делается?

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


23/07/05
17973
Москва
Amigo писал(а):
В этой книге содержится такая фраза:
Самой природе любой формализации теории чисел (далее –ТЧ) свойственно то, что её МЕТА ЯЗЫК содержится в ней самой. (1)
Ну и дела… даже не верится в такое, неужели это можно доказать? Именно в этом я и собираюсь разобраться. Но прежде хочу воспроизвести то, что звучит у меня в сознании когда произносится эта фраза, звучит так:
Существует такая область человеческих знаний, которая обладает тем свойством, что как бы мы её не формализовывали, всякая возможная формализация этой области знаний, в обязательном порядке будет включать в себя способ, при помощи которого мы можем говорить об самой этой ФОРМАЛИЗАЦИИ.


Высказывание достаточно подозрительное. Роль метатеории состоит в том, что она предоставляет средства для описания языка теории (алфавит, формулы и т.д.). При этом алфавит, формулы и т.д. являются объектами метатеории, но не являются объектами формализуемой теории. Если же мы допустим смешение этих теорий (метатеории и формальной теории), то запросто получим всякие противоречия типа парадокса лжеца, ибо появится возможность формулировать высказывания типа "Данное высказывание ложно".
Не видя книги, трудно говорить что-нибудь наверняка, но ведь возможна ситуация, когда в роли метатеории выступает "та же" теория, которую мы хотим формализовать. Например, мы можем строить формализацию арифметики средствами самой арифметики. Однако нужно помнить, что это две разные арифметики: арифметика как метатеория и формализованная арифметика. Метатеория тоже может быть формализованной, но тогда должна быть метаметатеория, и так далее. Где-то на самом верху в роли мета...метатеории будет естественный язык, который, разумеется, никакой формализации не имеет.

Amigo писал(а):
Что мне совершенно непонятно, что разве ТЧ не есть ФТЧ?


Ну, теория чисел не формализована и не может быть формализована в полном объёме, что и утверждает фактически теорема Гёделя о неполноте. Если в качестве формализации теории чисел взять арифметику Пеано, то известны истинные утверждения, которые в ней недоказуемы (отнюдь не утверждение о непротиворечивости), но доказуемые в более широкой теории (например, в теории множеств).

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


Примерно так: "Теория чисел, это, чем занимаются ..." (вместо многоточия нужно подставить список имён специалистов в данной области).

 Профиль  
                  
 
 
Сообщение02.04.2008, 19:10 


11/03/06
236
Someone писал(а):
Если же мы допустим смешение этих теорий (метатеории и формальной теории), то запросто получим всякие противоречия типа парадокса лжеца, ибо появится возможность формулировать высказывания типа "Данное высказывание ложно".

Совершенно верно, именно с этого и начинает автор. Он говорит, что в теореме Гёделя
"зашит" определённым образом парадокс Эпеминида, точнее это его модернизированная версия, которая позволяет не привести всё таки к парадоксу при определённых условиях.

Someone писал(а):
Не видя книги, трудно говорить что-нибудь наверняка

Someone да вот пожалуйста, посмотрите здесь:автор, сама книга.


Someone писал(а):
но ведь возможна ситуация, когда в роли метатеории выступает "та же" теория, которую мы хотим формализовать.

Someone, я думаю, что именно это он и собирается сделать. Но у меня нехватает ума
за всем уследить.

P.s.
Я не думаю, что эта книга ерунда из за того, что написана в необычной форме. Думаю, там теорема Геделя рассматривается полностью, без всякого остатка, только на человеческом языке.
P.P.s
Предлагаю всем скачать себе эту книгу, пока ссылка ещё работает. Такого шедевра Вы больше никогда не найдёте.

Цитата:
толстенная на почти 800 страниц формата А4, испещренная формулами и схемами книга стала бестселлером. Пулитцеровская и множество других премий, переиздания, дополнительные тиражи и торжественное юбилейное издание, переводы и издания на французском, итальянском, немецком, испанском, венгерском, шведском, португальском, китайском... Теперь, 23 года спустя, и на русском. Сейчас русские Интернет-магазины вывешивают ее в рекламе, но на запросы отвечают "нет в наличии" и ее приходится "доставать", как в дореволюционные времена.

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


23/07/05
17973
Москва
Amigo писал(а):
Я не думаю, что эта книга ерунда из за того, что написана в необычной форме.


Никто пока не говорил, что это ерунда. Это одна из попыток популярного изложения теоремы Гёделя и связанных с ней идей. Надеюсь, доброкачественная.

Amigo писал(а):
Существует такая область человеческих знаний, которая обладает тем свойством, что как бы мы её не формализовывали, всякая возможная формализация этой области знаний, в обязательном порядке будет включать в себя способ, при помощи которого мы можем говорить об самой этой ФОРМАЛИЗАЦИИ.


Кстати, автор может иметь в виду возможность кодирования метатеории в формализованной теории (нужна, мне кажется, метаметатеория, поскольку именно она имеет доступ к элементам метатеории), вследствие чего и появляется возможность в формализованной теории говорить о её формулах и т.п., однако, насколько я знаю, при этом возникают некоторые ограничения (по сравнению с "перемешиванием" теории и метатеории), не позволяющие получить противоречие. Однако я всё-таки не специалист в этой области, и подробностей не знаю.

Известно, что арифметика достаточно богата для такого кодирования. Ещё удобнее в этом отношении теория множеств.

 Профиль  
                  
 
 
Сообщение03.04.2008, 00:05 


04/10/05
272
ВМиК МГУ
Amigo писал(а):
Теперь попробую объяснить, что мне непонятно.
Предположим наша система является формализацией определённой отрасли знаний. Мы видим, что эта отрасль такова, что её формализация не включает в себя способа говорить о ней самой.
Кажется, что именно так обстоит дело со всеми вообще ФАС, которые моделирую определённую отрасль знаний. Но на самом деле, оказывается, что существует такая отрасль знаний, которую
невозможно формализовать таким способом, что бы говорить о ней самой (изнутри) мы не могли. Т.е. всякая формализация этой отрасли обязательно включает в себя средства (мета средства), позволяющие говорить о ней самой. Математики утверждают, что такой отраслю знаний является - ТЧ. Вот тут та я и хочу разобраться с тем - чем же собственно отличается теория чисел от всех других
теорий.


Теория чисел хороша только тем, что в ней можно формализовать понятие алгоритма, а, следовательно, и понятие доказательства. А говорить о самой теории в теории чисел можно только с точки зрения доказуемости. То есть, на языке теории чисел можно сформулировать что-то типа "утверждение A доказуемо в теории T" или "теория T непротиворечива". При этом в качестве T может быть любая формальная теория. Грубо говоря, в теории чисел можно записывать утверждения о синтаксических свойствах каких-либо строк символов. И больше ничего! Никаких других таких хороших особенностей теории чисел нет. Ну кроме, разве что, того, что теория чисел - одна из самых простых, обладающая этими свойствами (есть и более сильные и сложные - теория множеств, например).

Но не всё о теории чисел можно выразить в ней самой. Например, в теории чисел нельзя сформулировать понятие истинности в теории чисел. Да и вообще, в любой теории T (обладающей некоторым минимальным набором свойств, который я точно не помню) нельзя сформулировать понятие истинности в T.

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


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

 Профиль  
                  
 
 
Сообщение03.04.2008, 11:26 


11/03/06
236
Удивительное открытие!
Автор утверждает, что ЛЮБАЯ ФАС может быть переведена в нотацию ФТЧ.
Цитата:
В теорию чисел можно включить ВСЕ проблемы о ЛЮБОЙ формальной системе.

Последнее возможно, как я понял, из за того, что существует Геделева нумерация ЛЮБОЙ формальной системы. А ЛЮБОЕ
правило вывода в формальной системе, может быть заменено соответствующим АРЕФМИТИЧЕСКИМ правилом. Отсюда и получается, что любая ФАС изоморфно отображается на некоторую часть ТЧ. Далее автор, видимо собирается применить Геделеву
нумерацию к САМОЙ ФТЧ. Что неизбежно, как кажется, приведёт к тому, что в ней некоторые числа, будут одновременно и суждениями
о некоторых числах.

Таким образом, получается, что теория чисел стоит как бы особняком.

 Профиль  
                  
 
 
Сообщение04.04.2008, 20:31 


04/10/05
272
ВМиК МГУ
А что за учебник? Автор кто?

P.S. Теория чисел не может быть особняком. Есть и много других теорий с такими же свойствами. Например, есть хорошая теория строк символов с операцией конкатенации в качестве основы. Да и теорию множеств никто не отменял.

 Профиль  
                  
 
 
Сообщение05.04.2008, 01:52 


11/03/06
236
маткиб писал(а):
А что за учебник? Автор кто?


посмотрите здесь - http://dxdy.ru/viewtopic.php?p=110482#110482

маткиб писал(а):
P.S. Теория чисел не может быть особняком.

Насчёт "особняка" - это я сказал, а не автор.
маткиб писал(а):
Есть и много других теорий с такими же свойствами.

С какими именно свойствами?

У меня к Вам два вопроса:
1. Вы можете дать чёткое, исчерпывающее определении формальной теории и аксиомотаческой теории? Это как я понимаю совершенно разные вещи, так например в книге
В.И. Игошина - "математическая логика и теория алгоритмов", есть такая теорема:
"Всякая доказуемая в формализованном исчислении высказываний формула является тождественно истинной формулой алгебры высказываний". - как Вы проинтерпритируете эту теорему? Не кажется ли Вам, что одно дело просто теория а другое дело её формализация? Так например в той же книге на странице 123 начинается глава "Формализованное исчисление высказываний",(а до этого 123 страницы рассматривалась алгебра высказываний) и в предисловии к ней сказано: "В этой главе рассматривается аксиоматический подход к алгебре высказываний". Помимо этого в книге имеется две главы- "Аксиоматический метод в математике и аксиоматические теории" - глава 5, и следующая глава -"Формальные аксиоматические теории".
Как видете имеются серьезные основания считать, что одно дело теория, совсем другое дело её формализация. Итак, я возвращаюсь к своему первоначальному вопросу - что такое ТЧ и в чем её отличие
от ФТЧ?
2.Вы согласны с тем, что в теорию чисел можно перевести все проблемы о всех формальных теориях?
3. В разных книгах, в том числе и в лекции профессора Алексея Брониславовича Сосинского
http://www.math.ru/media/cat/dubna - повторяется нечто одинаковое, предьявляется некий нульместный предекат, определённым образом говорящий о самом себе. Что то типа следующего: "Меня доказать в данноё теории нельзя" - вот всё то, что получается в результате манипуляций с этим высказываний - понять не особо трудно. Самое же важное, что нужно понять, так это то, откуда вообще берётся этот предекат. Не Сосинский ни Смалиан,
на этом вопросе не останавлиятся, предпологая, что это очень сложный вопрос. Ну мне спешить совершенно некуда ( слава Богу), потому я намерен в нём разобраться и прошу Вас в меру сил мне посодействовать.

P.S.
Подход к доказательству теоремы Геделя основанный на теории алгоритмов, мне известен.
Читал я это 100 раз. Могу сказать, что совершенно неудачная попытка рассказывать теорему Гёделя таким способом. Во всей этой манипуляции с разрешимыми и перечислимыми множествами, не улавливается основная суть. Доказательство становится - бессущностным, неуловимым. И из них выхалащиваются основные идеи т.е. их просто не видно. Может это удобно в техническом плане, но в содержательном меня не устраивает. Но это мое
мнение, может и я и не прав.

 Профиль  
                  
 
 
Сообщение05.04.2008, 13:30 


04/10/05
272
ВМиК МГУ
Amigo писал(а):
маткиб писал(а):
А что за учебник? Автор кто?


посмотрите здесь - http://dxdy.ru/viewtopic.php?p=110482#110482


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

Amigo писал(а):
У меня к Вам два вопроса:
1. Вы можете дать чёткое, исчерпывающее определении формальной теории и аксиомотаческой теории?


Обычно под формальной теорией (или, что одно и то же, формальной аксиоматической теорией, или просто аксиоматической теорией) понимают совокупность, включающую в себя: 1) алфавит символов (конечный или счетный);
2) алгоритм, который проверяет, является ли строка символов x формулой теории (т.е. алгоритм, задающий язык теории);
3) алгоритм, который проверяет, является ли строка символов x аксиомой теории;
4) алгоритм, который проверяет, можно ли непосредственно вывести (за один шаг) строку символов y из строк x1, x2, ... xn (т.е. алгоритм, который задает правила вывода).

Что такое "теория вообще", я затруднюсь ответить. Это уже ближе к философии.

Amigo писал(а):
маткиб писал(а):
P.S. Теория чисел не может быть особняком.

Насчёт "особняка" - это я сказал, а не автор.
маткиб писал(а):
Есть и много других теорий с такими же свойствами.

С какими именно свойствами?


Ну как я понял из твоего же поста, имеется в виду следующее свойство: для любой формальной теории T можно построить отображение F (алгоритмически разрешимое) множества формул языка теории T в множество формул языка формальной арифметики, такое, что для любой формулы x верно (x выводима в T)<->(F(x) выводима в формальной арифметике Пеано).

Хотя про формальную арифметику Пеано ничего не говорилось, поэтому, возможно, имелось в виду (F(x) истинна в стандартной модели арифметики).

Если я правильно понял свойства (хотя бы в одном из случаев), то это верно и для многих других теорий.

Amigo писал(а):
2.Вы согласны с тем, что в теорию чисел можно перевести все проблемы о всех формальных теориях?

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

Другой вопрос, что все более или менее нужные проблемы о всех формальных теориях можно перевести в теорию чисел (к ним относятся проблемы доказуемости, непротиворечивости и т.п.). Под переводом подразумевается перевод в язык теории чисел, без привязки к какой-либо конкретной формальной теории, т.е. переводимая проблема будет эквивалентна истинности полученной после перевода формулы в стандартной модели арифметики.

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

Amigo писал(а):
P.S.
Подход к доказательству теоремы Геделя основанный на теории алгоритмов, мне известен.
Читал я это 100 раз. Могу сказать, что совершенно неудачная попытка рассказывать теорему Гёделя таким способом. Во всей этой манипуляции с разрешимыми и перечислимыми множествами, не улавливается основная суть. Доказательство становится - бессущностным, неуловимым. И из них выхалащиваются основные идеи т.е. их просто не видно. Может это удобно в техническом плане, но в содержательном меня не устраивает. Но это мое
мнение, может и я и не прав.


Кому что удобнее.
Мне вот как прикладнику и программисту гораздо более понятен подход через теорию алгоритмов. Конечно, он обладает гораздо меньшими возможностями с точки зрения обобщения теоремы Гёделя на разные там логики "нетрадиционной ориентации". Но зато позволяет ясно увидеть и почувствовать прикладную сущность теоремы - невозможность поиметь всю математику одним методом. А классический подход мне напоминает синтаксический фокус, в котором никакой глубинный смысл увидеть нельзя.

Кстати, хорошие книги - трехтомник Верещагина и Шеня, там изложены оба подхода, причём понятно и с улучшающими понимание примерами, комментариями. Да и объём небольшой.

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

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



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

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


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

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