О категории множеств (стр. 2 из 5)

g: b®c,

l, m: c®d

g – эпистрелка, если из равенства l °g=m °g (*)следует, что l=m.

Очевидно, что это равенство выполняется.(см. диаграмму). Учитывая, что codf = dom(l °g) = dom(m °g), применим к равенству (*) стрелку f. Получаем (l ° g)°f=(m ° g)°f. Далее, по ассоциативному закону:

l°(g°f)=m°(g°f).

g°f – эпистрелка Þl=m, что и требовалось доказать.

1.3. Изострелки

Определение: произвольная стрелка f: a®b называется изострелкой или обратимой в категории Ω стрелкой, если существует Ω- стрелка g:b®a, такая, что g°f=1_a и f°g=1_b. На самом деле такая стрелка только одна. Действительно, если предположить, что существует ещё одна такая стрелка g’, то g’=1_a°g’=(g°f)°g’=g°(f°g’)=g°1_b=g. Стрелка g, когда она существует, называется обратной к f стрелкой и обозначается f ^-1:b®a. Она определяется условиями: f ^-1°f=1_a, f °f ^-1=1_b .

· Любая изострелка является эпистрелкой.

Доказательство: пусть f: a®b – изострелка, и стрелки g,h: b®c.

Тогда g °f=h °f и существует f ^-1 . Тогда g = g °1_b = g °(f °f^-1) =(ассоциативность)= (g °f) °f^-1 = (h°f)°f^-1=h °(f °f ^-1)=h °1_b=h. Таким образом, f – сократима справа. Ч.т.д.

· Любая изострелка является монострелкой. (доказательство аналогично предыдущему).

· Любая изострелка является бистрелкой (эпи и монострелкой ).

Доказательство: следует из предыдущих двух утверждений.

· Каждая единичная стрелка является изострелкой.

Доказательство: Пусть f: a®a – единичная стрелка. Существует стрелка f ^–1 : a®a и f ^–1 °f=1_a, f °f ^–1=1_a .Þ f – изострелка. Ч.т.д.

· Если f – изострелка, то f ^–1 – изострелка.

Доказательство: пусть f: a®b – изострелка. Тогда f ^–1: b®a. f – изострелка Þ f °f ^–1=1_b, f ^–1 °f=1_a. Þ f ^–1 – изострелка. Ч.т.д.

· Если f, g – изострелки, то f °g – изострелка, при этом (f °g)^{- 1} = g^–1°f^{- 1}

Доказательство: пусть f: b®c, g: a®b. f °g: a®c. f,g- изострелки Þ $ f ^–1: c®b и $ g ^–1: b®a Þ$ g ^–1°f ^–1 :c®a. Эта композиция является «подозрительной» на обратную к стрелке f °g. Проверим это:

1) (g ^–1°f ^–1)°(f °g)=(ассоциативность)=g ^–1°(f ^–1°f °g)=g^–1°(1_b°g)=g^–1 °g=1_a.

2) (f °g )°g ^–1° f ^–1=f °(g °g ^–1°f ^–1)=f °(1_b°f ^–1)=f °f ^–1=1_c.

Þ f°g- изострелка и (f °g)^-1=g ^–1°f ^–1 .Ч.т.д.

1.4. Изоморфные объекты

Определение: Объекты a и b называются изоморфными в Ω (символически a@b), если существует Ω – стрелка f:a®b, являющаяся изострелкой в Ω, т.е. f: a@b.

· Произвольные Ω – объекты обладают следующими свойствами:

1) a@a

2) если a@b, то b@a

3) если a@b и b@с, то a@c

Доказательство:

1) в любой категории существует стрелка 1_a: a®a (по определению категории). Единичная стрелка является изострелкой (доказано выше). Получаем, что a@a (по определению изоморфных объектов).

2) a@b Þ$ f :a®b и f – изострелка Þ $ f ^–1: b®a (по определению изострелки). Ранее доказано, что если f - изострелка, то и f ^–1 – изострелка. Т.е. f ^–1: b®a – изострелка Þ b@a (по определению изоморфных объектов).

3) a@b Þ$ f :a®b – изострелка.

b@с Þ$ g :b®c – изострелка.

Dom g=cod f Þ $ g °f: a®c и g °f – изострелка (т.к.f и g – изострелки (доказано выше)). Чтобы доказать, что a@c, необходимо найти изострелку t: a®c. Возьмем в качестве такой изострелки t изострелку g °f. Ч.т.д.

1.5. Начальные объекты

Определение: объект 0 называется начальным в категории Ω, если для каждого объекта а из Ω существует одна и только одна Ω – стрелка из 0 в а.

· Любые два начальных объекта изоморфны в Ω.

Доказательство:

Предположим, что 0 и 0’- начальные объекты. Требуется доказать, что 0@0’. Для этого необходимо найти изострелку 0®0’.

Существуют единственные стрелки f: 0’®0 (т.к.0’ - начальный объект) и g: 0®0’ (т.к. 0 – начальный объект). Dom f=cod g Þ$ f °g: 0®0. 0 – начальный объект Þ $! стрелка 0®0. и по определению категории для каждого Ω – объекта $ единичная стрелка. Значит стрелка 1₀: 0®0 и стрелка f °g:0®0 совпадают. Аналогично, стрелка g °f:0’®0’ совпадает со стрелкой 1_0’. Тогда g имеет обратную стрелку (а именно f), т.е. g: 0@0’. Ч.т.д.

1.6. Конечные объекты

Обращая направление стрелок в определении начального объекта, получаем следующее определение.

Определение: объект 1 называется конечным в категории Ω, если для каждого Ω – объекта а существует одна и только одна стрелка из а в 1.

· Все конечные объекты изоморфны.

Доказательство:

Предположим, что 1 и 1’ – конечные объекты. Требуется доказать, что 1@1’. Для этого надо найти изострелку 1®1’.

Объект 1 – конечный Þ $! f: 1’®1 (по определению конечного объекта).

Объект 1’ - конечный Þ$! g:1®1’ ( по той же причине). Dom f=cod g Þ $ f °g :1®1.

1 – конечный объект. Þ f °g: 1®1 – единственная.

С другой стороны для любого объекта категории существует единичная стрелка 1₁:1®1. Значит f °g=1₁. Аналогично, g °f=1_1’. Таким образом, для стрелки g нашлась обратная (а именно f), т.е.g: 1@1’. Ч.т.д.

· Стрелка f:1®a – мономорфна.

Доказательство:

F: 1®a – мономорфна, если для любых стрелок g,h:b®1 из того, что f °g=f °h следует, что g=h. Но по определению конечного объекта, существует только одна стрелка b®1. Поэтому равенство стрелок g и h следует автоматически.

1.7. Двойственность

Можно заметить, что понятие эпистрелки получается из определения монострелки «обращением стрелок». То же справедливо для понятий конечного и начального объектов. Эти два примера иллюстрируют понятие двойственности в теории категорий.

Если å- предложение категорного языка, то двойственным å^ор назовем предложение, получаемое из å заменой «dom» на «cod», «cod» на«dom» и «h=g °f» на «h=f °g». Таким образом, все стрелки и композиции, входящие в å ,повернуты в å^ор в другую сторону. Понятие, описываемое предложением å^ор называется двойственным к понятию, описываемому å. Для данной категории Ω построим двойственную категорию Ω^ор следующим образом.

Категории Ω и Ω^ор имеют одни и те же объекты. Для каждой f:a®b вводим Ω- стрелку f^op:b®a (свою для каждой f). Так получаемые стрелки

исчерпывают все стрелки категории Ω^ор. Композиция f^op°g^op определена тогда и только тогда, когда определена в Ω композиция g°f и f^op°g^op=(g°f)^op. Dom f^op=cod f и codf^op=dom f.

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

1.8. Произведения

Как охарактеризовать произведение двух множеств

с помощью стрелок. Неужели это можно сделать без какого-то использования упорядоченных пар?

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

Поставим в соответствие произведению

два специальных отображения (проекции)

и , задаваемые равенствами , .

Допустим теперь, что задано ещё одно множество С с парой отображений f: C®A, g: C®B. Определим отображение p: C® правилом p(x)= ,

Тогда p_А(p(x))=f(x) и p_B(p(x))=g(x) для каждого хÎС. Таким образом, p_A°p=f и p_B°p=g, т.е. приведенная выше диаграмма коммутативна. Более того, p является единственной стрелкой, для которой эта диаграмма коммутативна. Действительно, если p(x)=<y,z>, то в силу условия p_A°p=f будет p_A(p(x))=f(x), т.е. y=f(x). Аналогично, если p_B°p=g, то z=g(x).

Отображение p, построенное по f и g, обозначаются обычно через <f,g> и называется произведением отображений f и g.

Эти рассмотрения служат мотивировкой для следующего определения.

Определение: произведением в категории Ω двух объектов a и b называется Ω-объект, обозначаемый через , вместе с парой (pr_a: ®a, pr_b: ®b) Ω- стрелок, такой, что для произвольной пары (f:c®a, g:c®b) Ω- стрелок существует одна и только одна стрелка <f,g>:c® , для которой диаграмма коммутативна, т.е. pr_a°<f,g>=f и pr_b°<f,g>=g. Стрелка <f,g> называется произведением стрелок f и g относительно проекций pr_a,pr_b.