МИНИСТЕРСТВООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВЯТСКИЙГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ
УНИВЕРСИТЕТ
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
ОКАТЕГОРИИ МНОЖЕСТВ
Выполнила студентка V курса
математического факультета
Одегова В.Н.
/>/подпись/
Научный руководитель:
Доктор ф.-м.н., профессор
Вечтомов Е.М.
/подпись/
/>
Рецензент: кандитат ф.-м.н., доцент Чермных В.В.
/>/подпись/
Допущен к защите в ГАК
/>Зав. кафедрой ВечтомовЕ.М.
(подпись)
/>/>2003г.
/>Декан факультета ВаранкинаВ.И.
(подпись)
/>/>2003г.
Киров, 2003г.
введение… 3
1 Основные понятия теории категорий… 4
1.1. Мономорфные стрелки. 6
1.2. Эпиморфные стрелки. 7
1.3. Изострелки. 8
1.5. Начальные объекты… 10
1.6. Конечные объекты… 10
1.7. Двойственность. 11
1.8. Произведения. 12
1.9. Произведение отображений. 15
1.10. Копроизведение объектов. 18
2 категориЯ множеств… 19
2.1. Мономорфизм в категории множеств. 20
2.2. Эпиморфизм в категории множеств. 21
2.3. Начальные и конечные объекты вкатегории множеств. 23
2.4. Произведение в категории множеств. 23
2.5. Копроизведения в категории множеств. 24
3 Примеры категорий… 24
3.1. Категория 1. 24
3.2. Категория 2. 25
3.3. Категория 3. 25
3.4. Категории предпорядка. 26
3.5. Дискретные категории. 26
3.6. Категория N… 27
Литература… 28
введение/>/>/>/>/>Сейчас многие отрасли математики используюттеоретико-множественные обозначения. Несомненно, теория множеств сыгралаогромную роль в развитии математики. У этой теории можно найти многопреимуществ, но в этой дипломной работе речь пойдет не об этом. Развитиемтеории множеств можно считать теорию категорий. Что такое «теория категорий».Это очень привлекательная и естественная альтернатива теории множеств. Конечно,можно мыслить объекты математического изучения как множества, но нет ужеуверенности, что и в будущем их будут рассматривать так. Без сомнения, основнойязык теории множеств останется важным инструментом в тех случаях, когда надорассматривать совокупности предметов. Но понимание самих предметов как множествпотеряло свое преимущественное значение в силу появления новой альтернативы./>/>/>/>Вданной дипломной работе рассматривается одна из важнейших категорий вматематике – категория множеств. В первом параграфе рассматриваются основныепонятия теории категорий. Доказываются необходимые свойства и утверждения./>/>/>/>Вовтором параграфе рассматривается категория множеств. Те понятия, которыеиспользуются в теории категорий, переносятся непосредственно в эту категорию.Интерпретируются теоремы из теории категорий в категорию множеств./>/>/>/>Втретьем параграфе приведены другие примеры категорий. Тем самым показанывыразительные возможности теории категорий.Теория категорий изложена в книгах [1]-[4].
1 Основныепонятия теории категорий
Для того чтобы проиллюстрировать формализациюинтуитивной математической идеи рассмотрим понятие функции.
Функция – есть связьмежду объектами. Точнее, это – соответствие, сопоставляющее заданному объектуточно один другой объект.
Если А – множество всехвозможных входов функции f, а В– множество, включающее все f-образыэлементов из А, то говорят, что fявляется функцией из множества А во множество В. Это выражают записью f: A®B.
Множество А называетсяобластью определения, а множество В – областью значений.
В общей теории категорийвместо слова «функция» используют более нейтральное слово «стрелка» (а такжеслово «морфизм»).
Выполняются следующиесвойства:
1. C каждой стрелкой связано дваспециальных объекта – её начало и конец.
2. Имеется операция композиции, котораяприменяется к определенным парам ‹ g, ¦› стрелок данной категории (когда область значения первойсовпадает с областью определения второй) и дает в результате новую стрелку g˚¦, также принадлежащую даннойкатегории.
3. С каждым объектом данной категориисвязана специальная стрелка – единичная, или тождественная, стрелка этогообъекта.
Итак, дадим аксиоматическоеопределение категории.
Категория Ω включаетв себя:
1) Совокупностьпредметов, называемых Ω — объектами
2) Совокупностьпредметов, называемых Ω-стрелками
3) Операции, ставящие всоответствие каждой Ω-стрелке f Ω-объект dom f (начало стрелки f) и Ω-объект cod f (конец стрелки f). То, что а=domf и b=cod f изображается так: f: a®b
4) Операцию, ставящую всоответствие каждой паре ‹ g, ¦› Ω-стрелок с dom g=cod f Ω-стрелку g˚¦, композицию f и g, с dom (g˚¦)=dom f и cod(g˚¦)=cod g, причем выполняется следующееусловие:
закон ассоциативности:
пусть f: a®b
g: b®c
h:c®d
/>тогда h ˚(g˚¦)= (h ˚g)˚¦.
Закон ассоциативностиутверждает, что диаграмма вида –
-коммутативна.
( втеории категорий удобным средством являются коммутативные диаграммы. Диаграмма– это схема, в которой указаны объекты и стрелки между ними. При этом, любыедва пути, ведущие по стрелкам из одного объекта в другой, равны. Диаграмманазывается коммутативной, если есть несколько путей от одного объекта кдругому, то все они приводят к одному и тому же результату. Точнее: диаграмманазывается коммутативной, когда все возможные треугольники, составляющие частиданной диаграммы, коммутативны. Это означает, что любые два пути стрелок даннойдиаграммы, начинающиеся в одном и том же объекте и заканчивающиеся в одном итом же объекте, задают в композиции одну и ту же функцию. Диаграммы в теориикатегорий используются для наглядности изложения.)
5) Сопоставление каждомуΩ-объекту b Ω-стрелки 1b: b®b, называемой единичной илитождественной стрелкой, так что выполнен Закон тождества:
/>для любых Ω-стрелок f:a®b и g:b®c 1b◦f=f и g◦1b=g, т.е. коммутативна диаграмма1.1.Мономорфные стрелки
Определение: Стрелка f:a®b вкатегории Ω называется мономорфной или монострелкой в Ω,если для любой пары g,h: c®a Ω-стрелок из равенства f °g=f ° h следует g=h.
· В произвольнойкатегории композиция g°fявляется монострелкой, если как f, так и gмономорфны.
Доказательство:
/>Воспользуемся определением монострелки:
/>Стрелка g°f:a®c является монострелкой, если длялюбых стрелок l,m:b®a если(g°f)°l=(g°f)°m, то l=m. Изобразим диаграмму. Очевидно, что требуемое равенствовыполняется, т.е. (g°f)°l=(g°f)°m. В любой категории должен выполняться ассоциативный закон. Применяя его,получаем следующее равенство: g°(f°l)=g°(f°m).
/> g – монострелка Þ f °l=f °m
f – монострелка Þl=m, что и требовалось доказать.
· В произвольнойкатегории, если композиция g°f– мономорфна, то и f– мономорфна.
Доказательство: пусть f: a®b
g: b®d,
l, m: c®a
f – мономорфна, если из равенства f °l=f °m (*)следует, что l=m.
/>Очевидно, что это равенство выполняется.(см.диаграмму). Учитывая, что domg = cod(f °l) = cod(f °m), применим к равенству (*) стрелку g.Получаем g°(f ° l)=g°(f °m). Далее, по ассоциативному закону:
/>(g°f)°l=(g°f)°m.
g°f – монострелка Þl=m, что и требовалось доказать.1.2.Эпиморфные стрелки
Определение: Стрелка f:a®bназывается эпиморфной или эпистрелкой в категории />Ω, если для произвольной пары стрелок g,h: b®c изравенства g°f=h°f следует g=h, т.е. есликоммутативна диаграмма, то g=h.
· Если g°f-эпистрелка, то g— эпистрелка.
Доказательство: пусть f: a®b
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=1a и f°g=1b. На самом деле такая стрелка толькоодна. Действительно, если предположить, что существует ещё одна такая стрелка g’, то g’=1a°g’=(g°f)°g’=g°(f°g’)=g°1b=g.Стрелка g, когда она существует, называетсяобратной к f стрелкой и обозначается f -1:b®a. Онаопределяется условиями: f -1°f=1a, f °f -1=1b.
· Любаяизострелка является эпистрелкой.
Доказательство: пусть f: a®b –изострелка, и стрелки g,h: b®c.
Тогда g °f=h °f и существует f -1. Тогда g = g °1b= g °(f °f-1) =(ассоциативность)= (g °f) °f-1 = (h°f)°f-1=h °(f °f -1)=h °1b=h.Таким образом, f – сократимасправа. Ч.т.д.
· Любаяизострелка является монострелкой. (доказательство аналогично предыдущему).
· Любаяизострелка является бистрелкой (эпи и монострелкой ).
Доказательство: следует из предыдущих двухутверждений.
· Каждаяединичная стрелка является изострелкой.
Доказательство: Пусть f: a®a –единичная стрелка. Существует стрелка f –1: a®a и f –1 °f=1a, f °f –1=1a.Þ f – изострелка. Ч.т.д.
· Если f– изострелка, то f–1– изострелка.
Доказательство: пусть f: a®b –изострелка. Тогда f –1: b®a. f – изострелка Þ f °f –1=1b,f –1 °f=1a. Þ 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°(1b°g)=g–1 °g=1a.
2) (f °g )°g–1° f –1=f °(g °g –1°f –1)=f °(1b°f –1)=f °f –1=1c.
Þ 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) в любой категориисуществует стрелка 1a: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. и по определению категории для каждого Ω – объекта $ единичная стрелка. Значит стрелка 10:0®0 и стрелка f °g:0®0 совпадают. Аналогично, стрелка g °f:0’®0’ совпадает со стрелкой 10’. Тогда 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 – единственная.
С другойстороны для любого объекта категории существует единичная стрелка 11:1®1. Значит f °g=11. Аналогично, g °f=11’. Таким образом, для стрелки 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 вводим Ω- стрелку fop:b®a (свою для каждой f). Так получаемые стрелки />исчерпывают все стрелкикатегории Ωор. Композиция fop°gopопределена тогда и только тогда, когда определена в Ω композиция g°f и fop°gop=(g°f)op. Domfop=cod f и codfop=dom f.
Конструкцию,двойственную к выражаемой предложением å,можно интерпретировать как первоначальное построение, примененное кдвойственной категории. Если åистинно в Ω, то åористинно в Ωор. Т.о. из произвольного истинного в теориикатегорий предложения получается другое истинное предложение åор. В этом состоит принципдвойственности. Принцип двойственности сокращает количество доказательстввдвое. Так, доказав, что два произвольных начальных объекта изоморфны, можносразу утверждать, что два произвольных конечных объекта изоморфны.1.8.Произведения
Какохарактеризовать произведение двух множеств
/> с помощью стрелок. Неужелиэто можно сделать без какого-то использования упорядоченных пар?
Оказывается это возможно.Способ, позволяющий избежать использования упорядоченных пар, даст возможностьвыяснить, что такое конструкция в теории категорий.
Поставим в соответствие произведению /> два специальныхотображения (проекции)
/>и />,задаваемые равенствами />, />.
/>Допустим теперь, чтозадано ещё одно множество С с парой отображений f: C®A, g: C®B. Определим отображение p: C®/> правилом p(x)=/>,
Тогда pА(p(x))=f(x) и pB(p(x))=g(x) длякаждого хÎС. Таким образом, pA°p=f и pB°p=g, т.е. приведенная выше диаграмма коммутативна. Более того, p является единственной стрелкой, для которой эта диаграммакоммутативна. Действительно, если p(x)=, то в силуусловия pA°p=f будет pA(p(x))=f(x), т.е. y=f(x). Аналогично, если pB°p=g, то z=g(x).
Отображение p, построенное по f и g, обозначаются обычно через и называется произведениемотображений f и g.
Эти рассмотрения служатмотивировкой для следующего определения.
/>Определение: произведением в категорииΩ двух объектов a и b называется Ω-объект,обозначаемый через />, вместе с парой(pra:/>®a, prb:/>®b) Ω- стрелок, такой, что дляпроизвольной пары (f:c®a, g:c®b)Ω- стрелок существует одна и только одна стрелка :c®/>, для которой диаграмма коммутативна, т.е. pra°=f и prb°=g. Стрелка называется произведением стрелок f и g относительно проекций pra,prb.
· pra,prb>=1/>.
/>Доказательство: изобразим данную ситуацию надиаграмме.(точнее левую часть доказываемого равенства). Видим, что стрелка переводит объект /> в объект />. А по определениюкатегории существует только одна единичная стрелка (та, которая переводитобъект категории в себя). Значит, эти стрелки совпадают. Ч.т.д.
· Если f,g>=k,h>, то f=kи g=h.
Доказательство: разберемся с условием утверждения.
a) Стрелка существует по условиюÞdomf=domg.Пусть f:c®a, g:c®b.тогда стрелка :c®/>.
b) Стрелка совпадает со стрелкой по условию. Þ dom=dom=c,cod=cod=/>. Þстрелки k,h такие, что domk=domh=c, аконцы этих стрелок в объектах a и b.
c) Предположим, что k:c®b, h:c®a.Если это так, то стрелка :c®/>. Тогда ¹, так как уних не совпадают концы.
d) Получилипротиворечие после того, как предположили, что k:c®b, h:c®a. остается один вариант: k:c®a, h:c®b.значит f=k, g=h. Ч.т.д.
· °h, g°h>=°h
/>Доказательство: Посмотрим, что означает стрелка. Во-первых: композиция двухстрелок существует, когда конец одной стрелки является началом другой. Изусловия следует, что domf=codh и domg=codh,а также dom=codh. Т.е. стрелки f, g, имеют одно и то же начало. Пустьh: d®c, g:c®b, f:c®a. Изобразим диаграмму: эта диаграммакоммутативна, т.е. pra°°h=f°h и prb°°h=g°h. Произведением стрелок f°h, g°h является однозначно-определеннаястрелка (она единственна по определению произведения). И этой стрелкой являетсякомпозиция стрелок и h. 1.9.Произведение отображений
Для данныхтеоретико-множественных функций f:A®B и g:C®D определим функцию />. /> является произведениемдвух композиций: /> и />. Поэтому дадим следующееопределение.
/>Определение: если f:a®b и g:c®d – две Ω-стрелки, то через />обозначимΩ-стрелку />.
· />
/>Доказательство: представим ситуацию диаграммой. Поопределению произведения стрелок стрелка />:/>®/>, и эта стрелка единственна. А по определениюкатегории, у каждого объекта существует единичная стрелка, т.е. та, котораяпереводит объект в себя. Значит стрелки /> и /> совпадают. Ч.т.д.
· />
/>Доказательство: для того, чтобы доказать изоморфизмдвух объектов, необходимо найти изострелку. В нашем случае изострелку f:/>®/>. Для существования произведения /> необходимо иметь двестрелки. Пусть g:a®b, h:b®a.тогда />:/>®/>. Эта стрелка единственна поопределению произведения. Изобразим диаграмму.
А теперь рассмотримстрелку />. Предположительно, этастрелка является обратной к стрелке />. (этастрелка тоже единственна по определению произведения). Действительно,композиция (/>)°(/>):/>®/>. Так как стрелки /> и /> — единственны, то и ихкомпозиция есть единственная стрелка. А по определению категории, каждый объектимеет единичную стрелку. Поэтому, (/>)°(/>)=/>. Аналогично (/>)°(/>)=/>. Значит, по определению изострелки,стрелка /> является изострелкой. Þ/> (по определению изоморфности двухобъектов). Ч.т.д.
· />
Доказательство: для доказательства этого утвержденияпостроим диаграмму.
/>
Стрелка />:/>. Если рассмотреть подобную диаграмму (вкоторой />), то получим стрелку />. Эта стрелка является обратной к стрелке />. (проверяется аналогично). Значит /> — изострелка. Þ Þ/>. Ч.т.д.
· />
Доказательство:
a) так каксуществует композиция />, то dom/>=cod/>.
b) Так каксуществует стрелка />, то domg=domk.
c) Изсуществования стрелки /> следует, что dom(f°g)=dom(h°k), domf=codg, domh=codk.
d) Изобразимдиаграмму. Композиция />: с®/>.
e) />/>: с®/>. А по определению произведенияобъектов стрелка /> — единственна. Значит стрелки и /> совпадают.Ч.т.д.
1.10. Копроизведение объектов
Понятие копроизведения,или суммы объектов, является двойственным к понятию произведения. Егоопределение получается непосредственно из определения произведения по принципудвойственности.
/>Определение: копроизведением в категорииΩ двух объектов a и b называется Ω-объект,обозначаемый через a+b, вместе с парой (ia:a®a+b, ib:b®a+b) -стрелок, такой, что для произвольной пары (f:a®c, g:b®c)–стрелок существует одна и только одна стрелка [f,g]:a+b®c, для которой диаграмма коммутативна,т.е. [f,g]°ia=f, [f,g]°ib=g. Стрелка [f,g] называется копроизведениемстрелок f,g относительно инъекций ia и ib.
Можно посмотреть длинныйсписок категорных вариантов математических конструкций и понятий. Мы уже имеемнекоторое представление о том, как теория категорий воссоздает мирматематических идей и в действительности раздвигает горизонты математическогомышления. Мы познакомились немного с категорией множеств.2категориЯ множеств
Пусть S-класс всевозможных множеств,рассматриваемых с отображениями одних множеств в другие.
f:A→Bобозначается отображение множества А во множество В.
Композицией отображений f:A→B и g:B→C, называется отображение g °f:A→C, вычисляемое по формуле: /> g°f(a)=g(f(a)). Эта частичная бинарная операциякомпозиция отображений ассоциативна (там, где определена). Проверяется это так:
даны отображения f:A→B, g:B→C, h:C→D. h°(g°f)=(h°g)°f. Обе частиопределены. Возьмем />. Преобразуемлевую часть: h°(g°f)(а)=h°(g°f(a))=h°(g(f(a)))=h(g(f(a))). Преобразуемправую часть: ((h°g)°f)(а)=(h°g)°f(a)=(h°g)(f(a))=(h°g(f(a)))=h(g(f(a))).левая и правая части равны.Þ h°(g°f)=(h°g)°f.Þкомпозиция ассоциативна.
/> 1А: А→А, что /> справедливы равенства:
1) 1А°g=g
2) h°1A=h
получили конкретнуюкатегорию множеств (категория Set).
В категории множествобъектами являются все множества, а стрелками – все функции между множествами.Выполняются следующие свойства:
1. С каждой стрелкойсвязано два специальных объекта – её начало и конец.
2. Имеется операциякомпозиции, которая применяется к определенным парам ‹ g, ¦› стрелок данной категории (когдаобласть значения первой совпадает с областью определения второй) и дает врезультате новую стрелку g˚¦, также принадлежащую данной категории.
3. С каждым объектомданной категории связана специальная стрелка – единичная, или тождественная,стрелка этого объекта.2.1. Мономорфизм в категории множеств
· В категории Set (категория множеств) для любогоотображения f:A→Bэквивалентны условия:
1) f- мономорфизм
2) f-инъекция
3) g°f=1Aдля некоторого g:B→A
Доказательство: поведем по циклу 1)→2)→3)→1)
/>1)→2): предположим, что мономорфизм f не является инъективнымотображением, т.е. /> в А и f(a1)=f(a2)=b.
Возьмем произвольноенепустое множество С и два отображения u:C→A, v:C→A, такие, что при отображении v множество С переходит в элемент а1ÎА, а при отображении u множество С переходит в элемент а2ÎА. Заметим, что u¹v. Тогда, нетрудно видеть, что f°u=b=f°v. но f –мономорфнаÞu=v. Пришли к противоречию, после того,как предположили, что f- неинъективнаÞf – инъективна.
/>2)→3) Пусть f-инъекция. Для доказательстванеобходимо найти отображение g:B→A. зададим отображение g правилом:
/> g(b)=
Тогда, очевидно, что g°f=1A .
3)→1) впроизвольной категории доказано свойство о том, что если заданы отображения f:A→B, g:B→A, тоиз того, что g°f — мономорфизм следует, что f-мономорфизм. По условию g°f=1А.Выше также доказано свойство о том, что любая единичная стрелка является монострелкой. Из всего вышесказанного следует, что f – мономорфизм. Теорема доказана полностью.2.2.Эпиморфизм в категории множеств
· В категории Set (категория множеств) для любогоотображения f:A→Bэквивалентны условия:
1) f- эпиморфизм, 2) f-сюръекция, 3) f°g=1B
для некоторого g:B→A
Доказательство:
доказательствоповедем по циклу 1)→2)→3)→1)
1)→2)пусть f – эпиморфизм. Предположим, чтоотображение f не является отображением «на», т.е.не является сюръекцией. (Imf¹B).
/>Возьмем b1ÎB\Imf.
Пусть С={b1,b2}. Возьмем отображения u:B→C, такое, что любой элемент из Впереходит в b2. отображение v:B→Cзададим следующим образом:
/>
Заметим, что u и v не совпадают.Тогда u°f=b=v°f. Так как f-эпиморфизм (по условию)Þu=v.Получили противоречие после того, как предположили, что f неявляется сюрьекцией. Значит, f – сюрьекция.
/>2)→3) пусть f- сюрьекция.
сюьективностьозначает, что /> его прообраз непуст. По аксиоме выбора: существует отображение g:B→/>. Тогда f °g=1B.Ч.т.д.
3)→1) в произвольной категории доказаносвойство о том, что если заданы отображения f:A→B, g:B→A, то из того, что g°f – эпиморфизм следует, что g-эпиморфизм (док-во см. выше). По условию g°f=1В. Выше также доказано свойство о том, что любаяединичная стрелка является эпистрелкой. Из всего вышесказанного следует, что g – эпиморфизм. Теорема доказанаполностью.
Следствие: в категории Setэквивалентны следующие условия: f-бистрелка,f-биекция, f-изоморфизм.2.3. Начальные и конечные объекты в категории множеств
Вкатегории множеств начальным объектом является пустое множество, так как пустоемножество есть подмножество любого множества. Стрелкой можно мыслить пары(элементу одного множества сопоставляется элемент другого). Таким образом,сопоставляя пустому множеству элемент любого множества, получим пустоемножество пар, которое является единственным.
Конечнымиобъектами в категории множеств являются одноэлементные множества. Для данногомножества А правило f(x)=e определяет функцию f:A→{e}. Так как e является единственным возможным значением, то эта функцияявляется единственной такой функцией. Таким образом, Setимеет много конечных объектов. Все они изоморфны между собой (конечные объектыизоморфны в любой категории). Их представителем является одноэлементноемножество {0}. 2.4. Произведение в категории множеств
/>В теории множеств есть понятие прямого произведениямножеств. Это такое множество />.Существуют естественные отображения – проекции /> и/>, такие, что pA(a,b)=a, pB(a,b)=b. Прямое отображение удовлетворяетсвойству универсальности: для любых множеств А, В, С и отображений f:C→A и g:C→Bсуществует единственное отображение h: />, делающее диаграмму (*)коммутативной.
Легко видеть,что h(c)=(f(c),g(c)). Это свойствоуниверсальности и берется в качестве определения произведения объектов впроизвольной категории.
· В категории Setпроизведение объектов Aи В изоморфно их прямому(декартову) произведению как множеств.
/>Доказательство: с одной стороны мы определили h(c)=(f(c),g(c)). Докажем, что />.
Рассмотримстрелку />. Очевидно, что l°h=1C,h°l=/>. Следовательно, />. 2.5. Копроизведения в категории множеств
/>
В категории Set копроизведение объектов А и В – этоих дизъюнктное объединение А+В, т.е. объединение двух множеств, изоморфных А иВ соответственно, но не пересекающихся. Точнее, пусть А’={:aÎA}=A´{0} и B’={:bÎB}=B´{1}. Положим А+В=A’ÈB’. инъекции iА: А®А+В, iВ: В®А+В определяются правилами iA(a)=,iB(b)=соответственно. 3 Примеры категорий3.1. Категория 1
Данная категория состоитиз одного объекта и одной стрелки. Этим она определяется полностью. Обозначимеё единственный объект через а, а её единственную стрелку – через f. Так как в этой категории толькоодин объект, то domf=codf=a, так как по определению категории с каждой стрелкой связанодва объекта –её начало и конец. А в данном случае объект только один. У каждогообъекта должна быть единичная стрелка. Но так как стрелка f – единственна, то её и берем вкачестве единичной. Единственной парой, для которой нужно определить операциюкомпозиции, является пара и мы полагаем, что f°f=f. Это дает законтождества, так как 1a°f=f°1a=f°f=f, и закон ассоциативности, так как f°(f°f)=(f°f)°f=f. Так мы определили категорию,которую можно изобразить так:
/>
3.2. Категория 2
Эта категория имеет дваобъекта и три стрелки и выглядит так:
/>в качестве парыобъектов возьмем числа 0 и 1, а в качестве стрелок – пары , и . Пусть :0®0,
:0®1,
:1®1.
Тогда =10(единичная стрелка на 0) и =11 (единичная стрелкана 1). При наших требованиях к категориям, композицию на этом множествеможно ввести только одним способом: 10°10=10, °10=, 11°=, 11°11=11. тогдадля любых объектов категории выполняется закон тождества и законассоциативности.3.3. Категория 3
Эта категория имеет триобъекта и шесть стрелок.
/>объекты: 0,1,2
стрелки: ,, , , , .
Стрелки,, — единичные.
Композицию определяемследующим образом:
10°10=10, 11°11=11, 12°12=12,°10=,11°=,°11=,12°=,°12=,10°=.Тогда выполняется закон тождества и закон ассоциативности. 3.4. Категории предпорядка
Категория, в которойлюбые два объекта p и q связаны не более чем одной стрелкой p®q, называется категориейпредпорядка. Если Р – совокупность объектов категории предпорядка, то наней определено следующее бинарное отношение R: ÎRÛ$ p®q. Отношение R обладает следующими свойствами:
2) рефлексивность (вытекает из того, что для любого объектакатегории существует единичная стрелка)
3) транзитивность (вытекает из того, что стрелка p®q дает в композиции со стрелкой q®s стрелку p®s)
Первыетри примера являются и примерами категории предпорядка. Но в них отношениепредпорядка удовлетворяет еще свойству антисимметричности, а именно еслиp®q и q®p, то p=q.Антисимметричное отношение предпорядка называют отношением частичного порядка.Простейшим примером категории предпорядка, />но не частичного порядка является двухобъектнаякатегория с четырьмя стрелками: в этой категории существуют стрелки p→q и q→p, но р¹q.3.5. Дискретные категории
Категория W называется дискретной, если в нейимеются только единичные стрелки, т.е. каждая стрелка является единичной длянекоторого объекта. Отождествляя объекты с единичными стрелками, можнозаметить, что дискретная категория есть не что иное, как совокупность объектов.Действительно, любое множество Xможно превратить в дискретную категорию, добавив единичные стрелки для каждого xÎX.3.6. Категория N
/>В этой категориировно один объект, обозначаемый через N. Также категория имеет бесконечную совокупность стрелок из N в N. По определению этими стрелками являются натуральные числа0,1,2,3…. Каждая стрелка имеет одно и то же начало и конец, а именноединственный объект N. Композиция двухстрелок (чисел) m и n есть снова число. Положим m°n=m+n. Итак, диаграмма коммутативна поопределению. Закон ассоциативности для стрелок вытекает из ассоциативностисложения.
/>Единичная стрелка 1N объекта N задается числом 0. Диаграмма коммутативна, так как 0+m=m n+0=n.Литература
1. Букур И., ДелянуА. Введение в теорию категорий и функторов. – М.: Мир, 1972.
2. Голдблат Р.Топосы. Категорный анализ логики. – М.: Мир, 1983.
3. Скорняков Л.А.Элементы общей алгебры. – М.: Наука, 1983.
4. Цаленко М.Ш.,Шульгейфер Е.Г. Основы теории категорий. – М.: Наука, 1974.