Cтраница 1
Понятие выводимости из посылок позволяет переформулировать теорему о корректности исчисления предикатов. [1]
Понятие выводимости в исчислении предикатов может быть редуцировано к понятию доказуемости способом, аналогичным соответствующей редукции в исчислении высказываний: дедукционная теорема, сформулированная в виде теоремы 3.1, может быть перенесена на исчисление предикатов, и то же самое справедливо по отношению к теореме 3.2. Из обоих этих расширений вытекает, что если мы сможем доказать равносильность утверждений шЛ и - Л, то мы получим доказательство эквивалентности неформального и формального исчисления предикатов-как самих по себе, так и при использовании какого-либо множества формул-посылок. Как и для исчисления высказываний в одну сторону, это доказывается легко. [2]
Задача формалистского преобразования понятий выводимости и непротиворечивости состоит в получении финитных понятий. Достигнуто сведение несчетного к счетно-бесконечному, потому что тождественность и выполнимость относятся к совокупности логических функций, которая несчетна, в то время как их теоретико-доказательственные эквиваленты - доказуемость и неопровержимость - относятся только к счетно-бесконечной совокупности формальных доказательств. В метаматематике рассуждения о понятиях также финитны. Хотя доказательство эквивалентности, которое дает геде-левская теорема о полноте, не может принадлежать метаматематике, для последней существенно, что теоретико-множественные понятия оказываются эквивалентными теоретико-доказательственным, коль скоро рассуждения ведутся в нефинитной плоскости, которой принадлежат теоретико-множественные понятия. [3]
Если бы мы употребляли понятие выводимости в том и другом смысле, то необходимо было бы различать эти два понятия различными терминами. [4]
В исчислении высказываний важную роль играло понятие выводимости из посылок и связанная с ним лемма о дедукции ( с. Для исчисления предикатов ситуация немного меняется. Если разрешить использовать посылки наравне с аксиомами безо всяких ограничений, то утверждение, аналогичное лемме о дедукции, будет неверным. [5]
Это соображение очень важно, так как понятие выводимости в данном формализме включает в себя не только условия выводимости соответствующего равенства, но также и условия невыводимости других равенств. [6]
Посредством этих двух теорем и достигается сведение понятия выводимости к понятию доказуемости. [7]
Понятие истинности формулы на системе наряду с понятием выводимости принадлежит к основным понятиям математической логики. Важность этого понятия объясняется тем, что многие теоремы математики можно выразить как утверждение об истинности некоторой формулы на алгебраических системах из некоторого класса. Это связано с тем, что при бесконечном А пп. [8]
Обычно в аргументационных системах определение аргумента основывается на понятии выводимости в базовом логическом языке. Но иногда оказывается полезным определять специальные правила построения новых аргументов. Это важно, например, в случае формализации предположительного вывода. При предположительном выводе мы предполагаем нечто, что не может быть выведено из исходных данных ( ВХОДа), выводим заключения из предположений, и затем исключаем предположения, чтобы получить связанное заключение, которое больше не зависит от исходного предположения. [9]
Следующее понятие относительной примитивной рекурсивности естественно появляется в нашей теории как средство установления примитивной рекурсивности функций, подобно тому, как понятие выводимости возникло в нашей теории как средство установления доказуемости формул. [10]
Построив новую формальную систему, можно тем самым частично формализовать метаязык ранее построенной системы, о возможности чего уже говорилось. А именно, формализовано понятие выводимости, относящееся к прежней системе. Для новой системы можно определить относящиеся к ней понятия В. [11]
Многие понятия семантики, такие как различные определения истинности, реализуемость по Клини, понятие выводимости в полуформальных системах естественно формализуются именно как общие индуктивные определения. В некоторых случаях общие индуктивные определения допускают дополнительное конструктивное обоснование. [12]
Но это вовсе не означает какого-либо опровержения второй теоремы Геделя. Действительно, эта теорема, как мы помним, содержит в качестве посылок условия 1, 2 и 3, наложенные на понятие выводимости, и мы не показали, что эти условия в F выполнены. При ближайшем рассмотрении условие 1 для F оказывается вообще неопределенным, так как в F не определена выводимость одной формулы из другой. [13]
Для Яп гформул при ге1 истинность конъюнкций и V-формул определяется обычным образом через истинность компонент, а истинность импликации А В означает выводимость В из Л по нек-рым правилам Sn, о к-рых уже доказано, что они сохраняют истинность Я - формул. Системы Sn содержат ео-пра-вило, а в качестве аксиом - все истинные Я - формулы. Понятие выводимости в Sn вводится обобщенным индуктивным определением, а для доказательства мета-теорем применяется соответствующий принцип индукции. Системы Sn 3, ri i, состоят из обычных правил для рассматриваемых связок, включая ш-правило. Оказывается, что почти нормальная формула А истинна по Маркову тогда и только тогда, когда примитивно рекурсивное дерево Т д поиска вывода формулы А без сечения ( но с ш-правилом и принципом Маркова) является выводом в смысле индуктивного определения. В мажорантной семантике Н. А. Шанина для каждой почти нормальной формулы А определяется трансфинитная иерархия Ла формул простой структуры, причем Аа эА доказуемо в подходящей формальной системе. А, и А считается истинной формулой ранга а, если Аа верна. [14]
Как интерпретировать условия выполнимости и выводимости, используемые в этих предусловиях. В самом деле, интерпретация этих условий должна апеллировать к отношению выводимости, заданному системой, которая содержит эти правила с предусловиями. Интерпретация понятия выводимости, входящего в предусловие нельзя сделать вывод, что х не летает, должна учитывать то, что можно вывести с помощью оснащенных этим предусловием правил. [15]