Системы логики, основанные на порядковых числах -Systems of Logic Based on Ordinals

«Системы логики, основанные на порядковых числах» - это докторская диссертация математика Алана Тьюринга .

Тезис Тьюринга не касается нового типа формальной логики, и его не интересовали системы так называемой «ранжированной логики», производные от порядковой или относительной нумерации, в которых можно проводить сравнения между состояниями истинности на основе относительной достоверности. Вместо этого Тьюринг исследовал возможность разрешения условия гёделевской неполноты, используя метод бесконечностей Кантора . Это условие можно сформулировать так: во всех системах с конечным набором аксиом условие исключающего ИЛИ применяется к выразительной силе и доказуемости; то есть у человека может быть сила и никакого доказательства, или доказательство и никакая сила, но не то и другое одновременно.

Диссертация представляет собой исследование формальных математических систем после теоремы Гёделя . Гёдель показал, что для любой формальной системы S, достаточно мощной для представления арифметики, существует теорема G, которая верна, но система не может доказать. G можно было бы добавить в систему как дополнительную аксиому вместо доказательства. Однако это создало бы новую систему S 'со своей собственной недоказуемой истинной теоремой G' и так далее. В тезисе Тьюринга рассматривается, что произойдет, если вы просто повторяете этот процесс несколько раз, генерируя бесконечный набор новых аксиом, добавляемых к исходной теории, и даже идет еще на один шаг в использовании трансфинитной рекурсии для перехода «за бесконечность», что дает набор новых теории G n , по одной на каждый порядковый номер n.

Диссертация была завершена в Принстоне под руководством Алонзо Черча и была классической математической работой, которая ввела понятие порядковой логики .

Мартин Дэвис утверждает, что, хотя использование Тьюринга вычислительного оракула не является основным предметом диссертации, оно оказалось очень влиятельным в теоретической информатике , например, в иерархии полиномиального времени .

использованная литература

внешние ссылки


Значок заглушки

Эта статья по математической логике - незавершенная . Вы можете помочь Википедии, расширив ее .
Значок заглушки

Эта статья о математическом издании - незавершенная . Вы можете помочь Википедии, расширив ее .