Почему разумность подразумевает последовательность?

12

Я читал вопрос, что последовательность и полнота означают разумность? и первое утверждение в нем говорит:

Я понимаю, что разумность подразумевает последовательность.

Что меня очень озадачило, потому что я думал, что разумность была более слабым утверждением, чем последовательность (то есть я думал, что согласованные системы должны быть надежными, но я думаю, что это не так). Я использовал неофициальное определение, которое Скотт Ааронсон использовал в своем курсе 6.045 / 18.400 в Массачусетском технологическом институте для последовательности и надежности:

  1. Надежность = система доказательств является надежной, если все утверждения, которые она доказывает, на самом деле верны (все доказуемо верно). т.е. если IF ( доказуемо) ( - True). Так что ЕСЛИ (есть путь к формуле) ТО (то, что формула Истина)ϕϕ
  2. Согласованность = согласованная система никогда не доказывает A и НЕ (A). Таким образом, только один А или его отрицание могут быть Истинными.

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

CharlieSystem{Axioms={A,¬A},InferenceRules={NOT()}}

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

В моей голове это имеет смысл интуитивно, потому что разумность просто говорит о том, что как только мы начинаем с аксиомы и проверяем правила вывода, мы достигаем только назначения (то есть утверждения), которые являются Истинными. Тем не менее, он на самом деле не говорит, куда мы прибываем. Тем не менее, согласованность говорит о том, что мы можем достичь только места назначения, которые достигают либо либо (оба не оба). Таким образом, каждая непротиворечивая система должна включать в себя закон исключенной середины в качестве аксиомы, чего я, конечно, не сделал, а затем просто включил отрицание единственной аксиомы в качестве единственной другой аксиомы. Так что не кажется, что я сделал что-то слишком умное, но что-то не так?A¬A


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

в отношении семантики системы

их полная цитата:

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

Чарли Паркер
источник
Все системы мы заинтересованы в противоречие можно получить от и . A¬A
Юваль Фильмус
@YuvalFilmus Я не думаю, что понимаю, что означает ваш комментарий ... означает ли это, что с моими аксиомами вы всегда можете получить противоречие? Это было вроде моей точки зрения нет? Извините, я не понимаю. Я думаю, что мой вопрос касается только семантики слова «разумность» и «согласованность», поскольку мой пример касается только категоризации «логической системы», которую я составил.
Чарли Паркер
Это означает, что ваша система не так интересна. Все системы, которые появляются в исследовании, достаточно сильны, чтобы вызвать противоречие в этой ситуации.
Юваль Фильмус
1
@YuvalFilmus моя система не должна быть «интересной» для реальной математики, конечно, я знаю это. Моя система была педагогически определена, чтобы, конечно, сделать мой вопрос ясным и простым и прояснить путаницу, которую я испытываю в отношении обоснованности и последовательности. Но в той лекции, которую я связал, Скотт позже говорит, что Разумность, поскольку говорит о «настоящей» Истине, должна быть последовательной, потому что Истина должна быть согласованной с самим собой (т. Е. Истина не может быть равна Ложному). Так что кажется, что звуковая система просто наследует по аксиоме исключенного среднего автоматически. Является ли мое текущее понимание.
Чарли Паркер
Являются ли и верными? Если нет то как это звучит? A¬A
user253751

Ответы:

16

Я рекомендую изучать формальную логику за пределами смутных, волнистых описаний. Это интересно и очень актуально для информатики. К сожалению, терминология и узкая направленность даже учебников, особенно о формальной логике, могут дать искаженную картину того, что такое логика. Проблема в том, что большую часть времени, когда математики говорят о «логике», они (часто неявно) подразумевают классическую логику высказываний или классическую логику первого порядка. Хотя это чрезвычайно важные логические системы, они далеко не широки логики. В любом случае, то, что я собираюсь сказать, в основном происходит в этом узком контексте, но я хочу прояснить, что это происходит в определенном контексте и не обязательно должно быть правдивым вне его.

Во-первых, если согласованность определена как не доказывающая и и , что произойдет, если в нашей логике даже нет отрицания или еслиA¬A¬значит что-то еще? Понятно, что это понятие согласованности делает некоторые предположения о логическом контексте, в котором оно действует. Как правило, это то, что мы работаем в классической логике высказываний или некотором ее расширении, таком как классическая логика первого порядка. Существует несколько презентаций, то есть списков аксиом и правил, которые можно назвать классической логикой высказываний / первого порядка, но для наших целей это не имеет значения. Они эквивалентны в некотором подходящем смысле. Как правило, когда мы говорим о логической системе, мы имеем в виду (классическую) теорию первого порядка. Это начинается с правил и (логических) аксиом классической логики первого порядка, к которым вы добавляете заданные символы функций, символы предикатов и аксиомы (называемые нелогическими аксиомами). Эти теории первого порядка, как правило, то, что мы

Далее, обоснованность обычно означает разумность по отношению к семантике. Согласованность - это синтаксическое свойство, имеющее отношение к тому, какие формальные доказательства мы можем сделать. Надежность - это семантическое свойство, которое связано с тем, как мы интерпретируем формулы, функциональные символы и символы предикатов в математические объекты и утверждения. Чтобы даже начать говорить о разумности, вам нужно дать семантику, то есть толкование вышеупомянутых вещей. Опять же, у нас есть разделение между логическими связями и логическими аксиомами, а также символами функций, предикатами и нелогическими аксиомами. Что делает соединительные связки и логические аксиомы логическими аксиомами с семантической точки зрения, так это то, что они обрабатываются специально семантикой, а функциональные символы, предикаты и нелогические аксиомы - нет.[[φψ]]=[[φ]][[ψ]] где я использую как интерпретация формулы . В частности, Где - набор доменов. Идея формулы - это толкование множества (наборов) доменных элементов, которые удовлетворяют формуле. Замкнутая формула (т. Е. Формула без свободных переменных) интерпретируется как нулевое отношение, то есть подмножество одноэлементного множества, которое может быть только этим одноэлементным или пустым множеством. Закрытая формула «истина», если она не интерпретируется как пустой набор. Обоснованность - это утверждение, что каждая доказуемая (замкнутая) формула является «верной» в вышеприведенном смысле.[[φ]]φ[[¬φ]]=D[[φ]]D

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

[[φ¬φ]]=[[φ]](D[[φ]])=
[[φ¬φ]]φ
Дерек Элкинс покинул ЮВ
источник
2
не стесняйтесь рекомендовать мне книгу по логике, я не знаю, что такое хороший справочник, особенно для начинающих по логике. Самое смешное, что я взял алгоритмы и реальный анализ, поэтому я никогда не задумывался о самой логике.
Чарли Паркер
1
Интересно, я всегда думал, что «истина» означает, что мы сопоставили утверждение с логическими значениями 0 и 1. Но, похоже, это было неправильно. Я предполагаю, что мы можем исправить мою неправильную модель, установив пустую карту отображения в 0 и непустую в 1. В противном случае, я не уверен, как можно переписать ваше доказательство в «моем определении истины как функции». отображение на 1 или 0 ".
Чарли Паркер
1
Это типичная семантика для классической логики высказываний , которую можно рассматривать как частный случай классической логики первого порядка, когда все предикаты являются нулевыми. Булевы «истинные» значения действительно отображаются на пустой набор и набор синглтона в этом представлении. Одним из не слишком вопиющих моментов моего первого абзаца было предположение, что разные логики имеют разные понятия семантики. Даже для фиксированной логики есть несколько возможных семантик, которые могут быть даны для нее. Есть причина, по которой я говорю «типичная семантика», а не просто «семантика».
Дерек Элкинс покинул ЮВ
1
Дерек, если у вас есть время, вы не возражаете, возможно, сделать конкретный пример домена и как он действительно приводит к пустому набору? (Я также рад задать новый вопрос, если хотите). Я имел в виду пример, но не знал, как его завершить. Пример показал, что 2 рационально, а 2 - нерационально приводит к пустому набору (или с ). Я имел в виду D кортеж целых чисел. Затем Сопоставлено с но я не был уверен, что сопоставлено . Вы знаете, как закончить этот пример разумным способом? Или укажите мне на пример? 2[[2 is rational]](2,1)[[2 is irrational ]]
Чарли Паркер
1
Вот где может прийти философия математики. Платонисты верят, что истинность теоретических утверждений (скажем, множеств) просто известна, не прибегая к логике. Возможно, для них теоретико-множественные выражения являются смыслом логических формул. Формалисты будут использовать синтаксические, а не семантические подходы, т.е. «истинно» = «доказуемо». У конструктивистов другое представление об «истине», и чем более ориентированная на вычисления подшкола из них станет свидетелем «правды» через программу.
Дерек Элкинс покинул ЮВ
3

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

В сфере семантики эти два свойства связаны

Определение 1 ( Обоснованность [Семантика] - заимствовано из Википедии ) Обоснованность дедуктивной системы - это свойство, что любое предложение, которое доказуемо в этой дедуктивной системе, также верно для всех интерпретаций или структур семантической теории для языка, на котором эта теория основан.

Определение 2 ( непротиворечивости [Семантика] ) множество высказываний на языке совместна тогда и только тогда , когда существует структура языка , который удовлетворяет все предложения в . Дедуктивная система является последовательной, если существует структура, которая удовлетворяет всем формулам, доказуемым в ней.ALLA

Из двух приведенных выше определений становится ясно, что разумность подразумевает последовательность. Т.е. если множество всех доказуемых предложений выполняется во всех структурах языка, то существует хотя бы одна структура, которая их удовлетворяет.

Дмитрий Чубаров
источник
1
на самом деле я явно избегал википедии, потому что не понимаю, что означает «в отношении семантики». Не могли бы вы уточнить, что это значит? Кроме того, не могли бы вы объяснить более четко, почему его чистота и правильность подразумевают последовательность? Конечно, мне неясно, так как этот вопрос существует: р
Чарли Паркер
@CharlieParker Я читаю ваши комментарии под другими постами. Я не уверен, что существует текст для начинающих, который объясняет основы систем доказательства и теории моделей лучше, чем вводные главы «Теории моделей» Ходжеса. Единственным исключением является «Теория более короткой модели» того же автора. Признаюсь, в своем посте я обманул и определил последовательность как выполнимость , потому что смысл говорить о непротиворечивости - иметь характеристику выполнимости в системе доказательств.
Дмитрий Чубаров
Благодарность! Я проверю это! На самом деле, мне не нужна «книга для начинающих», а хорошая книга - это хорошо. Если книга также подчеркивает интуицию и идеи, а не только доказательства, это было бы еще лучше!
Чарли Паркер
2

Ваша система доказательств не является ни здравой, ни непротиворечивой, поскольку не является истинным предложением, если только В этом случае не является истинным предложением. Этот аргумент показывает, что каждая система звукоизоляции также является последовательной.AA¬A

Юваль Фильмус
источник
Что плохого в том, чтобы иметь функцию которая отображает вещи в True или False. и являются символами, отображаемыми на True (как в системе, которую я определил). Я не уверен, что технически не так с этим, кроме того, что он не «интересен» для выполнения реальной математики. Но определение реальной системы для математики не было целью моего вопроса. Truth()A¬A
Чарли Паркер
Истина имеет семантическое определение: оценка истинности при всех назначениях истины. Вы не можете выбрать, как вы определяете этот термин.
Юваль Фильмус
Возможно, именно здесь я запутался, отсюда и мой вопрос. Хотя технически Скотт упомянул правду не может быть определена математически ... но давайте проигнорируем эту техническую природу ради аргумента, чтобы я мог понять проблему. Не могли бы вы еще раз объяснить, что означает Истина? Спасибо за ваше терпение. :)
Чарли Паркер
1
В контексте логики высказываний формула является тавтологией, если она верна во всех случаях установления истинности. Система доказательства пропозициональности является надежной, если все формулы, которые она доказывает, являются тавтологическими.
Юваль Фильмус
Я знаю, что вы пытаетесь помочь, и я ценю это, но каким-то образом ваше доказательство слишком короткое, чтобы действительно объяснить мне, что пошло не так с моим примером в оригинальном посте. Если бы вы могли уточнить, это было бы здорово. Я предполагаю, что мой вопрос заключается в том, какие назначения правды приносят проблемы в систему, которую я предложил?
Чарли Паркер
2

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

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

Это, конечно, подразумевает, что у вас есть понятие «натуральных чисел», выходящее за рамки их определения Пеано, и некоторое представление о том, что является истинным или ложным для натуральных чисел, без получения этих истин из какого-либо конкретного набора аксиом. Попытка объяснить, откуда берутся эти истины или как их можно проверить, может привести вас в философские горячие воды. Но если вы воспринимаете это как данность, что существуют натуральные числа и существует некоторая коллекция правдивых фактов о них, то вы можете рассматривать проект аксиоматизации как просто попытку придумать краткую формальную спецификацию, из которой многие из наиболее важных истины могут быть получены. Тогда аксиоматизация является обоснованной, если все, что она может доказать на самом деле, находится в заранее заданном наборе истин, то есть

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

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

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

PA + Con (PA) имеет модели, но они являются моделями, которые должны включать в себя «дополнительные» объекты, «нестандартные натуральные числа», включая тот, который, как он утверждает, кодирует «доказательство», о котором идет речь. Теория просто не оснащена необходимыми инструментами, чтобы отличить эти нестандартные элементы от подлинных добросовестных членов или продемонстрировать, что доказательство не является законным доказательством.¬N

В качестве альтернативы вы можете интерпретировать это как: PA + Con (PA) - совершенно законная логическая система - она ​​просто не точно описывает натуральные числа, и натуральные числа не являются ее моделью.¬

Еще одна вещь: мы не предполагаем, что аксиомы верны по определению. Все аксиомы по определению являются лишь основными строительными блоками доказательств. Это просто утверждения: они верны или ложны только применительно к конкретным математическим объектам. У вас могут быть ложные аксиомы, это просто довольно глупо, потому что ваша система обязательно и сразу же не будет здоровой.

Бен Милвуд
источник
1

Чтобы получить краткий (и интуитивно понятный) ответ, я перефразирую то, что сказал Скотт Ааронсон в своей лекции в 6.045 / 18.400 MIT. Он сказал что-то вроде этого:

Обоснованность означает, что все доказуемое верно. Поскольку согласованность означает, что в ней уже нет противоречий и разумности, концепция истины и истины должна быть согласованной (т. Е. True! = False), то это должно означать, что звуковые системы также согласованы. Таким образом, разумность подразумевает последовательность, потому что (истинно) истинные вещи не имеют противоречий.

Теперь, когда я размышляю, я понимаю, что у меня были некоторые неправильные предположения / идеи:

  1. Я не понимал, что разумность была о семантике. Таким образом, мне не удалось осознать, что простого использования правил вывода из аксиом недостаточно для того, чтобы привести к истинным последствиям (и что это не гарантирует этого, что, по моему мнению, было невозможно достичь противоречивых вещей, пока мы начинали с аксиом и использованы действующие правила вывода).
  2. Я думал, что до тех пор, пока аксиомы верны и правила вывода имеют смысл, все происходящее будет верным. Что, как я теперь понимаю, может оказаться неверным, поскольку, если у нас есть огромный список аксиом и правил вывода, трудно будет рассуждать, если все последующее будет правдой. т. е. простого начала с аксиомы и использования действующего правила вывода недостаточно, чтобы гарантировать, что следующий шаг будет верным.
  3. Предыдущее по сути связано с тем, что я не осознавал, что существует два уровня сложности: 1) семантика 2) синтаксика. Скручивание символов, игра в хруст, может привести к противоречиям.
  4. Я не осознавал, что не знаю правильной характеристики истины, и Дерек проделал отличную работу по ее характеристике.
Чарли Паркер
источник
«Я думал, что до тех пор, пока аксиомы верны и правила вывода имеют смысл, все происходящее будет верным». Для достаточно точного понятия «имеет смысл» это правильно. Если ваша система не работает, то (по крайней мере) одна из ваших аксиом неверна или правила вывода недействительны.
Бен Милвуд
@BenMillwood, но это неправильно, нет? Из-за второй теоремы Гёделя о неполноте. Для любой формальной системы F, которая включает в себя арифметику, невозможно доказать ее согласованность в пределах F. Я понял, что это означает, что мое предположение о здравости невозможно (т.е. у нас не может быть формальной системы, в которой все доказуемое в ней истинно, потому что это подразумевает непротиворечивость, которая кажется невозможной, если, конечно, у меня нет неправильного представления о 2-й теореме о неполноте). Честно говоря, я в порядке, если у нас нет полноты, меня беспокоит то, что у нас не может быть последовательности.
Чарли Паркер
F, конечно, может быть последовательным, вы просто не можете найти доказательства этого факта в F. Вы должны обратиться либо к какой-то более мощной системе, либо к неформальным аргументам, либо просто принять некоторую неопределенность, даже если F может быть последовательным для вас. не сможет построить водонепроницаемый аргумент, что это так.
Бен Милвуд
@ BenMillwood Я думаю, это то, что я предполагаю в своем ответе. Существует неопределенность, что доказательства действительно работают, и следующий шаг может привести к некоторой лжи. Если бы я знал, что это не так, то я бы точно знал, что никогда не достигну противоречия, нарушающего 2-ю теорему Гёделя о неполноте. Или это то, что я понимаю прямо сейчас.
Чарли Паркер
@BenMillwood Думаю, я отказался от убеждения, что применение правил вывода дает нам следующие утверждения, которые на 100% верны. Вместо этого я думаю, что я неявно предполагал, что продвижение вперед - это просто вопрос синтаксики, а не семантики ... конечно, это может быть неправильно, этот вопрос кажется запутанным и тонким.
Чарли Паркер