Частичная функция - Partial function

В математике , А частичная функция F от множества X до множества Y является функцией от подмножества S из X (возможно , Х сам по себе) в Y . Подмножество S , то есть домен из F рассматривается как функция, называется областью определения из F . Если S равно X , то есть если f определено для каждого элемента в X , то f называется полным .

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

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

Когда стрелочная нотация используется для функций, частичная функция от до иногда записывается как f : XY , или, однако, не существует общего соглашения, и последнее обозначение чаще используется для инъективных функций .

В частности, для частичной функции и любой из них:

  • (это единственный элемент в Y ), или
  • не определено.

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

определяется:
если и только если,

then определяется, только если является полным квадратом (то есть ). Так что, но не определено.

Основные понятия

Пример инъективной частичной функции .
Пример функции, которая не является инъективной.

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

Поскольку функция тривиально сюръективна, если ограничена ее образом, термин частичная биекция обозначает частичную функцию, которая является инъективной.

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

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

Функция

Функция представляет собой бинарное отношение , что является функциональным (также называемым правым уникальным) и последовательным (также называемым левым всего). Это более сильное определение, чем определение частичной функции, которое требует только функционального свойства.

Функциональные пространства

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

последнее также записывается как В конечном случае его мощность равна

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

Обсуждение и примеры

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

Натуральный логарифм

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

Вычитание натуральных чисел

Вычитание натуральных чисел (неотрицательных целых чисел ) можно рассматривать как частичную функцию:

Он определяется только тогда, когда

Нижний элемент

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

В информатике частичная функция соответствует подпрограмме, которая вызывает исключение или зацикливается навсегда. Стандарт IEEE с плавающей запятой определяет не-числовое значение, которое возвращается, когда операция с плавающей запятой не определена и исключения подавляются, например, когда запрашивается квадратный корень из отрицательного числа.

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

В теории категорий

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

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

Категория множеств и частичных биекций эквивалентна своей двойственной . Это типичная обратная категория .

В абстрактной алгебре

Частичная алгебра обобщает понятие универсальной алгебры на частичные операции . Примером может служить поле , в котором мультипликативная инверсия является единственной правильной частичной операцией (поскольку деление на ноль не определено).

Множество всех частичных функций (частичных преобразований ) на заданном базовом наборе образует регулярную полугруппу, называемую полугруппой всех частичных преобразований (или полугруппой частичных преобразований на ), обычно обозначаемой как Набор всех частичных биекций на образует симметричный обратный полугруппа .

Карты и атласы для многообразий и пучков волокон

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

Причина использования частичных функций вместо функций состоит в том, чтобы разрешить представление общих глобальных топологий путем сшивания локальных патчей для описания глобальной структуры. «Патчи» - это области, в которых определены диаграммы.

Смотрите также

Рекомендации

  • Мартин Дэвис (1958), « Вычислимость и неразрешимость» , McGraw – Hill Book Company, Inc., Нью-Йорк. Переиздано Dover в 1982 году. ISBN  0-486-61471-9 .
  • Стивен Клини (1952), Введение в мета-математику , издательство North-Holland Publishing Company, Амстердам, Нидерланды, 10-е издание с исправлениями, внесенными в 7-е издание (1974). ISBN  0-7204-2103-9 .
  • Гарольд С. Стоун (1972), Введение в компьютерную организацию и структуры данных , McGraw – Hill Book Company, Нью-Йорк.