|
Насчёт индукции - она эквивалентна утверждению, что (счётное ;) множество истинных утверждений {An} получается из истинного утверждения-базы A1, порождающего правила (An=>An+1) и логической аксиомы(или модуса, доказываемого в разных подходах мат. логики - кому как нравится) Modus Ponens. На мой взгляд, это утверждение интуитивно понятно, и непосредственного отношения к натуральным числам не имеет. Числа нужны только для индексирования(определения порядка) множества. Но ведь индексировать можно любым линейно упорядоченным множеством. Тут прослеживается связь с множествами, порождающей процедурой задания множества и логикой.
Видимо, понятие множества строк конечной длины и операции подстановок-конкатенации эквивалентно понятию числа(попутно вспоминаем нормальные алгоритмы Маркова). Но возможно ли на языке НАМ, задать арифметические операции для любого(неограниченной разрядности) числа?
Представляется, что число можно определить и на языке формальных грамматик(в которых работает рекурсия, а не индукция), не совсем уверен насчёт определения арифметических операций. Допустим алфавит {1}, X+Y->X|Y(единичная система счисления). Как записать, что XY->X|X|X...|X Y раз?
Например, так? XY->X|X(Y-1) где Y-1 - отщепление символа от Y, X1->X? Но тогда конкатенации не хватит, нужно уметь отщеплять/стирать символы.
Понятие числа также включает в себя понятие "полностью упорядоченного счётного множества", с точностью до биекции. Верно ли обратное? Можно ли, например, с помощью нескольких аксиом на полностью упорядоченном множестве - задать функцию сложения, например?
Еще есть связь с композицией операций - композицию одинаковых операций можно задать числом, но это те же строки вида aaaaa... по сути. С рекурсией тоже связь очевидна, как уже подмечено, потому что тривиальная рекурсия без ветвлений - тот же линейный порядок.
Так что довольно простой вопрос "А что такое N?" может навести на незамысловатые, но занимательные размышления.
|
18.08.2015, 23:57 
ом