2.7: Операції по відносинам

Last updated
Save as PDF

Page ID: 53178

\( \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}}\)

Template:MathJaxZach

Часто корисно змінювати або комбінувати відносини. У Пропозиції 2.5.1 ми розглянули союз відносин, який є всього лише об'єднанням двох відносин, що розглядаються як множини пар. Аналогічно в Пропозиції 2.5.2 ми розглянули відносну різницю відносин. Ось деякі інші операції, які ми можемо виконати над відносинами.

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

Нехай\(R\),\(S\) будуть відносини, і\(A\) бути будь-який набір.

\(R\)Зворотне є\(R^{-1} = \Setabs{\tuple{y, x}}{\tuple{x, y} \in R}\).

Відносний добуток\(R\) і\(S\) є\((R \mid S) = \{\tuple{x, z} : \exists y(Rxy \land Syz)\}\).

Обмеження\(R\) до\(A\) є\(\funrestrictionto{R}{A}= R \cap A^2\).

Застосування\(R\) до\(A\) є\(\funimage{R}{A} = \{y : (\exists x \in A)Rxy\}\)

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

\(S \subseteq \Int^2\)Дозволяти бути спадкоємцем відносини на\(\Int\)\(S = \Setabs{\tuple{x, y} \in \Int^2}{x + 1 = y}\), тобто, так що\(Sxy\) iff\(x + 1 = y\).

\(S^{-1}\)є попередником відношення на\(\Int\), тобто,\(\Setabs{\tuple{x,y}\in\Int^2}{x -1 =y}\).

\(S\mid S\)є\(\Setabs{\tuple{x,y}\in\Int^2}{x + 2 =y}\)

\(\funrestrictionto{S}{\Nat}\)є спадкоємцем відносини на\(\Nat\).

\(\funimage{S}{\{1,2,3\}}\)є\(\{2, 3, 4\}\).

Визначення\(\PageIndex{2}\): Transitive closure

\(R \subseteq A^2\)Дозволяти двійкове відношення.

Перехідне закриття\(R\) є\(R^+ = \bigcup_{0 < n \in \Nat} R^n\), де ми рекурсивно визначаємо\(R^1 = R\) і\(R^{n+1} = R^n \mid R\).

Рефлекторне перехідне закриття\(R\) є\(R^* = R^+ \cup \Id{X}\).

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

Візьміть відносини спадкоємця\(S \subseteq \Int^2\). \(S^2xy\)iff\(x + 2 = y\),\(S^3xy\) iff і\(x + 3 = y\) т.д. так що\(S^+xy\) iff\(x + n = y\) для деяких\(n > 1\). Іншими словами,\(S^+xy\) iff\(x < y\), і\(S^*xy\) iff\(x \le y\).

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

Показати, що перехідне закриття насправді\(R\) є перехідним.