1.1: Що таке замовлення?
- Page ID
- 66285
Вище ми неофіційно говорили про дві різні впорядковані множини: порядок підключення системи та порядок на логічних помилкових ≤ true. Потім ми пов'язували ці дві впорядковані множини за допомогою спостереження Аліси Φ. Перш ніж продовжувати, нам потрібно зробити такі ідеї більш точними. Починаємо в розділі 1.2.1 з огляду множин і відносин. У розділі 1.2.2 ми дамо визначення попереднього замовлення - скорочено для попередньо впорядкованого набору - і велику кількість прикладів.
Огляд множин, відносин і функцій
Ми не будемо давати визначення множини тут, але неофіційно ми будемо думати про набір як сукупність речей, відомих як елементи. Ці речі можуть бути всі листя на певному дереві, або назви ваших улюблених фруктів, або просто деякі символи a, b, c. Наприклад, ми пишемо A = {h ,1} для позначення множини, яка називається A, яка містить рівно два елементи, один називається h і один називається 1. Множина {h, h, 1, h, 1} точно така ж, як A, оскільки вони обидва містять однакові елементи, h і 1, і повторення елемента більше одного разу в позначенні не змінює множини.3 Для довільного множини X ми пишемо х\(\in\) х, якщо х є елементом X; так що у нас є\(h \in A\) і\(1 \in A\), але\(0 \notin A\).
Ось деякі важливі набори з математики - і позначення, які ми будемо використовувати - які знову з'являться в цій книзі.
- \(\varnothing\)позначає порожній набір; він не має елементів.
- {1} позначає множину з одним елементом; вона має один елемент, 1.
- \(\mathbb{B}\)позначає набір логічних знаків; він має два елементи, true і false.
- \(\mathbb{N}\)позначає множину натуральних чисел; вона має елементи\(0,1,2,3, \ldots, 90^{717}, \ldots\)
- \(n,\)для будь-якого\(n \in \mathbb{N},\) позначає\(n^{t h}\) порядковий; він має\(n\) елементи\(1,2, \ldots, n .\) Наприклад,\(\underline{0}=\varnothing, \underline{1}=\{1\},\) і\(\underline{5}=\{1,2,3,4,5\}\)
- \(\mathbb{Z},\)множина цілих чисел; він має елементи\(\ldots,-2,-1,0,1,2, \ldots, 90^{717}, \ldots\)
- \(\mathbb{R},\)набір дійсних чисел; він має такі елементи, як\(\pi, 3.14,5 * \sqrt{2}, e, e^{2},-1457,90^{717},\) і т.д.
З огляду на множини X і Y, ми говоримо, що X є підмножиною Y, і пишемо X Y, якщо кожен елемент в X також знаходиться в Y. Наприклад {h}\(\subseteq\) A. Зауважте, що порожній набір Ø: = {} є підмножиною будь-якого іншого множини.4 Враховуючи множину Y та властивість P, яка є істинним або хибним для кожного елемента Y, ми пишемо {y\(\in\) Y | P (y)}, щоб означати підмножину ті y, які задовольняють P.
- Чи правда, що N = {n\(\in\) Z | n ≥ 0}?
- Чи правда, що N = {n\(\in\) Z | n ≥ 1}?
- Чи правда, що Ø = {n\(\in\) Z | 1 < n < 2}?
Якщо обидва X 1 і X 2 є підмножинами Y, їх об'єднання, позначене X 1 X 2, також є підмножиною Y, а саме той, що містить елементи в X 1 і елементи в X 2, але не більше. Наприклад, якщо Y = {1,2,3,4} і X 1 = {1,2} і X 2 = {2,4}, то X 1\(\cup\) X 2 = {1,2,4}. Зверніть увагу, що Ø\(\cup\) X = X для будь-якого X\(\subseteq\) Y.
Аналогічно, якщо і X 1, і X 2 є підмножинами Y, то їх перетин, що позначається \(\cap\)X 1 X 2, також є підмножиною Y, а саме той, що містить всі елементи Y, які обидва знаходяться в X 1 і в Х 2, і ніяких інших. Отже, {1,2,3}\(\cap\) {2,5} = {2}.
Що робити, якщо нам потрібно об'єднати або перетинати багато підмножин? Наприклад, розглянемо множини X 0 = Ø, X 1 = {1}, X 2 = {1,2} і т.д. як підмножини N, і ми хочемо знати, що таке об'єднання всіх з них. Це об'єднання записано\(\cup\) \(\in\)n N X n, і це підмножина N, яка містить кожен елемент кожного X n, але немає інших. А саме,\(\cup\) \(\in\)n N X n = {n\(\in\) N | n ≥ 1}. Аналогічно можна записати\(\cap\) \(\in\)n N X n для перетину всіх з них, яке буде порожнім у наведеному вище випадку.
З урахуванням двох множин X і Y добуток X × Y X і Y є множиною пар (x, y), де x\(\in\) X і y\(\in\) Y.
Нарешті, ми можемо захотіти взяти неспільний союз двох наборів, навіть якщо вони мають спільні елементи. З огляду на дві множини X і Y, їх неспільне об'єднання X\(\sqcup\) Y - це сукупність пар виду (x, 1) або (y, 2), де x\(\in\) X і y\(\in\) Y.
Нехай A = {h, 1} і B = {1, 2, 3}.
- Є вісім підмножин B; випишіть їх.
- Візьміть будь-які дві непорожні підмножини B і випишіть їх об'єднання.
- У A × B є шість елементів; випишіть їх. ♦
- Є п'ять елементів A\(\cup\) B; випишіть їх.
- Якщо розглядати A і B як підмножини множини {h, 1, 2, 3}, існує чотири елементи A\(\cup\) B; випишіть їх.
Відносини між різними множинами, наприклад, між набором дерев у вашому районі та набором улюблених фруктів фіксуються за допомогою підмножин та наборів продуктів.
Нехай X і Y будуть множинами. Відношення між X і Y є підмножиною R\(\subseteq\) X × Y. Двійкове відношення на X - це відношення між X і X, тобто підмножина R\(\subseteq\) X × X.
Зручно використовувати те, що називається інфіксними позначеннями для двійкових відносин R\(\subseteq\) A × A.
Це означає, що один вибирає символ, скажімо ⋆, і пише a ⋆ b, щоб означати (a, b)\(\in\) R.
Існує двійкове відношення на R з інфіксним позначенням ≤. Замість того, щоб писати (5, 6)\(\in\) R, ми пишемо 5 ≤ 6. Іншими прикладами інфіксних позначень для відносин є =, ≈, <, >. У теорії чисел їх цікавить, чи ділиться одне число без залишку на інше число; це відношення позначається інфіксним позначенням |, так 5|10.
Перегородки та співвідношення еквівалентності. Тепер ми можемо визначити розділи більш формально.
Якщо A є множиною, розділ A складається з множини P і, для кожного p\(\in\) P, непорожнього підмножини A p\(\subseteq\) A, такий, що
(1,15)
Розділ ми можемо позначити {A p} p\(\in\) P. Ми посилаємось на P як набір міток деталей, і якщо\(\in\) p P є міткою частини, ми посилаємось на A p як\(^{th}\) частину p. Умова (1.15) говорить про те, що кожен елемент a A знаходиться рівно в одній частині. Ми вважаємо, що два різних розділи {\(\left\{A_{p}\right\}_{p \in P}\)\(\left\{A_{p^{\prime}}^{\prime}\right\}_{p^{\prime} \in P^{\prime}}\)} та {} з A однаковими, якщо для кожного\(\in\) p P існує p'\(\in\) P' з\(A_{p}\) =\(A'_{p'}\),. Іншими словами, якщо два способи поділу A на частини абсолютно однакові, єдина зміна є в мітках, то ми не робимо різниці між ними.
Припустимо, що A є множиною, а {\(A_{p}\)} \(\in\)p P і {\(\left\{A_{p^{\prime}}^{\prime}\right\}_{p^{\prime} \in P^{\prime}}\)} - це два розділи
Такий, що для кожного\(\in\) р Р існує p ′\(\in\) P 'з\(A_{p}\) =\(A′_{p′}\),.
- Покажіть, що для кожного\(\in\) р Р є щонайменше один р ′\(\in\) P ′ такий, що\(A_{p}\) =\(A′_{p′}\)
- Покажіть, що для кожного\(\in\) р ′ P ′ є p\(\in\) P такий, що\(A_{p}\) =\(A′_{p′}\),.
Розглянемо розділ, показаний нижче:
- Відповідь
-
Для будь-яких двох елементів a, b\(\in\) {11,12,13,21,22,23} давайте дозволимо собі написати символ twiddle a ↑ b між ними, якщо a і b обидва знаходяться в одній частині. Запишіть кожну пару елементів (a, b), які знаходяться в одній частині. Повинно бути 10.5 ♦
Ми побачимо в Пропозиції 1.19, що існує сильний зв'язок між розділами та чимось, що називається відносинами еквівалентності, які ми визначаємо далі.
Нехай A буде набором. Відношення еквівалентності на A є двійковим відношенням, давайте дамо йому інфіксне позначення, що задовольняє наступним трьом властивостям:
- a ↑ a, для всіх \(\in\)A,
- a b \(iff_{a}\)b ↑ a, для всіх a, b\(\in\) A, і
- якщо a b і b ↑ c то a c, для всіх a, b, c\(\in\) A.
Ці властивості називаються рефлексивністю, симетрією і перехідністю відповідно.
«Iff» - це скорочення від «якщо і тільки якщо».
Нехай A буде набором. Існує відповідність один до одного між способами поділу А і співвідношеннями еквівалентності на А.
Доказ. Спочатку ми показуємо, що кожен розділ породжує відношення еквівалентності, а потім, що кожне відношення еквівалентності породжує розділ. Наші дві конструкції будуть взаємно обернені, доводячи пропозицію.
Припустимо, що нам дано розділ {\(\left\{A_{p}\right\}_{p \in P}\)}; ми визначаємо відношення ↑ і показуємо, що це відношення еквівалентності. Визначте a b, щоб означати, що a і b знаходяться в одній частині: є деякі p\(\in\) P такі, що a\(\in\)\(A_{p}\) і b\(\in\)\(A_{q}\). Очевидно, що a знаходиться в тій же частині, що і сама. Так само очевидно, що якщо a знаходиться в тій же частині, що і b, то b знаходиться в тій же частині, що і a, і що якщо далі b знаходиться в тій же частині, що і c, то a знаходиться в тій же частині, що і c. Таким чином, - це відношення еквівалентності, визначене у Визначенні 1.18.
Припустимо, задано відношення еквівалентності; ми сформуємо розділ на A, сказавши, що це за частини. Скажімо, що підмножина X\(\subseteq\) A є () -закрита, якщо для кожного \(\in\)x X і x ′ ↑ x, у нас є х ′\(\in\) X. Скажімо, що підмножина X\(\subseteq\) A є () -з'єднана, якщо вона непорожня, і x y для кожного x, y\(\in\) X. Тоді частини, що відповідають, є саме (↑) -замкнутими, (↑) -з'єднаними підмножинами. Це не важко перевірити, що вони дійсно утворюють розділ. □
Давайте завершимо частину «це не важко перевірити» в доказ Пропозиції 1.19. Припустимо, що ↑ є співвідношенням еквівалентності на множині A, і нехай P буде множиною () -замкнутих і () -з'єднаних підмножин {\(\left\{A_{p}\right\}_{p \in P}\)}.
- Показати, що кожна частина\(A_{p}\) непорожня.
- Показати, що якщо p\(\neq\) q, тобто якщо\(A_{p}\) і\(A_{q}\) не зовсім однакові множини,\(A_{p}\) то\(A_{q}\) = Ø.
- Покажіть, що A =\(\cup\) p \(\in\)P\(A_{p}\). ♦
З огляду на множину A та відношення еквівалентності ↑ на A, скажемо, що частка A /від A під є множиною частин відповідного розділу.
Функції. Найбільш часто використовуваний вид відношення між множинами - це функції.
Нехай S і T будуть множинами. Функція від S до T - це підмножина F\(subseteq\) S × T така, що для всіх\(\in\) s S існує унікальна t\(\in\) T з (s, т)\(\in\) Ф.
Функція F часто позначається F: S → T. Відтепер ми пишемо F (s) = t, а іноді s → t, щоб означати (s, t)\(\in\) F. Для будь-якого t\(\in\) T попереднє зображення t уздовж F є підмножиною {s\(\in\) S | F (s) = t}.
Функція називається суб'єктивною, або сюрекцією, якщо для всіх t T існує \(\in\)s з F (s) = t. Функція називається ін'єкційної, або ін'єкційної,
якщо для всіх \(\in\)t і s 1, s 2\(\in\) S з F (s 1) = t і F (s 2) = t, ми маємо s 1 = s 2. Функція називається біективної, якщо вона одночасно і суб'єктивна, і ін'єкційна.
Використовуємо різні прикраси на стрілках,для позначення цих спеціальних видів функцій. Ось таблиця з назвою, прикрасою стрілок та прикладом кожної функції:
довільна функція, суб'єктивна функція, ін'єкційна функція, біективна функція
Важливим, але дуже простим видом функції є функція ідентичності на множині X, позначається id X. Це двооб'єктивна функція id X (x) = x.
Для узгодженості позначень з визначенням 1.22 стрілки у прикладі 1.23 можуть бути намальовані як →, а не ->. Стрілки в стилі —> були намальовані, тому що ми думали, що це гарніше, тобто легше на око. Краса теж важлива; незбалансована перевага суворої правильності над красою стає педантичністю. Але поза знімками ми будемо обережні.
У наступному не використовуйте жодних прикладів, вже намальованих вище.
- Знайдіть дві множини A та B та функцію f: A → B, яка є ін'єкційною, але не суб'єктивною.
- Знайдіть дві множини A та B та функцію f: A → B, яка є суб'єктивною, але не ін'єкційною.
Тепер розглянемо чотири відносини, показані тут:
або кожне відношення, відповісти на наступні два питання.
3. Це функція?
4. Якщо ні, то чому б і ні? Якщо так, то це ін'єкційний, суб'єктивний, обидва (тобто біктивний), чи ні? ♦
Припустимо, що A - множина, а f: A → Ø - функція для порожньої множини. Покажіть, що A порожній.
Розділ на множині А також можна розуміти з точки зору суб'єктивних функцій з А. За даними суб'єктивної функції f: A —» P, де P є будь-якою іншою множиною, преобрази f −1 (p)\(\subseteq\) A, по одному для кожного елемента\(\in\) p P, утворюють розділ A. Ось приклад.
Розглянемо розділ S: = {11, 12, 13, 21, 22, 23}, показаний нижче:
Він був розділений на чотири частини, тому нехай P = {a, b, c, d} і нехай f: S —» P буде дано
ф (11) = а, ф (12) = а, ф (13) = б, ф (21) = с, ф (22) = д, ф (23) = д
Запишіть відхилення, що відповідає кожному з п'яти розділів у еквалайзері (1.5) . ♦
Якщо F: X → Y є функцією, а G: Y → Z є функцією, їх складеною є функція X → Z, визначена як G (F (x)) для будь-якого x \(\in\)Х. Його часто позначають G ◦ F, але ми вважаємо за краще позначати його F; G. Він приймає будь-який елемент x\(\in\) X, оцінює F, щоб отримати елемент F (x)\(\in\) Y, а потім оцінює G, щоб отримати елемент G (F (x)).
Якщо X є будь-якою множиною, а \(\in\)x X є будь-яким елементом, ми можемо думати про x як функцію {1} → X, а саме функцію, яка надсилає 1 до x. Наприклад, наведені нижче три функції {1} → {1, 2, 3} відповідають трьом елементам {1, 2, 3}:
Припустимо, задано функцію F: X → Y та елемент X, який розглядається як функція x: {1} → X. Потім оцінка F при x задається композитом, F (x) = x; F.
Попередні замовлення
У розділі 1.1 ми кілька разів використовували символ ≤ для позначення свого роду порядку. Ось формальне визначення того, що означає для набору мати замовлення.
Відношення попереднього порядку на множині X - це двійкове відношення на X, тут позначається інфіксним позначенням ≤, таким чином, що
(а) х ≤ х; і
(b) якщо x ≤ y і y ≤ z, то x ≤ z.
Перша умова називається рефлексивністю, а друге - транзитивністю. Якщо x ≤ y і y ≤ x, ми запишемо x\(\cong\) y і скажемо x і y еквівалентні. Пару (X, ≤), що складається з множини, обладнаної співвідношенням попереднього порядку, попереднім порядком.
Зауваження 1.31. Зверніть увагу, що рефлексивність та транзитивність знайомі з Визначення 1.18: попередні замовлення - це просто співвідношення еквівалентності без умови симетрії.
Кожен набір X можна розглядати як дискретний попередній порядок (X, =). Це означає, що єдині відносини порядку на X мають вигляд x ≤ x; якщо x\(\neq\) y, то ні x ≤ y, ні y ≤ x не утримуються.
Ми зображуємо дискретні попередні замовлення як просто сукупність пунктів:
З кожного множини ми також можемо побудувати його кодискретний попередній порядок (X, ≤), оснастивши його загальним двійковим співвідношенням X ×\(\subseteq\) X X × X. Це дуже тривіальна структура: це означає, що для всіх x і y в X ми маємо x ≤ y (а отже, і y ≤ x).
Булеві значення\(\mathbb{B}\) = {false, true} утворюють попередній порядок з false ≤ true.
Зауваження 1.35 (Часткові замовлення - це скелетні попередні замовлення). Попереднє замовлення - це часткове замовлення, якщо ми додатково маємо це
(в) х\(\cong\) у має на увазі х = у.
У термінології теорії категорій вимога, що x\(\cong\) y передбачає x = y, відома як скелетність, тому часткові замовлення є скелетними попередніми замовленнями. Коротше кажучи, ми також використовуємо термін poset, скорочення частково впорядкованої множини.
Різниця між попередніми замовленнями і частковими замовленнями досить незначна. Частковий порядок вже є попереднім порядком, і кожне попереднє замовлення можна зробити в частковому порядку, прирівнюючи будь-які два елементи x, y, для яких x ≤\(\cong\) y, тобто для яких x ≤ y та y ≤ x.
Наприклад, будь-який дискретний попередній порядок вже є частковим порядком, тоді як будь-який кодискретний попередній порядок просто стає унікальним частковим порядком на одному наборі елементів.
Ми вже представили кілька прикладів попередніх замовлень за допомогою діаграм Хассе. Буде зручно продовжувати це робити, тому давайте трохи формальніше про те, що ми маємо на увазі. Для початку нам потрібно визначити графік.
Граф G = (V, A, s, t) складається з множини V, елементи якої називаються вершинами, множини A, елементи якого називаються стрілками, і двох функцій s,
t: A → V відомий як функції джерела та цілі відповідно. Задано \(\in\)A з s (a) = v і t (a) = w, скажемо, що a - стрілка від v до w.
Під контуром в G ми маємо на увазі будь-яку послідовність стрілок таким чином, що мета однієї стрілки є джерелом наступної. Сюди входять послідовності довжини 1, які є просто стрілками \(\in\)a в G, і послідовності довжиною 0, які тільки починаються і закінчуються в одній вершині v, не обходячи жодної стрілки.
Ось картинка графіка:
Він має V = {1, 2, 3, 4} і A = {a, b, c, d, e}. Функції джерела та цілі, s, t: A → V задаються наступними частково заповненими таблицями (див. Вправа 1.38):
Існує один шлях від 2 до 3, а саме стрілка е - шлях довжиною 1. Немає шляхів від 4 до 3, але є один шлях від 4 до 4, а саме шлях довжиною 0. Існує нескінченно багато шляхів 1 → 2, тому що один може циклічно і цикл і цикл через d стільки разів, скільки заманеться.
Заповніть таблицю з Прикладу 1.37. ♦
Зауваження 1.39. З кожного графіка ми можемо отримати попереднє замовлення. Дійсно, діаграма Хассе - це граф G = (V, A, s, t), який дає уявлення про попередній порядок (P, ≤). Елементи P є вершинами V у G, а порядок ≤ задається v ≤ w, якщо є шлях v → w. Для будь-якої вершини v завжди існує шлях v → v, і це перекладається на закон рефлексивності з Визначення 1.30. Той факт, що шляхи u → v і v → w можуть бути об'єднані до шляху u → w, перекладається на закон перехідності.
Яке відношення попереднього порядку (P, ≤) зображено графом G у прикладі 1.37? Тобто, які є елементи P і запишіть кожну пару (p 1, p 2) для якої p 1 ≤ p 2. ♦
Чи зараховується колекція балів, як у прикладі 1.32, як діаграма Хассе? ♦
Нехай X - це множина розділів {•, ◦, ∗}; він має п'ять елементів і порядок за грубістю, як показано на діаграмі Хассе Eq. (1.5). Запишіть кожну пару (x, y) елементів у X таким чином, що x ≤ y. Їх повинно бути 12. ♦
Зауваження 1.43. У зауваження 1.35 ми обговорювали часткові замовлення попередніх замовлень із властивістю, що коли два елементи еквівалентні, вони однакові, а потім сказали, що ця властивість є досить несуттєвою: будь-який попередній порядок може бути перетворений у частковий порядок, який є «еквівалентною» категорії-теоретично. Частковий порядок схожий на попередній порядок з химерною стрижкою: деякі математики можуть навіть не помітити цього.
Однак є й інші типи попередніх замовлень, які є більш особливими і помітними. Наприклад, загальне замовлення має наступне додаткове властивість:
(d) для всіх x, y, або x ≤ y, або y ≤ x.
Ми говоримо, що два елементи x, y попереднього порядку можна порівняти, якщо або x ≤ y або y ≤ x, тому загальний порядок є попереднім порядком, де кожні два елементи можна порівняти.
Чи правильно сказати, що дискретний попередній порядок - це той, де не можна порівняти два елементи?
Натуральні числа\(\mathbb{N}\) := {0, 1, 2, 3,.} є попереднім порядком з порядком, заданим звичайним порядком розмірів, наприклад 0 ≤ 1 і 5 ≤ 100. Це загальний порядок: або m ≤ n, або n ≤ m для всіх m, n. Видно, що його діаграма Хассе виглядає як лінія:
Що зробило Eq. (1.5) не схожим на рядок, полягає в тому, що існують незрівнянні елементи a та b, а саме всі ті, що знаходяться в середньому рядку. які не задовольняють ні a ≤ b, ні b ≤ a.
Зверніть увагу, що для будь-якого набору S існує безліч різних способів присвоєння замовлення S. Дійсно, для множини N ми також могли б використовувати дискретне впорядкування: записувати тільки n ≤ m, якщо n = m. Іншим порядком є зворотне впорядкування, як 5 ≤ 3 та 3 ≤ 2, наприклад, як гольф забивається (5 гірше, ніж 3).
Ще одне впорядкування\(\mathbb{N}\) задається діленням: ми говоримо, що n ≤ m, якщо n ділиться на m без залишку. У такому порядку 2 ≤ 4, наприклад, але 2\(\neq\) 3, так як є залишок, коли 2 ділиться на 3.
Запишіть числа 1,2,... ,10 і намалюйте стрілку a → b, якщо a ідеально ділиться на b. Це загальне замовлення? ♦
Справжні числа\(\mathbb{R}\) також утворюють попередній порядок із «звичайним впорядкуванням», наприклад −500 ≤ −499 ≤ 0 ≤ √2 ≤ 100/3.
Чи є звичайне ≤ впорядкування на множині\(\mathbb{R}\) дійсних чисел загальним порядком? ♦
За попереднім порядком, тобто попередньо впорядкованим множиною (P, ≤), ми визначили поняття еквівалентності елементів, що позначаються x\(\cong \) y, що означає x ≤ y та y ≤ x. Це відношення еквівалентності, тому воно індукує розділ на P. (Фраза «A індукує B» означає, що у нас є автоматичний спосіб перетворити A на B. У цьому випадку ми говоримо, що у нас є автоматичний спосіб перетворити відносини еквівалентності на розділи, що ми робимо; див. Пропозиція 1.19.)
Наприклад, попередній порядок, діаграма Хассе якого намальована зліва, відповідає розділу, намальованому праворуч.
З огляду на множину X, множина підмножин X відома як множина потужності X; ми позначаємо його P (X). Набір потужності, природно, може бути надано порядок шляхом включення підмножин (і відтепер, коли ми говоримо про набір потужності як впорядкований набір, це порядок, який ми маємо на увазі).
Наприклад, взявши X = {0, 1, 2}, зображуємо P (X) як
Бачите куб? Діаграма Хассе для множини степеней скінченної множини, скажімо P {1, 2,., n},\(^{a}\) завжди виглядає як куб розмірності n.
\(^{a}\)Зверніть увагу, що ми опускаємо дужки тут, пишемо P X замість P (X); протягом усієї цієї книги ми опустимо дужки, якщо судити, що презентація чистіша, і це навряд чи спричинить плутанину.
Намалюйте діаграми Хассе для P (Ø), P {1} та P {1, 2} . ♦
Ми говорили про отримання розділу з попереднього замовлення; тепер давайте подумаємо про те, як ми могли б замовити набір Prt (A) всіх розділів A, для деяких набір A. Насправді ми робили це раніше в еквалайзері (1.5). А саме, ми впорядковуємо на розділах по тонкості: розділ P тонше, ніж розділ Q if, для кожної частини\(\in\) p P є частина q ↑ Q така, що Ap \(\subseteq\)A q. Можна також сказати, що Q грубіше, ніж P.
Нагадаємо з Прикладу 1.26, що розділи на A можна розглядати як суб'єктивні функції з A. Тоді f: A —» P тонше g: A —» Q, якщо є функція h: P → Q така, що f; h = g.
Для будь-якого набору S є найгрубіша перегородка, що має всього одну частину. Якій суб'єктивній функції вона відповідає? Є і найтонша перегородка, де все знаходиться у власній перегородці. Якій суб'єктивній функції вона відповідає? ♦
За попереднім порядком (P, ≤), верхня множина в P є підмножиною U P, що задовольняє умову, що якщо p\(\in\) U та p ≤ q, то q\(\in\) U. «Якщо р є елементом, то так щось більше.» Запишіть U (P) для множини верхніх множин в P. Ми можемо дати множині U порядок, дозволивши U ≤ V, якщо U міститься в V.
Наприклад, якщо (\(\mathbb{B}\), ≤) є логічним значенням (приклад 1.34), то його попередній порядок верхніх множин\(\cup\) (\(\mathbb{B}\)) дорівнює
Підмножина {false} не\(\subseteq\)\(\mathbb{B}\) є верхньою множиною, тому що false ≤ true і true\(\not in\) {false}.
Доведіть, що попередній порядок верхніх множин на дискретному попередньому порядку (див. Приклад 1.32) на множині X просто потужність набір P (X) . ♦
За даними попередніх замовлень (P, ≤) та (Q, ≤), ми можемо визначити структуру попереднього замовлення на множині продукту P × Q шляхом встановлення (p, q) ≤ (p ′, q ′) тоді і лише тоді, коли p ≤ p та q ≤ q ′. Ми називаємо це попереднім замовленням товару. Це основний приклад більш загальної конструкції, відомої як твір категорій.
Намалюйте діаграму Хассе для добутку двох попередніх замовлень, намальованих нижче:
-
Для отримання бонусних балів обчислити верхній встановлений попередній порядок на результат. ♦
Задавши попередній порядок (P, ≤), ми можемо визначити протилежний попередній порядок (P, ≤\(^{op}\)), щоб мати однаковий набір елементів, але з (p ≤\(^{op}\)) q if і тільки якщо q ≤ p.
Монотонні карти
Ми говорили, що категорична перспектива підкреслює відносини між речами. Наприклад, попередній порядок - це налаштування або світ, в якому ми маємо один вид відносин, ≤, і будь-які два об'єкти можуть бути або не бути такими пов'язаними. Підстрибуючи рівень, категорична перспектива підкреслює, що попередні замовлення кожного мініатюрного світу, що складається з багатьох відносин, можуть бути пов'язані один з одним.
Найважливіший вид взаємозв'язку між попередніми замовленнями називається монотонна карта. Це функції, які зберігають відносини попереднього порядку в певному сенсі відображення, які поважають ≤ і, отже, вважаються правильним поняттям структури збереження карти для попередніх замовлень.
Монотонна карта між попередніми замовленнями (A, ≤ A) та (B, ≤ B) є функцією f: A → B такою, що для всіх елементів x, y\(\in\) A, якщо x ≤ A y потім f (x) ≤ B f (y).
Монотонна карта A → B між двома попередніми порядками пов'язує з кожним елементом попереднього порядку A елемент попереднього порядку B. Ми зображуємо це, намалювавши пунктирну стрілку від кожного елемента x\(\in\) A до його зображення f (x)\(\in\) B. Зауважте, що порядок повинен бути збережений для того, щоб вважати дійсною монотонною мапою, тому якщо елемент x знаходиться над елементом y в лівому попередньому порядку A, то зображення f (x) буде вище зображення f (y) у праворуч передзамовлення.
\(\mathbb{B}\)\(\mathbb{N}\)Дозволяти і бути попередні замовлення булевих з Прикладу 1.34 і N попередній порядок натуральних чисел з Прикладу 1.45. Карта\(\mathbb{B}\) →\(\mathbb{N}\) надсилання false до 17 та true до 24 є монотонною картою, оскільки вона зберігає порядок.
Розглянемо набір усіх класифікацій тварин, наприклад «тигр», «ссавець», «сапієнс», «хижак» тощо. Вони впорядковані за специфікою: оскільки «тигр» - це тип «ссавців», ми пишемо тигр ≤ ссавець. В результаті виходить попередній порядок, який фактично утворює дерево, яке часто називають деревом життя. У верхній частині наступної схеми ми бачимо невелику її частину:
Внизу ми бачимо ієрархічну структуру як попередній порядок. Пунктирними стрілками відображається монотонна карта, назвемо її F, від класифікацій до ієрархії. Він монотонний, оскільки зберігає порядок: всякий раз, коли нагорі є шлях x → y, внизу є шлях F (x) → F (y).
З огляду на скінченну множину X, згадайте множину потужності P (X) та її співвідношення природного порядку з Прикладу 1.50. Карта |·|: P (X) →\(\mathbb{N}\) надсилання кожної підмножини S до кількості елементів | S |, яку також називають її кардинальністю, є монотонною картою.
Нехай X = {0, 1, 2}.
- Намалюйте діаграму Хассе для P (X).
- Намалюйте діаграму Хассе для попереднього порядку 0 ≤ 1 ≤ 2 ≤ 3.
- Намалюйте карту кардинальності |·| з Прикладу 1.62 у вигляді пунктирних ліній між ними. ♦
Згадаймо поняття верхньої множини з Прикладу 1.54. За попереднім порядком (P, ≤) карта U (P) → P (P), що надсилає кожну верхню множину (P, ≤) до себе — вважається підмножиною P, є монотонною картою.
Розглянемо попередній порядок B. Діаграма Хассе для U (\(\mathbb{B}\)) була намальована в прикладі 1.54, і ви намалювали діаграму Хассе для P (\(\mathbb{B}\)) у вправі 1.51. Тепер намалюйте монотонну карту між ними, як описано в прикладі 1.64.
Нехай (P, ≤) є попереднім порядком, і згадати поняття протилежного попереднього порядку з Прикладу 1.58.
- Показати, що множина ↑ p: = {p ′\(\in\) P | p ≤ p ′} є верхньою множиною, для будь-якого p\(\in\) P.
- Показати, що ця конструкція визначає монотонну карту ↑: P\(^{op}\) → U (P).
- Показати, що якщо p ≤ p ′ в P, якщо і тільки якщо ↑ (p ′)\(\subseteq\) ↑ (p) ↑ (p).
- Намалюйте малюнок карти ↑ у випадку, коли P - попередній порядок (b ≥ a ≤ c) з Прикладу 1.56.
Це відоме як лема Yoneda для попередніх замовлень. Якщо і тільки якщо умова, доведена в частині 3, означає, що до еквівалентності знати елемент - це те саме, що знати його верхній набір - тобто знання його павутини відносин з іншими елементами попереднього порядку. Загальна лема Yoneda є потужним інструментом в теорії категорій, і захоплююча філософська ідея, крім того. ♦
Як ви самі добре знаєте, монотонна карта f: (P, ≤ P) → (Q, ≤ Q) складається з функції f: P → Q, яка задовольняє властивість «монотонності». Показати, що коли (P, ≤ P) є дискретним передпорядком, то кожна функція P → Q задовольняє властивість монотонності незалежно від порядку ≤ Q
Нагадаємо, з прикладу 1.52, що за допомогою множини X ми визначаємо Prt (X) як набір розділів на X, і що розділ може бути визначено за допомогою суб'єктивної функції s: X —» P для деякого набору P. Будь-яка суб'єктивна функція f: X —» Y індукує монотонну карту\(^{*}\): Частина (Y) → Частина (X), рухаючись «назад». Він визначається шляхом надсилання розділу s: Y —» P до складеного f; s: X —» P. \(^{7}\)
Виберіть два множини X і Y з щонайменше трьома елементами кожен і виберіть суб'єктивну, неідентичну функцію f: X —» Y між ними. Запишіть два різних розділи P і Q з Y, а потім знайдіть f\(^{*}\) (P) і f\(^{*}\) (Q) . ♦
Наступна пропозиція, Пропозиція 1.70, є простою для перевірки. Згадаймо визначення функції ідентичності з прикладу 1.23 і визначення композиції з Визначення 1.28.
Для будь-якого попереднього порядку (P, ≤ P) функція ідентичності є монотонною. Якщо (Q, ≤ Q) і (R, ≤ R) є попередніми порядками, а f: P → Q і g: Q → R монотонні, то (f; g): P → R також монотонний.
Перевірте дві претензії, зроблені в Пропозиції 1.70. ♦
Згадаймо ще раз визначення протилежного попереднього порядку з Прикладу 1.58. Ідентифікаційна функція id P: P → P - монотонна карта (P, ≤) → (P, ≤\(^{op}\)) тоді і тільки тоді, коли для всіх p, q\(\in\) P ми маємо q ≤ p щоразу, коли p ≤ q. З історичних причин, пов'язаних з лінійною алгеброю, коли це вірно, ми називаємо (P, ≤) попереднім порядком кинджала.
Але насправді ми бачили попередні замовлення кинджала раніше в іншому образі. Дійсно, якщо (P, ≤) є кинджальним попереднім порядком, то відношення ≤ симетричне: p ≤ q якщо і тільки якщо q ≤ p, і воно також є рефлексивним і перехідним за визначенням попереднього порядку. Так насправді ≤ це відношення еквівалентності (Визначення 1.18).
Згадаймо поняття скелетних попередніх замовлень (Зауваження 1.35) і дискретних попередніх замовлень (приклад 1.32). Покажіть, що попередній порядок скелетного кинджала - це лише дискретний попередній порядок, і, отже, може бути ідентифікований набором. ♦
Зауваження 1.74. Ми говоримо, що A «можна ідентифікувати з» a B, коли будь-який A дає нам унікальний B, а будь-який B дає нам унікальний A, і обидва обидва подорожі від A до B і назад до A, або з a B до A і назад до B повернути нас, де ми почали. Наприклад, будь-який дискретний передпорядок (P, ≤) має базову множину P, а будь-яка множина P може бути перетворена в дискретний попередній порядок (p 1 ≤ p 2 iff p 1 = p 2), і зворотні поїздки повертають нас з того місця, де ми почали. Так в чому різниця? Це як поняття предметної постійності з жаргону розвитку дитини: ми можемо розпізнати «той самий стілець, тільки що переміщений з однієї кімнати в іншу». Стілець в кімнаті комплектів можна перенести на стілець в кімнату попередніх замовлень. Освітлення різне, але стілець однаковий.
Зрештою, ми зможемо зрозуміти це поняття з точки зору еквівалентності категорій, які пов'язані з ізоморфізмами, які ми розглянемо далі у Визначенні 1.75.
Нехай (P, ≤ P) і (Q, ≤ Q) є попередніми замовленнями. Монотонна функція f: P → Q називається ізоморфізмом, якщо існує монотонна функція g: Q → P така, що f; g\(id_{P}\) і g; f \(id_{Q}\). Це означає, що для будь-яких\(\in\) p P і q\(\in\) Q у нас є p = g (f (p)) і q = f (g (q)). Ми називаємо g зворотним f, і навпаки: f - обернене g. Якщо є ізоморфізм P → Q, ми говоримо, що P і Q ізоморфні.
Ізоморфізм між попередніми замовленнями - це в основному лише мітка елементів.
Ось діаграми Хассе для трьох попередніх порядків P, Q і R, всі з яких є ізоморфними:
Карта f: P → Q задана f (a) = v, f (b) = w, f (c) = x, f (d) = y, і f ( e) = z має зворотну.
Насправді Q і R - це один і той же попередній порядок. Одного може збентежити той факт, що в діаграмі Хассе для R є стрілка x → z, а не одна в Q, але насправді ця стрілка зайва. За властивістю перехідності попередніх замовлень (визначення 1.30), оскільки x ≤ y та y ≤ z, ми повинні мати x ≤ z, незалежно від того, намальовано воно чи ні. Аналогічно, ми могли б намалювати стрілку v → у або Q або R, і це не змінило б попередній порядок.
Згадати попередній порядок\(\mathbb{B}\) = {false, true}, де false ≤ true. Настільки ж простий, як це попереднє замовлення, він також є одним з найважливіших.
Покажіть, що карта Φ з Розділу 1.1.1, яка була приблизно дана «Чи підключено • до ∗?» є монотонною картою Prt ({∗, •, ◦}) → B; див. також Eq. (1.5) . ♦
Нехай P буде попереднім замовленням. Монотонні карти Р →\(\mathbb{B}\) знаходяться в однозначній відповідності з верхніми множинами P.
Доказ. Ліворуч f: P → B — монотонна карта. Ми покажемо, що підмножина f\(^{-1}\) (true)\(\subseteq\) P - це верхня множина. Припустимо, p\(\in\) f\(^{-1}\) (true) і p ≤ q; тоді істинно = f (p) ≤ f (q). Але в B, якщо істинно ≤ f (q), то true = f (q). Це означає q\(\in\) f\(^{-1}\) (true) і таким чином показує, що f\(^{-1}\) (true) є верхньою множиною. І навпаки, якщо U є верхньою множиною в P, визначте f U: P → B таким чином, що f U (p) = true, коли p\(\in\) U, і f U (p) = помилковий, коли р\(\not in\) U.
Це монотонна карта, тому що якщо p ≤ q, то або p\(\in\) U, так q\(\in\) U і f (p) = true = f (q), або p\(\not in\) U, так f (p) = брехня ≤ f (q).
Ці дві конструкції взаємно обернені, і, отже, доводять судження.
Нехай P і Q будуть попередніми порядками, а f: P → Q — монотонною картою. Тоді ми можемо визначити монотонну карту f\(^{*}\): U (Q) → U (P), відправляючи верхній набір U\(\subseteq\) Q до верхнього набору f\(^{-1}\) (U)\(\subseteq\) P. Ми називаємо це відкат уздовж f. Переглядаючи верхні набори як монотонні карти,\(\mathbb{B}\) як у Пропозиції 1.78, відкат можна зрозуміти з точки зору композиції. Дійсно, показати, що f\(^{*}\) визначається прийняттям u: Q →\(\mathbb{B}\) to (f; u): P → B ♦