Mozibur Ullah

Как теорема о неполноте Гёделя интерпретируется в интуиционистской логике?


Логика Филосовская из-математики Гёдель Крипке Философия

Классически устанавливаются аксиоматическая система с формальной системой дедукции и интерпретация в модели. Как правило, это звучит , т. Е. Формально выведенная теорема также верна при интерпретации в модели. Обратное называется полнотой, если предложение в модели истинно, то оно также формально выводимо. Это утверждение теоремы полноты Гёдельса .

Сложная теорема о неполноте Гёделя относится к понятию разрешимости (это отличает понятие разрешимости в теории вычислений как машины Тьюринга и т. П.) - утверждение разрешимо, когда мы можем определить (решить), что оно имеет либо доказательство, либо недостоверность. Если все утверждения на языке разрешимы, мы называем это полным. Теорема гласит, что аксиоматические системы, содержащие ПА, неполны - то есть всегда есть утверждения, которые мы не можем найти доказательства или доказательства.

Теперь, что произойдет, если формальная система дедукции не классическая, а интуиционистская? Интуиционистская логика многозначна, а не моделирует правду. Одна модель конструктивности / доказуемости, которая вместо использования семантики теории множеств использует семантику Крипке. Теперь:

  1. Все еще звучит ? То есть: формально выведенная теорема также конструктивна?

  2. Это неполное ? Существует конструктивное предложение, которое формально не выводимо?

  3. Имеются ли у него неразрешимые заявления?

commando♦
Далеко не хорошо читайте эту тему, но на странице SEP по интуиционизму есть несколько упоминаний о теореме о неполноте и может быть полезно.

Nikos M.
как упоминалось в ответах, теоремы о неполноте Геделя применимы к интуиционистской логике только тогда, когда они формализованы как своего рода классическая логика без ЛЕМ , но это не отражает Интуиционизм, предложенный Брюером. По сути, IL - это не просто классическая логика без LEM, так как семантика отличается не только несколькими изменениями i (i.modify несколько правил) в синтаксисе.

Nikos M.
Более того, конструктивная математика - это не просто классическая математика без аксиомы выбора (что подразумевает ЛЕМ), но в цитатах эта аналогия сделана. Он воплощает в себе другое мнение, связанное с семантикой. В этом смысле, имея предложения, которые могут быть неразрешимыми, эффективно внедряет теоремы Геде, как неотъемлемую часть интиоризма с самого начала

Nikos M.
хороший пост «Доказательство и интуиционизм Гёделя» в том же направлении и значение, что и мои предыдущие комментарии ( аналогичный вопрос на math.SE )

Ответы


Dennis

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

Поскольку он звучит и дополняется, он не является неполным. Тот факт, что они относятся к «истине» как к чему-то вроде «доказуемости», не имеет отношения к ситуации.

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

Вопрос, который, как я полагаю, вы имеете в виду (хотя я извиняюсь за то, что я мог читать ваши мысли), является ли интуиционистская / конструктивная математика восприимчивой к неполноте. Ответ здесь да. Гёдель дал доказательства в конструктивном / интуиционистски приемлемом виде (т. Е. Используя только выводы, которые они одобряют), и поэтому результат будет иметь место для интуиционистской теории чисел.

Стоит отметить, что вам не нужна арифметика, столь же сильная, как ПА, чтобы стать жертвой незавершенности. Все, что требуется, - это теория чисел, которая рекурсивно аксиоматизируема.

Арифметика Робинсона (Q) - теория, намного слабее PA (я считаю, что это PA без индукции), но незавершенность все еще возникает. Это может быть (точно не помню) самая слабая система по-прежнему преследует теоремы о неполноте. На самом деле он был разработан как слабая система - система, которая может представлять все и только рекурсивные теоретико-числовые функции.

Вот интересная статья, которую я нашел на эту тему - выглядит как хорошее чтение. Эти лекционные заметки (опять же от Кевина Клемента) неплохо ходят по теоремам Гёделя, если вы этого хотите. В противном случае ссылка SEP entry @commando должна быть полезной.

Mozibur Ullah
спасибо за ссылки, они выглядят полезными. Не нужно извиняться - вы правильно читаете мои намерения! Я думаю, что я вводил в заблуждение полноту, которая ссылается на синтаксис и семантику и неполноту, которая ссылается только на синтаксис «формального доказательства» только через систему вывода / дедукции / доказательства, если я правильно вас прочитал. Какое стандартное название использовать - inference / deductive / proof - они, кажется, все используются ?!

Dennis
@MoziburUllah Боюсь, что я не совсем понимаю, в чем вы указываете. Насколько я знаю, существует только одна форма (в) полноты: (не) возможность формально доказать каждую истину вашей теории.

Mozibur Ullah
Вы сказали, что «он звучит и завершен, он не является неполным », а затем «ли это неприемлемо для незавершенности . Ответ здесь да». Я думаю, что эти два понятия о полноте, которые я перепутал, просто потому, что у них есть похожие имена.

Lenar Hoyt
@Dennis Мне кажется удивительным, что интуиционистская логика завершена, а конструктивная математика - нет, что означало бы, что есть дополнительные аксиомы, которые вызывают неполноту?

Dennis
@mcb На самом деле это не удивительно. (Классический) Логика первого порядка - это язык, в котором формализована большая математика. Логика первого порядка полна, но очень мало математических теорий, сформулированных в ней. Итак, да, вы правы, есть дополнительные аксиомы, которые вы добавляете к базе интуиционистской логики, которые вызывают неполноту конструктивной математики. В частности, любые аксиомы, которые вы добавляете, которые позволят вам определить арифметику, по крайней мере такую ​​же сильную, как арифметика Робинсона, - это аксиомы, которые приведут к применению теоремы о неполноте.

Mauro ALLEGRANZA

Два понятия (полнота и неполнота) не являются противоположностями, но очень связаны (не только именем Гёделя во имя двух теорем).

Примите во внимание, что полнота Гёделя в Логике первого порядка:
если предложение истинно во всех моделях аксиом (т. е. является логическим следствием аксиом), то оно также формально выводимо (в FOL) аксиомами.

Неполнота Геделя Th относительно формальных систем, содержащих «определенную сумму» арифметики (например: Арифметика Робинсона, которая слабее, чем у Пеано), и говорит, что мы можем эффективно найти выражение, выражаемое в тех формальных системах, которые являются «истинными» «в предполагаемой модели (т. е. модели с доменом стандартных номеров и операции стандартного сложения и умножения), но не выводимой из аксиом.

Это не противоречит полноте Th: вышеупомянутое утверждение верно в стандартной модели, но НЕ истинно в какой-либо другой «странной» модели (их много): по этой причине она не выводима из указанных аксиом.

Арифметическое утверждение, построенное Годелем в его доказательстве, довольно «странно», но, исходя из результата Парижа и Харрингтона (1977), в математической логике было возможно найти утверждения, которые верны (в стандартной модели), но не доказуемы в арифметике Peano и более «естественны». Это был первый «естественный» пример истинного утверждения о целых числах, которые могут быть указаны на языке арифметики, но не доказаны в арифметике Peano.

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

Hurkyl

Стоит отметить, что вопрос о неполноте имеет довольно тривиальный ответ.

Формулировка интуиционистской логики не включает в себя закон исключенной середины, но и это не отрицает .

Классическая логика = интуиционистская логика + больше аксиом / правил вычета.

Интуиционистские правила дедукции доказывают меньше теорем, чем классические; если некоторая классическая теория, порожденная аксиомами, не может доказать P и не докажет ¬P , то интуиционистская теория, порожденная одними и теми же аксиомами, также не сможет доказать оба утверждения.


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


Nikos M.

воспроизведено с https://math.stackexchange.com/a/1418923/139391

ПРИМЕЧАНИЕ. Интуиционистская логика НЕ многозначна! (и на самом деле имя Геделя снова связано с исследованиями в этом направлении)

Являются ли теоремы о неполноте Геделя действительными как для классической, так и для интуиционистской логики?

В некотором смысле ДА.

НО

  1. Теорема о неполноте Геделя применяется сначала к классической логике

  2. Теорема неполноты Геделя и ее доказательство конструктивны, но не интуиционистски конструктивны ( статья Годела )

Зачем?

Сам Годел заявил в своей статье, что вышеуказанная процедура « конструктивно не вызывает возражений », однако

a) Ссылка Геделя на конструктивизм (интуиционизм) довольно формальна, чем фактическая (более подробно ниже)

б) вариации ЛЕМ (закон исключенного среднего) используются на протяжении всего доказательства Гёделя

c) в сочетании с использованием процедуры диагонализации

(см. также Доказательство и Интуиционизм Гёделя для другого анализа)

Оказывает ли это то же самое на интуиционистскую логику?

В некотором смысле ДА.

НО

  1. Отрицательный перевод классической логики Геделя на интуиционистскую логику является лишь формальным ( статья Годеля )

Зачем?

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

б) интуиционизм в некотором смысле уже вложил в теоремы о неполноте, поскольку он принимает статеты, которые не могут быть ни доказаны, ни опровергнуты (в определенный момент времени)

в) Брувер сам предвидел результаты Годеля на десятилетие (примечание: сам Гедел присутствовал на лекциях Брауэра об основах математики)

Цитата из «Понимание конструктивной семантики Артемова» (лекция Спинозы)

введите описание изображения здесь

А также отсюда

Интуиционистская и классическая перспектива

Интуиционисты обычно основывают свои формальные системы на интуиции конструктивной, например, неформальной семантики стиля БХК , а не на классических основах ...

Классические математики (такие как Гёдель, Колмогоров, Клине, Новиков и другие) стремятся к строгому

классическое определение конструктивной семантики.

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

For advertisement and collaboration please email answer.adv@gmail.com