2.1: Відносини як множини

Template:MathJaxZach

У розділі 1.3 ми згадали деякі важливі набори:\(\Nat\),\(\Int\),\(\Rat\),\(\Real\). Ви без сумніву запам'ятаєте деякі цікаві відносини між елементами деяких з цих наборів. Наприклад, кожен з цих наборів має повністю стандартне відношення порядку на ньому. Існує також відношення ідентичне тому, що кожен предмет несе собі і ні до чого іншого. Є ще багато цікавих відносин, з якими ми зіткнемося, і навіть більше можливих відносин. Перш ніж ми розглянемо їх, однак, ми почнемо з того, що ми можемо розглядати відносини як особливий вид набору.

Для цього згадайте дві речі з розділу 1.5. Для початку згадаємо поняття впорядкованої пари: дано\(a\) і\(b\), ми можемо сформувати\(\tuple{a, b}\). Важливо, що порядок елементів тут має значення. Так що якщо\(a \neq b\) тоді\(\tuple{a, b} \neq \tuple{b, a}\). (Контрастуйте це з невпорядкованими парами, тобто,\(2\) -element sets, де\(\{a, b\}=\{b, a\}\).) По-друге, нагадаємо поняття декартового добутку: якщо\(A\) і\(B\) є множинами, то ми можемо сформувати\(A \times B\), множину всіх пар\(\tuple{x, y}\) з\(x \in A\) і\(y \in B\). Зокрема,\(A^{2}= A \times A\) це набір всіх впорядкованих пар з\(A\).

Зараз ми розглянемо конкретне відношення на множині:\(<\) -відношення на множині\(\Nat\) натуральних чисел. Розглянемо множину всіх пар чисел\(\tuple{n, m}\) де\(n<m\), тобто\[R=\Setabs{\tuple{n, m}}{n, m \in \Nat \text{ and } n<m}.\nonumber\] існує тісний зв'язок між\(n\) тим\(m\), що менше, і пара\(\tuple{n, m}\) є членом\(R\) , а саме:\[n<m\text{ iff }\tuple{n, m} \in R.\nonumber\] Дійсно, без будь-якої втрати інформації, ми можемо вважати\(R\) множиною\(<\) -відношення на\(\Nat\).

Таким же чином ми можемо побудувати підмножину\(\Nat^{2}\) для будь-якого відношення між числами. І навпаки, при будь-якому наборі пар чисел\(S \subseteq \Nat^{2}\) існує відповідне відношення між числами, а саме відношення\(n\) несе\(m\) якщо і тільки якщо\(\tuple{n, m} \in S\). Це виправдовує наступне визначення:

Визначення\(\PageIndex{1}\): Binary relation

Двійкове відношення на множині\(A\) є підмножиною\(A^{2}\). Якщо\(R \subseteq A^{2}\) це двійкове відношення на\(A\) і\(x, y \in A\), ми іноді пишемо\(Rxy\) (або\(xRy\)) для\(\tuple{x, y} \in R\).

Приклад\(\PageIndex{1}\)

\(\Nat^{2}\)Безліч пар натуральних чисел можна перерахувати в 2-мірну матрицю так:\[\begin{array}{ccccc} \mathbf{\tuple{ 0,0 }} & \tuple{ 0,1 } & \tuple{ 0,2 } & \tuple{ 0,3 } & \ldots\\ \tuple{ 1,0 } & \mathbf{\tuple{ 1,1 }} & \tuple{ 1,2 } & \tuple{ 1,3 } & \ldots\\ \tuple{ 2,0 } & \tuple{ 2,1 } & \mathbf{\tuple{ 2,2 }} & \tuple{ 2,3 } & \ldots\\ \tuple{ 3,0 } & \tuple{ 3,1 } & \tuple{ 3,2 } & \mathbf{\tuple{ 3,3 }} & \ldots\\ \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots} \end{array}\nonumber\] Ми поставили діагональ, тут, жирним шрифтом, так як підмножина\(\Nat^2\) складається з пар, що лежать на діагоналі,\[\{\tuple{0,0 }, \tuple{ 1,1 }, \tuple{ 2,2 }, \dots\},\nonumber\] т. Е. відношення ідентичності на\(\Nat\). (Оскільки відношення ідентичності є популярним, давайте визначимо\(\Id{A}=\Setabs{\tuple{ x,x }}{x \in X}\) для будь-якого набору\(A\).) Підмножина всіх пар, що лежать над діагоналлю,\[L = \{\tuple{ 0,1 },\tuple{ 0,2 },\ldots,\tuple{ 1,2 }, \tuple{ 1,3 }, \dots, \tuple{ 2,3 }, \tuple{ 2,4 },\ldots\},\nonumber\] тобто є меншим, ніж відношення, тобто\(Lnm\) iff\(n<m\). Підмножина пар нижче діагоналі,\[G=\{ \tuple{ 1,0 },\tuple{ 2,0 },\tuple{ 2,1 }, \tuple{ 3,0 },\tuple{ 3,1 },\tuple{ 3,2 }, \dots\},\nonumber\] тобто відношення більше ніж, тобто\(Gnm\) iff\(n>m\). \(L\)Союз з\(I\), який ми могли б назвати\(K=L\cup I\), є меншим, ніж або дорівнює відношення:\(Knm\) iff\(n \le m\). \(H=G \cup I\)Аналогічно, це більше або дорівнює відношенню. Ці відносини\(L\),\(G\)\(K\), і\(H\) є особливими видами відносин, які називаються орденами. \(L\)і\(G\) мати властивість, яку жоден номер не несе\(L\) або\(G\) собі (тобто для всіх\(n\), ні\(Lnn\) ні\(Gnn\)). Відносини з цією властивістю називаються іррефлексивними, і, якщо вони теж трапляються накази, то їх називають суворими розпорядженнями.

Хоча порядки та ідентичність є важливими та природними відносинами, слід підкреслити, що згідно з нашим визначенням будь-яка підмножина\(A^{2}\) - це відношення\(A\), незалежно від того, наскільки це неприродним чи надуманим здається. Зокрема,\(\emptyset\) це відношення на будь-якому множині (порожнє відношення, яке не несе жодна пара елементів), а\(A^{2}\) саме відношення\(A\) також (яке несе кожна пара), називається універсальним відношенням. Але також щось на\(E=\Setabs{\tuple{n, m}}{n>5 \text{ or } m \times n \ge 34}\) кшталт вважається відношенням.

Проблема\(\PageIndex{1}\)

Перерахуйте елементи відношення\(\subseteq\) на множині\(\Pow{\{a, b, c\}}\).