Эрнест Нагель, Джеймс Рой Ньюмен. Теорема Гёделя


Один пример абсолютного доказательства непротиворечивости



Скачать 72.03 Kb.
страница5/7
Дата30.07.2018
Размер72.03 Kb.
ТипКнига
1   2   3   4   5   6   7
Один пример абсолютного доказательства непротиворечивости

В качестве переменных мы будем использовать буквы «р», «q», «r», ..., «p1», «p2» ..., «1», «q2», … Постоянные символы (константы) — это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; «∨» — «или»; «⊃» — «если..., то...»; «•» — «и»; знаки препинания: «(» — «левая скобка», «)» — «правая скобка».

Формулой является каждая пропозициональная переменная. Если «S» обозначает некоторую формулу (именно обозначает, но не является формулой (является именем формулы); S, не принадлежащая алфавиту описываемого исчисления, относится к его метаязыку), то ее «формальное отрицание» «~(S)» также есть формула. Аналогично, если «S1» и «S2» суть обозначения некоторых формул, то выражения «(S1) ∨ (S2)», «(S1) ⊃ (S2)» и «(S1) • (S2)» также суть формулы.

Примеры формул: «р», «~р», «(р)⊃(q)», «((q)∨(r))⊃(р)». Однако выражения «(р)(~q)» или «((р)⊃(q))∨» формулами не являются, так как они не удовлетворяют приведенному здесь определению формулы.

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

Второе правило преобразования — это так называемое правило отделения (или modus ponens). Согласно этому правилу из любых двух формул, имеющих соответственно вид «S1» и «S1⊃S2», можно вывести и формулу «S2». Например, из формул «p∨~р» и «(р∨~р)⊃(р⊃р)» мы можем вывести «р⊃р».

Наконец, аксиомами нашего исчисления (по существу теми же, что в Principia Mathematica являются следующие четыре формулы:


  1. (p∨p)⊃р [если р или р, то р];

  2. p⊃(р∨q) [если р, то р или q];

  3. (р∨q)⊃(q∨p) [если р или q, то q или р];

  4. (p⊃q)⊃((r∨p)⊃(r∨q) [если р влечет q, то (r или р) влечет (r или q)].

Цель наша состоит в том, чтобы показать непротиворечивость этой системы аксиом, т.е. дать «абсолютное» доказательство невозможности вывода из данных аксиом с помощью правил преобразования никакой формулы S одновременно с ее формальным отрицанием ~S.

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

Оказалось, что для столь простой системы свойство «быть тавтологией» наследственно относительно применений правила modus ponens. С другой стороны, можно привести пример формулы нашего исчисления, не являющейся тавтологией. Т.е., можно найти формулу, не являющуюся теоремой нашей системы. Но в случае противоречивости выбранной нами системы аксиом такой формулы в нашем исчислении не нашлось бы. Таким образом, из аксиом исчисления высказываний нельзя вывести никакой формулы одновременно с ее отрицанием. Этим и завершается абсолютное доказательство непротиворечивости исчисления высказываний.

Мы установили, что каждая теорема этого исчисления является тавтологией. Естественно задать и обратный вопрос: каждое ли логически истинное высказывание, выразимое на языке нашего исчисления (т.е. каждая ли тавтология), является теоремой данного исчисления (выводимой из его аксиом)? И на этот вопрос можно дать положительный ответ. Результат этот свидетельствует о достаточности выбранных нами аксиом для получения всех тавтологичных формул — иными словами, всех логически истинных высказываний, выразимых на языке исчисления высказываний. Системы аксиом, обладающие таким свойством, принято называть «полными».

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

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




Каталог: wp-content -> uploads -> 2015
2015 -> Социальная философия
2015 -> Курсовая работа на тему: Наши эмоции друзья или враги? Их роль в конфликтоной ситуации
2015 -> Медиалогия как интегрированная наука информационной эпохи и ее роль в модернизации России Ключевые слова
2015 -> -
2015 -> Вопросы для подготовки к вступительному экзамену в аспирантуру по «Философии»
2015 -> Никколо Макиавелли
2015 -> Астрономия и современная картина мира
2015 -> Методы социологического исследования


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница