離散數學 - 關係

每當討論集合時，集合元素之間的關係就是接下來要討論的內容。**關係**可能存在於同一集合的物件之間，或者存在於兩個或多個集合的物件之間。

定義和性質

從集合 x 到集合 y 的二元關係 R（寫成 $xRy$ 或 $R(x,y)$）是笛卡爾積 $x \times y$ 的一個子集。如果 G 的有序對反轉，關係也會發生變化。

通常，集合 $A_1, \dots ,\ and\ A_n$ 之間的 n 元關係 R 是 n 元積 $A_1 \times \dots \times A_n$ 的一個子集。在這種情況下，關係 R 的最小基數為零，最大基數為 $n^2$。

單個集合 A 上的二元關係 R 是 $A \times A$ 的一個子集。

對於兩個不同的集合 A 和 B，分別具有基數 m 和 n，從 A 到 B 的關係 R 的最大基數為 mn。

域和範圍

如果有兩個集合 A 和 B，並且關係 R 有序對 (x, y)，則 -

• R 的**域** Dom(R) 是集合 $\lbrace x \:| \: (x, y) \in R \:for\: some\: y\: in\: B \rbrace$

• R 的**範圍** Ran(R) 是集合 $\lbrace y\: |\: (x, y) \in R \:for\: some\: x\: in\: A\rbrace$

示例

令，$A = \lbrace 1, 2, 9 \rbrace $ 和 $ B = \lbrace 1, 3, 7 \rbrace$

• 情況 1 - 如果關係 R 是“等於”，則 $R = \lbrace (1, 1), (3, 3) \rbrace$

  Dom(R) = $\lbrace 1, 3 \rbrace , Ran(R) = \lbrace 1, 3 \rbrace$

• 情況 2 - 如果關係 R 是“小於”，則 $R = \lbrace (1, 3), (1, 7), (2, 3), (2, 7) \rbrace$

  Dom(R) = $\lbrace 1, 2 \rbrace , Ran(R) = \lbrace 3, 7 \rbrace$

• 情況 3 - 如果關係 R 是“大於”，則 $R = \lbrace (2, 1), (9, 1), (9, 3), (9, 7) \rbrace$

  Dom(R) = $\lbrace 2, 9 \rbrace , Ran(R) = \lbrace 1, 3, 7 \rbrace$

使用圖表示關係

關係可以使用有向圖來表示。

圖中頂點的數量等於定義關係的集合中元素的數量。對於關係 R 中的每個有序對 (x, y)，從頂點“x”到頂點“y”將有一條有向邊。如果存在有序對 (x, x)，則頂點“x”上將有一個自環。

假設，在集合 $S = \lbrace 1, 2, 3 \rbrace$ 上存在一個關係 $R = \lbrace (1, 1), (1,2), (3, 2) \rbrace$，它可以用下圖表示 -

關係的型別

• 集合 X 和 Y 之間或集合 E 上的**空關係**是空集 $\emptyset$

• 集合 X 和 Y 之間的**全關係**是集合 $X \times Y$

• 集合 X 上的**恆等關係**是集合 $\lbrace (x, x) | x \in X \rbrace$

• 關係 R 的逆關係 R' 定義為 - $R' = \lbrace (b, a) | (a, b) \in R \rbrace$

  **示例** - 如果 $R = \lbrace (1, 2), (2, 3) \rbrace$，則 $R'$ 將是 $\lbrace (2, 1), (3, 2) \rbrace$

• 如果 $\forall a \in A$ 與 a 相關（aRa 成立），則稱集合 A 上的關係 R 為**自反**的。

  **示例** - 集合 $X = \lbrace a, b \rbrace$ 上的關係 $R = \lbrace (a, a), (b, b) \rbrace$ 是自反的。

• 如果不存在 $a \in A$ 與 a 相關（aRa 不成立），則稱集合 A 上的關係 R 為**反自反**的。

  **示例** - 集合 $X = \lbrace a, b \rbrace$ 上的關係 $R = \lbrace (a, b), (b, a) \rbrace$ 是反自反的。

• 如果 $xRy$ 意味著 $yRx$，$\forall x \in A$ 和 $\forall y \in A$，則稱集合 A 上的關係 R 為**對稱**的。

  **示例** - 集合 $A = \lbrace 1, 2, 3 \rbrace$ 上的關係 $R = \lbrace (1, 2), (2, 1), (3, 2), (2, 3) \rbrace$ 是對稱的。

• 如果 $xRy$ 和 $yRx$ 意味著 $x = y \: \forall x \in A$ 和 $\forall y \in A$，則稱集合 A 上的關係 R 為**反對稱**的。

  **示例** - 關係 $R = \lbrace (x, y)\to N |\:x \leq y \rbrace$ 是反對稱的，因為 $x \leq y$ 和 $y \leq x$ 意味著 $x = y$。

• 如果 $xRy$ 和 $yRz$ 意味著 $xRz, \forall x,y,z \in A$，則稱集合 A 上的關係 R 為**傳遞**的。

  **示例** - 集合 $A = \lbrace 1, 2, 3 \rbrace$ 上的關係 $R = \lbrace (1, 2), (2, 3), (1, 3) \rbrace$ 是傳遞的。

• 如果關係是自反的、對稱的和傳遞的，則它是**等價關係**。

  **示例** - 集合 $A = \lbrace 1, 2, 3 \rbrace$ 上的關係 $R = \lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \rbrace$ 是等價關係，因為它自反、對稱和傳遞。