Я читал вопрос, что последовательность и полнота означают разумность? и первое утверждение в нем говорит:
Я понимаю, что разумность подразумевает последовательность.
Что меня очень озадачило, потому что я думал, что разумность была более слабым утверждением, чем последовательность (то есть я думал, что согласованные системы должны быть надежными, но я думаю, что это не так). Я использовал неофициальное определение, которое Скотт Ааронсон использовал в своем курсе 6.045 / 18.400 в Массачусетском технологическом институте для последовательности и надежности:
- Надежность = система доказательств является надежной, если все утверждения, которые она доказывает, на самом деле верны (все доказуемо верно). т.е. если IF ( доказуемо) ( - True). Так что ЕСЛИ (есть путь к формуле) ТО (то, что формула Истина)
- Согласованность = согласованная система никогда не доказывает A и НЕ (A). Таким образом, только один А или его отрицание могут быть Истинными.
Используя эти (возможно, неформальные) определения, я построил следующий пример, чтобы продемонстрировать, что существует система, которая является надежной, но не последовательной:
Причина, по которой я думал, что это была звуковая система, заключается в том, что, по предположению, аксиомы верны. Таким образом, A и не A оба верны (да, я знаю, что закон исключенного среднего не включен). Поскольку единственное правило вывода - отрицание, мы получаем, что мы можем достичь и A, и не A из аксиом и достичь друг друга. Таким образом, мы достигаем только истинных утверждений относительно этой системы. Однако, конечно, система не согласована, потому что мы можем доказать отрицание единственного утверждения в системе. Поэтому я продемонстрировал, что звуковая система может быть непоследовательной. Почему этот пример неверен? Что я сделал не так?
В моей голове это имеет смысл интуитивно, потому что разумность просто говорит о том, что как только мы начинаем с аксиомы и проверяем правила вывода, мы достигаем только назначения (то есть утверждения), которые являются Истинными. Тем не менее, он на самом деле не говорит, куда мы прибываем. Тем не менее, согласованность говорит о том, что мы можем достичь только места назначения, которые достигают либо либо (оба не оба). Таким образом, каждая непротиворечивая система должна включать в себя закон исключенной середины в качестве аксиомы, чего я, конечно, не сделал, а затем просто включил отрицание единственной аксиомы в качестве единственной другой аксиомы. Так что не кажется, что я сделал что-то слишком умное, но что-то не так?
Я просто понимаю, что это может быть проблемой, потому что я использую неформальное определение Скотта. Еще до того, как я написал вопрос, я проверил Википедию, но их определение не имело для меня смысла. В частности, часть, которую они говорят:
в отношении семантики системы
их полная цитата:
каждая формула, которая может быть доказана в системе, логически верна с точки зрения семантики системы.
Ответы:
Я рекомендую изучать формальную логику за пределами смутных, волнистых описаний. Это интересно и очень актуально для информатики. К сожалению, терминология и узкая направленность даже учебников, особенно о формальной логике, могут дать искаженную картину того, что такое логика. Проблема в том, что большую часть времени, когда математики говорят о «логике», они (часто неявно) подразумевают классическую логику высказываний или классическую логику первого порядка. Хотя это чрезвычайно важные логические системы, они далеко не широки логики. В любом случае, то, что я собираюсь сказать, в основном происходит в этом узком контексте, но я хочу прояснить, что это происходит в определенном контексте и не обязательно должно быть правдивым вне его.
Во-первых, если согласованность определена как не доказывающая и и , что произойдет, если в нашей логике даже нет отрицания или еслиA ¬A ¬ значит что-то еще? Понятно, что это понятие согласованности делает некоторые предположения о логическом контексте, в котором оно действует. Как правило, это то, что мы работаем в классической логике высказываний или некотором ее расширении, таком как классическая логика первого порядка. Существует несколько презентаций, то есть списков аксиом и правил, которые можно назвать классической логикой высказываний / первого порядка, но для наших целей это не имеет значения. Они эквивалентны в некотором подходящем смысле. Как правило, когда мы говорим о логической системе, мы имеем в виду (классическую) теорию первого порядка. Это начинается с правил и (логических) аксиом классической логики первого порядка, к которым вы добавляете заданные символы функций, символы предикатов и аксиомы (называемые нелогическими аксиомами). Эти теории первого порядка, как правило, то, что мы
Далее, обоснованность обычно означает разумность по отношению к семантике. Согласованность - это синтаксическое свойство, имеющее отношение к тому, какие формальные доказательства мы можем сделать. Надежность - это семантическое свойство, которое связано с тем, как мы интерпретируем формулы, функциональные символы и символы предикатов в математические объекты и утверждения. Чтобы даже начать говорить о разумности, вам нужно дать семантику, то есть толкование вышеупомянутых вещей. Опять же, у нас есть разделение между логическими связями и логическими аксиомами, а также символами функций, предикатами и нелогическими аксиомами. Что делает соединительные связки и логические аксиомы логическими аксиомами с семантической точки зрения, так это то, что они обрабатываются специально семантикой, а функциональные символы, предикаты и нелогические аксиомы - нет.[[φ∧ψ]]=[[φ]]∩[[ψ]] где я использую как интерпретация формулы . В частности, Где - набор доменов. Идея формулы - это толкование множества (наборов) доменных элементов, которые удовлетворяют формуле. Замкнутая формула (т. Е. Формула без свободных переменных) интерпретируется как нулевое отношение, то есть подмножество одноэлементного множества, которое может быть только этим одноэлементным или пустым множеством. Закрытая формула «истина», если она не интерпретируется как пустой набор. Обоснованность - это утверждение, что каждая доказуемая (замкнутая) формула является «верной» в вышеприведенном смысле.[[φ]] φ [[¬φ]]=D∖[[φ]] D
Отсюда легко, даже по эскизу, который я дал, доказать, что разумность подразумевает последовательность (в контексте классической логики первого порядка и семантики, которую я набросал). Если ваша логика звук, затем каждые доказуемые формулы интерпретируют как непустое множество, но не всегда интерпретируется как пустое множество , независимо от того , какая формула есть, и так оно не может быть доказуемо, т. е. ваша логика последовательна
источник
Надежность и последовательность являются свойствами дедуктивных систем. Обоснованность может быть определена только в отношении некоторой семантики, которая, как предполагается, дается независимо от дедуктивной системы.
В сфере семантики эти два свойства связаны
Определение 1 ( Обоснованность [Семантика] - заимствовано из Википедии ) Обоснованность дедуктивной системы - это свойство, что любое предложение, которое доказуемо в этой дедуктивной системе, также верно для всех интерпретаций или структур семантической теории для языка, на котором эта теория основан.
Определение 2 ( непротиворечивости [Семантика] ) множество высказываний на языке совместна тогда и только тогда , когда существует структура языка , который удовлетворяет все предложения в . Дедуктивная система является последовательной, если существует структура, которая удовлетворяет всем формулам, доказуемым в ней.A L L A
Из двух приведенных выше определений становится ясно, что разумность подразумевает последовательность. Т.е. если множество всех доказуемых предложений выполняется во всех структурах языка, то существует хотя бы одна структура, которая их удовлетворяет.
источник
Ваша система доказательств не является ни здравой, ни непротиворечивой, поскольку не является истинным предложением, если только В этом случае не является истинным предложением. Этот аргумент показывает, что каждая система звукоизоляции также является последовательной.A A≡⊤ ¬A≡⊥
источник
Часто, когда мы придумываем логические системы, они мотивируются попыткой описать ранее существовавший феномен. Например, арифметика Пеано - это попытка аксиоматизировать натуральные числа вместе с операциями сложения и умножения.
Обоснованность может быть определена только относительно явления, которое вы пытаетесь описать, и, по сути, означает, что ваши аксиомы и правила вывода действительно описывают данную вещь. Так, например, арифметика Пеано является правильной, потому что ее аксиомы и правила вывода действительно верны натуральным числам.
Это, конечно, подразумевает, что у вас есть понятие «натуральных чисел», выходящее за рамки их определения Пеано, и некоторое представление о том, что является истинным или ложным для натуральных чисел, без получения этих истин из какого-либо конкретного набора аксиом. Попытка объяснить, откуда берутся эти истины или как их можно проверить, может привести вас в философские горячие воды. Но если вы воспринимаете это как данность, что существуют натуральные числа и существует некоторая коллекция правдивых фактов о них, то вы можете рассматривать проект аксиоматизации как просто попытку придумать краткую формальную спецификацию, из которой многие из наиболее важных истины могут быть получены. Тогда аксиоматизация является обоснованной, если все, что она может доказать на самом деле, находится в заранее заданном наборе истин, то есть
(Обратите внимание, в частности, что ваша формальная спецификация не собирается доказывать все, что верно в отношении натуральных чисел, и, кроме того, не будет однозначно описывать натуральные числа тем, что существуют другие структуры, отличные от натуральных чисел, в которых аксиомы Пеано тоже правда.)
В логике первого порядка, по крайней мере, теория является последовательной, если она вообще имеет какие-либо модели. Надежность означает, что у нее есть конкретная модель, которую вы хотели: конкретная структура, которую вы пытались описать своей теорией, на самом деле является моделью вашей теории. С этой точки зрения ясно, почему обоснованность подразумевает последовательность.
В качестве примера теории, которая непротиворечива, но не обоснована: арифметика Пеано, PA, способна кодировать логические формулы в виде арифметических конструкций, и, в частности, вы можете закодировать предложение «PA непротиворечиво» («доказательства ложности из аксиомы ПА "). Назовите это предложение Con (PA). Вам также может быть известно, что (поскольку это правильно и, следовательно, согласованно), PA не может доказать Con (PA) по первой теореме Гёделя о неполноте. Это также означает, что теория PA +¬ Con (PA) не может доказать противоречие, поэтому оно должно быть последовательным. Но это не так: он утверждает, что существует натуральное число, кодирующее доказательство лжи из аксиом PA, но такое число не может быть в «реальных» натуральных числах, так как в противном случае мы могли бы извлечь подлинное доказательство несостоятельности ПА от него.
PA + Con (PA) имеет модели, но они являются моделями, которые должны включать в себя «дополнительные» объекты, «нестандартные натуральные числа», включая тот, который, как он утверждает, кодирует «доказательство», о котором идет речь. Теория просто не оснащена необходимыми инструментами, чтобы отличить эти нестандартные элементы от подлинных добросовестных членов или продемонстрировать, что доказательство не является законным доказательством.¬ N
В качестве альтернативы вы можете интерпретировать это как: PA + Con (PA) - совершенно законная логическая система - она просто не точно описывает натуральные числа, и натуральные числа не являются ее моделью.¬
Еще одна вещь: мы не предполагаем, что аксиомы верны по определению. Все аксиомы по определению являются лишь основными строительными блоками доказательств. Это просто утверждения: они верны или ложны только применительно к конкретным математическим объектам. У вас могут быть ложные аксиомы, это просто довольно глупо, потому что ваша система обязательно и сразу же не будет здоровой.
источник
Чтобы получить краткий (и интуитивно понятный) ответ, я перефразирую то, что сказал Скотт Ааронсон в своей лекции в 6.045 / 18.400 MIT. Он сказал что-то вроде этого:
Теперь, когда я размышляю, я понимаю, что у меня были некоторые неправильные предположения / идеи:
источник