7.2: Набір категорій як зразковий топос

Last updated
Save as PDF

Page ID: 66468

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Ми хочемо думати про дуже абстрактний вид речі, званий топос, тому що ми побачимо, що типи поведінки утворюють топос. Для початку ми починаємо з однієї з найпростіших топозицій, про яку слід подумати, а саме topos Set of set. У цьому розділі ми обговоримо спільні риси між множинами та будь-якими іншими топосами. Ми займемося деякими подробицями про категорію наборів, щоб дати інтуїцію іншим топосам. Зокрема, ми приділимо пильну увагу логіці множин, адже ми з часом хочемо зрозуміти логіку поведінки.

Дійсно, логіка і множини тісно пов'язані між собою. Наприклад, логічне твердження, більш формально відоме як присудок likes_cats, визначає функцію від множини P людей до множини$\mathbb{B}$ = {false, true} значень істини, де Брендан$\in$ P відображає true, тому що йому подобаються коти, тоді як Урсула$\in$ П карти помилково, тому що вона цього не робить. Крім того, likes_cats також визначає підмножину P, що складається саме з людей, які люблять котів

{p$\in$ P | лайки_кішки (p)}.

З точки зору цих підмножин логічні операції відповідають операціям множини, наприклад AND відповідає перетину: дійсно, набір людей для (зіставлений на true by) предикат likes_cats_і_likes_dogs дорівнює перетину множини для likes_cats і множини для likes_dogs.

Ми побачили в главі 3, що такі операції, які є прикладами запитів до бази даних, можуть бути описані з точки зору лімітів і колімітів у Set. Дійсно, категорія Set має багато таких структур і властивостей, які разом роблять можливою логіку в цій настройці. У цьому розділі ми хочемо визначити ці властивості та показати, як логічні операції можуть бути визначені з їх допомогою.

Чому ми хочемо абстрактно знайти такі структури і властивості? У наступному розділі ми почнемо пошук інших категорій, які також мають їх. Такі категорії, які називаються топозами, будуть Set подібними до логіки, але мають набагато більш складну і цікаву семантику. Дійсно, ми обговоримо той, логіка якого дозволяє міркувати не про властивості множин, а про поведінкові властивості дуже загальних машин.

Встановити подібні властивості, якими користуються будь-які топоси

Хоча ми не доведемо цього в цій книзі, топози - це категорії, схожі на Набір у багатьох відношеннях. Ось деякі факти, які вірні для будь-якого топоса$\mathcal{E}$:

$\mathcal{E}$має всі межі,
$\mathcal{E}$має всі обмеження,
$\mathcal{E}$декартова замкнута,
$\mathcal{E}$має епі-моно факторизації,
$\mathcal{E} \text { has a subobject classifier } 1 \stackrel{\text { true }}{\longrightarrow} \Omega \text { . }$

Зокрема, оскільки Set є топосом, всі перераховані вище факти вірні для$\mathcal{E}$ = Set. Наша перша мета - коротко розглянути ці поняття, зосередившись найбільше на підпредметному класифікаторі.

Ліміти та обмеження. Ми коротко обговорили обмеження та обмеження в розділі 3.4.2, але основна ідея полягає в тому, що можна створювати нові об'єкти зі старих, беручи продукти, використовуючи рівняння для визначення підоб'єктів, утворюючи неспільні союзи та приймаючи коефіцієнти.object 0. Одним з найважливіших типів ліміту (resp. colimit) є відкатів (resp. pushouts); див. Приклад 3.99 та Визначення 6.19. Для нашої роботи нижче нам потрібно буде знати трохи більше про відкати, ніж ми обговорювали досі, тож давайте почнемо там.

Припустимо, що C є категорією і розглянемо діаграми нижче:

$Знімок екрана 2021-01-25 о 1.56.43 PM.png$

У лівому квадраті символ кута$\text { I }$ однозначно означає, що квадрат (B, C, E, F) - це відкат. Але в правому квадраті, чи означає символ кута, що (A, B, D, E) є відкат або що (A, C, D, F) є відкат? Це неоднозначно, але, як ми далі показуємо, це стає однозначним, якщо правий квадрат - це відкат.

Пропозиція 7.3.

На комутативній діаграмі нижче, припустимо, що квадрат (B, C, B ′, C ′) є відкат:

$Знімок екрана 2021-01-25 о 1.57.45 PM.png$

Тоді (A, B, A ′, B ′) квадрат є відкат, якщо (A, C, A ′, C ′) прямокутник є відкат.

Вправа 7.4.

Доведіть пропозицію 7.3, використовуючи визначення межі з розділу 3.4.2. ♦

Епі-моно факторизації. Абревіатура 'epi' розшифровується як епіморфізм, а ab- абревіатура 'mono' розшифровується як мономорфізм. Епіморфізми - це карти, які діють як відмови, а мономорфізми - це карти, які діють як ін'єкції. $^{3}$Ми можемо визначити їх формально з точки зору віджимань і відкатів.

Визначення 7.5.

Нехай C буде категорією, а ліворуч f: A → B - морфізмом. Його називають мономорфізмом (resp. епіморфізм) якщо квадрат вліво - відкат (реп. квадрат праворуч - відштовхування):

$Знімок екрана 2021-01-25 о 2.12.15 PM.png$

Вправа 7.6.

Покажіть, що в Сет мономорфізми - це всього лише ін'єкції:

1. Покажіть, що якщо f - мономорфізм, то він ін'єкційний.
2. Покажіть, що якщо f: A → B є ін'єкційним, то це мономорфізм. ♦

Вправа 7.7.

1. Покажіть, що відкат ізоморфізму уздовж будь-якого морфізму - це ізоморфізм. Тобто припустимо, що i: B ′ → B - ізоморфізм, а f: A → B - будь-який морфізм. Покажіть, що i ′ - це ізоморфізм, на наступній діаграмі:

$Знімок екрана 2021-01-25 о 2.15.29 PM.png$

2. Показати, що для будь-якої карти f: A → B показаний квадрат є відкат:

$Знімок екрана 2021-01-25 о 2.16.23 PM.png$ ♦

Вправа 7.8.

Припустимо, що наступна діаграма є відкат у категорії C:

$Знімок екрана 2021-01-25 о 2.18.10 PM.png$

Використовуйте Пропозицію 7.3 та Вправу 7.7, щоб показати, що якщо f - мономорфізм, то так і f ′ . ♦

Тепер, коли ми визначили епіморфізми та мономорфізми, ми можемо сказати, що таке епімоно факторизації. Ми говоримо, що морфізм f: C → D в E має епі-моно факторизацію, якщо він має «зображення»; тобто є об'єкт im (f), епіморфізм C$\twoheadrightarrow$ im (f) та мономорфізм im (f)$\rightarrowtail$ D , чиїм складом є f.

У наборі епіморфізми - це відмови, а мономорфізми - ін'єкції.

Кожна функція f: C → D може бути врахована як суб'єктивна функція на її зображення im (f) = {f (c) |$\in$ c C} з подальшим включенням цього зображення до кодомену D. Більш того, ця факторизація унікальна аж до ізоморфізму.

Вправа 7.9.

Фактор наступної функції f: 3 → 3 як епіморфізм з подальшим мономорфізмом.

$Знімок екрана 2021-01-25 о 2.19.45 PM.png$ ♦

Так відбувається в будь-якому топосі$\mathcal{E}$: при будь-якому морфізмі f: c → d існує епіморфізм e і мономорфізм m такий, що f = (e; m) є їх складовим.

Декартова закрита. Категорія C будучи декартовим замкнутим означає, що C має симетричну моноїдальну структуру, задану виробами, і вона моноїдальна закрита щодо цього. (Раніше ми бачили моноїдальне закриття у Визначенні 2.79 (для попередніх замовлень) та Пропозиції 4.60 як наслідок компактного закриття.) Трохи більше вниз до землі, декартове замикання означає, що для будь-яких двох об'єктів $\in$C, D C існує 'hom-об'єкт' D$^{C}$ $\in$C і природний ізоморфізм для будь-якого A$\in$ C:

С (А × С, Г)$\cong$ С (А, Г$^{C}$) (7,10)

Подумайте про це так. Припустимо, що ви A, а я C, і ми взаємодіємо через якусь гру f (−, −): A × C → D: для будь-якої дії $\in$A, яку ви вживаєте, і дії c$\in$ C що я take, f (a, c) - деяке значення в D. Оскільки ви егоцентричні, але люблячі, ви думаєте про цю ситуацію так, ніби ви створюєте ігровий досвід для мене. Коли ви робите a, ви робите гру f (a, −): C → D тільки для мене. У формалізмі D$^{C}$ представляє набір ігор для мене. Отже, тепер ви перетворили гру для двох гравців, оцінену в D, в гру для одного гравця, ви гравець, який цінується в... іграх для одного гравця, оцінених у D. Ця трансформація є оборотною, ви можете перемикати свою точку зору за бажанням, і це називається каррі. Це зміст Прикладу 3.72.

Вправа 7.11.

Нехай V = (V, ≤, I,) буде a (одинична, комутативна) кванта див. Визначення 2.90 і припустимо, що воно задовольняє наступне для всіх v, w, x$\in$ V:

• v ≤ I,

• v w ≤ v і v w ≤ w, і

• якщо x ≤ v і x ≤ w, то x ≤ v w.

1. Показати, що V є декартовою замкнутою категорією, насправді декартовим замкнутим попереднім порядком.

2. Чи може кожен декартовий закритий попередній замовлення бути отриманий таким чином? ♦

Класифікатор суб'єкт. Поняття підпредметного класифікатора вимагає більшої уваги, оскільки його існування має величезні наслідки для категорії C. Зокрема, він створює налаштування для існування багатої системи логіки вищого порядку всередині C; це робить, надаючи деякі речі, які називаються «істинними значеннями». Логіка вищого порядку проявляється у своїй повній славі, коли C має кінцеві межі і декартова замкнута, оскільки ці факти породжують логічні операції над значеннями істинності.4 Зокрема, логіка вищого порядку існує в будь-якому топосі.

Ми пояснимо класифікатори підоб'єктів якомога докладніше; насправді це буде нашою темою для решти розділу 7.2.

Класифікатор суб'єкт

Перш ніж дати визначення підпредметних класифікаторів, нагадаємо, що мономорфізми в Set - це ін'єкції, а будь-яка ін'єкція X$\rightarrowtail$ Y ізоморфна до підмножини Y. Це дає простий і корисний спосіб концептуалізації мономорфізмів у Y при читанні наступного визначення: не зашкодить думати про них як про підоб'єкти Y.

Визначення 7.12.

Дозволяти$\mathcal{E}$ бути категорія з скінченними межами, тобто з відкатами і термінальним об'єктом 1. Суб'єктний класифікатор в$\mathcal{E}$ складається з об'єкта Ω$\in$$\mathcal{E}$, разом з мономорфізмом істинний: 1 → Ω, що задовольняє таку властивість: для будь-яких об'єктів X і Y і мономорфізму m: X$\rightarrowtail$ Y в $\mathcal{E}$, існує унікальний морфізм$\lceil{m}\rceil$: Y → Ω такий, що діаграма зліва від Eq. (7.13) є відкат в$\mathcal{E}$:

$Знімок екрана 2021-01-25 о 2.40.17 PM.png$

Ми$\lceil{m}\rceil$ називаємо характерною картою$\lceil{m}\rceil$, або ми говоримо, що m класифікує$\lceil{m}\rceil$. І навпаки, задавши будь-яку карту p: Y → Ω, позначимо відкат істинного як праворуч від ур. (7.13).

Присудок на Y - це морфізм Y → Ω.

Визначення 7.12 трохи важко обійти свій розум, частково тому, що важко уявити його наслідки. Це як надщільний самородок з космосу, і завдяки науковим дослідженням в другій половині 20 століття ми виявили, що він приносить наддержави до тих, які його мають категорії. Деякі наслідки ми пояснимо нижче, але дуже швидко ідея наступна.

Коли категорія має класифікатор підоб'єктів, вона забезпечує перекладач, перетворюючи підоб'єкти будь-якого об'єкта Y на карти від цього Y до конкретного об'єкта Ω. Відкат мономорфізму істинний: 1 → Ω забезпечує перекладач, який повертає назад, перетворюючи карти Y → Ω на підоб'єкти Y. Ми можемо замінити нашу фантазію про надщільний самородок трохи більш витонченою історією: «будь-який об'єкт Y розуміє себе - його частини і логіку того, як вони поєднуються між собою - задаючи питання оракулу Ω, шукаючи, що правда». Або, щоб бути повністю точним, але сухим, «підоб'єкти Y класифікуються за предикатами на Y».

Перейдемо від історій і гасел до конкретних фактів.

Класифікатор підоб'єктів у Set. Оскільки Set є топосом, він має класифікатор підоб'єктів. Це буде набір з нібито чудовими властивостями; який це набір?

Класифікатор subobject в Set - це набір булевих,

Ω$_{Set}$ :=$\mathbb{B}$ = {істина, хибна} . (7.14)

Таким чином, у наборі, істинні значення є істинними і хибними.

За визначенням (Def. 7.12), підпредметний класифікатор оснащений морфізмом, загально званим істинним: 1 → Ω; у випадку Set він відтворюється функцією 1 → {true, false}, яка посилає 1 до true. Іншими словами, морфізм істинний влучно названий в даному випадку.

Для наборів мономорфізм якраз означає ін'єкції, про що ми вже згадували вище. Отже, Defini- tion 7.12 говорить, що для будь-якої ін'єкційної функції m: X$\rightarrowtail$ Y між множинами, ми повинні бути в змозі знайти характеристичну функцію$\lceil{m}\rceil$: Y → {true, false} з якоюсь властивістю відкату.

Пропонуємо наступне визначення$\lceil{m}\rceil$:

$Знімок екрана 2021-01-25 о 2.55.41 PM.png$

Іншими словами, якщо ми думаємо про X як про підоб'єкт Y, то ми робимо$\lceil{m}\rceil$ (y) рівним істинному iff y$\in$ X.

Зокрема, властивість класифікатора підоб'єктів перетворює $\subseteq$підмножини X Y у функції p: Y →$\mathbb{B}$, і навпаки.

Як це працює, закодовано у визначенні 7.12, але основна ідея полягає в тому, що X буде набором усіх речей у Y, що p посилає до true:

X = {у$\in$ Y | р (у) = істина} . (7.15)

Це може допомогти пояснити наші абстрактні позначення {Y | p} в ур. (7.13).

Вправа 7.16.

Нехай X$\mathbb{N}$ = {0, 1, 2,...} і Y$\mathbb{Z}$ = {..., −1, 0, 1, 2, ... };

ми маємо X$\subseteq$ Y, тому розглядаємо його як мономорфізм m: X$\rightarrowtail$ Y.

Він має характерну функцію$\lceil{m}\rceil$: Y →$\mathbb{B}$, як у Визначенні 7.12.

1. Що таке$\lceil{m}\rceil$ (−5)$\in$$\mathbb{B}$?

2. Що таке$\lceil{m}\rceil$ (0)$\in$$\mathbb{B}$? ♦

Вправа 7.17.

1. Розглянемо ідентифікаційну функцію id$_{\mathbb{N}}$:$\mathbb{N}$ →$\mathbb{N}$.

Це ін'єкція, тому має характерну функцію id$\lceil{_{\mathbb{N}}}\rceil$:$\mathbb{N}$ →$\mathbb{B}$.

Дайте конкретний опис id$\lceil{_{\mathbb{N}}}\rceil$, тобто його точне значення для кожного натурального числа n$\in$$\mathbb{N}$.

2. Розглянемо унікальну функцію! $_{\mathbb{N}}$: Ø → N з порожнього набору. Дайте конкретний опис$\lceil{!_{\mathbb{N}}}\rceil$:$\mathbb{N}$ →$\mathbb{B}$. ♦

Логіка в наборі топосів

Як ми вже говорили вище, subobject класифікатор будь-якого топоса$\mathcal{E}$ дає настройку, в якій потрібно робити логіку. Перш ніж ми пояснимо трохи про те, як працює топовна логіка загалом, ми продовжуємо працювати конкретно, зосереджуючись на логіці в наборі топосів.

Отримання операції І. Розглянемо функцію 1 →$\mathbb{B}$ ×$\mathbb{B}$ виділення елемента (true, true). Це мономорфізм, тому він визначає характерну функцію$\lceil{(true, true)}\rceil$:$\mathbb{B}$ ×$\mathbb{B}$ →$\mathbb{B}$. Що це за функція? За еквалайзером (7.15) єдиним елементом$\mathbb{B}$ ×$\mathbb{B}$, який можна надіслати до true є (true, true). Таким чином$\lceil{(true, true)}\rceil$ (P, Q)$\in$$\mathbb{B}$ повинні бути наведені наступною таблицею істинності

$Знімок екрана 2021-01-25 о 3.38.32 PM.png$

Це саме таблиця істинності для І P і Q, тобто для P$\bigwedge$ Q. Іншими словами,$\lceil{(true, true)}\rceil$ =$\bigwedge$.

Зауважте, що це визначає$\bigwedge$ як функцію$\bigwedge$:$\mathbb{B}$ ×$\mathbb{B}$ →$\mathbb{B}$, і ми використовуємо звичайне інфіксне позначення x$\bigwedge$ y: =$\bigwedge$ (x, y).

Отримання операції ОР. Давайте підемо назад на цей раз.

Таблиця істинності для OR P і Q, тобто для функції$\bigvee$:$\mathbb{B}$ ×$\mathbb{B}$ →$\mathbb{B}$ визначення OR, є:

$Знімок екрана 2021-01-25 о 4.10.21 PM.png$

Якби ми хотіли отримати цю функцію як характерну функцію$\lceil{m}\rceil$ деякої підмножини m: X$\subseteq$$\mathbb{B}$ ×$\mathbb{B}$, яка підмножина буде X? За еквалайзером (7.15) X має бути множиною y$\in$ Y, які надсилаються до true. Таким чином, m - характерна карта для трьохелементної підмножини.

X = {(правда, правда), (правда, брехня), (брехня, правда)}$\subseteq$$\mathbb{B}$ ×$\mathbb{B}$.

Щоб підготуватися до подальшого узагальнення цієї ідеї в будь-якому топосі, нам потрібен спосіб мислення X тільки з точки зору властивостей, перерахованих на початку Розділу 7.2.1. Насправді, можна вважати X об'єднанням {true} ×$\mathbb{B}$ і$\mathbb{B}$ × {true} коліміту меж, що включає класифікатор підоб'єктів і термінальний об'єкт. Цей опис побудує аналогічний підоб'єкт Ω × Ω, і, отже, класифікує карту Ω × Ω → Ω, у будь-якому топосі$\mathcal{E}$.

Вправа 7.19.

Кожне логічне значення має заперечення, ¬false = true і ¬true = false. Функція ¬:$\mathbb{B}$ →$\mathbb{B}$ - характерна функція якоїсь речі, (*? *).

Яку річ повинна (*? *) бути? Наприклад, повинна ¬ бути характерною функцією об'єкта? Топос? Морфізм? Суб'єкт? Діаграма відкату?
Тепер, коли ви знаєте, що таке (*? *) є, яка річ такого роду це? ♦

Вправа 7.20.

Задано два булевих значення P, Q, визначити P ⇒ Q, щоб означати P = (P$\bigwedge$ Q).

1. Запишіть таблицю істинності для твердження P = (P$\bigwedge$ Q):

$Знімок екрана 2021-01-25 о 4.26.36 PM.png$

Якщо ви вже маєте уявлення, що має означати P ⇒ Q, чи згоден він з останнім стовпцем таблиці вище?
Що таке характеристична функція m:$\mathbb{B}$ ×$\mathbb{B}$ →$\mathbb{B}$ для P ⇒ Q?
Який субоб'єкт класифікує м? ♦

Вправа 7.21.

Розглянемо множини E: = {n$\in$$\mathbb{N}$ | n парне}, P: = {n$\in$$\mathbb{N}$ | n - просте}, а T := {n$\in$$\mathbb{N}$ | n ≥ 10}. Кожна з них є підмножиною N, тому визначає функцію N → B.

1. Що таке$\lceil{E}\rceil$ (17)?

2. Що таке$\lceil{P}\rceil$ (17)?

3. Що таке$\lceil{T}\rceil$ (17)?

4. Назвіть найменші три елементи множини, що класифікуються за допомогою ($\lceil{E}\rceil$$\bigwedge$$\lceil{P}\rceil$)$\bigvee$$\lceil{T}\rceil$. ♦

Рецензія. Давайте підведемо підсумки того, де ми знаходимося і куди йдемо. У розділі 7.1 ми поставили нашу мету довести властивості поведінки, і ми сказали, що теорія топосів є хорошим математичним налаштуванням для цього. Зараз ми знаходимося в кінці розділу 7.2, який був про Set як приклад топос. Що сталося?

У розділі 7.2.1 ми говорили про властивості Set, якими користуються будь-які топоси: межі та коліміти, декартове замикання, епі-моно факторизації та класифікатори підоб'єктів. Потім у розділі 7.2.2 ми почали думати про класифікатор підоб'єктів загалом та у конкретному наборі топосів, де це множина$\mathbb{B}$ булевих, оскільки будь-яка підмножина Y класифікується певним предикатом p: Y →$\mathbb{B}$. Нарешті, в розділі 7.2.3 ми обговорювали, як зрозуміти логіку з точки зору Ω: існують різні карти$\bigwedge$$\bigvee$, ⇒: Ω × Ω → Ω і ¬: Ω → Ω і т.д., які служать логічними зв'язками. Це операції над значеннями істинності.

Ми багато говорили про топози, але поки що бачили лише одну: категорію наборів. Але ми насправді бачили більше, не знаючи цього: категорія C- Inst екземплярів на будь-якій схемі бази даних від визначення 3.60 є топос. Такі топози називаються presheaf топози і є фундаментальними, але ми зупинимося на топозах сніпів, тому що наші топоси типів поведінки будуть топосом снопа. Снопи - захоплюючі, але дуже абстрактні математичні об'єкти. Вони не для людей зі слабкими математичними серцями (ті, хто слабкі від фізичного серця, можуть продовжити).