попытка конструктива

[avva]

Что вы не знаете и хотели бы узнать?

Что вы не понимаете и хотели бы понять?

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

(это пробный камень. Если запись оправдает себя, сделаю ее регулярной. Прошу не троллить и не паясничать, спасибо)

Comments

[sascha (from livejournal.com)]

Не понимаю теорему о неподвижной точке в арифметике Пеано.
То есть доказательство понимаю, оно несложное, но неформально понять "откуда оно берётся" не получается.
Причём неформально на уровне "возьмём утверждение 'я обладаю свойством, которое характеризуется мной'" -- для меня слишком неформально и неинтересно. :)

[avva.livejournal.com]

1. Диагональная функция рекурсивна (интуитивно очевидный факт; диагональная функция от x это взять формулу с номером x, подставить в нее x вместо ее первой свободной переменной, и взять номер того, что получилось).

2. Следовательно, диагональная функция представима в арифметике Пеано.

3. Любую представимую функцию f(x) можно "спрятать" внутрь формулы в том смысле, что применение формулы phi к f(x) эквивалетно применению какой-то другой формулы phi' к x, и эквивалентность доказуема внутри системы. Интуитивно говоря, мы расписываем f(x) внутри phi, используя представимость f(x), и называем это phi'.

4. Если применить это к f(x)=диагональная функция d(x), то получится, что подставить d(x) в phi - все равно, что подставить x в phi', и это эквивалентно для любого x. Но если мы выберем x, равный номеру phi', то d(x) как раз и будет номером формулы "x, подставленный в phi'", которая эквивалентна phi(d(x)). Мы нашли неподвижную точку для phi: это phi' с подставленным в себя собственным номером.

Это тот уровень, который вам нужен? Он игнорирует много подробностей :)

"Откуда оно берется" - реальное значение тут играет представимость всех рекурсивных функций в PA (очень мощное утверждение) и арифметизация синтаксика, позволяющая легко увидеть, что диагональная функция рекурсивна.

[sascha (from livejournal.com)]

Спасибо :)
Стало чуть более понятно.