1.3: З'єднання Галуа

Last updated
Save as PDF

Page ID: 66286

$ \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}}$

Збереження зустрічей і приєднань, і, зокрема, питань, що стосуються генеративних ефектів, тісно пов'язане з теорією зв'язків Галуа, що є окремим випадком більш загальної теорії, яку ми обговоримо пізніше, а саме ад'юнкцій. Ми будемо використовувати деяку термінологію примикання при описі з'єднань Галуа.

Визначення та приклади з'єднань Галуа

Зв'язки Галуа між попередніми замовленнями вперше розглядав Еваріст Галуа, який не називав їх таким ім'ям в контексті зв'язку, який він виявив між «розширеннями полів» та «групами автоморфізму». Ми не будемо обговорювати це далі, але ідея полягає в тому, що, враховуючи два попередні замовлення P і Q, з'єднання Галуа - це пара карт назад і вперед від P до Q і від Q до P з певними властивостями, які роблять його схожим на розслаблену версію ізоморфізми. Якщо бути трохи точніше, ізоморфізми попереднього порядку є прикладами зв'язків Галуа, але з'єднання Галуа не повинні бути передпорядкованими ізоморфізмами.

Визначення: 1.95.

Зв'язку Галуа між попередніми порядками P і Q є парою монотонних карт f: P → Q і g: Q → P таких, що

f (p) ≤ q якщо і тільки якщо p ≤ g (q) . (1,96)

Говоримо, що f - лівий прилеглий, а g - правий примикає до з'єднання Галуа.

Приклад 1.97.

Розглянемо карту (3×−):$\mathbb{Z}$ →,$\mathbb{R}$ яка посилає x$\in$$\mathbb{Z}$ до 3 x, яке ми можемо розглядати як дійсне число 3 x$\in$$\mathbb{Z}$$\subseteq$$\mathbb{R}$.

Давайте знайдемо лівий прилеглий для карти (3 × −).

Напишіть z для найменшого натурального числа вище z$\in$$\mathbb{R}$ і запишіть z для найбільшого цілого числа нижче z$\in$ R, наприклад, 3.14= 4 і 3.14= 3. $^{a}$Як лівий сумісний$\mathbb{R}$ →$\mathbb{Z}$, давайте подивимося, чи працює −/3.

Легко перевіряється, що

x/3 ≤ y тоді і тільки тоді, коли x ≤ 3 y.

Успіху! Таким чином, ми маємо зв'язок Галуа між −/3і (3 × −).

$^{a}$Під «вище» і «нижче» ми маємо на увазі більше або дорівнює або менше або дорівнює; останній є ротом. Так чи інакше, 3= 3 = 3.

Вправа 1.98.

У прикладі 1.97 ми знайшли ліве спрямування для монотонної карти (3×−):$\mathbb{Z}$ →$\mathbb{R}$. Тепер знайдіть правильне примикання для тієї ж карти, і покажіть його правильно. ♦

Вправа 1.99.

Розглянемо попередній порядок P = Q = 3.

1. Нехай f, g будуть монотонними картами, показаними нижче:

$Знімок екрана 2021-01-05 в 2.40.51 PM.png$

Це так, що f ліворуч прилягає до g? Переконайтеся, що для кожного 1 ≤ p, q ≤ 3 один має f (p) ≤ q iff p ≤ g (q).

2. Нехай f, g будуть монотонними картами, показаними нижче:

3. Це так, що f ліворуч прилягає до g? ♦

Зауваження 1.100. Зображення у вправі 1.99 пропонують наступну ідею. Якщо P і Q - сумарні порядки, а f: P → Q і g: Q → P намальовані стрілками, що згинаються проти годинникової стрілки, то f ліворуч прилягають до g, якщо стрілки не перетинаються. Трохи роздумуючи, це можна формалізувати. Ми вважаємо, що це досить акуратний спосіб візуалізації зв'язків Галуа між загальними замовленнями!

Вправа 1.101.

Чи має −/3лівий стик L:$\mathbb{Z}$ →$\mathbb{R}$?
Якщо ні, то чому? Якщо так, то чи має лівий прилеглий лівий суглоб?

Повернутися до розділів

Нагадаємо з прикладу 1.52, що ми можемо зрозуміти множину Prt (S) розділів на множині S в терміні суб'єктивних функцій з S.

Припустимо, нам задано будь-яку функцію g: S → T. Ми покажемо, що ця функція g індукує зв'язок$g_{!}: \operatorname{Prt}(S) \leftrightarrows \operatorname{Prt}(T): g^{*}$ Галуа між попереднім порядком S -розділів і попереднім порядком T -розділів. Те, як ви можете пояснити це досвідченому теоретику категорії:

Лівий прилеглий дається, приймаючи будь-який surjection з S і виштовхуючи вздовж g, щоб отримати surjection з T. Правий сумісний дається, приймаючи будь-яке перенапруження з T, складаючи з g, щоб отримати функцію з S, а потім приймати епі-моно факторизацію, щоб отримати surjection з S.

$Знімок екрана 2021-01-05 в 2.44.33 PM.png$

До кінця цієї книги читач зрозуміє віджимання та епімоно факторизації, тому він зможе зрозуміти вищевказане твердження. Але поки ми пояснимо процес більш приземленими термінами.

Почніть з g: S → T; ми спочатку хочемо зрозуміти g! : Порт (S) → Порт (T). Отже, почніть$_{∼S}$ з розділу S. Щоб почати процес отримання розділу$_{∼T}$ на Т, скажімо, що два елементи$t_{1}$,$t_{2}$$\in$ Т знаходяться в одній частині$t_{1}$$_{∼T}$$t_{2}$, якщо є$s_{1}$,$s_{2}$$\in$ S з такі,$s_{1}$ що s $s_{2}$і g ($s_{1}$) =$t_{1}$ і g (s 2) =$t_{2}$. Однак результат цього не обов'язково буде перехідним, ви можете отримати$t_{1}$ T $t_{2}$і$t_{2}$ T $t_{3}$без,$t_{1} \sim_{T}^{?} t_{3}-$ а розділи повинні бути перехідними. Тож завершіть процес, просто додавши відсутні шматки (візьміть перехідне закриття). Результат - г! (S) :=$_{∼T}$. Знову починаючи з g, ми хочемо отримати правильне прилегле g ∗: Prt (T) → Prt (S). Отже, почніть$_{∼T}$ з розділу T. Отримати розділ$_{∼S}$ на S, сказавши, що$s_{1}$$_{∼S}$$s_{2}$ iff g ($s_{1}$)$_{∼T}$ g ($s_{2}$). Результат - g * ($_{~T}$) :=$_{~S}$.

Приклад 1.102.

Нехай S = {1,2,3,4}, T = {12,3,4}, і г: S → T по g (1) := g (2) := 12, g (3) := 3, і g (4) := 4. Розділ, показаний ліворуч нижче,$g_{!}$ перекладається на розділ, показаний праворуч.

$Знімок екрана 2021-01-07 в 8.32.35 PM.png$

Вправа 1.103.

У комплекті 15 різних перегородок з чотирма елементами. Виберіть 6 різних і для кожного з них називайте це c: S —» P, знайдіть g! (c), де S, T,

і g: S → T такі ж, як вони були в прикладі 1.102. ♦

Приклад 1.104.

Дозвольте S, T бути як показано нижче, і нехай g: S → T буде функція показана синім кольором. Ось картина того, як$g^{∗}$ бере розділ на T і «тягне його назад» до розділу на S:

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

Вправа 1.105.

Існує п'ять розділів, можливих на множині з трьома елементами, скажімо, T = {12,3,4}. Використовуючи ті ж S і g: S → T, що і в прикладі 1.102, визначте розділ$g^{∗}$ (c) на S для кожного з п'яти розділів c: T -» P. ♦

Щоб перевірити, чи для будь-якої функції g: S → T, монотонна карта$g_{!}$: Prt (S) → Prt (T) дійсно ліворуч прилягає до$g^{∗}$: Prt (T) → Prt (S) займе занадто багато часу для цього ескізу. Але наступна вправа дає деякі докази.

Вправа 1.106.

Нехай S, T і g: S → T будуть такими, як у прикладі 1.102.

Виберіть нетривіальний розділ c: S —» P і нехай$g_{!}$ (c) буде його push вперед розділ на T.
Виберіть будь-який грубіший розділ d: T —» P ′, тобто де$g_{!}$ (c) ≤ d.
Виберіть будь-який негрубіший розділ e: T —» Q, тобто де$g_{!}$ (c)$\nleq$ e. (Якщо ви не можете цього зробити, перегляньте свою відповідь на #1.)
Знайти$g^{∗}$ (г) і$g^{∗}$ (е).
Формула примикання Eq. (1.96) в даному випадку говорить, що оскільки$g_{!}$ (c) ≤ d і$g_{!}$ (c)$\nleq$ e, ми повинні мати c ≤$g^{∗}$ (d) і c$\nleq$$g^{∗}$ (e). Покажіть, що це правда. ♦

Основна теорія зв'язків Галуа

Пропозиція 1.107

Припустимо, що f: P → Q і g: Q → P - монотонні карти. Наступні є рівнозначними

f і g утворюють з'єднання Галуа, де f залишається прилеглим до g,

(б) для кожного р$\in$ Р і q$\in$ Q у нас є

p ≤ g (f (p)) і f (г (q)) ≤ q. (1.108)

Доказ. Припустимо, f ліворуч примикає до g. Візьміть будь-який$\in$ р Р, і нехай q: = f (p). За рефлексивністю ми маємо f (p) ≤ q, тому за визначенням 1,95 зв'язку Галуа ми маємо p ≤ g (q), але це означає p ≤ g (f (p)). Доказ того, що f (g (q)) ≤ q подібний.

Тепер припустимо, що Eq. (1.108) тримає для всіх p P і q Q. Ми хочемо показати, що f (p) ≤ q iff p ≤ g (q). Припустимо f (p) ≤ q; то так як g монотонний, g (f (p)) ≤ g (q), але p ≤ g (f (p)) так p ≤ g ( q). Доказ того, що p ≤ g (q) означає f (p) ≤ q, аналогічний. □

Вправа 1.109.

Заповніть доказ Пропозиції 1.107, показавши, що

якщо f ліворуч прилягає до g, то для будь-якого $\in$q Q ми маємо f (g (q)) ≤ q, і
якщо екв. (1.108) тримає значення, то утримує p ≤ g (q), якщо f (p) ≤ q тримає значення для всіх p$\in$ P і q$\in$ Q. ♦

Якщо замінити ≤ на = в еквалайзері (1.108), ми повернемо визначення ізоморфізму (визначення 1.75); саме тому ми говорили на початку розділу 1.4.1, що з'єднання Галуа є своєрідною розслабленою версією ізоморфізмів.

Вправа 1.110.

Покажіть, що якщо f: P → Q має право прилеглий g, то він є унікальним аж до ізоморфізму. Це означає, що для будь-якого іншого права суміжні g ′, у нас є g (q)$\cong$ g ′ (q) для всіх q$\in$ Q.
Це те ж саме стосується лівих суглобах? Тобто, якщо h: P → Q має ліве прилегле, чи обов'язково воно унікальне аж до ізоморфізму? ♦

Пропозиція 1.111 (Праві примикає збереження відповідає).

Нехай f: P → Q залишати прилеглими до g: Q → P. Припустимо, A$\subseteq$ Q будь-якої підмножини, і нехай g (A) := {g (a) | $\in$a} буде його зображенням. Тоді, якщо A має зустріч$\bigwedge$ A$\in$ Q, то g (A) має зустрітися$\bigwedge$ g (A) в P, і ми маємо

г ($\bigwedge A)$$\cong$$\bigwedge$г (А).

Тобто, правильні примикає збереження зустрічає. Аналогічно, ліві сукупності зберігають об'єднання: якщо A$\subseteq$ P - це будь-яка підмножина, яка має об'єднання V A $\in$P, то f (A) має об'єднання V f (A) в Q, і ми маємо

ф (В А)$\cong$ В ф (А).

Доказ. Ліворуч f: P → Q і g: Q → P бути суміжними монотонними картами, з g праворуч прилягають до f. Нехай A$\subseteq$ Q буде будь-якою підмножиною і нехай m :=$bigwedge$ A буде його зустрічатися. Тоді, оскільки g є монотонним g (m) ≤ g (a) для всіх $\in$A, тому g (m) - нижня межа множини g (A). Ми будемо робити, якщо ми зможемо показати g (m) найбільшу нижню межу. Тому візьміть будь-яку іншу нижню межу b для g (A); тобто припустимо, що для всіх $\in$A, у нас є b ≤ g (a) і ми хочемо показати b ≤ g (m). Тоді за визначенням g є праворуч суміжним (Визначення 1.95), ми також маємо f (b) ≤ a. Це означає, що f (b) - нижня межа для A в Q. Оскільки зустріч m - найбільша нижня межа, ми маємо f (b) ≤ m. Ще раз використовуючи з'єднання Галуа, b ≤ g (m), доводячи, що g (m) дійсно найбільша нижня межа для g (A), за бажанням.

Друга вимога доведена аналогічно; див. Вправа 1.112.

Вправа 1.112.

Завершіть доказ Пропозиції 1.111, показавши, що ліві примикання зберігають приєднання. ♦

Оскільки ліві суглобами зберігають приєднання, ми знаємо, що вони не можуть мати генеративних ефектів. Насправді, ми побачимо в теоремі 1.115, що монотонна карта не має генеративних ефектів - тобто зберігає з'єднання - тоді і лише тоді, коли вона є лівою суміжною з якимось іншим монотоном.

Приклад 1.113.

Праві примикання не повинні зберігати з'єднання. Ось приклад:

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

Дозвольте g бути карта, яка зберігає мітки, і нехай f карта, яка зберігає мітки, наскільки це можливо, але з f (3.9) := 4. Обидва є f і g монотонними, і можна перевірити, що g правильно прилягає до f (див. Вправа 1.114). Але g не зберігає з'єднань, оскільки 1$\lor$ 2 = 4 тримає в Q, тоді як g (1)$\lor$ g (2) = 1$\lor$ 2 = 3.9$\neq$ 4 = g (4) в P.

Вправа 1.114.

Щоб переконатися, що g дійсно є правильним прилеглим до f у прикладі 1.113, є дванадцять крихітних речей, щоб перевірити; зробіть це. Тобто для кожного p$\in$ P і q$\in$ Q перевірте, що f (p) ≤ q iff p ≤ g (q) . ♦

Теорема 1.115 (Теорма спряжених функторів для попередніх замовлень).

Припустимо, Q є попереднім порядком, який має всі відповідає і нехай P бути будь-яким попереднім замовленням. Монотонна карта g: Q → P зберігає зустрічає лише тоді і лише тоді, коли вона є праворуч прилеглою.

Аналогічно, якщо P має всі об'єднання, а Q є будь-яким попереднім порядком, монотонна карта f: P → Q зберігає з'єднання тоді і лише тоді, коли вона є лівою суміжною.

Доказ. Ми лише доведемо претензію про зустрічі; позов про приєднання слідує аналогічно. Доведено один напрямок у Пропозиції 1.111, а саме те, що правильні сукупності зберігають відповідає. Для іншого, припустимо, що g - монотонна карта, яка зберігає зустрічей; ми побудуємо ліву прилеглу f.

Визначаємо нашого кандидата f: P → Q на будь-якому п$\in$ п по

f (р) :=$\bigwedge$ {q$\in$ Q | р$\leq$ г (q)}; (1,116)

ця зустріч чітко визначена, тому що Q має всі зустрічі, але для того, щоб f дійсно бути кандидатом, нам потрібно показати, що це монотонно. Так припустимо, що р ≤ p ′. Потім {q ′$\in$ Q | р ′ ≤ г (q ′)}$\subseteq$ {q$\in$ Q | p ≤ g (q)}. За пропозицією 1.91 це означає f (p) ≤ f (p ′). Таким чином, f є монотонним.

За пропозицією 1.111 достатньо показати, що$p_{0}$ ≤ g (f ($p_{0}$)) і що f (g ($q_{0}$)) ≤$q_{0}$ для всіх$p_{0}$$\in$ P і$q_{0}$$\in$ Q. Для першого ми маємо

$p_{0}$$\leq$$\bigwedge${г (q)$\in$ Р |$p_{0}$$\leq$ г (q)}$\cong$ г ($\bigwedge${q$\in$ Q |$p_{0}$$\leq$ г (q)}) = г (ф ($p_{0}$),

де перша нерівність випливає з того,$p_{0}$ що якщо нижче кожного елемента множини, то воно нижче їх зустрічається, а ізоморфізм за визначенням g збереження відповідає. Для другого у нас є

f (г ($q_{0}$) =$\bigwedge$ {q$\in$ Q | г ($q_{0}$)$\leq$ г (q)}$\leq$$\bigwedge$ {$q_{0}$} =$q_{0}$,

де перша нерівність випливає з Пропозиції 1.91, оскільки$\subseteq$ {$q_{0}$} {$\in$q | g ($q_{0}$) ≤ g (q)}, і той факт, що$\bigwedge$ {$q_{0}$} =$q_{0}$. □

Приклад 1.117.

Нехай f: A → B буде функцією між множинами. Ми можемо уявити собі A як набір яблук, B як набір відер, і f як покласти кожне яблуко у відро.

Тоді у нас є монотонна карта$f^{∗}$: P (Y) → P (X), яку теоретики категорій називають «відкат уздовж f». Ця карта приймає підмножину $\subseteq$B ′ B до свого попереднього зображення$f^{ −1}$ (B ′)$\subseteq$ A: тобто вона бере колекцію B ′ відра, і повідомляє вам усі яблука, які вони містять в цілому. Ця операція монотонна (більше відра означає більше яблук) і має як лівий, так і правий прилеглий. Лівий суміжний$f_{!}$ (A) задається прямим зображенням: він відображає підмножину A ′$\subseteq$ A до

$f_{!}$(A') := {b$\in$ B | існує$\in$ A 'такий, що f (a) = b}

Ця карта займає набір A ′ яблук і повідомляє вам усі відра, які містять принаймні одне з цих яблук.

Правий сумісний$f^{∗}$ відображає підмножину A ′$\subseteq$ A до

$f_{*}$(A') := {b$\in$ B | для всіх таких, що f (a) = b, ми маємо$\in$ A '}

Ця карта приймає набір A ′ яблук, і повідомляє вам всі відра b, які всі A ′: всі яблука в b знаходяться з обраної підмножини A ′. Зверніть увагу, що якщо відро взагалі не містить яблук, то пилососно всі його яблука з A ′, тому порожні відра рахуються, наскільки$f_{∗}$ це стосується.

Зверніть увагу, що всі три ці операції виявляються цікавими: почніть з набору B ′ відра і поверніть всі яблука в них, або почніть з набору A ′ яблук і або знайдіть відра, які містять хоча б одне яблуко від А ′, або відра, чиї тільки яблука. знаходяться від A ′. Але ми не вигадували ці відображення$f_{∗}$$f_{!}$, а$f_{∗}$: вони були викликані функцією f. Вони були автоматичними. Це одне із задоволень теорії категорій, які так часто стикаються, виявляються цікавими смисловими інтерпретаціями.

Вправа 1.118.

Виберіть множини X і Y з двома і чотирма елементами кожен, і оберіть функцію f: X → Y.

Виберіть дві різні підмножини B 1, B 2$\subseteq$ Y і знайдіть$f^{∗}$ (B1) і$f^{∗}$ (B2).
Виберіть дві різні підмножини A 1, A 2$\subseteq$ X і знайдіть$f_{!}$ (A 1) і$f_{!}$ (A 2).
З тими ж А 1, А 2$\subseteq$ Х знайдіть$f_{∗}$ (А 1) і$f_{∗}$ (А 2) . ♦

Оператори закриття

За умови зв'язку Галуа з f: P → Q ліворуч прилягають до g: Q → P, ми можемо скласти f і g, щоб прийти до монотонної карти f: P → P з попереднього порядку P до себе. Ця монотонна карта має властивість, що p ≤ (f; g) (p), і що (f; g; f; g) (p) (f; g)$\cong$ (f; g) (p) для будь-якого p$\in$ P. Це приклад оператора закриття.

Вправа 1.119.

Припустимо, що f залишається прилеглим до g. Скористайтеся пропозицією 1.107, щоб показати наступне.

р ≤ (ф; г) (р).
(ф; г; ф; г) (р)$\cong$ (ф; г) (р). Щоб довести це, покажіть нерівності в обох напрямках, ≤ і ≥ . ♦

Визначення: 1.120.

Оператор закриття j: P → P на попередньому порядку P - монотонна карта така, що для всіх p$\in$ P ми маємо

(а) р ≤ j (р);
(б) j (j (р))$\cong$ j (р).

Приклад 1.121.

Ось приклад операторів закриття з обчислень, дуже приблизно представлений. Уявіть собі обчислення як процес перезапису вхідних виразів на вихідні вирази. Наприклад, комп'ютер може переписати вираз 7+2+3 як вираз 12. Набір арифметичних виразів має частковий порядок відповідно до того, чи можна переписати один вираз як інше.

Ми могли б думати про комп'ютерну програму, то, як метод прийняття виразу і скорочення його до іншого виразу. Так що це карта j: exp → exp. Крім того, бажано вимагати, щоб ця комп'ютерна програма була оператором закриття. Монотонність означає, що якщо вираз x можна переписати у вираз y, то зменшення j (x) можна переписати в j (y). Більше того, вимога x ≤ j (x) передбачає, що j може перетворити один вираз в інше, якщо це є допустимим перезаписом. Вимога

j (j (x)) = j (x) має на увазі, якщо ви намагаєтеся зменшити вже скорочений вираз, комп'ютерна програма залишає його як є. Ці властивості забезпечують корисну структуру при аналізі програмної семантики.

Приклад 1.122 (Ад'юнктипми від операторів закриття).

Подібно до того, як кожне примикання породжує оператор закриття, з кожного оператора закриття ми можемо побудувати примикання.

Нехай P є попереднім порядком, а j: P → P — оператор закриття. Ми можемо визначити попередній порядок,$fix_{j}$ щоб мати елементи фіксованих точок j; тобто

$fix_{j}$:= {р$\in$ Р | j (р)$\cong$ р}.

Це підмножина P, і успадковує порядок в результаті; отже$fix_{j}$, підпорядок P. Зверніть увагу, що j (p) є фіксованою точкою для всіх$\in$ p P, оскільки j (p))$\cong$ j (p).

Визначимо примикання з лівим суміжним j: P →$fix_{j}$ відправкою p до j (p), а праворуч прилеглим g:$fix_{j}$ → P просто включенням підпорядку. Щоб побачити, що це дійсно примикання, ми повинні побачити, що для будь-яких p$\in$ P і q$\in$$fix_{j}$, ми маємо j (p) ≤ q якщо і тільки якщо p ≤ q. Давайте перевіримо це. Починаючи з p ≤ j (p), ми маємо, що j (p) ≤ q означає p ≤ q за перехідністю. І навпаки, оскільки q є фіксованою точкою, p ≤ q передбачає j (p) ≤ j (q)$\cong$ q.

Приклад 1.123.

Інший приклад операторів закриття походить з логіки. Про це піде мова в заключному розділі книги, зокрема Розділі 7.4.5, але ми наведемо тут короткий огляд. По суті, логіка - це вивчення того, коли одне формальне твердження або судження має на увазі інше. Наприклад, якщо n є простим, то n не кратний 6, або якщо йде дощ, то земля стає більш вологою. Тут «n є простим», «n не кратне 6», «йде дощ», і «земля стає більш вологою» - це пропозиції, і ми дали два наслідки. Візьміть множину всіх пропозицій і впорядкуйте їх по p ≤ q, якщо p має на увазі q, що позначається p ⇒ q. Оскільки р ⇒ р і оскільки всякий раз, коли р ⇒ q і q ⇒ r, у нас також є p ⇒ r, це дійсно попередній порядок.

Оператор закриття на ньому часто називають модальним оператором. Це функція j від пропозицій до пропозицій, для яких p ⇒ j (p) і j (j (p)) = j (p). Прикладом j є «припускаючи, що Боб знаходиться в Сан-Дієго...» Подумайте про це як про пропозицію B; так що «припускаючи, що Боб знаходиться в Сан-Дієго, р» означає B ⇒ p. Давайте розберемося, чому B ⇒ − є оператором закриття. Якщо 'p' вірно, то «припускаючи, що Боб знаходиться в Сан-Дієго, р» все ще вірно. Припустимо, що «припускаючи, що Боб знаходиться в Сан-Дієго, це той випадок, що, припускаючи, що Боб знаходиться в Сан-Дієго, p 'правда». Звідси випливає, що «припускаючи, що Боб знаходиться в Сан-Дієго, р» - це правда. Тож ми бачили, принаймні неофіційно, що «припускаючи, що Боб знаходиться в Сан-Дієго...» - це оператор закриття.

Зсув рівня

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

З огляду на будь-яку множину S, існує множина Rel (S) двійкових зв'язків на S. Елемент R$\in$ Rel (S) формально є підмножиною R$\subseteq$ S × S. Набір Rel (S) може бути надано порядок через відношення підмножини, R$\subseteq$ R ′, тобто якщо всякий раз, коли R ($_{s1}$,$_{s2}$) тримає, то і R ′ ($_{s1}$,$_{s2}$).

Наприклад, діаграма Хассе для Rel ({1}) така:

$Знімок екрана 2021-01-05 в 3.44.55 PM.png$

Вправа 1.124.

Намалюйте діаграму Хассе для попереднього порядку Rel ({1, 2}) всіх двійкових зв'язків на множині {1, 2} . ♦

Для будь-якого набору S також існує набір Pos (S), що складається з усіх зв'язків попереднього порядку на S. Насправді існує структура попереднього порядку$\sqsubseteq$ на Pos (S), знову задана включенням: ≤ знаходиться нижче ≤′ (ми запишемо ≤$\sqsubseteq$ ≤′), якщо a ≤ b передбачає ≤′ b для кожного a, b$\in$ S . Попереднє замовлення конструкцій? Ось що ми маємо на увазі під зміщенням рівня.

Кожне відношення попереднього замовлення є певним відношенням, тому ми маємо включення Pos (S) → Rel (S). Це правий примик з'єднання Галуа.

Його лівий суміжний - це монотонна карта Cl: Rel (S) → Pos (S), задана шляхом прийняття будь-якого відношення R, запису його в інфіксних позначеннях з використанням ≤, і прийняття рефлексивного та перехідного замикання, тобто додавання s ≤ s для кожного s і додаючи s ≤ u щоразу, коли s ≤ t і t ≤ u.

Вправа 1.125.

Нехай S = {1, 2, 3}. Спробуємо розібратися в розглянутому вище примиканні.

1. Придумайте будь-яке відношення попереднього порядку ≤ на S і визначте U (≤) як підмножина U (≤) := {(s 1, s 2) | s 1 ≤ s 2}$\subseteq$ S × S, тобто U (≤) - зображення ≤ під включенням Pos (S) → Rel (S), відношення «лежить в основі» попереднього замовлення.

2. Придумайте будь-які два двійкові відносини Q$\subseteq$ S × S і Q ′$\subseteq$ S × S такі, що Q$\subseteq$ U (≤) але Q ′$\nsubseteq$ U (≤). Зверніть увагу, що ваш вибір Q, Q ′ не повинен виходити з попередніх замовлень.

Тепер ми хочемо перевірити, що в цьому випадку операція закриття Cl дійсно залишилася прилеглою до карти «базового відношення» U.

3. Конкретно (без використання твердження, що існує якесь примикання), покажіть, що Cl (Q)$\sqsubseteq$ ≤, де$\sqsubseteq$ знаходиться порядок на Pos (S), визначений безпосередньо над цією вправою.

4. Конкретно показати, що Cl (Q ′)$\not\sqsubseteq$ ≤ . ♦