Jump to content

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

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

Этимология [ править ]

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

Определение [ править ]

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

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

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

что естественно в X , Y и Z. [3]

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

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

Основные конструкции [ править ]

Оценка [ править ]

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

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

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

Состав [ править ]

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

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

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

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

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

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

Разделы [ править ]

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

где стрелка справа — p И а стрелка внизу соответствует тождеству на Y . Тогда Γ ( p ) называется объектом сечений p Y . Его часто называют Γ Y ( X ).

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

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

Примеры [ править ]

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

  • Категория Set всех множеств с функциями как морфизмами является декартово замкнутой. Произведение 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 , определяемым формулой ( g . F )( y ) = g .F( g −1 ) для всех g в G , F : Y Z и y в Y. .y
  • Категория конечных G -множеств также является декартово замкнутой.
  • Категория Cat всех малых категорий (с функторами в качестве морфизмов) декартово замкнута; экспонента C Д задается категорией функторов, состоящей из всех функторов от D до C с естественными преобразованиями в качестве морфизмов.
  • Если C малая категория , то функторная категория Set С состоящее из всех ковариантных функторов из C в категорию множеств с естественными преобразованиями в качестве морфизмов, является декартово замкнутым. Если F и G — два функтора из C в Set , то экспонента F Г значение которого на объекте X группы C задается множеством всех естественных преобразований из ( X ,−)× G в F. — это функтор ,
    • Приведенный выше пример G -множеств можно рассматривать как частный случай категорий функторов: каждую группу можно рассматривать как однообъектную категорию, а G -множества представляют собой не что иное, как функторы из этой категории в Set.
    • Категория всех ориентированных графов декартово замкнута; это категория функтора, как описано в разделе «Категория функтора».
    • В частности, категория симплициальных множеств (которые являются функторами X : ∆ на Set ) декартово замкнуто.
  • В более общем смысле каждый элементарный топос является декартово замкнутым.
  • В алгебраической топологии с декартовыми замкнутыми категориями особенно легко работать. Ни категория топологических пространств с непрерывными отображениями, ни категория гладких многообразий с гладкими отображениями не являются декартово замкнутыми. Поэтому были рассмотрены замещающие категории: категория компактно порожденных хаусдорфовых пространств декартово замкнута, как и категория пространств Фрелихера .
  • В теории порядка полные частичные порядки ( cpo s) имеют естественную топологию, топологию Скотта , непрерывные отображения которой действительно образуют декартову замкнутую категорию (т. е. объекты — это cpos, а морфизмы — непрерывные карты Скотта ). И каррирование , и применение являются непрерывными функциями в топологии Скотта, а каррирование вместе с применением обеспечивают сопряжение. [5]
  • Алгебра Гейтинга — это декартова замкнутая (ограниченная) решетка . Важный пример возникает из топологических пространств. Если X — топологическое пространство, то открытые множества в X образуют объекты категории O( X ), для которой существует единственный морфизм из U в V, если U — подмножество V , и нет морфизма в противном случае. Это ЧУМ представляет собой декартову замкнутую категорию: «произведение» U и V представляет собой пересечение U и V и экспоненциальной функции U. V является внутренней частью U ∪( X \ V ) .
  • Категория с нулевым объектом является декартово замкнутой тогда и только тогда, когда она эквивалентна категории только с одним объектом и одним тождественным морфизмом. Действительно, если 0 — начальный объект, а 1 — конечный объект, и мы имеем , затем который имеет только один элемент. [6]

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

  • Каждый элементарный топос локально декартово замкнут. Этот пример включает Set , FinSet , G -множества для группы G , а также Set С малых категорий C. для
  • Категория LH, объектами которой являются топологические пространства и морфизмы которых являются локальными гомеоморфизмами, является локально декартово замкнутой, поскольку LH/X эквивалентна категории пучков . Однако LH не имеет конечного объекта и, следовательно, не является декартово замкнутым.
  • Если C имеет обратные модели и для каждой стрелки p : X Y функтор p * : C/Y C/X , заданный путем обратного образа, имеет правый сопряженный, то C локально декартово замкнуто.
  • Если C локально декартово замкнуто, то все его категории срезов C/X также локально декартово замкнуты.

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

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

Приложения [ править ]

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

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

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

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

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

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

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

Левый сопряженный называется зависимой суммой и задается композицией .

Правильный сопряженный называется зависимым произведением .

Экспоненту P в C/Y можно выразить через зависимое произведение по формуле .

Причина этих названий в том, что при интерпретации P как зависимого типа , функторы и соответствуют типам образований и соответственно.

теория Эквациональная

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

( х и ) С = ( х С ) и .

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

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

Бикартезианские замкнутые категории [ править ]

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

  • х + у = у + х
  • ( Икс + у ) + z знак равно Икс + ( у + z )
  • Икс ×( у + z ) = Икс × у + Икс × z
  • х ( у + г ) = х и ×x С
  • 0 + х = х
  • x ×0 = 0
  • х 0 = 1

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

Ссылки [ править ]

  1. ^ Баэз, Джон С .; Останься, Майк (2011). «Физика, топология, логика и вычисления: Розеттский камень» (PDF) . В Куке, Боб (ред.). Новые структуры для физики . Конспект лекций по физике. Том. 813. Спрингер. стр. 95–174. arXiv : 0903.0340 . CiteSeerX   10.1.1.296.1044 . дои : 10.1007/978-3-642-12821-9_2 . ISBN  978-3-642-12821-9 . S2CID   115169297 .
  2. ^ Сондерс, Мак Лейн (1978). Категории для работающего математика (2-е изд.). Спрингер. ISBN  1441931236 . OCLC   851741862 .
  3. ^ «декартова замкнутая категория в nLab» . ncatlab.org . Проверено 17 сентября 2017 г.
  4. ^ Локально декартова закрытая категория в n Lab
  5. ^ Барендрегт, HP (1984). «Теорема 1.2.16». Лямбда-исчисление . Северная Голландия. ISBN  0-444-87508-5 .
  6. ^ "Теория категорий - является ли декартово замкнутой категория коммутативных моноидов?" .
  7. ^ Бэкус, Джон (1981). Программы функционального уровня как математические объекты . Нью-Йорк, Нью-Йорк, США: ACM Press. дои : 10.1145/800223.806757 .
  8. ^ Соловьев, С.В. (1983). «Категория конечных множеств и декартовы замкнутые категории». J Math Sci . 22 (3): 1387–1400. дои : 10.1007/BF01084396 . S2CID   122693163 .
  9. ^ Фиоре, М.; Космо, Р. Ди; Балат, В. (2006). «Замечания об изоморфизмах в типизированных лямбда-исчислениях с пустыми типами и типами сумм» (PDF) . Анналы чистой и прикладной логики . 141 (1–2): 35–50. дои : 10.1016/j.apal.2005.09.001 .

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 15fbf06f4c6dca5db86d03bd0b12ad3f__1696099440
URL1:https://arc.ask3.ru/arc/aa/15/3f/15fbf06f4c6dca5db86d03bd0b12ad3f.html
Заголовок, (Title) документа по адресу, URL1:
Cartesian closed category - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)