Доклад: Эквивалентность элементарных функций

Докажем, что L ₄ L ₁ (для этого выразим операции суммирования и мультиплицирования через функции L ₄ )

Выразим м3ультиплицирование через ограниченную рекурсию.

Где (x,y)-к-ступенчатая функция.

Выразим суммирование через ограниченную рекурсию.

Докажем, что L ₁ L ₅ (для этого выразим x*y через функции L ₅ )

Докажем, что L ₅ L ₃ (для этого выразим 2^x и операцию ограниченной минимизации выразим через функции L ₅ )

Пусть

тогда

Эквивалентность классов доказана.