Функции. Термы.

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

Если область определения функции совпадает с множеством Х, то функцию называют всюду определенной.

Две функции f и g из Х в Y называются равными, если они имеют одну и ту же область определения и значения их совпадают в каждой точке области определения. Частичные функции из множества во множество Y называют частичными функциями от n переменных или n-местными функциями (частичными) из Х в Y. Частичная функция из прямого произведения в Х, называется n-местной частичной операцией на Х.

Для записи различных выражений пользуются особым формальным языком. Алфавит этого языка состоит из символов трех групп.

Символы первой группы называются предметными символами. В качестве таких символов обычно употребляют буквы a, b, x, y, … или те же буквы с индексами.

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

Символы третьей группы – это левая и правая скобка и запятая.

Слова особого вида, записанные в этом алфавите, называются термами.

Термы длины 1 – это однобуквенные слова, составленные из букв, являющихся предметными переменными. Далее пользуемся индукцией. Пусть для некоторого термы длины, меньшей S, определены. Тогда слово длины S называется термом, если оно имеет вид , где - термы меньшей длины, а f – это n – местный функциональный символ. Например, если а, х – предметные символы, а f, g – одноместный и двуместный функциональные символы, то слова x, f(a), g(x, a), g(f(x), g(a, x)) являются термами длины 1, 4, 6, 14 соответственно.

По определению, задать значение предметного символа – это значит указать некоторое непустое множество, называемое основным множеством и сопоставить с рассматриваемым символом некоторый элемент этого множества, который называется значением данного символа.

Задать значение n-местного функционального символа – это значит сопоставить с ним какую-нибудь частичную n–местную операцию, определенную на основном множестве.

Теперь по индукции можно определить значение терма.

Если в качестве значений функциональных символов взяты частичные операции, определенные не всюду на основном множестве, то и значение терма может оказаться неопределенным. При записи термов пользуются сокращениями. Если, например, x, y – предметные символы, f – символ двуместной операции, то терм f(x, y) обычно пишут в виде xfy. В частности, если двуместные операции обозначаются символами +, ×, -, то термы ,сокращенно обозначают . Дальше всюду под числами понимаем 0 и натуральные числа 0, 1, 2, 3, …

Множество этих чисел будем обозначать N. Частичные функции, определённые на прямом произведении , направленные в N будем называть k-местными числовыми частичными функциями. Для краткости будем называть их просто функциями. Символы +, *, - будем считать двуместными функциональными символами, фиксированными значениями которых являются обычные арифметические операции. Во множестве натуральных чисел первые две операции всюду определены, а операция вычитания – частичная. Далее нам будут необходимы следующие числовые функции , имеющие по определению следующие значения:

,

,

.

Эти функции будем называть простейшими. Верхние индексы говорят, от какого числа переменных эти функции зависят. Поэтому вместо символов , будем писать S, O. Результатом функции S есть первоначальное число, увеличенное на единицу. Функция О обнуляет исходную числовую последовательность. А последняя функция J выбирает из предъявленной числовой последовательности число, стоящее на определённом месте. Эти функции можно комбинировать, получая более сложные функции.