Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        теорема Геделя о неполноте
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 ]
Модераторы: Roman Osipov, RKI, attention, paradise
  

Indigo


Удален


Цитата: valjok написал 16 июля 2005 15:59




Цитата: Indigo написал 15 июля 2005 20:16

Цитата: Guest написал 15 июля 2005 16:51
Не бред ли это?



Еще хуже! Это - философия...



Доказывали-то математики, Гёдель /= Гегель. Хотелось бы пояснений на вторую часть вопроса о невозможности доказать тождественную истинность любой формулы исчисления предикатов, к философии он пока не имеет отношения. Почему Гёдель говорит - можно, Чёрч - нельзя?



А почему вы решили, что они противоречат друг другу?

Гедель утверждает, грубо говоря , что для любой формулы F исчисления предикатов можно построить (существует) вывод F , или вывод не-F.

Черч - что не существует ЕДИНОГО алгоритма, на вход которого подается формула F, а на выходе одно из двух значений - 0 или 1 (соответсвенно, если формула логически неверна или верна).

Это только у радикальных интуиционистов доказуемость == алгоритмическая доказуемость, для остальных математиков все по-другому

Например, вот ссылка (к сожалению, по-английски):

http://www.math.psu.edu/simpson/papers/philmath/node10.html

А так - имхо не стоит читать сурьезные математические источники, в оглавлении которых попадается фраза "Метафизические аспекты проблемы вычислимости функции сознания."


Цитата: valjok написал 16 июля 2005 16:15

Но так как он лжец и говорит, что он лжец, то получается, что он говорит правду.


Значит, в действительности он лжёт и поэтому говорит не правду.



Почему?

Атрибут данного объекта - "лжец". Он говорит: "я - лжец" (я имею атрибут "лжец" ). Следовательно, говорит правду (высказывание - истинно).

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 20:12 | IP
Indigo


Удален

Вдогонку - о том, почему, как правило, под теорему Геделя не-математики пытаются подвести какую-либо философию.
Причины имхо таковы:

1) Несмотря на свою сложность и довольно обширный background, эта теорема формулируется обманчиво-заманчиво-просто.

Действительно, если человеку без математического образования дать прочитать теорему о гомоморфизме из курса общей алгебры (Гомоморфный образ группы изоморфен факторгруппе по ядру гомоморфизма) - то из всей формулировке он/она поймет разве что слово "по" . А в теореме Геделя все слова вроде как знакомы, причем благодаря неизвестным популяризаторам от математики в народе ходит приблизительно такая формулировка: "непротиворечивость формальной системы не может быть установлена средствами самой системы" - что, конечно, является недопустимой профанацией

2) Непонимание. Нематематики, которые пытаются интерпретировать теорему Геделя, схожи с древними греками, которых привели, поставили перед "Черным Квадратом" и спросили - "что вы об этом думаете?" Я имею в виду, что для того, чтобы ПОНЯТЬ, почему "Черный Квадрат" считается произведением искусства, а не чем-либо еще, необходимо ЗНАТЬ историю искусства от древних греков и до современности.
Равно и в математике - чтобы понимать, что теорема Геделя - всего одна, пусть очень красивая и чрезвычайно важная, теорема матлогики, которая не содержит в себе ничего сверхъестественного или философского, необходимо знать эту самую матлогику .

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


Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 22:17 | IP
valjok


Удален


Цитата: Indigo написал 16 июля 2005 22:12


Например, вот ссылка (к сожалению, по-английски):

http://www.math.psu.edu/simpson/papers/philmath/node10.html



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




Почему?
Атрибут данного объекта - "лжец". Он говорит: "я - лжец" (я имею атрибут "лжец" ). Следовательно, говорит правду (высказывание - истинно).


Поздравляю, вам удалось разрешить парадокс то ли Евклида то ли Арестотеля!

http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%BB%D0%B6%D0%B5%D1%86%D0%B0



А так - имхо не стоит читать сурьезные математические источники, в оглавлении которых попадается фраза "Метафизические аспекты проблемы вычислимости функции сознания."


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

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 июля 2005 22:58 | IP
Indigo


Удален

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



Цитата: valjok написал 16 июля 2005 21:58

Цитата: Indigo написал 16 июля 2005 22:12


Например, вот ссылка (к сожалению, по-английски):

http://www.math.psu.edu/simpson/papers/philmath/node10.html



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




В первых параграфах этой ссылки говорится о построении вывода вручную для КОНКРЕТНОЙ формулы. Например, предложения вида "если встречается "узел" вида А, то создаем два "узла" вида В и С" или "повторяем процедуры до тех пор, пока это не станет невозможным"- не являются шагом алгоритма. Это так, руководство к поиску вывода для конкретной формулы, а по сути - перефразировка правил вывода в логике предикатов (правило C (choice), правило де Моргана и т.д.)
Под "алгоритмом" в последнем параграфе подразумевается алгоритм в строгом смысле этого слова, то есть набор команд для машины Тюринга.




Почему?
Атрибут данного объекта - "лжец". Он говорит: "я - лжец" (я имею атрибут "лжец" ). Следовательно, говорит правду (высказывание - истинно).




Поздравляю, вам удалось разрешить парадокс то ли Евклида то ли Арестотеля!





Ни в коем случае. Это просто более детальная перефразировка отцитированного утверждения "Но так как он лжец и говорит, что он лжец, то получается, что он говорит правду. " Дальнейшее противоречие никто не отменял



Сможет ли он решать задачи подвластные мозгу?



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

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 июля 2005 0:25 | IP
valjok


Удален



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


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




В первых параграфах этой ссылки говорится о построении вывода вручную для КОНКРЕТНОЙ формулы.


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



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


На этот вопрос может ответить только Мозг, если ещё не ответил. Было подмечено что между замечателными датами замечательных людей существуют строгие периоды, google гитлер 2018. Я хоть и родился ровно через 100 лет после Эйнштейна, определённо не его реинкарнация. Подождём.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 июля 2005 14:30 | IP
Guest



Новичок

2 SCERB
Так получается, что эта формула всё же выводима, раз Гёдель сумел её вывести. Получается противоречие с условием теоремы.
Я говорю про доказательство по ссылке http://ivanem.chat.ru/godel1.htm
Вывод там чем-то напоминает парадокс брадобрея, а не лжеца.
Или вы не это доказательство имели в виду?

Всего сообщений: Нет | Присоединился: Never | Отправлено: 17 июля 2005 20:58 | IP
Indigo


Удален



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



Честно говоря, с трудом себе представляю НАСТОЛЬКО подвинутого физика



Например считается, к основам математики можно приступать освоив основную часть университетской программы



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



общее предписание для определения истинности, т.е. - алгоритм




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



Ладно, при первой возможности будем читать Чёрча, может и прояснится.



Это очень правильно. "Введение в математическую логику" Алонсо Черча - имхо самый правильно построенный курс.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 июля 2005 22:00 | IP
valjok


Удален



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


Т.е. вы согласны, что в школе основы давать рановато, т.е. не всега полезно начинать с основ.



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


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

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 17 июля 2005 22:41 | IP
Indigo


Удален




Т.е. вы согласны, что в школе основы давать рановато, т.е. не всега полезно начинать с основ.



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

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




предписание как из первых получить вторые - тоже



можно цитату из приведенной ссылки, где строго указаны такие предписания?

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

Ну, если у меня не получилось вас убедить, что формальный алгоритм и мысли-вслух-о-том-как-решать-задачу - это разные вещи, то, может, это получится сделать у Джона Маккарти, отца computational logic и LISP'a?  :

http://www-formal.stanford.edu/jmc/basis1/node14.html

пункт 3, proof procedures and proof checking procedures.




Всего сообщений: N/A | Присоединился: N/A | Отправлено: 18 июля 2005 0:16 | IP
Unnamed


Новичок

Indigo @ postno=6 wrote:

Еще хуже! Это - философия...
В общем-то, это и правда философия, но прочно завязанная на математике – а точнее, на рассуждениях в рамках математики. Хотя у автора статьи для «философии» выделен отдельный бонус-трек в виде 3-й страницы, где можно лицезреть действительно кошмарно грубые «метафизические» рассуждения (сюда входят: абсолютно топорное опровержнение функционализма, не менее убийственное доказательство единственности «Я» и то, что из него следует, а также некоторые тезисы, для меня представляющиеся абсурдными или по меньшей мере необоснованными и далеко не очевидными, которые автор почему-то считает чем-то самим собой разумеющимся).

SCERB @ postno=7 wrote:

Господа, при построении невыводимой в формальной арифметике (аксиомы и правила вывода) формулы Гедель использовал идею парадокса лжеца.
Фишка любого парадокса в том, что прежде чем к нему прийти, мы что-то сделали неправильно – совершили какое-то недопустимое действие. И именно выявление этого недопустимого действия позволяет разрешить парадокс. А потому не плохо бы усвоить полученный урок да поразмышлять над недопустимостью этого действия не только в рамках тех манипуляций, которые привели нас к парадоксу, а недопустимость его вообще – при любых обстоятельствах. Когда же мы используем доказательство методом «от противного», мы не имеем права совершать более одного необоснованного действия, чтобы потом признать неправомерность только какого-то одного из этих действий.

А доказательство, которое допускает существование таких сомнительных «штучек», как замыкающиеся на себе осмысленные высказывания, для которых существует характеристика «истина-ложь», уже, на мой взгляд, имеет одно необоснованное допущение, и потому опровергать с его помощью ещё какое-то допущение никак нельзя.

А именно:на Крите все жители лжецы. Критянин Вася говорит "я лжец". Так как Вася критянин, то он действительно лжец. Но так как он лжец и говорит, что он лжец, то получается, что он говорит правду.
Решается всё очень просто: фразы в духе «Я лжец», «Я лгу в данный момент» и т.п. можно считать неосмысленными и не рассматривать их как высказывания. С другой стороны, есть некая идея придать-таки смысл фразе «Я лгу в данный момент». В общем-то данная фраза сродни той, что мы уже рассматривали выше – «Данное высказывание ложно». Его и рассмотрим (снова).

Полагается, что у этого высказывания можно раскрыть контекст (который хоть и не сказан явно, но подразумевается по умолчанию), и в результате получить более развернутое высказывание: «Данное высказывание (утверждение) и истинно и ложно» (т.е. всякое утверждение на самом деле что-то утверждает, а потому заведомо подразумевает само себя истинным). Но, поскольку утверждение не может быть одновременно и истинно, и ложно, то данному утверждению отводится статус ложного – оно утверждает то, чего не может быть. Однако уж больно смущает тот факт, что в нашей ситуации, будучи в первоначальном (свернутом) виде («Данное высказывание ложно»), сие утверждение явно глаголит о себе истину – оно, как мы договорились считать, действительно ложно. Т.о., уловить в нём какой-либо смысл на самом деле не представляется возможным: повернёшь его так – получишь одно, повернёшь эдак – получишь другое.

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

Насколько мне известно, теорема Геделя принята многими математиками, в том числе и Давидом Гильбертом.
Я вовсе не собираюсь опровергать теорему Гёделя. Я лишь против той идеи, которая изложена в ссылке http://ivanem.chat.ru/godel1.htm. Самого Гёделевского док-ва я не видел, а автор статьи мог всё-таки исказить его смысл. Кстати, я нашёл книжку (в неважнецком качестве, правда), где, вроде как, приведено одно из док-в теоремы Гёделя. Правда, читать её долго и муторно, а Лемму 6 (представленную на с.24) вместе с её док-вом я так и не понял.

Допускаю ли я, что само гёделевское док-во может быть неверным? Да, допускаю: то, что неверное док-во может быть принято многими математеками хотя и маловероятно, но в то же время не является невозможным. Неверность же может заключаться в каком-нибудь недопустимом шаге, который внешне кажется вполне допустимым.

Свою силу и истинность математика подтверждает практикой.
Боюсь, что это не про такие теоремы, как теорема Гёделя.

valjok @ postno=9 wrote:

Всё так, только похоже, что без рекурсий в математике нельзя, например супремум:

По мнению Рассела, все парадоксы возникают из-за одной логической ошибки, названной им принципом порочного круга. Этот принцип можно сформулировать так: «Если для того, чтобы определить множество, необходимо использовать все множество, такое определение не имеет смысла». Пуанкаре предложил для этого специальный термин «непредикативное определение». Как бороться с непредикативными определениями, было непонятно. С одной стороны, такие определения могут приводить к парадоксам, но, с другой стороны, как переформулировать определения, чтобы они не были непредикативными?

В качестве непредикативного определения можно привести определение наименьшей верхней границы. Рассмотрим множество всех x, таких, что 3<x<5. Верхними границами называются числа, превосходящие все числа данного множества. Среди них существует наименьшая – это число 5. Таким образом, наименьшая верхняя граница определена через класс верхних границ, содержащий ее саму, но сформулировать его иначе не удавалось.



Не вижу схожести ситуаций. Совокупность верхних границ – это множество. Наименьшая верхняя граница – это его элемент. Где тут мы определяем множество через всё само это множество?

valjok @ page 1, postno=10 wrote:

а с Ивановым как быть, который и в самом деле может доказать, что доказать не может?
Признать фразу «Иванов не может доказать это высказывание» не являющейся высказыванием, обладающим характеристикой «истина-ложь». Вот и всё.

Indigo @ page~2, postno=12

Она применима только в математической логике и связанных с нею областях, и никак не в философии или теологии.
Т.е. в философии совсем нельзя использовать выводы математики?

(Сообщение отредактировал Unnamed 19 июля 2005 13:26)

Всего сообщений: 44 | Присоединился: март 2005 | Отправлено: 18 июля 2005 14:32 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 ]

Форум работает на скрипте © Ikonboard.com