Декартова закрытая категория

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

• 1 Этимология
• 2 Определение
• 3 Базовые конструкции
  • 3.1 Оценка
  • 3.2 Состав
  • 3.3 Разделы
• 4 Примеры
• 5 Приложения
• 6 Зависимая сумма и произведение
• 7 Теория уравнений
  • 7.1 Бикартезианские закрытые категории
• 8 Ссылки
• 9 Внешние ссылки

Назван в честь Рене Декарта (1596–1650), французского философа, математика, и ученый, чья формулировка аналитической геометрии породила концепцию декартова произведения, которая позже была обобщена до понятия категориального продукта.

Категория C называется декартово замкнутым тогда и только тогда, когда удовлетворяет следующим трем свойствам:

• Он имеет конечный объект.
• Любые два объекта X и Y в C имеют продукт X × Y в C.
• Любые два объекта Y и Z из C имеют экспоненту Z в C.

Первые два условия могут быть объединены с единственным требованием, чтобы любое конечное (возможно, пустое) семейство объекты C допускают продукт в C из-за естественной ассоциативности категориального продукта и потому, что пустой продукт в категории является конечным объектом этой категории.

Третье условие эквивалентно требованию, чтобы функтор - × Y (т. Е. Функтор из C в C, который отображает объекты X в X × Y и морфизмы φ в φ × id Y) имеет правый сопряженный элемент, обычно обозначаемый - для всех объектов Y в C. Для локально малых категорий это может быть выражено наличием биекция между гом-множествами

$H\; om\; (X\; \times \; Y,\; Z)\; \cong \; H\; om\; (X,\; ZY)\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{Hom\}\; (X\; \backslash \; times\; Y,\; Z)\; \backslash \; cong\; \backslash \; mathrm\; \{Hom\}\; (X,\; Z\; ^\; \{Y\})\}$

что является естественным как в X, так и в Z.

Обратите внимание, что декартова закрытая категория не обязательно иметь конечные пределы; гарантия только на конечные продукты.

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

Оценка

Для каждого объекта Y счет экспоненциального присоединения является естественным преобразованием

$ev\; Y,\; Z:\; ZY\; \times \; Y\; \to \; Z\; \{\; \backslash \; displaystyle\; \backslash \; mathrm\; \{ev\}\; \_\; \{Y,\; Z\}:\; Z\; ^\; \{Y\}\; \backslash \; times\; Y\; \backslash \; to\; Z\}$

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

$приложение\; X,\; Y,\; Z:\; ZX\; \times \; Y\; \times \; X\; \cong \; (ZY)\; X\; \times \; X\; \to \; ev\; X,\; ЗЫЗЫ.\; \{\backslash \; Displaystyle\; \backslash \; mathrm\; \{papply\}\; \_\; \{X,\; Y,\; Z\}:\; Z\; ^\; \{X\; \backslash \; times\; Y\}\; \backslash \; times\; X\; \backslash \; cong\; (Z\; ^\; \{Y\})\; ^\; \{X\}\; \backslash \; times\; X\; \{\backslash \; xrightarrow\; \{\backslash \; mathrm\; \{ev\}\; \_\; \{X,\; Z\; ^\; \{Y\}\}\}\}\; Z\; ^\; \{Y\}.\}$

В частном случае категории Set они сводятся к обычным операциям:

$ev\; Y,\; Z\; (f,\; y)\; =\; f\; (y).\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{ev\}\; \_\; \{Y,\; Z\}\; (f,\; y)\; =\; f\; (y).\}$

Состав

Вычисление экспоненты одним аргументом при морфизме p: X → Y дает морфизмы

$p\; Z:\; XZ\; \to \; YZ,\; \{\backslash \; displaystyle\; p\; ^\; \{Z\}:\; X\; ^\; \{Z\}\; \backslash \; to\; Y\; ^\; \{Z\},\}$

$Z\; p:\; ZY\; \to \; ZX,\; \{\backslash \; displaystyle\; Z\; ^\; \{p\}:\; Z\; ^\; \{Y\}\; \backslash \; to\; Z\; ^\; \{X\},\}$

, соответствующий операции композиции с p. Альтернативные обозначения для операции p включают p * и p∘-. Альтернативные обозначения для операции Z включают p и -∘p.

Оценочные карты можно объединить в цепочку:

$ZY\; \times \; YX\; \times \; X\; \to \; id\; \times \; ev\; X,\; YZY\; \times \; Y\; \to \; ev\; Y,\; ZZ\; \{\backslash \; displaystyle\; Z\; ^\; \{Y\}\; \backslash \; times\; Y\; ^\; \{X\}\; \backslash \; раз\; X\; \{\backslash \; xrightarrow\; \{\backslash \; mathrm\; \{id\}\; \backslash \; times\; \backslash \; mathrm\; \{ev\}\; \_\; \{X,\; Y\}\}\}\; Z\; ^\; \{Y\}\; \backslash \; times\; Y\; \{\backslash \; xrightarrow\; \{\backslash \; mathrm\; \{ev\}\; \_\; \{Y,\; Z\}\}\; \}\; Z\}$

соответствующая стрелка под экспоненциальным присоединением

$c\; X,\; Y,\; Z:\; ZY\; \times \; YX\; \to \; ZX\; \{\backslash \; displaystyle\; c\_\; \{X,\; Y,\; Z\}:\; Z\; ^\; \{Y\}\; \backslash \; times\; Y\; ^\; \{\; X\}\; \backslash \; to\; Z\; ^\; \{X\}\}$

называется (внутренней) составной картой.

В частном случае категории Set это обычная операция композиции:

$c\; X,\; Y,\; Z\; (g,\; f)\; =\; g\; \circ \; f.\; \{\backslash \; displaystyle\; c\_\; \{X,\; Y,\; Z\}\; (g,\; f)\; =\; g\; \backslash \; circ\; f.\}$

Секции

Для морфизма p: X → Y предположим, что существует следующий квадрат возврата, который определяет подобъект X, соответствующий картам, композиция которых с p является тождеством:

$\Gamma \; Y\; (p)\; \to \; XY\; \downarrow \; \downarrow \; 1\; \to \; YY\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{ccc\}\; \backslash \; Gamma\; \_\; \{Y\}\; (\; p)\; \backslash \; to\; X\; ^\; \{Y\}\; \backslash \backslash \backslash \; downarrow\; \backslash \; downarrow\; \backslash \backslash \; 1\; \backslash \; to\; Y\; ^\; \{Y\}\; \backslash \; end\; \{array\}\}\}$

где стрелка справа - это p, а стрелка на bottom соответствует тождеству на Y. Тогда Γ Y (p) называется объектом секций p. Часто его обозначают сокращенно Γ Y (X).

Если Γ Y (p) существует для любого морфизма p с областью области Y, то его можно собрать в функтор Γ Y : C / Y → C на категория срезов, которая сопряжена справа с вариантом функтора произведения:

$hom\; C\; /\; Y\; \; (X\; \times \; Y\; \to \; \pi \; 2\; Y,\; Z\; \to \; p\; Y)\; \cong \; hom\; C\; \; (X,\; \Gamma \; Y\; (p)).\; \{\backslash \; displaystyle\; \backslash \; hom\; \_\; \{C\; /\; Y\}\; (X\; \backslash \; times\; Y\; \{\backslash \; xrightarrow\; \{\backslash \; pi\; \_\; \{2\}\}\}\; Y,\; Z\; \{\backslash \; xrightarrow\; \{p\}\}\; Y)\; \backslash \; cong\; \backslash \; hom\; \_\; \{C\}\; (X,\; \backslash \; Gamma\; \_\; \{Y\}\; (p)).\}$

Экспонента по Y может быть выражена через секции:

$ZY\; \cong \; \Gamma \; Y\; (Z\; \times \; Y\; \to \; \pi \; 2\; Y).\; \{\backslash \; displaystyle\; Z\; ^\; \{Y\}\; \backslash \; cong\; \backslash \; Gamma\; \_\; \{Y\}\; (Z\; \backslash \; times\; Y\; \{\backslash \; xrightarrow\; \{\backslash \; pi\; \_\; \{2\}\}\}\; Y).\}$

Примеры декартовых К закрытым категориям относятся:

• Категория Набор из всех наборов с функциями в качестве морфизмов является декартово замкнутой. Произведение X × Y - это декартово произведение X и Y, а Z - это множество всех функций от Y до Z. Сопряженность выражается следующим фактом: функция f: X × Y → Z естественным образом отождествляется с каррированная функция g: X → Z, определенная как g (x) (y) = f (x, y) для всех x в X и y в Y.
• Категория конечное множество с функциями как морфизмами является декартово замкнутым по той же причине.
• Если G является группой, то категория всех G-множеств декартово замкнуто. Если Y и Z - два G-множества, то Z - это множество всех функций от Y до Z с действием G, определенным формулой (gF) (y) = g. (F (gy)) для всех g в G, F: Y → Z и y в Y.
• Категория конечных G-множеств также декартово замкнута.
• Категория Cat всех малых категорий (с функторами как морфизмами) декартово замкнуто; экспонента C задается функцией категории, состоящей из всех функторов от D до C, с естественными преобразованиями как морфизмы.
• Если C является малой категорией, то категория функторов Набор, состоящий из всех ковариантных функторов из C в категорию множеств с естественными преобразованиями как морфизмы, декартово замкнут. Если F и G - два функтора от C до Set, то экспонента F - это функтор, значение которого на объекте X из C задается набором всех естественных преобразований из (X, -) × G to F.
  • Предыдущий пример G-множеств можно рассматривать как частный случай категорий функторов: каждую группу можно рассматривать как категорию с одним объектом, а G-множества - не что иное, как функторы из этой категории в Установить
  • Категория всех ориентированных графов декартово замкнута; это категория функторов, как объяснено в разделе категория функторов.
  • В частности, категория симплициальных множеств (которые являются функторами X: Δ → Set ) декартово замкнута.
• В более общем смысле, каждый элементарный topos является декартово замкнутым.
• В алгебраической топологии особенно легко работать с декартово замкнутыми категориями. Ни категория топологических пространств с непрерывными отображениями, ни категория гладких многообразий с гладкими отображениями не являются декартово замкнутыми. Поэтому были рассмотрены замещающие категории: категория компактно порожденных хаусдорфовых пространств декартово замкнута, как и категория пространств Фрелихера.
• в теории порядка, полные частичные порядки (cpos) имеют естественную топологию, топологию Скотта, непрерывные отображения которой действительно образуют декартову замкнутую категорию (то есть объекты являются cpos, а морфизмы - Скотт непрерывные карты). И каррирование, и apply являются непрерывными функциями в топологии Скотта, и каррирование вместе с apply обеспечивают сопряженные.
• A алгебра Гейтинга является декартовой замкнутой (ограниченной) решетка. Важный пример возникает из топологических пространств. Если X - топологическое пространство, то открытые множества в X образуют объекты категории O (X), для которой существует уникальный морфизм из U в V, если U является подмножеством V и не имеет морфизма в противном случае. Этот poset является декартовой замкнутой категорией: «произведение» U и V является пересечением U и V, а экспонента U - внутреннее U∪ (X \ V).
• Категория с нулевым объектом является декартово замкнутой тогда и только тогда, когда она эквивалентна категории только с одним объектом и одним морфизмом идентичности. Действительно, если 0 - начальный объект, а 1 - конечный объект, и мы имеем $0\; \cong \; 1\; \{\backslash \; displaystyle\; 0\; \backslash \; cong\; 1\}$, то $H\; om\; (X,\; Y)\; \cong \; ЧАС\; (1,\; YX)\; \cong \; ЧАСОМ\; (0,\; YX)\; \cong \; 1\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{Hom\}\; (X,\; Y)\; \backslash \; cong\; \backslash \; mathrm\; \{Hom\}\; (1,\; Y\; ^\; \{X\})\; \backslash \; cong\; \backslash \; mathrm\; \{Hom\}\; (0,\; Y\; ^\; \{X\})\; \backslash \; cong\; 1\}$, который имеет только один элемент.
  • В частности, любая нетривиальная категория с нулевым объектом, например абелева категория, не является декартово замкнутой. Таким образом, категория модулей над кольцом не является декартово замкнутой. Однако у функтора тензорного произведения $-\; \otimes \; M\; \{\backslash \; displaystyle\; -\; \backslash \; otimes\; M\}$с фиксированным модулем действительно есть правое сопряженное соединение. Тензорное произведение не является категориальным произведением, поэтому это не противоречит сказанному выше. Вместо этого мы получаем, что категория модулей моноидально замкнутая.

. Примеры локально декартовых замкнутых категорий включают:

• Каждый элементарный топос локально декартово замкнут. Этот пример включает Set, FinSet, G-sets для группы G, а также Set для малых категорий C.
• Категория LH, объекты которой являются топологическими пространствами. и чьи морфизмы являются локальными гомеоморфизмами локально декартово замкнуто, поскольку LH / X эквивалентна категории пучков $S\; h\; (X)\; \{\backslash \; displaystyle\; Sh\; (X)\}$. Однако LH не имеет терминального объекта и, следовательно, не является декартово замкнутым.
• Если C имеет откаты и для каждой стрелки p: X → Y, функтор p: C / Y → C / X задается формулой получение откатов имеет правое сопряженное соединение, тогда C локально декартово замкнуто.
• Если C локально декартово замкнуто, то все его категории срезов C / X также являются локально декартово замкнутыми.

Декартовы замкнутые категории включают:

• Cat не является локально декартово замкнутым.

В декартовых замкнутых категориях - «функция двух переменных» (морфизм f: X × Y → Z) всегда можно представить в виде «функции одной переменной» (морфизм λf: X → Z). В приложениях информатики это известно как каррирование ; он привел к осознанию того, что просто типизированное лямбда-исчисление можно интерпретировать в любой декартовой закрытой категории.

Соответствие Карри – Ховарда – Ламбека обеспечивает глубокий изоморфизм между интуиционистской логикой, простым типизированным лямбда-исчислением и декартово закрытыми категориями.

Определенные декартовы закрытые категории, topoi, были предложены в качестве общей установки для математики вместо традиционной теории множеств.

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

Пусть C - локально декартова замкнутая категория. Тогда C имеет все откаты, потому что откат двух стрелок с доменом Z задается произведением в C / Z.

Для каждой стрелки p: X → Y пусть P обозначает соответствующий объект C / Y. Возврат по p дает функтор p: C / Y → C / X, который имеет как левый, так и правый сопряженный.

Левый сопряженный элемент $\Sigma \; p:\; C\; /\; X\; \to \; C\; /\; Y\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{p\}:\; C\; /\; X\; \backslash \; to\; C\; /\; Y\}$называется зависимая сумма и дается составом с п.

Правый сопряженный элемент $\Pi \; p:\; C\; /\; X\; \to \; C\; /\; Y\; \{\backslash \; displaystyle\; \backslash \; Pi\; \_\; \{p\}:\; C\; /\; X\; \backslash \; to\; C\; /\; Y\}$называется зависимый продукт .

Показатель P в C / Y может быть выражен через зависимый продукт по формуле $QP\; \cong \; \Pi \; p\; (p\; \ast \; (Q))\; \{\backslash \; displaystyle\; Q\; ^\; \{P\}\; \backslash \; cong\; \backslash \; Pi\; \_\; \{p\}\; (p\; ^\; \{*\}\; (Q))\}$.

Причина этих имен в том, что при интерпретации P как зависимого типа $y:\; Y\; ⊢\; P\; (y):\; T\; ype\; \{\backslash \; displaystyle\; y:\; Y\; \backslash \; vdash\; P\; (y):\; \backslash \; mathrm\; \{Type\}\}$, функторы $\Sigma \; p\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{p\}\}$и $\Pi \; p\; \{\backslash \; displaystyle\; \backslash \; Pi\; \_\; \{p\}\}$соответствуют образованиям типов $\Sigma \; x:\; P\; (y)\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{\; x:\; P\; (y)\}\}$и $\Pi \; x:\; P\; (y)\; \{\backslash \; displaystyle\; \backslash \; Pi\; \_\; \{x:\; P\; (y)\}\}$соответственно.

В каждой декартовой замкнутой категории (с использованием экспоненциальной записи) (X) и (X) изоморфны для всех объектов X, Y и Z. Мы запишите это как «уравнение»

(x) = (x).

Можно спросить, какие еще такие уравнения действительны во всех декартовых замкнутых категориях. Оказывается, все они логически следуют из следующих аксиом:

• x × (y × z) = (x × y) × z
• x × y = y × x
• x × 1 = x (здесь 1 обозначает конечный объект C)
• 1 = 1
• x = x
• (x × y) = x × y
• (x) = x

Бикартезианские закрытые категории

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

• x + y = y + x
• (x + y) + z = x + (y + z)
• x × (y + z) = x × y + x × z
• x = x × x
• 0 + x = x
• x × 0 = 0
• x = 1

Обратите внимание, однако, что приведенный выше список не является полным; изоморфизм типов в свободном BCCC не является конечно аксиоматизируемым, и его разрешимость все еще остается открытой проблемой.

1. ^Джон К. Баез и Майк Стэй, «Физика, топология, логика и вычисления: Розеттский камень ", (2009) ArXiv 0903.0340 в New Structures for Physics, ed. Боб Кок, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, стр. 95-174.
2. ^Saunders., Mac Lane (1978). Категории для рабочего математика (Второе изд.). Нью-Йорк, Нью-Йорк: Springer New York. ISBN 1441931236. OCLC 851741862.
3. ^«декартова закрытая категория в nLab». ncatlab.org. Проверено 17 сентября 2017 г.
4. ^Локально декартова закрытая категория в nLab
5. ^H. П. Барендрегт, Лямбда-исчисление, (1984) Северная Голландия ISBN 0-444-87508-5 (см. Теорему 1.2.16)
6. ^«Ct. теория категорий - декартова замкнутая коммутативная моноида категорий? ".
7. ^С. Соловьев. «Категория конечных множеств и декартовы замкнутые категории», Журнал советской математики, 22, 3 (1983)
8. ^Фиоре, Космо и Балат. Замечания об изоморфизмах типизированных лямбда-исчислений с пустыми типами и типами суммы [1]

• Сили Р.А.Г. (1984). «Локально декартовы замкнутые категории и теория типов». Математические труды Кембриджского философского общества. 95 (1): 33–48. doi : 10.1017 / S0305004100061284. ISSN 1469-8064.

• Декартова закрытая категория в nLab
• Сообщение в блоге о связи между CCC и лямбда-исчислением :https://golem.ph.utexas.edu/category/2006/08/cartesian_closed_categories_an_1.html