ГЛАВА 1. РЕКУРСИВНЫЕ ФУНКЦИИ

1. Конструктивные объекты

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

Здесь и всюду в дальнейшем, когда возникает опасность недоразумений, присутствие пустого слова указывается с помощью символа . Целые числа

— это слова в двухбуквенном алфавите Добавляя знак , мы можем строить рациональные числа

Несколько более сложные примеры дают нам формулы аксиоматической теории, например арифметики первого порядка

Мы можем также рассматривать конструктивные объекты, устроенные нелинейным образом, например конечные деревья

целочисленные матрицы

и релейно-контактные схемы

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

а целочисленные матрицы — в виде слов в четырехбуквенном алфавите

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

Таким образом, достаточно было бы рассматривать только натуральные числа. Однако необходимость все время линейно упорядочивать символы причиняет некоторые неудобства, а необходимость нумеровать все рассматриваемые объекты приводила бы к еще

большей громоздкости. Вот почему мы предпочитаем работать с более общим понятием конструктивного объекта.

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

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