Декартова закрытая категория - Cartesian closed category

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

Этимология

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

Определение

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

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

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

Третье условие эквивалентно требованию, чтобы функтор – ×Y (т.е. функтор из C к C который отображает объекты Икс к Икс ×Y и морфизмы φ в φ × id_Y) имеет правый смежный, обычно обозначается -^Y, для всех объектов Y в C. За местные небольшие категории, это можно выразить наличием биекция между домашние наборы

${\displaystyle \mathrm {Hom} (X\times Y,Z)\cong \mathrm {Hom} (X,Z^{Y})}$

который естественный в обоих Икс и Z.^[3]

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

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

Основные конструкции

Оценка

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

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

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

${\displaystyle \mathrm {papply} _{X,Y,Z}:Z^{X\times Y}\times X\cong (Z^{Y})^{X}\times X{\xrightarrow {\mathrm {ev} _{X,Z^{Y}}}}Z^{Y}.}$

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

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

Сочинение

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

${\displaystyle p^{Z}:X^{Z}\to Y^{Z},}$

${\displaystyle Z^{p}:Z^{Y}\to Z^{X},}$

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

Карты оценки могут быть объединены в цепочку как

${\displaystyle Z^{Y}\times Y^{X}\times X{\xrightarrow {\mathrm {id} \times \mathrm {ev} _{X,Y}}}Z^{Y}\times Y{\xrightarrow {\mathrm {ev} _{Y,Z}}}Z}$

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

${\displaystyle c_{X,Y,Z}:Z^{Y}\times Y^{X}\to Z^{X}}$

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

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

${\displaystyle c_{X,Y,Z}(g,f)=g\circ f.}$

Разделы

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

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

где стрелка справа п^Y а стрелка внизу соответствует тождеству на Y. Тогда Γ_Y(п) называется объект разделов из п. Часто его обозначают сокращенно Γ_Y(Икс).

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

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

Экспонента на Y можно выразить в виде разделов:

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

Примеры

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

• Категория Набор из всех наборы, с функции как морфизмы, декартово замкнуто. Продукт Икс×Y является декартовым произведением Икс и Y, и Z^Y это набор всех функций из Y к Z. Сопряженность выражается в следующем факте: функция ж : Икс×Y → Z естественно отождествляется с карри функция грамм : Икс → Z^Y определяется грамм(Икс)(у) = ж(Икс,у) для всех Икс в Икс и у в Y.
• Категория конечный множества, с функциями как морфизмами, декартово замкнуто по той же причине.
• Если грамм это группа, то категория всех грамм-наборы декартово замкнуто. Если Y и Z два грамм-установки, то Z^Y это набор всех функций из Y к Z с грамм действие, определяемое (грамм.F)(у) = грамм. (F (грамм⁻¹.y)) для всех грамм в грамм, F:Y → Z и у в Y.
• Категория конечных грамм-sets также является декартово замкнутым.
• Категория Кот всех малых категорий (с функторами как морфизмами) декартово замкнуто; экспоненциальный C^D дается категория функторов состоящий из всех функторов из D к C, с естественными преобразованиями в виде морфизмов.
• Если C это малая категория, то категория функторов Набор^C состоящий из всех ковариантных функторов из C в категорию множеств с естественными преобразованиями как морфизмы декартово замкнуто. Если F и грамм два функтора из C к Набор, то экспоненциальная F^грамм это функтор, значение которого на объекте Икс из C задается множеством всех естественных преобразований из (Икс,−) × грамм к F.
  • Предыдущий пример грамм-наборы можно рассматривать как частный случай категорий функторов: каждую группу можно рассматривать как категорию с одним объектом, и грамм-множества - не что иное, как функторы из этой категории в Набор
  • Категория всех ориентированные графы декартово замкнуто; это категория функторов, как объясняется в разделе категория функторов.
  • В частности, категория симплициальные множества (которые являются функторами Икс : Δ^op → Набор) декартово замкнуто.
• Более того, каждый элементарный топос декартово замкнуто.
• В алгебраическая топология, Особенно легко работать с декартовыми замкнутыми категориями. Ни категория топологические пространства с непрерывный карты, ни категория гладкие многообразия с гладкими отображениями декартово замкнуто. Поэтому рассматривались замещающие категории: категория компактно порожденные хаусдорфовы пространства декартово замкнуто, как и категория Пространства Фрелихера.
• В теория порядка, полные частичные заказы (cpos) имеют естественную топологию, Топология Скотта, чьи непрерывные отображения действительно образуют декартову замкнутую категорию (то есть объекты - это cpos, а морфизмы - это Скотт непрерывный карты). Обе карри и подать заявление являются непрерывными функциями в топологии Скотта, и каррирование вместе с apply обеспечивает сопряженное.^[5]
• А Алгебра Гейтинга является декартово замкнутым (ограниченным) решетка. Важный пример возникает из топологических пространств. Если Икс топологическое пространство, то открытые наборы в Икс образуют объекты категории О (Икс), для которого существует единственный морфизм из U к V если U это подмножество V и никакого морфизма иначе. Этот посеть является декартовой закрытой категорией: «продукт» U и V это пересечение U и V и экспоненциальный U^V это интерьер из U∪(Икс\V).
• Категория с нулевой объект декартово замкнуто тогда и только тогда, когда оно эквивалентно категории только с одним объектом и одним морфизмом идентичности. Действительно, если 0 - начальный объект, а 1 - конечный объект, и мы имеем ${\displaystyle 0\cong 1}$, тогда ${\displaystyle \mathrm {Hom} (X,Y)\cong \mathrm {Hom} (1,Y^{X})\cong \mathrm {Hom} (0,Y^{X})\cong 1}$ который имеет только один элемент.^[6]
  • В частности, любая нетривиальная категория с нулевым объектом, например абелева категория, не является декартово замкнутым. Итак, категория модули над кольцом не является декартово замкнутым. Однако функтор тензорное произведение ${\displaystyle -\otimes M}$ с фиксированным модулем имеет правый смежный. Тензорное произведение не является категориальным произведением, поэтому это не противоречит сказанному выше. Вместо этого мы получаем, что категория модулей моноидально закрытый.

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

• Каждый элементарный топос локально декартово замкнут. Этот пример включает Набор, FinSet, грамм-наборы для группы грамм, а также Набор^C для малых категорий C.
• Категория LH чьи объекты являются топологическими пространствами, а морфизмы локальные гомеоморфизмы локально декартово замкнуто, так как LH / X эквивалентна категории пучков ${\displaystyle Sh(X)}$. Тем не мение, LH не имеет конечного объекта и, следовательно, не является декартово замкнутым.
• Если C есть откаты и за каждую стрелку п : Икс → Y, функтор п^* : C / Y → C / X заданный путем взятия откатов, имеет правый сопряженный элемент, тогда C является локально декартово замкнутым.
• Если C локально декартово замкнуто, то все его категории срезов C / X также являются локально декартово замкнутыми.

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

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

Приложения

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

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

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

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

Зависимая сумма и произведение

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

За каждую стрелку п : Икс → Y, позволять п обозначают соответствующий объект C / Y. Принимая откаты п дает функтор п^* : C / Y → C / X который имеет как левый, так и правый сопряженный.

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

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

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

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

Теория уравнений

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

(Икс^у)^z = (Икс^z)^у.

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

• Икс×(у×z) = (Икс×у)×z
• Икс×у = у×Икс
• Икс×1 = Икс (здесь 1 обозначает конечный объект C)
• 1^Икс = 1
• Икс¹ = Икс
• (Икс×у)^z = Икс^z×у^z
• (Икс^у)^z = Икс^(у×z)

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

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

• Икс + у = у + Икс
• (Икс + у) + z = Икс + (у + z)
• Икс×(у + z) = Икс×у + Икс×z
• Икс^{(у + z)} = Икс^у× х^z
• 0 + Икс = Икс
• Икс×0 = 0
• Икс⁰ = 1

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

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

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

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

внешняя ссылка

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