Я пытаюсь построить нотацию для больших счетных ординалов "естественным образом". Под «естественным путем» я подразумеваю, что при индуктивном типе данных X это равенство должно быть обычным рекурсивным равенством (таким же, как deriving Eqв Haskell), а порядок должен быть обычным рекурсивным лексикографическим порядком (таким же, как deriving Ordв Haskell; ), и существует разрешимый предикат, который определяет, является ли член X действительным порядковым обозначением или нет.
Например, порядковые номера, меньшие ε 0, могут быть представлены наследственно конечными отсортированными списками и удовлетворяют этим требованиям. Определите X как µα. μβ. 1 + α × β, то есть наследственно конечные списки. Определите, isValidчтобы проверить, что X отсортирован и все члены X являются isValid. Действительными членами X являются все порядковые числа меньше ε 0 в обычном лексикографическом порядке.
Я предполагаю, что μα 0. … Μα n . 1 + α 0 ×… × α n может использоваться для определения ординалов, меньших φ n + 1 (0), где φ - функция Веблена, аналогичным образом.
Как видите, я исчерпал µ квантификаторов при φ ω (0). Могу ли я построить более крупные порядковые обозначения, удовлетворяющие моим требованиям? Я надеялся добраться до 0 . Могу ли я получить ординалы большего размера, если откажусь от требования разрешимости для моего предиката достоверности?
источник
compareв coq.inria.fr/pylons/contribs/files/Cantor/v8.3/… В этом же файле есть лемма,nf_introкоторая может характеризовать действительность.Inductive lt : T2 -> T2 -> Propне похож на лексикографический порядок для меня.Ответы:
У Германа Руге Джервела есть хорошая система, которая идет вплоть до ординала Бахмана-Ховарда, основанного на помеченных деревьях. Смотрите: http://folk.uio.no/herman/logsem.pdf
Мне также нравится его книга по теории доказательств, в которой обсуждается эта система: http://folk.uio.no/herman/bevisteori.ps
источник