Теорема Лёбса - Википедия - Löbs theorem

В математическая логика, Теорема Лёба заявляет, что в Арифметика Пеано (PA) (или любая формальная система, включая PA) для любой формулы п, если в ПА можно доказать, что "если п доказуемо в PA, то п верно ", тогда п доказуемо в PA. Более формально, если Prov (п) означает, что формула п доказуемо, то

или же

Непосредственное следствие ( контрапозитивный ) теоремы Лёба состоит в том, что если п не доказуемо в PA, то "если п доказуемо в PA, то п истинно "не доказуемо в PA. Например," Если доказуемо в PA, то "не доказуемо в ПА.[примечание 1]

Теорема Лёба названа в честь Мартин Хьюго Лёб, сформулировавший его в 1955 году.

Теорема Лёба в логике доказуемости

Логика доказуемости абстракции от деталей кодировок, используемых в Теоремы Гёделя о неполноте выражая доказуемость в данной системе на языке модальная логика, посредством модальности .

Тогда мы можем формализовать теорему Лёба с помощью аксиомы

известная как аксиома GL по Гёделю – Лёбу. Иногда это формализуется с помощью правила вывода, которое

из

Логика доказуемости GL, возникающая в результате взятия модальная логика K4 (или же K, поскольку схема аксиом 4, , затем становится избыточным) и добавление указанной выше аксиомы GL является наиболее интенсивно исследуемой системой в логике доказуемости.

Модальное доказательство теоремы Лёба

Теорема Лёба может быть доказана в рамках модальной логики, используя только некоторые основные правила об операторе доказуемости (система K4) плюс существование модальных неподвижных точек.

Модальные формулы

Мы будем предполагать следующую грамматику формул:

  1. Если это пропозициональная переменная, тогда это формула.
  2. Если пропозициональная константа, то это формула.
  3. Если формула, то это формула.
  4. Если и формулы, то и , , , , и

Модальное предложение - это модальная формула, не содержащая пропозициональных переменных. Мы используем значить это теорема.

Модальные фиксированные точки

Если является модальной формулой только с одной пропозициональной переменной , то модальная неподвижная точка это приговор такой, что

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

Модальные правила вывода

Помимо существования модальных неподвижных точек, мы предполагаем следующие правила вывода для оператора доказуемости , известный как Условия доказуемости Гильберта – Бернейса.:

  1. (необходимость) Из заключить : Неформально это говорит, что если A - теорема, то она доказуема.
  2. (внутренняя необходимость) : Если A доказуемо, то доказуемо.
  3. (распределительная коробка) : Это правило позволяет вам выполнять modus ponens внутри оператора доказуемости. Если доказуемо, что A влечет B и A доказуемо, то B доказуемо.

Доказательство теоремы Лёба.

  1. Предположим, что есть модальное предложение такой, что .
    Грубо говоря, это теорема, что если доказуемо, то это действительно так.
    Это требование прочность.
  2. Из существования модальных неподвижных точек для каждой формулы (в частности, формулы ) следует, что существует предложение такой, что .
  3. Из 2 следует, что .
  4. Из правила необходимости следует, что .
  5. Из 4 и правила распределенности ящика следует, что .
  6. Применение правила распределенности коробки с и дает нам .
  7. Из 5 и 6 следует, что .
  8. Из правила внутренней необходимости следует, что .
  9. Из 7 и 8 следует, что .
  10. Из 1 и 9 следует, что .
  11. Из 2 следует, что .
  12. Из 10 и 11 следует, что
  13. Из 12 и правила необходимости следует, что .
  14. Из 13 и 10 следует, что .

Примеры

Непосредственным следствием теоремы Лёба является то, что если п не доказуемо в PA, то "если п доказуемо в PA, то п верно "не доказуемо в PA. Учитывая, что мы знаем, что PA согласован (но PA не знает, что PA согласован), вот несколько простых примеров:

  • "Если доказуемо в PA, то "не доказуемо в PA, поскольку не доказуемо в PA (так как ложно).
  • "Если доказуемо в PA, то "доказуемо в PA, как и любое утверждение вида" Если X, то ".
  • "Если усиленная конечная теорема Рамсея доказуема в PA, то усиленная конечная теорема Рамсея верна »не доказуема в PA, так как« Усиленная конечная теорема Рамсея верна »не доказуема в PA (несмотря на то, что она истинна).

В Доксастическая логика, Теорема Лёба показывает, что любая система, классифицируемая как рефлексивный "тип 4 "рассуждающий также должен быть"скромный": такой рассуждающий никогда не может поверить, что" моя вера в P будет означать, что P истинно ", не поверив сначала, что P истинно.[1]

Вторая теорема Гёделя о неполноте следует из теоремы Лёба заменой ложного утверждения за п.

Обратное: из теоремы Лёба следует существование модальных неподвижных точек

Из существования модальных неподвижных точек следует не только теорема Лёба, но и обратное. Когда теорема Лёба представлена ​​как аксиома (схема), существование неподвижной точки (с точностью до доказуемой эквивалентности) для любой формулы А(п) модализовано в p можно вывести.[2] Таким образом, в нормальная модальная логика, Аксиома Лёба эквивалентна конъюнкции схемы аксиом 4, , и существование модальных неподвижных точек.

Примечания

  1. ^ Если только PA не противоречит (в этом случае каждое утверждение доказуемо, включая ).

Цитаты

  1. ^ Смуллян, Раймонд М., (1986) Логики, рассуждающие о себе, Материалы конференции 1986 года по теоретическим аспектам рассуждений о знаниях, Монтерей (Калифорния), Morgan Kaufmann Publishers Inc., Сан-Франциско (Калифорния), стр. 341-352
  2. ^ Пер Линдстрем (июнь 2006 г.). «Примечание о некоторых конструкциях с фиксированной точкой в ​​логике обеспечения возможности». Журнал философской логики. 35 (3): 225–230. Дои:10.1007 / s10992-005-9013-8.

Рекомендации

внешняя ссылка