PS Может тему в раздел мат. логики перенести?
Захотят — перенесут.
аксиоматики Пеано людям мало?
Насколько я знаю, аксиоматику Пеано не всегда возможно сформулировать внутри строящейся формальной системы. Усиляя последнее суждение
{0}, аксиоматика Пеано как раз и утверждает, что система обладает хотя бы какой-нибудь рекурсией.
ИМХО, формальная система не имеет право задаваться вопросом, откуда взялись те инструменты, которыми она располагает на этапе её формирования. В частности, если во время построения теории используется рекурсия, то сама система не может установить этот факт, если только при помощи рекурсии не был построен какой-то объект или аксиома, выражающие рекурсию. Иначе можно задаться более фундаментальным вопросом: что такое подстановка подстроки вместо символа в другой строке?
