Алгебро-логические свойства R-функций. Дифференциальные свойства R-функций. Алгоритмически полные системы R-функций, страница 3

В 1932 г. была доказана теорема Уитни, из которой следует, что для всякого замкнутого точечного множества существует бесконечно дифференцируемое (не аналитическое!) уравнение. Простое доказательство теоремы Уитни с использованием специальных функций содержится, например, в книге В.Л.Рвачева [1]. Таким образом, для целей построения уравнений произвольных замкнутых множеств достаточно было бы ограничиться множеством бесконечно дифференцируемых функций.

Наложение дополнительного требования аналитичности функции f приводит к излишнему сужению множества чертежей f(x)=0. Рассмотрим, например, квадрат с вершинами в точках (0,0), (а,0), (0, а) и (а, а). Пусть f(x)=0 – уравнение этого квадрата, причем функция f аналитична, а радиус сходимости её ряда Тейлора в окрестности начала координат. Тогда, поскольку на стороне (0,0), (а,0) функция f(x) равна нулю, всюду в пределах круга сходимости равны нулю все её производные по переменной х. Следовательно, f(x) равна нулю и на интервале (-r, 0), который не является частью границы квадрата; но тогда уравнение f(x)=0 не будет уравнением квадрата.

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

Покажем, как использование R-функций позволяет задавать одним уравнением полуалгебраические чертежи.

7. Алгоритмически полные системы R-функций

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

а) отображения, составляющие Н;

б) тождественное отображение;

в) отображения вида , где  - отображения из ;

г) композиции вида , где  - отображения из .

Элементы множества  будем называть Н-реализуемыми отображениями, а если базовые функции определены на Rⁿ, то Н-реализуемыми функциями.

Для фактического построения уравнений рассматриваемых чертежей надо располагать некоторой системой конструктивных средств записи функции f(x). Выбрав в качестве набора базовых функций , , получим, что Н₀-реализуемыми будут целые рациональные функции; им соответствует множество алгебраических чертежей.

Более широким конструктивным множеством является множество элементарных функций. По аналогии с полуалгебраическими, можно ввести понятие полуэлементарных чертежей, включающее геометрические образы конечных систем элементарных уравнений и неравенств и их конечные объединения. Можно показать, что, в отличие от ситуации с алгебраическими чертежами, всякий полуэлементарный чертеж является в то же время элементарным. Схема рассуждений может быть такой: всякая конечная система элементарных неравенств может быть записана с помощью одной из введенных выше основных систем R-функций в виде одного неравенства, включающего R-конъюнкции элементарных функций; всякая конечная совокупность элементарных неравенств может быть представлена в виде одного неравенства, содержащего R-дизъюнкции (и, возможно, R-отрицания). Поскольку R-функции основных систем принадлежат множеству элементарных функций, в итоге получаем одно элементарное уравнение (неравенство), геометрическим образом которого является данный полуэлементарный чертеж.

Рассуждения, проведенные для рассмотренных базисных систем, можно провести для любой другой базисной системы. При этом возможны две ситуации: а) имеются полу-Н-реализуемые чертежи, не являющиеся Н-реализуемыми (как в случае алгебраических функций); б) всякий полу-Н-реализуемый чертеж одновременно является Н-реализуемым. В последнем случае базисную систему будем называть алгоритмически полной.

Понятие алгоритмической полноты обобщено на случай, когда допускаются преобразования чертежей. Если T – некоторое множество преобразований, то множество чертежей, получающихся из Н-реализуемых путем применения этих преобразований, может либо быть, либо не быть Н-реализуемым. В том случае, когда эти множества совпедают, базисная система называется алгоритмически полной относительно преобразований T. Очевидно, любая базисная система, полученная расширением алгебраического базиса, является алгоритмически полной относительно преобразований подобия, переноса и поворота.