Часть IV Рекурсии на несчетных рекурсиях

Суждение о множестве или его элементах может быть эквивалентно другому множеству, но само по себе никогда не является им - следствие Аксиом Выделения, Преобразования и Свертывания.

Приветствую всех кто добрался до четвертой части, и раз уж вы здесь, то вероятно вы серьезно настроены разобраться в теме больших чисел. Но перед тем как идти дальше нам опять необходимо определить подсистему арифметики второго порядка, в которой мы будем создавать рекурсии. И раз уж мы решительны в своем намерении постичь большие числа, то нам просто необходимо понять сами принципы выделения этих подсистем. Как всегда начнем издалека, и чтобы понять как создаются некоторые подсистемы арифметики разных порядков, давайте сперва поговорим о средствах языка, на котором формулируются аксиомы.

Средства формулировки аксиом и теорем на их основе изучаются математической логикой, а это отдельный раздел математики. Так давайте немного погрузимся в математическую логику и дадим определение понятию формула. Формула - это выражение, которое состоит из предикатов, функций и переменных. Под функцией подразумевают функцию определенную на числах или множествах, как минимум арифметическую. Например, операции " +, ×, - , / " однозначно являются функциями, причем 2-арными (бинарными), то есть принимающими два аргумента. Операции a! - факториал, |a| - модуль и т.п. называют 1-арными (унитарными), то есть принимающими один аргумент. Функции 0-арные, не принимающие аргументов, называют константами, например, если в выражении встретилось какое-либо число, допустим "2", это можно считать 0-арной функцией, результат которой всегда равен 2, вероятно это звучит излишне усложнено и запутано, зато позволяет встроить все в одну общую схему. В языке арифметики в качестве переменных a, b, c, x, y, z,... могут выступать числа, или A, B, C, X, Y, Z,... - множества, если мы говорим о языке арифметики второго порядка.

А вот о том, что такое предикаты - мы поговорим отдельно. Предикатом называют математическое суждение, или логическую функцию. Например, операции " < , ≤ , > , ≥ , = , ≠ " являются 2-арными (бинарными) предикатами, то есть выносящими математическое суждение о двух аргументах, результатом логического суждения может быть либо "правда" (true), либо "ложь" (false). Предикаты тоже могут принимать разное число аргументов, например, быть 1-арными (унитарными), как ¬a - логическое отрицание, или 0-арными, не принимающими аргументов - логическими константами, например, просто "true". Предикаты так же как и функции могут быть простыми (не составными) и сложными (составными). Последние это такие, которые включают в себя другие предикаты или функции.

Как всегда разобраться в теории без примеров многим будет сложно, поэтому привожу формулу, которую мы разберем на составляющие. Формула y!×(x+5) ≤ z состоит из 2-арного предиката "≤", который принимает два аргумента: y!×(x+5) и переменную "z"; аргумент y!×(x+5) является 2-арной функцией "×", которая состоит из аргументов (x+5) и y!, каждый из которых тоже является функцией: первая функция 1-арная "!" на переменной "y", а вторая 2-арная функция "+", принимающая два аргумента: переменную "x" и 0-арную функцию (константу), всегда равную "5".

А теперь я расскажу о кванторах, так называют специальные ограничители, которые задают область распространения предиката. Допустим я высказываю такое математическое суждение: "каждое четное число делится на два", формально я должен записать это суждение следующим образом: ∀x∈E∃y∈N(x/2=y), что дословно расшифровывается так: для любого x являющегося четным числом, существует y являющееся натуральным числом, так что при делении x на 2 получится y (где N - множество натуральных чисел, E - множество четных чисел). Знаки "∀" и "∃" как раз являются кванторами, которые определяют область действия предиката x/2=y. "∀" называют квантором всеобщности и расшифровывается он как "для каждого", "∀" называют квантором существования и расшифровывается он как "существует". Формально квантор всеобщности на неком предикате определяется так: ∀P(x) = "P(x₁) и P(x₂) и P(x₃) и ...", ну а квантор существования так: ∃P(x) = "P(x₁) или P(x₂) или P(x₃) или ...". Эти предикаты неизбежно возникают в определении достаточно сложных формул. Если в приложениях, в которых приводились аксиомы к разным теориям, вы пропустили формальное определение этих аксиом, то теперь вы можете к ним вернуться и, уже зная что такое предикаты и кванторы, попробовать расшифровать это формальное определение.

Вам будет проще понять идею квантификации, если вы хотя бы немного знакомы с программированием. В программировании кванторы можно выразить как циклы, то есть повторяющиеся операции с неким условием завершения этого цикла. Так например, квантор "∀" эквивалентен циклу while(P(x) = true), где P(x) некий предикат, то есть логическая функция над переменной x. Иными словами цикл работает пока x удовлетворяет некому условию. В свою очередь квантор "∃" эквивалентен циклу while(P(x) = false), где P(x) некий предикат, то есть логическая функция над переменной x. Это когда цикл работает до тех пор пока x не удовлетворит некому условию. Вроде бы оба примера похожи, и может показаться, что один можно легко превратить в другой. А вот и нет, такое превращение while(P(x) = true) ↔ while(P(x) = false) возможно далеко не всегда.

Теперь, когда вы знаете что такое квантификация, я расскажу вам об еще одной важной вещи, настолько важной, что если вы ее не поймете, то ближе к концу книги, когда мы будем обсуждать уже невероятно сильные рекурсии, вы совсем не сможете в них разобраться без этих знаний. Знакомьтесь: Арифметическая иерархия! В двух словах это классификация рекурсивных формул на основе принципов квантификации. Дело в том, что любую рекурсивную функцию мы можем записать как формулу содержащую простые функции объединенные кванторами в более сложные функции. Начну с объяснения самых простых рекурсий, которые создаются примитивно-рекурсивными функциями, можете посмотреть в третьей главе их полное определение, в двух словах напомню, что это функции выражаемые при помощи циклов, в которых заранее известно количество итераций (таких циклов, в которых мы можем быть уверены, что в них не возникнет бесконечная петля при вычислении и наш компьютер на зависнет). В программировании такие циклы будут выглядеть так: while(x<y) или while(x>y), причем любую примитивную рекурсию можно выразить как при помощи первого вида циклов, так и при помощи второго вида циклов, а это значит, что квантификации ∀x(x<y) и ∃x(x<y) полностью эквивалентны, такие квантификации и называют ограниченными. Формулы, которые содержат только ∀x(x<y), называют П₀-формулами, а формулы, которые содержат только ∃x(x<y), называют Σ₀-формулами. Как мы выяснили, в случае ограниченной квантификации не имеет значения какой квантор использовать "∀" или "∃", все равно П₀-формулы будут эквивалентны Σ₀-формулам.

int add(int a,int b){
    int i = 0;
    while (i < b){
        a++;
        i++;
    }
    return a;
}

int mul(int a,int b){
    int r = 0
    int i = 0;
    while (i < b){
        r = add(a,r);
        i++;
    }    
    return r;

}
int pow(int a,int b){
    int r = 1;
    int i = 0;
    while (i < b){
        r = mul(a,r);
        i++;
    }        
    return r;
}

int tetra(int a,int b){
    int r = 1;
    int i = 0;
    while (i < b){
        r = pow(a,r);
        i++;
    }        
    return r;
}

int add(int a,int b){
    for (int i=0; i<b; i++) a++;
    return a;
} 

int mul(int a,int b){
    int r = 0;
    for (int i=0; i<b; i++) r = add(a,r);
    return r;
}

int pow(int a,int b){
    int r = 1;
    for (int i=0; i<b; i++) r = mul(a,r);
    return r;
}

int tetra(int a,int b){
    int r = 1;
    for (int i=0; i<b; i++) r = pow(a,r);
    return r;
}

int add(int a,int b){
    if (b > 0) return add(a+1,b-1); 
    else return a;
}
	
int mul(int a,int b){
    if (b == 0) return 0;
    else if (b > 0) return add(a,mul(a,b-1));
    else return a;
}
	
int pow(int a,int b){
    if (b == 0) return 1;
    else if (b > 0) return mul(a,pow(a,b-1));
    else return a;
}
		
int tetra(int a,int b){
    if (b == 0) return 1;
    else if (b > 0) return pow(a,tetra(a,b-1));
    else return a;
}

int ackermann(int m, int n){ 
    if (m = 0) return n+1;
    else if (n = 0) return ackermann(m-1, 1); 
    else return ackermann(m-1, ackermann(m, n-1)); 
}

int ackermann(int m, int n) {
    int v[n];
    int s = 0;
    while (true) {
        if (m == 0) {
            n++;
            if (s-- == 0) break;
            m = v[s];
            continue;
        }
        if (n == 0) {
            m--;
            n = 1;
            continue;
        }
        int i = s++;
        v[i] = m - 1;
        n--;
    }
    return n;
}

Функции, которые не являются примитивно-рекурсивными, нельзя выразить при помощи ограниченной квантификации, то есть на основе П₀-формул или Σ₀-формул, для них может потребоваться квантификация некого произвольного предиката. Как я и говорил ранее для вычисления таких функций нам необходимы такие условия выхода из цикла, которые не зависят напрямую от происходящей в нем рекурсии. Конечно внутри цикла будет происходить вычисление на основе П₀-формул или Σ₀-формул, однако выход из верхнего цикла определяется по методу исключения, то есть при программировании такой формулы мы заранее не можем знать сколько раз сработает цикл, и чисто теоретически, если внутренние П₀-формулы или Σ₀-формулы будут заданы неверно, то выход из цикла так и не произойдет и наш компьютер зависнет. Таких циклов основанных на исключениях можно задавать сколько угодно. Но как мы знаем исключения бывают двух видов, первый: P(x) = true - когда цикл работает пока условие удовлетворяет какому-либо требованию, второй: P(x) = false - когда цикл работает до тех пор пока условие не удовлетворит какому-либо требованию. Интересно то, что сила создаваемой рекурсии будет определяться не количеством подобных циклов, а за счет чередованием их вида. Так например, формула основанная только на первом виде циклов с исключениями будет формально записываться так ∀a∀b∀c∀...(f(a,b,c,z)) [где f() - это П₀-формула или Σ₀-формула] - и будет называться П₁-формулой, ну а формула основанная только на втором виде циклов с исключениями будет формально записываться так ∃a∃b∃c∃...(f(a,b,c,z)) [где f() - это П₀-формула или Σ₀-формула] - и будет называться Σ₁-формулой. При этом каждая из формул ∃a∀b(f(a,b,z)) или ∀a∃b(f(a,b,z)) [где f() - это по-прежнему некая П₀-формула или Σ₀-формула] может быть сильнее любой из выше перечисленных Σ₁-формул или П₁-формул, и относится они будут уже к классу Σ₂-формул и П₂-формул соответственно. Теперь мы можем дать формальное определение понятию П_n-формула и Σ_n-формула:
Σ_n - ∃a₁∃b₁∃c₁∃...∀a₂∀b₂∀c₂∀...∃a₃∃b₃∃c₃∃...∀a₄∀b₄∀c₄∀...∃a₅∃b₅∃c₅∃... ...Qa_nQb_nQc_nQ...(f(a,b,c,z))
П_n - ∀a₁∀b₁∀c₁∀...∃a₂∃b₂∃c₂∃...∀a₃∀b₃∀c₃∀...∃a₄∃b₄∃c₄∃...∀a₅∀b₅∀c₅∀... ...Qa_nQb_nQc_nQ...(f(a,b,c,z))
где f() - некая П₀-формула или Σ₀-формула, Q будет квантором "∀" или "∃" в зависимости от четности n.

Тем, кому сложно понять такое формальное определение арифметической иерархии, я попробую объяснить все это еще раз, но уже немного упрощенно. П₀-формула = Σ₀-формула - это формула, которая содержит любое количество кванторов "∀" и "∃", но каждый из них ограничен тем, что может быть применим только к предикату (x<y). Поскольку П₀-формулы и Σ₀-формулы эквиваленты при вычислении, то следующие два определения для них тоже будут верными: (1) формула, которая содержит любое количество кванторов "∀", применимых только к предикату (x<y) и (2) формула, которая содержит любое количество кванторов "∃", применимых только к предикату (x<y). П₁-формула - это формула, которая содержит любое количество кванторов "∀" (их можно применять к любым предикатам). Σ₁-формула - это формула, которая содержит любое количество кванторов "∃" (их можно применять к любым предикатам). П₂-формула - это формула, которая содержит любое количество кванторов "∀", за которым следует любое количество кванторов "∃". Σ₂-формула - это формула, которая содержит любое количество кванторов "∃", за которым следует любое количество кванторов "∀". П₃-формула - это формула, которая содержит любое количество кванторов "∀", за которым следует любое количество кванторов "∃", за которым следует любое количество кванторов "∀". Σ₃-формула - это формула, которая содержит любое количество кванторов "∃", за которым следует любое количество кванторов "∀", за которым следует любое количество кванторов "∃". И так далее.

Как можно заметить из определения: П₁-формулы включают в себя П₀-формулы и Σ₀-формулы, так же как Σ₁-формулы включают в себя П₀-формулы и Σ₀-формулы. В свою очередь П₂-формулы включают в себя П₁-формулы и Σ₁-формулы, так же как Σ₂-формулы включают в себя П₁-формулы и Σ₁-формулы. И так далее. Поэтому подобную классификацию формул и называют арифметической иерархией. Однако пусть П₀-формулы и Σ₀-формулы эквивалентны, то есть могут быть выражены и так и так, но при этом всевозможные П₁-формулы и Σ₁-формулы уже нельзя выразить друг через друга, так же как П_n-формулы и Σ_n-формулы, где n>0; эквивалентно друг через друга можно выразить только часть из них. Как раз эту часть П_n-формул и Σ_n-формул, которую можно взаимовыразить, называют Δ_n-формулами. За исключением Σ₀ = П₀ = Δ₀, потенциально возможные формулы Δ_n создают рекурсию слабее, чем П_n-формулы или Σ_n-формулы, но те в свою очередь, хоть и несводимы, создают одинаковые по силе рекурсии.

Теперь давайте поговорим об уровне переменных. Если в качестве переменных мы используем только натуральные числа, то это считается нулевым уровнем в арифметической иерархии и для разного вида формул записывается просто как "Σ_n", "П_n", "Δ_n" или же с применением верхнего индекса "Σ⁰_n", "П⁰_n", "Δ⁰_n" (данная запись применяется редко). Если кроме натуральных чисел нам дозволено использовать в формулах еще и множества натуральных чисел, то это считается первым уровнем в арифметической иерархии и записывается так "Σ¹_n", "П¹_n", "Δ¹_n" (иногда это называют аналитической иерархией). Если мы так же можем пользоваться множествами множеств натуральных чисел, то это будет уже второй уровень и записываться будет так "Σ²_n", "П²_n", "Δ²_n". И так далее, мы можем определять все бо́льшие и бо́льшие уровни арифметической иерархии. Общее правило взаимосвязи между уровнями будет следующее: Σ^m_ω = П^m_ω = Δ^m_ω = Σ^m+1₀ = П^m+1₀ = Δ^m+1₀. Нам же пока будет достаточно нулевого и первого уровня.

Вот теперь мы полностью готовы разбираться с правилами выделения подситем арифметики второго порядка. Еще раз напомню, что арифметика второго порядка это очень сильная арифметическая система, которая отличается от арифметики первого порядка тем, что мы можем использовать в ней не только натуральные числа, но и множества натуральных чисел. С точки зрения системы аксиом, она отличается тем, что в ней изменена аксиома индукции и добавлена аксиома свертывания. Напомню, что в своем стандартном виде аксиома индукции утверждает: то что в неком математическом суждении верно для некого натурального числа и верно для следующего за ним, должно быть верно для всех натуральных чисел (при этом "0" разрешено исключить из этого правила). В арифметике второго порядка в определении индукции понятие математического суждения заменено на понятие принадлежности к некому множеству, что позволяет включить в индукцию не только натуральные числа, но и множества натуральных чисел. Аксиома свертывания - это утверждение о том, что выделение подмножества на множестве натуральных чисел может быть сопоставлено некой формуле над этим подмножеством, что значит: каждой арифметической формуле может быть сопоставлено определенное подмножество натуральных чисел, которое будет ей эквивалентно (но тем не менее сама формула не является этим подмножеством). Эта аксиома и будет являться основным инструментом для выделения подсистем, нам всего лишь нужно ограничить уровень арифметической формулы, которая может быть сопоставлена с подмножеством натуральных чисел, методами арифметической иерархии.

Итак давайте разбирать на примерах: Σ₀-СA₀, П₀-СA₀, или Δ₀-СA₀ так будет называться подсистема арифметики второго порядка, в которой аксиома свертывания ограничена Σ₀-формулами, П₀-формулами, или Δ₀-формулами, которые как мы знаем полностью эквивалентны друг другу. Но это еще не все, последний нолик в названии подсистемы говорит о том, что аксиома индукции тоже ограничена в рамках этих формул и распространяется только на них, если этого не сделать, то возможности подсистемы станут намного шире. Так вот, Σ₀-СA₀, П₀-СA₀, или Δ₀-СA₀ это все равнозначные определения RCA₀ - Аксиом рекурсивного свертывания, что эквивалентно PRA - примитивно-рекурсивной арифметике, максимально возможная рекурсия и следовательно PTO этой подсистемы будут равны ω^ω. Интересно то, что Δ₁-СA₀ - подсистема арифметики второго порядка, в которой аксиома свертывания ограничена Δ₁-формулами тоже будет иметь PTO равный ω^ω и будет эквивалентна RCA₀ и PRA.

Подсистемы Σ₁-СA₀, П₁-СA₀ и Δ₂-СA₀ уже не будут полностью эквивалентны друг другу, потому что, как мы помним, формулы П_n и Σ_n, где n>0, нельзя взаимовыразить, однако максимально возможная рекурсия на основе этих аксиоматических систем будет одинаковой: PTO = ω^ωω. Соответственно PTO для подсистем Σ₂-СA₀, П₂-СA₀ и Δ₃-СA₀ будет равен ω^ωωω, и так далее. В арифметике первого порядка тоже можно выделить похожие подсистемы. Подсистемы арифметики первого порядка с ограниченной аксиомой индукции обычно кратко записывают так I'F', где на место 'F' подставляют тип формул из арифметической иерархии, на которые распространяется аксиома индукции, так IΣ₀ = IП₀ = IΔ₀ = IΔ₁ = PRA. Соответственно подсистемы IΣ₁, IП₁, IΔ₂ будут сильнее, но уже не эквивалентны друг другу, однако все будут иметь PTO равный ω^ωω . Тогда у подсистем IΣ₁, IП₁, IΔ₂ будет PTO равный ω^ωωω, и так далее. В общем случае мы даже можем вывести правило для определения PTO, которое будет работать для всех таких подсиcтем: PTO Σ_n-СA₀ = PTO П_n-СA₀ = PTO Δ_n+1-СA₀ = PTO IΣ_n = PTO IП_n = PTO IΔ_n+1 = ⁿ⁺²ω.

Теперь мы можем определить подсистемы Σ_ω-СA₀, П_ω-СA₀ и Δ_ω-СA₀, которые будут эквивалентны. Их следует понимать как арифметику второго порядка, в которой аксиома свертывания ограничена только для формул на натуральных числах с использованием любого числа кванторов, любых видов и в любом порядке (то есть речь идет о любых арифметических формулах на натуральных числах). Как мы помним, по-другому эту подсистему называют ACA₀ (Аксиомами арифметического свертывания), которая эквивалентна Арифметике Пеано (PA) - обычной арифметике первого порядка (в которой вообще нет множеств), она же будет эквивалентна Σ¹₀-СA₀, П¹₀-СA₀ и Δ¹₀-СA₀, то есть арифметике второго порядка, в которой аксиома свертывания ограничена только для формул на множествах натуральных чисел с использованием кванторов, применимых только к предикату (x<y). Ну и наконец, Δ¹₁-СA₀ тоже будет эквивалентна ACA₀, где под Δ¹₁ - понимаются формулы на множествах натуральных чисел, с использованием любого количества кванторов "∀", такие что их можно выразить с использованием любого количества кванторов "∃", и наоборот. Так же если в подсистемах Σ_n-СA₀, П_n-СA₀ и Δ_n-СA₀ мы не будем ограничивать аксиому индукции, а оставим ее в том виде, в котором она определена в полной системе арифметики второго порядка, то тогда подсистемы следует записывать так Σ_n-СA, П_n-СA, и Δ_n-СA - как я и говорил, они станут сильнее и тоже будут эквивалентны ACA₀. Однако стоит отметить, что в ACA₀ аксиома индукции тоже ограничена тем, что сформулирована так как она определена в арифметике первого порядка (во всех более сильных подсистемах под ограничением аксиомы индукции будет подразумеваться именно это), только с таким ограничением ACA₀ эквивалентна PA и ее PTO = ε₀. В случае, если мы оставим аксиому индукции не ограниченной, такой какой она определена в полной системе арифметики второго порядка, то тогда подсистема будет называться ACA и ее PTO станет равен ε_ε0, а это значит, что в такой подсистеме есть возможность создать более сильные рекурсии.

Если с приставками Σ^m_n, П^m_n, Δ^m_n и суффиксами CA и CA₀ вам все уже должно быть понятно, то теперь нам с вами еще следует разобрать такие суффиксы: TR₀, ТR, CA+BI. Все они тоже обозначают изменения в аксиоме индукции. TR₀ - значит, что индукция сформулирована для арифметических формул как в арифметике первого порядка, но допускает свое применение не только к натуральным числам, но и к трансфинитным ординалам. TR - значит, что индукция сформулирована как в полной системе арифметики второго порядка, то есть в определении вместо "суждения над натуральными числами" используется "принадлежность натуральных чисел к множеству", ну и само понятие натуральных чисел так же может быть расширено до трансфинитных ординалов. Наконец, CA+BI - означает применение аксиомы ограничивающей индукции, которая взамен классической формулировки предлагает другую: "что верно для бесконечной последовательности натуральных чисел, будет верно и для любого ее конечного участка". Каждая подобная модификация аксиомы индукции создает разные по силе аксиоматические системы.

На самом деле есть еще огромное количество других способов изменить аксиомы арифметики второго порядка, сделав их слабее, и выделяя тем самым другие подсистемы аксиом, но в рамках данной книги нам достаточно и этих способов. Поэтому теперь, вооружившись всеми нашими знаниями, давайте сопоставим все подсистемы арифметики второго порядка, какие мы сможем выделить, в порядке возрастания их силы и начнем с тех, рекурсивные возможности которых мы уже преодолели в нашей погоне за большими числами.

А в следующей таблице так же в порядке возрастания их рекурсивной силы приведем подсистемы арифметики второго порядка, пределы возможностей которых нам только предстоит достичь. В ней же я приведу PTO этих подсистем, и пусть вам пока они будут не понятны, но вы всегда можете вернуться к этой таблице по мере того как постигнете масштабы этих ординалов.

Хочу сразу предупредить вас, что на сегодняшний день предел рекурсивных возможностей арифметики второго порядка до сих пор не достигнут, есть исследовательские работы или гипотетические разработки на счет этого, но не существует гарантированной рабочей ординальной нотации, такой в которой можно было бы показать, что она является вполне упорядоченной, так чтобы можно было проверить все ее фундаментальные последовательности. Самое большое что профессионально изучалось со всеми доказательствами - это рекурсивный предел подсистемы П¹₂-CA₀ (однако, как оказалось, эта работа содержала ряд технических ошибок, так что фактически фундаментальные последовательности этого предела тоже не рабочие). Для более сильных систем PTO, которые я привел в таблице, не имеют надежной  проверенной ординальной нотации, способной расписать их фундаментальные последовательности, а саму запись таких PTO следует считать условной (поэтому я отметил их знаком "?!"). Мы с вами тоже доберемся до этих зыбких полугипотетических масштабов, но пока что мы стоим на твердой почве Ординальной коллапсирующей функции Бухольца, по которой легко сможем добраться до пределов П¹₁-CA₀. На этом я заканчиваю данное отступление и мы с вами снова продолжаем карабкаться вверх.

В конце третьей части мы остановились на ψ(^ωΩ), который именовался Ординалом Бахмана-Говарда, в сущности он представляет собой бесконечную степенную башню их несчетных ординалов внутри коллапсирующей функции. Как мы с вами выяснили арифметические действия выше уровня ^ωn над ординалами уже не применимы, при чем не важно над счетными или над несчетными, однако мы можем воспользоваться особенностями ординальной арифметики чтобы продолжить рекурсии дальше. Помните в третьей части мы вывели с вами два важных принципа: первый - ω^α+1 = α×ω, если ω^α = α; и второй: ε_α+1 = ^ωα, если ω^α = α; так вот эту особенность ординальной арифметики можно применить и к несчетным ординалам:
Ω×ω = ω^Ω+1
Ω² = ω^Ω×2
Ω^ω = ω^ωΩ+1
Ω^Ω = ω^ωΩ×2
Ω^Ωω = ω^ωωΩ+1
Ω^ΩΩ = ω^ωωΩ×2
Ω^ΩΩω = ω^ωωωΩ+1
Ω^ΩΩΩ = ω^ωωωΩ×2
Ω^ΩΩΩω = ω^ωωωωΩ+1
ε_Ω+1 = Ω^ΩΩΩ...= ω^ωω...Ω+1

Выражение арифметики любых больших ординалов до уровня ω-тетрации таким способом, называется применением нормальной формы Кантора (Cantor normal form - CNF), с ней мы уже встречались, когда обсуждали нотацию Кантора, так вот с ее помощью можно увеличить любой ординал α, такой что ω^α = α, до уровня ε_α+1. Обращаю ваше внимание, что такое выражение ε_Ω будет равно просто Ω, так же как ε_ζ0 = ζ₀, ε_η0 = η₀, и т.д. Так проиходит потому что ε_Ω обозначает неподвижную точку α↦ω^α (ω^ωωω...) под номером Ω - несчетного ординала, которая и будет, по сути, несчетным ординалом, однако ε_Ω+1 будет означать следующую неподвижную точку α↦ω^α (ω^ωωω...), идущую после Ω и, собственно, равную ω^ωω...Ω+1 или Ω^ΩΩΩ... = ^ωΩ. Таким образом, мы можем продолжать наращивать рекурсии на Ω и после ^ωΩ. Например, выражение ε_Ω+2 будет означать вторую неподвижную точку α↦ω^α (ω^ωωω...), идущую после Ω, и будет равно ε_Ω+1^{ε_Ω+1ε_Ω+1ε_Ω+1...} = ω^{ωω...ε_Ω+1}. Так же как мы делали ранее, когда очень условно сопоставляли высшие арифметические действия с расширенной ординальной нотацией Кантора, так же очень условно мы можем сопоставить ε_Ω+2 ≅ ^ω×2Ω. Соотвественно, ε_Ω+3 = ε_Ω+2^{ε_Ω+2ε_Ω+2ε_Ω+2...} = ω^{ωω...ε_Ω+2} ≅ ^ω×3Ω. Продолжая создавать подобные неподвижные точки, сразу перейдем к их трансфинитным значениям: ε_Ω+ω = ε_Ω+ψ(1), ε_Ω+ε0 = ε_Ω+ψ(Ω), ε_Ω+Г0 = ε_Ω+ψ(²Ω), ..., ε_Ω+ψ(^ωΩ) = ε_{Ω+ψ(εΩ+1)}. Так можно добраться до ε_Ω+Ω, которую в рамках коллапсирующей функции можно представить как диагонализацию: ψ(ε_Ω+Ω) = ψ(ε_Ω×2) = ψ(ε_{Ω+ψ(εΩ+ψ(εΩ+...))}). Ну а затем, как мы уже умеем, создадим последовательность диагонализаций используя Ω - несчетный ординал: ψ(ε_Ω×Ω) = ψ(ε_Ω²) = ψ(ε_{Ω×ψ(εΩ×ψ(εΩ×...))}), ψ(ε_Ω^Ω)= ψ(ε_{Ω^{ψ(εΩψ(εΩ...))}}), и т.д., до тех пор пока ψ(ε_εΩ+1) = ψ(ε_Ω^ΩΩΩ...), ну а затем ψ(ε_εεΩ+1) = ψ(ε_{εΩ^ΩΩΩ...}), и так до ψ(ε_εε...Ω+1), что уже следует считать следующей неподвижной точкой α↦ε_α (ε_εεε...), идущей после Ω, которую можно записать так ζ_Ω+1. Опять же очень условно ее можно сравнить с пентацией ζ_Ω+1 ≅ Ω[5]ω, так же как мы делали это ранее для ζ₀ ≅ ω[5]ω. Чтобы не ходить вокруг да около, сразу перейдем к ζ_ζζ...Ω+1 = η_Ω+1 следующей неподвижной точке α↦ζ_α (ζ_ζζζ...), идущей после Ω, так же условно сопоставимой с гексацией η_Ω+1 ≅ Ω[6]ω. Такие условные сопоставления возможны только до уровня Г_Ω+1, что вероятно было бы эквивалентно Г_Ω+1 ≅ ...[Ω[Ω[Ω]Ω]Ω]..., но поэтапно добраться до этого уровня будет непросто.

Давайте позовем на помощь Функцию Веблена. Нам ничто не мешает, немного изменив ее опредение, применять ее на несчетных ординалах. Тогда ε_Ω+1 = φ(1,Ω+1), ζ_Ω+1 = φ(2,Ω+1), η_Ω+1 = φ(3,Ω+1), и так до φ(ω,Ω+1). Как мы помним, φ(ω,1) был пределом последовательности {ω^φ(ω,1)+1 = φ(φ(ω,1)+1), ε_φ(ω,1)+1 = φ(1,φ(ω,1)+1), ζ_φ(ω,1)+1 = φ(2,φ(ω,1)+1), η_φ(ω,1)+1 = φ(3,φ(ω,1)+1), ... }, соответственно φ(ω,Ω+2) будет пределом последовательности {ω^{φ(ω,Ω+1)+1} = φ(φ(ω,Ω+1)+1), ε_{φ(ω,Ω+1)+1} = φ(1,φ(ω,Ω+1)+1), ζ_{φ(ω,Ω+1)+1} = φ(2,φ(ω,Ω+1)+1), η_{φ(ω,Ω+1)+1} = φ(3,φ(ω,Ω+1)+1), ... }. Дальше тоже все аналогично, как φ(ω+1,0) являлась первой неподвижной точкой α↦φ(ω,α), для последовательности {φ(ω,1), φ(ω,φ(ω,1)), φ(ω,φ(ω,φ(ω,1))), ...}, так же и φ(ω+1,Ω+1) является первой неподвижной точкой для последовательности {φ(ω,Ω+1), φ(ω,φ(ω,Ω+1)), φ(ω,φ(ω,φ(ω,Ω+1))), ...}. В общем, используя аналогии тех рекурсий, что мы создавали на счетных ординалах, делаем тоже самое с нечетными. Например, запишем такое выражение: φ(φ(φ(φ(...,0),0),0),Ω+1) = φ(Г₀,Ω+1) = φ(ψ(Ω^Ω),Ω+1). Дальше φ(ψ(ε_Ω+1),Ω+1) = φ(ψ(φ(1,Ω+1)),Ω+1), потом φ(ψ(φ(ψ(1,Ω+1)),Ω+1)),Ω+1) и так, в рамках ординальной коллапсирующей функции, мы можем дойти до α↦ψ(φ(α,Ω+1)) = ψ(φ(ψ(φ(ψ(φ(ψ(φ(...,Ω+1)),Ω+1)),Ω+1)),Ω+1)), которую сможем диагонализировать таким образом ψ(φ(Ω,1)). Следующая диагонализация будет выглядеть так ψ(φ(Ω,Ω)) = ψ(φ(Ω,ψ(φ(Ω,ψ(φ(Ω,...)))))) = α↦ψ(φ(Ω,α)). Тогда, продолжая диагонализации дальше, получим: ψ(φ(Ω+1,0)) = ψ(φ(Ω,φ(Ω,φ(Ω,φ(Ω,...))))) = ψ(α↦φ(Ω,α)). Ну и, в конце концов, создавая череду выражений: ψ(φ(φ(Ω,1),0)), ψ(φ(φ(φ(Ω,1),0),0)), ψ(φ(φ(φ(φ(Ω,1),0),0),0)), ... мы наконец-то достигнем заветного ψ(φ(φ(φ(...φ(Ω,1)...,0),0),0)) = ψ(φ(1,0,Ω+1)) = ψ(Г_Ω+1).

Дальше я не буду расписывать как можно продолжать накручивать рекурсии Функцией Веблена на Иерархии Бахмана. Пройдемся только по основным моментам. От выражения ψ(φ(1,0,Ω+1)) сразу перейдем к ψ(φ(1,0,0,...,Ω+1)), которое в матричном виде можно записать так ψ(φ(¹_ω^Ω+1₀)). Отсюда сразу, минуя все промежуточные матричные представления Шутте, переходим к ψ(φ(¹_{φ(¹φ(¹φ(¹...)))} ^Ω+1₀)) = ψ(φ(¹_ψ(Ω^ΩΩ) ^Ω+1₀)). Потом совершаем резкий скачек к ψ(φ(¹_{ψ(φ(¹ψ(Ω^ΩΩ) ^Ω+10))} ^Ω+1₀)). В итоге, если мы продолжим такую цепочку подстановок, наш ожидает неподвижная точка α↦ψ(φ(¹_α ^Ω+1₀)), которую мы можем диагонализировать так ψ(φ(¹_Ω¹₀)). Это позволит довести Иерархию Веблена до своего апофеоза в виде последовательности: {ψ(φ(¹_Ω¹₀)), ψ(φ(¹_φ(¹Ω¹0))), ψ(φ(¹_{φ(¹φ(¹Ω¹0))})), ..., ψ(φ(¹_{φ(¹φ(¹...φ(¹Ω¹0)...))}))}. Но, так или иначе, это очень слабый способ усиления Иерархии Бахмана, поскольку для ее продолжения мы используем более слабую по сравнению с ней Иерархию Веблена. Чтобы по-настоящему усилить Иерархию Бахмана, нам нужна уже другая Иерархая Бахмана над ней.

Кроме того все рекурсии выше уровня ε_Ω+1 внутри коллапсирующей функции становятся условными, потому что в ее определении нет ни Расширенной нотации Кантора, ни Функции Веблена, поэтому без добавления их внутрь определения мы не сможем определить фундаментальные последовательности для функций быстрорастущих иерархий, которые нужны нам для вычисления конечного числа. Конечно их можно туда внедрить, но это только усложнит определение коллапсирующей функции, так же как и усложнит определение фундаментальных последовательностей, да к тому же, как мы выяснили, будет не эффективно с точки зрения усиления рекурсии, ведь, как мы помним, для настоящего усиления рекурсии требуется создать над ней другую рекурсию либо такую же по силе, либо еще сильнее. Как минимум такой же по силе будет рекурсия основанная на другой коллапсирующей функции.

Основная идея заключается в том же преемственном процессе рекурсирования. Как когда для создания рекурсий над конечными числами мы использовали счетные ординалы с кардианльностью ℵ₀, и как когда для создания рекурсий над счетными ординалами мы использовали несчетные ординалы с кардианльностью ℵ₁, так же для создания рекурсий над последними нам нужны ординалы с кардинальностью ℵ₂. Наименьший ординал обладающий кардинальностью ℵ₂ называется ω₂ - это ординал идущий сразу после всех ординалов с кардинальностью ℵ₁, то есть он точно больше чем любая рекурсия построенная на ординале ω₁. Внутри коллапсирующей функции ординал ω₂ принято записывать так Ω₂. Ну а мы, получается, имеем уже две коллапсирующие функции, давайте их пронумеруем: ψ₀(n) - это наша старая знакомая, с помощью которой создавались счетные ординалы из несчетных ординалов с кардианльностью ℵ₁, тогда ψ₁(n) - это будет новая коллапсирующая функция, с помощью которой будут создаваться несчетные ординалы с кардианльностью ℵ₁, из несчетных ординалов с кардианльностью ℵ₂. Работать она будет аналогично ψ₀(n), только у нее будет расширена область определения и возвращать она всегда будет только несчетные ординалы с кардианльностью ℵ₁. Кроме собственно ординалов с кардианльностью ℵ₂ в нее так же можно подставлять меньшие по значению аргументы, в том числе конечные числа, счетные ординалы и несчетные ординалы с кардианльностью ℵ₁. Так например, ψ₁(0) = Ω, ψ₁(1) = Ω×ω = ω^Ω+1, ψ₁(2) = Ω×ω² = ω^Ω+2, и т.д. В общем случае мы можем вывести правило: ψ₁(n) = ω^Ω+n. Тогда получается, что ψ₁(Ω) = ψ₁(ψ₁(0)) = ω^Ω+Ω = ω^Ω×2 = Ω², затем ψ₁(Ω×2) = ψ₁(ψ₁(0)+ψ₁(0)) = ω^Ω+Ω+Ω = ω^Ω×3 = Ω³. В итоге ψ₁(Ω×Ω) = ψ₁(Ω²) = ψ₁(ψ₁(ψ₁(0))) = ω^ωΩ×2= Ω^Ω. Череду подстановок можно продолжить и дальше ψ₁(ψ₁(ψ₁(ψ₁(0)))) = ω^ωωΩ×2 = Ω^ΩΩ , ψ₁(ψ₁(ψ₁(ψ₁(ψ₁(0))))) = ω^ωωωΩ×2 = Ω^ΩΩΩ, пока не доберемся до ψ₁(ψ₁(ψ₁(ψ₁(ψ₁(ψ₁(ψ₁(...))))))) = ε_Ω+1, Что и потребует от нас диагонализации соответствующего уровня ψ₁(Ω₂) = ε_Ω+1, так же как это было ранее для получения счетных ординалов ψ₀(Ω) = ε₀. Тогда полная запись Ординала Бахмана-Говарда должна выглядеть так: ψ₀(ψ₁(Ω₂)), однако для краткости и в соотвествии с требованиями функции, как только у нас появляется диагонализатор верхнего уровня, цепь коллапсирующих функций не записывается и правильной будет запись просто ψ(Ω₂).

Дальше все рекурсии идут по общим правилам коллапсирующей функции, и неважно что внутри нее уже есть ординал с кардианльностью ℵ₂, поскольку это ординал его так же можно увеличивать по правилам ординальной арифметики обычными арифметическими действиями, каждое из которых на выходе из коллапсирующей функции создает рекурсии: ψ(Ω₂)+ψ(Ω₂)+ψ(Ω₂)+... = ψ(Ω₂+1) = ψ(ε_Ω+1)+ψ(ε_Ω+1)+ψ(ε_Ω+1)+... = ψ(ε_Ω+1)×ω = ω^{ψ(ε_Ω+1)+1}, ψ(Ω₂+1)+ψ(Ω₂+1)+ψ(Ω₂+1)+... = ψ(Ω₂+2) = ψ(ε_Ω+1)×ω×ω = ω^{ψ(ε_Ω+1)+2} , ну и, следуя логике функции, получается, что ψ(Ω₂+Ω) = ψ(ε_Ω+1)^{ψ(ε_Ω+1)ψ(ε_Ω+1)...} = ψ(ε_Ω+1+Ω), затем ψ(Ω₂+Ω^ΩΩΩ...) = ψ(Ω₂+ψ₁(Ω₂)) = ψ(ε_Ω+1×2), потом ψ(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂))) = ψ(ε_Ω+1²) = ψ(ω^ε_Ω+1×2), сразу следом ψ(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂)))) = ψ(ε_Ω+1^ε_Ω+1) = ψ(ω^ωε_Ω+1×2) и так мы постепенно доберемся до первой арифметической диагонализации на Ω₂, которая будет равна ψ(Ω₂+Ω₂) = ψ(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂+ψ₁(Ω₂+...)))) = ψ(ε_Ω+1^{ε_Ω+1ε_Ω+1...}) = ψ(ω^{ωω...ε_Ω+1}) = ψ(ε_Ω+2). Следующая диагонализация будет такой: ψ(Ω₂×Ω₂) = ψ(Ω₂×ψ₁(Ω₂×ψ₁(Ω₂×ψ₁(Ω₂×...)))) = ψ(ε_εε...Ω+1) = ψ(ζ_Ω+1). Ну и соотвественно ψ(Ω₂^Ω₂) = ψ(Ω₂^{ψ₁(Ω₂ψ₁(Ω₂ψ₁(...)))}) = ψ(Г_Ω+1), и уже ψ(Ω₂^Ω₂Ω₂) = ψ(Ω₂^{Ω₂ψ₁(Ω₂Ω₂ψ₁(Ω₂Ω₂...)))}) = ψ(φ(¹_{φ(¹φ(¹...φ(¹Ω¹0)...))})) станет пределом для Вебленских расширений рекурсий над Ω, так же как ψ₀(Ω^ΩΩ) = φ(¹_{φ(¹φ(¹φ(¹...)))}) стала пределом для Функции Веблена над счетными ординалами.

Чтобы еще раз хорошенько прочувствовать почему коллапсирование над коллапсированием будет правильным выбором в нашем дальнейшем пути, я привожу еще одну гигантскую сравнительную таблицу, где буду сравнивать возможности ψ₀(n) и ψ₀(ψ₁(n)). В этой таблице можно еще раз наглядно проследить все пройденные нами рекурсии, но также она еще раз даст вам возможность убедиться в преимуществах иерархии Бахмана.

Таким образом мы снова достигнем бесконечной степенной башни, но уже сделанной из ординалов ω₂ (имеющих кардинальность ℵ₂). И следуя намеченной нами стратегии, вместо дальнейшего наращивания рекурсий на ω₂, мы должны получить их при помощи коллапсирования ординала следующей кардинальности ω₃ - минимального ординала с кардинальностью ℵ₃. Принципы работы новой коллапсирующей функции будут те же, она будет возвращать ординалы с кардинальностью ℵ₂, однако уровень рекурсии заложенный в ней будет намного больше, потому что в качестве аргументов такая функция сможет принимать не только ординалы с кардинальностью ℵ₃, но и ординалы с кардинальностью ℵ₂, и ординалы с кардинальностью ℵ₁, и ординалы с кардинальностью ℵ₀ (счетные ординалы), и конечные числа. Полагаю основная идея вам уже понятна, но чтобы еще раз наглядно показать, что с введением каждой дополнительной коллапсирующей функции работающей с бо́льшей кардинальностью, уровень рекурсий будет стремительно расти, я приведу еще одну таблицу, в которой буду сравнивать рекурсивные возможности ψ₀(ψ₁(n)) и ψ₀(ψ₁(ψ₂(n))). Обратите внимание на одну важную деталь, которая обязательно встретится вам в сравнениях, внутри коллапсирующей функции верхнего уровня не всегда необходимо расколлапсировать ординал до уровня счетного ординала. Так например, ψ(Ω₃) = ψ(ψ₁(ψ₂(Ω₃))) - это очень большой рекурсивно-созданный счетный ординал, а ψ₁(Ω₃) = ψ₁(ψ₂(Ω₃)) - это ψ₁(ε_Ω2+1) - ординал с кардинальностью ℵ₁ зарекурсированный до Бахманского уровня. Всю цепочку внутренних коллаппсирующих функций обычно не пишут, ибо она и так подразумевается, поэтому во избежании путаницы при сравнениях эту цепочку приходится достраивать в голове, например, ψ(Ω₃+ψ(Ω₂)) < ψ(Ω₃+ψ₁(Ω₂)), потому что иначе это выражение можно записать так ψ(Ω₃+ψ(ψ₁(Ω₂))) < ψ(Ω₃+ψ₁(Ω₂)), что так же равносильно выражению ψ(Ω₃+ψ(ε_Ω+1)) < ψ(Ω₃+ε_Ω+1).