July 3rd, 2013

Свечка и валокардин

(no subject)

Чего-то я не понимаю. Согласно статье "Recursiveness of initial segments of Kleen's O" (Carl Jockusch, Jr., 1973) для каждого рекурсивного ординала ф существует рекурсивная запись всех ординалов ниже его. (Т.е. некая грамматика G и заданное на ней вычислимой функцией отношение частичного порядка R, порядкоизоморфное ф. Т.е. каждому ординалу ниже ф соответствует выражение G.)

А где-то раньше я читал, что максимальным ординалом для которого возможна сюрьективная рекурсивная запись является малый ординал Веблена, а записи более высоких ординалов неизбежно пропускают по дороге какие-то ординалы (т.е. речь вообще идёт о системах записи другого плана: тут ординалы задаются не через отношения порядка на конкретных конструктивных объектах, а через фундаментальные последовательности.).

Upd: кажется факт про ординал Веблена получается, если говорить не про вообще рекурсивные, а только примитивно-рекурсивные сюрьективные системы записи.