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

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

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

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

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

При использовании стрелочной нотации для функций частичная функция от до иногда записывается как или Однако общего соглашения не существует, и последняя нотация чаще используется для карт включения или вложений . ^[^{необходима ссылка}^] $f$ $X$ $Y$ $f:X\rightharpoonup Y,$ $f:X\nrightarrow Y,$ $f:X\hookrightarrow Y.$

В частности, для частичной функции и любой имеет место одно из следующих условий: $f:X\rightharpoonup Y,$ $x\in X,$

$f(x)=y\in Y$ (это один элемент в $Y$ ), или
$f(x)$ не определено.

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

f:\mathbb {Z} \to \mathbb {N} ,

определяется:

f(n)=m

если и только если,

m^{2}=n,

m\in \mathbb {N} ,n\in \mathbb {Z} ,

тогда определено только если является полным квадратом (то есть ). Так что но не определено. $f(n)$ $n$ $0,1,4,9,16,\ldots$ $f(25)=5$ $f(26)$

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

Частичная функция возникает из рассмотрения отображений между двумя множествами $X$ и $Y$ , которые могут быть определены не на всем множестве $X.$ Типичным примером является операция извлечения квадратного корня из действительных чисел : поскольку отрицательные действительные числа не имеют действительных квадратных корней, операцию можно рассматривать как частичную функцию от до Область определения частичной функции — это подмножество $S$ множества $X$ , на котором определена частичная функция; в этом случае частичную функцию можно также рассматривать как функцию из $S$ в $Y.$ В примере операции извлечения квадратного корня множество $S$ состоит из неотрицательных действительных чисел $\mathbb {R}$ $\mathbb {R}$ $\mathbb {R} .$ $[0,+\infty).$

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

В случае, если область определения $S$ равна всему множеству $X$ , частичная функция называется полной . Таким образом, полные частичные функции из $X$ в $Y$ совпадают с функциями из $X$ в $Y.$

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

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

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

Понятие преобразования можно обобщить и на частичные функции. Частичное преобразование — это функция , где и являются подмножествами некоторого множества ^[1] $f:A\rightharpoonup B,$ $А$ $Б$ $X.$

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

Для удобства обозначим множество всех частичных функций из множества в множество через Это множество представляет собой объединение множеств функций, определенных на подмножествах с одной и той же областью определения : $f:X\rightharpoonup Y$ $X$ $Y$ $[X\rightharpoonup Y].$ $X$ $Y$

[X\rightharpoonup Y]=\bigcup _{D\subseteq X}[D\to Y],

последний также записывается как В конечном случае его мощность равна ${\textstyle \bigcup _{D\subseteq {X}}Y^{D}.}$

|[X\rightharpoonup Y]|=(|Y|+1)^{|X|},

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

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

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

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

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

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

Вычитание натуральных чисел (в которых — неотрицательные целые числа ) является частичной функцией: $\mathbb {N}$

f:\mathbb {N} \times \mathbb {N} \rightharpoonup \mathbb {N}

f(x,y)=x-y.

Он определяется только тогда, когда $x\geq y.$

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

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

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

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

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

В теории категорий при рассмотрении операции композиции морфизмов в конкретных категориях операция композиции является функцией тогда и только тогда, когда имеет один элемент. Причина этого в том, что два морфизма и могут быть составлены только так, как если бы то есть область значений должна равняться области значений $\circ \;:\;\hom(C)\times \hom(C)\to \hom(C)$ $\operatorname {ob} (C)$ $f:X\to Y$ $g:U\to V$ $g\circ f$ $Y=U,$ $f$ $g.$

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

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

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

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

Множество всех частичных функций (частичных преобразований ) на заданном базовом множестве образует регулярную полугруппу, называемую полугруппой всех частичных преобразований (или полугруппой частичных преобразований на ), обычно обозначаемую как ^[7]^[8]^[9] Множество всех частичных биекций на образует симметричную обратную полугруппу . ^[7]^[8] $X,$ $X$ ${\mathcal {PT}}_{X}.$ $X$

Схемы и атласы для коллекторов и пучков волокон

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

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

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

Аналитическое продолжение – расширение области определения аналитической функции (математика)
Многозначная функция – Обобщенная математическая функция
Плотно определенный оператор – функция, которая определена почти всюду (математика)

Ссылки

^ ab Кристофер Холлингс (2014). Математика через железный занавес: История алгебраической теории полугрупп. Американское математическое общество. стр. 251. ISBN 978-1-4704-1493-1.
^ Лутц Шредер (2001). «Категории: бесплатная экскурсия». В Юргене Козловски и Остине Мелтоне (ред.). Категориальные перспективы . Springer Science & Business Media. п. 10. ISBN 978-0-8176-4186-3.
^ Нил Коблиц; Б. Зильбер; Ю. И. Манин (2009). Курс математической логики для математиков . Springer Science & Business Media. стр. 290. ISBN 978-1-4419-0615-1.
^ Фрэнсис Борсе (1994). Справочник по категориальной алгебре: Том 2, Категории и структуры. Cambridge University Press. стр. 289. ISBN 978-0-521-44179-7.
^ Марко Грандис (2012). Гомологическая алгебра: взаимодействие гомологии с дистрибутивными решетками и ортодоксальными полугруппами. World Scientific. стр. 55. ISBN 978-981-4407-06-9.
^ Питер Бурмейстер (1993). «Частичные алгебры – вводный обзор». В Ivo G. Rosenberg; Gert Sabidussi (ред.). Algebras and Orders . Springer Science & Business Media. ISBN 978-0-7923-2143-9.
^ ab Alfred Hoblitzelle Clifford; GB Preston (1967). Алгебраическая теория полугрупп. Том II. Американское математическое общество. стр. xii. ISBN 978-0-8218-0272-4.
^ ab Питер М. Хиггинс (1992). Методы теории полугрупп . Oxford University Press, Incorporated. стр. 4. ISBN 978-0-19-853577-5.
^ Александр Ганюшкин; Владимир Мазорчук (2008). Классические конечные полугруппы преобразований: введение . Springer Science & Business Media. стр. 16 и 24. ISBN 978-1-84800-281-4.

Мартин Дэвис (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, Нью-Йорк.