Вопрос:
Предположим, у меня есть спецификация задачи, состоящей из аксиом и цели (т. Е. Связанная проблема доказательства состоит в том, является ли цель выполнимой при всех аксиомах). Предположим также, что проблема не содержит каких-либо противоречий / противоречий между аксиомами. Есть ли способ заранее определить (т. Е. Без предварительного построения полного доказательства), что для доказательства проблемы потребуются «рассуждения более высокого порядка»?
Под «рассуждением более высокого порядка» я подразумеваю применение шагов доказательства, которые требуют записи логики более высокого порядка. Типичным примером «рассуждений высшего порядка» может быть индукция: для записи схемы индукции в принципе требуется использование логики высшего порядка.
Пример:
Можно указать задачу доказательства «Является ли сложение на двух натуральных числах коммутативным?» используя логику первого порядка (т.е. определяем натуральное число через конструкторы ноль / succ вместе со стандартными аксиомами вместе с аксиомами, которые рекурсивно определяют функцию «плюс»). Доказательство этой проблемы требует наведения на структуру первого или второго аргумента «плюс» (в зависимости от точного определения «плюс»). Мог ли я знать это до того, как попытаться доказать это, например, проанализировав природу входной проблемы ...? (Конечно, это просто простой пример для иллюстрации - на самом деле это было бы интересно для более сложных задач доказательства, чем коммутативность плюс.)
Еще немного контекста:
В своих исследованиях я часто пытаюсь применить автоматические средства доказательства теорем первого порядка, такие как Vampire, eprover и т. Д., Для решения задач доказательства (или части проблем доказательства), некоторые из которых могут потребовать рассуждения более высокого порядка. Зачастую доказателям требуется некоторое время, чтобы придумать доказательство (при условии, что существует доказательство, которое требует только рассуждений первого порядка). Конечно, попытка применить теорему первого порядка к задаче, которая требует рассуждений более высокого порядка, обычно приводит к таймауту.
Поэтому мне было интересно, существуют ли какие-либо методы / приемы, которые могли бы заранее сказать мне, потребует ли доказательная задача техник рассуждения более высокого порядка (то есть «не тратьте время, пытаясь передать ее доказателю теоремы первого порядка»). ) или нет, по крайней мере, может быть для конкретных проблем ввода.
Я искал в литературе ответ на свой вопрос и спросил некоторых коллег из области теоремы, доказывающей это, - но до сих пор я не получил хороших ответов. Я ожидал бы, что по этой теме будут проведены исследования людей, которые пытаются совместить интерактивное доказательство теорем и автоматическое доказательство теорем (Сообщество Coq? Сообщество Изабель (Кувалда)?) - но пока я ничего не смог найти.
Я предполагаю, что в целом проблема, которую я здесь изложил, неразрешима (не так ли?). Но, может быть, есть хорошие ответы на уточненные версии проблемы ...?
источник
Ответы:
Вкратце, каждая теорема, изложенная в логике первого порядка, имеет доказательство первого порядка.
В своей книге «Введение в математическую логику и теорию типов» Питер Б. Эндрюс развивает логику первого порядка и систему логики высшего порядка Q 0 , которая, как правило, считается основой теории современных доказателей высшего порядка. , (См. Введение к логике HOL, например.)
Для Q 0 и аналогичных систем Эндрюс показывает, что описываемые им логики высшего порядка могут рассматриваться как консервативные расширения логики первого порядка и пишет (второе издание, стр. 259), что «в итоге, каждая теорема первого порядка теория типов имеет доказательство первого порядка ".
Учитывая ваши практические проблемы, я также цитирую следующий абзац:
«Однако некоторые теоремы логики первого порядка могут быть наиболее эффективно доказаны с помощью понятий, которые могут быть выражены только в логике высшего порядка. Примеры можно найти в [Andrews and Bishop, 1996] и [Boolos, 1998, Chapter 25] Статман доказал [Statman, 1978, предложение 6.3.5], что минимальная длина доказательства в логике первого порядка в логике первого порядка может быть необычайно длиннее, чем минимальная длина доказательства того же самого в Логика второго порядка. Связанный результат Годеля [Godel, 1936] заключается в том, что в общем случае «переход к логике следующего более высокого порядка имеет эффект не только того, что можно сделать доказуемыми некоторые высказывания, которые раньше не были доказуемыми, но и сделать можно сократить на необычайную величину бесконечно много уже имеющихся доказательств ». Полное доказательство этого можно найти в [Buss,1994] «.
источник