離散數學/函式與關係

簡介

本文考察了函式和關係的概念。

關係 是一個集合元素之間的任何關聯或聯絡，這個集合被稱為定義域（非正式地稱為輸入集），另一個集合被稱為值域（或輸出集）。有些人錯誤地將值域稱為陪域，但正如我們將看到的，它實際上是指所有可能的輸出，即使是關係實際上未使用的值。（注意：一些作者不使用陪域一詞，而是使用值域來表示這個含義。這些作者使用像集 來表示我們稱為值域的含義。因此，將值域或像集稱為陪域是錯誤的，但將陪域稱為值域並不一定是錯誤的。）

例如，如果定義域是集合 Fruits = {蘋果，橙子，香蕉}，而陪域是集合 Flavors = {甜味，酸味，苦味}，那麼這些水果的味道構成了一個關係：我們可以說蘋果與兩種味道（甜味和酸味）相關聯，而橙子只與酸味相關聯，香蕉只與甜味相關聯。（我們可能略有不同意見，但這與本書主題無關。）注意，“苦味”雖然是 Flavors（陪域）中的一種可能味道，但實際上沒有用於這些關係中的任何一個；因此它不是值域（或像集）{甜味，酸味}的一部分。

從另一個角度來看，我們可以說關係是有序對的子集，這些有序對從所有可能的有序對集合（兩個其他集合的元素的有序對，我們通常稱之為這些集合的笛卡爾積）中提取出來。形式上，R 是一個關係，如果

$R\subseteq X\times Y=\{(x,y)|x\in X,y\in Y\}$

對於定義域 X 和陪域 Y。R 的逆關係，寫成 R^-1，是我們交換 X 和 Y 值時得到的結果

$R^{-1}=\{(y,x)|(x,y)\in R\}$

使用上面的例子，我們可以用集合符號寫出關係：{(蘋果，甜味)，(蘋果，酸味)，(橙子，酸味)，(香蕉，甜味)}。逆關係，我們可以描述為“特定味道的水果”，是 {(甜味，蘋果)，(甜味，香蕉)，(酸味，蘋果)，(酸味，橙子)}。（這裡，和其他地方一樣，集合中元素的順序沒有意義。）

關係中一種重要的型別是函式。函式 是一種關係，對於定義域中的每個可能的輸入，它都只有一個輸出。（定義域不一定必須包含所有可能的給定型別的物件。事實上，我們有時有意使用受限定義域，以滿足一些期望的性質。）上面討論的關係（水果的味道和特定味道的水果）不是函式：第一個對於輸入“蘋果”有兩個可能的輸出（甜味和酸味）；第二個對於“甜味”（蘋果和香蕉）和“酸味”（蘋果和橙子）都有兩個輸出。

不允許對於同一個輸入有多個輸出的主要原因是，它讓我們可以將同一個函式應用於同一個東西的不同形式，而不會改變它們的等價性。也就是說，如果 f 是一個在它的定義域中包含 a（或 b）的函式，那麼 a = b 意味著 f(a) = f(b)。例如，z - 3 = 5 意味著 z = 8，因為 f(x) = x + 3 是一個對所有數字 x 定義明確的函式。

反之，f(a) = f(b) 意味著 a = b，並不總是成立。當它成立時，對於某個特定輸出 y = f(x)，永遠不會存在超過一個輸入 x。這與函式的定義相同，但交換了 X 和 Y 的角色；因此這意味著逆關係 f^-1 也必須是一個函式。一般來說，無論原始關係是否是一個函式，逆關係有時是一個函式，有時不是。

當 f 和 f^-1 都是函式時，它們被稱為一對一、單射或可逆函式。這是函式 f 可能（或可能不）擁有的兩個非常重要的性質之一；另一個性質被稱為滿射或對映，這意味著，對於任何 y ∈ Y（在陪域中），都存在某個 x ∈ X（在定義域中），使得 f(x) = y。換句話說，一個滿射函式 f 將對映到每個可能的輸出至少一次。

一個函式可以是既不是一對一也不是滿射，既是一對一又是滿射（在這種情況下它也被稱為雙射或一一對應），或者僅僅是其中一個，而另一個不是。（作為既不是一對一也不是滿射的例子，考慮 f = {(0,2)，(1,2)}。它是一個函式，因為它對於每個 x 值只有一個 y 值；但是對於輸出 y = 2，存在多個輸入 x；並且它顯然沒有“對映到”所有整數。）

關係

在上面關於函式及其性質的部分，我們注意到所有函式都必須具有的重要性質，即如果一個函式將值從其定義域對映到其陪域，它必須將該值對映到陪域中的唯一值。

用集合符號寫出來，如果a 是某個固定值

|{f(x)|x=a}| ∈ {0, 1}

這個語句的字面意思是：對於某個固定值 a，集合 {f(x)|x=a} 的基數（元素數量）是集合 {0, 1} 的一個元素。換句話說，函式 f 在任何固定輸入 a 處可能具有的輸出數量要麼為零（在這種情況下，它在該輸入處未定義），要麼為一（在這種情況下，輸出是唯一的）。

然而，當我們考慮關係時，我們放寬了這種限制，因此一個關係可以將一個值對映到多個其他值。一般來說，關係是其定義域和陪域的笛卡爾積的任何子集。

那麼，所有函式都可以被認為是關係。

符號

當一個值與另一個值相關聯時，我們稱這種關係為二元關係，我們將其寫為

x R y

其中 R 是關係。

對於箭頭圖和集合符號，請記住，對於關係，我們沒有函式的限制，我們可以畫一個箭頭來表示對映，對於集合圖，我們只需要寫下關係所採用的所有有序對：同樣，舉個例子

f = {(0,0),(1,1),(-1,1),(2,2),(-2,2)}

是一個關係而不是函式，因為 1 和 2 都對映到兩個值（分別為 1 和 -1 以及 2 和 -2）例如，設 A=2,3,5；B=4,6,9 則 A*B=(2,4),(2,6),(2,9),(3,4),(3,6),(3,9),(5,4),(5,6),(5,9) 定義關係 R=(2,4),(2,6),(3,6),(3,9) 將函式和問題新增到彼此。

一些簡單的例子

讓我們考察一些簡單的關係。

假設 f 由以下定義

{(0,0),(1,1),(2,2),(3,3),(1,2),(2,3),(3,1),(2,1),(3,2),(1,3)}

這是一個關係（而不是函式），因為我們可以觀察到 1 對映到 2 和 3，例如。

小於，“<”，也是一種關係。許多數字可以小於某個固定的數字，因此它不能是函式。

屬性

當我們檢視關係時，我們可以觀察到不同的關係可能具有一些特殊的屬性。

自反

如果我們觀察到對所有值 a

a R a

換句話說，所有值都與其自身相關聯。

相等關係，“=” 是自反的。觀察到，例如，對於所有數字 a（域為 R）

a = a

所以“=” 是自反的。

在自反關係中，我們有所有域中值的箭頭指向自身

請注意，≤ 也是自反的（a ≤ a 對於 R 中的任何 a 成立）。另一方面，關係 < 不是（a < a 對於 R 中的任何 a 都是假的）。

對稱

如果我們觀察到對所有值 a 和 b

a R b 意味著 b R a

相等關係再次是對稱的。如果 x=y，我們也可以寫成 y=x。

在對稱關係中，對於每個箭頭，我們也都有一個相反的箭頭，即 x 和 y 之間要麼沒有箭頭，要麼箭頭從 x 指向 y，然後箭頭從 y 指向 x

≤ 和 < 都不是對稱的（2 ≤ 3 和 2 < 3 但 3 ≤ 2 和 3 < 2 都不成立）。

傳遞

如果對所有值 a、b、c

a R b 和 b R c 意味著 a R c

關係大於“>” 是傳遞的。如果 x > y 且 y > z，則 x > z 成立。當我們將發生的事情寫成文字時，這變得更加清楚。x 大於 y 且 y 大於 z。所以 x 大於 y 和 z。

關係不等於“≠” 不是傳遞的。如果 x ≠ y 且 y ≠ z，那麼我們可能會有 x = z 或 x ≠ z（例如 1 ≠ 2 且 2 ≠ 3 且 1 ≠ 3 但 0 ≠ 1 且 1 ≠ 0 且 0 = 0）。

在箭頭圖中，兩個值 a 和 b 之間，以及 b 和 c 之間的每個箭頭都有一個箭頭直接從 a 指向 c。

反對稱

如果我們觀察到對所有值 a 和 b

a R b 和 b R a 意味著 a=b

請注意，反對稱與“非對稱”不同。

取關係大於或等於，“≥” 如果 x ≥ y 且 y ≥ x，則 y 必須等於 x。當且僅當 a∈A，(a,a)∈R 時，關係是反對稱的

三等分

如果我們觀察到對所有值 a 和 b，它都成立：aRb 或 bRa，則關係滿足三等分。

關係大於或等於滿足，因為對於給定的 2 個實數 a 和 b，a ≥ b 或 b ≥ a 成立（如果 a = b，則兩者都成立）。

問題集

鑑於以上資訊，確定哪些關係在以下方面是自反的、傳遞的、對稱的或反對稱的 - 可能存在多個特徵。（答案如下。）x R y 如果

1. x = y
2. x < y
3. x² = y²
4. x ≤ y

答案

1. 對稱、自反和傳遞
2. 傳遞、三等分
3. 對稱、自反和傳遞（x² = y² 只是相等的一個特例，所以適用於 x = y 的所有屬性也適用於這種情況）
4. 自反、傳遞和反對稱（並滿足三等分）

等價關係

我們已經看到，某些常見的關係，如“=” 和全等（我們將在下一節中討論）遵守上述某些規則。我們將討論的關係在離散數學中非常重要，被稱為等價關係。它們本質上斷言某種相等概念或等價性，因此得名。

等價關係的特徵

對於關係 R 成為等價關係，它必須具有以下屬性，即 R 必須是

• 對稱的
• 傳遞的
• 自反的

（一個有用的助記符，S-T-R）

在前面的問題集中，您已經證明了相等，“=”，是自反的、對稱的和傳遞的。所以“=” 是等價關係。

一般情況下，我們用 $x\sim y$ 來表示等價關係。

示例證明

假設我們被要求證明“=” 是等價關係。然後，我們依次證明上面的每個屬性（通常，傳遞性的證明是最難的）。

• 自反：顯然，a = a 對所有值 a 成立。因此，= 是自反的。
• 對稱：如果 a = b，則 b = a 也成立。因此，= 是對稱的
• 傳遞性：如果a = b 且 b = c，這意味著a 與b 相同，而b 又與c 相同。所以a 也與c 相同，所以a = c，因此 = 是傳遞的。

因此 = 是一個等價關係。

劃分和等價類

當我們處理關係時，我們會發現很多值與一個固定值相關聯，這是真的。

例如，當我們檢視同餘的性質時，該性質是指對於給定的一些數字a，與a 同餘的數字是那些在被某個數字n 除後具有相同餘數或模數的數字，與a 相同，我們寫成

a ≡ b (mod n)

這與寫成以下形式相同

b = a+kn，其中 k 是某個整數。

（我們將在後面詳細介紹同餘，但對這一概念的簡單考察或理解將在其對等價關係的應用中很有趣）

例如，2 ≡ 0 (mod 2)，因為 2 除以 2 的餘數實際上是 0，0 除以 2 的餘數也是 0。

我們可以證明同餘是一個等價關係（這留作練習，在下面的提示中使用上面描述的同餘的等價形式）。

然而，更有趣的是我們可以將所有彼此等價的數字分組。

對於模 2 同餘關係（即使用 n=2，如上），或者更正式地說

x ~ y 當且僅當 x ≡ y (mod 2)

我們可以將所有彼此等價的數字分組。觀察

$0\equiv 2\equiv 4\equiv \ldots {\pmod {2}}$

$1\equiv 3\equiv 5\equiv \ldots {\pmod {2}}$

上面的第一個方程式告訴我們所有偶數在 ~ 下彼此等價，所有奇數在 ~ 下彼此等價。

我們可以用集合符號來表示。然而，我們有一個特殊的符號。我們寫

[0]={0,2,4,...}

[1]={1,3,5,...}

我們稱這兩個集合為等價類。

根據定義，等價類中的所有元素彼此等價，因此請注意，我們不需要包含 [2]，因為 2 ~ 0。

我們將根據某個等價關係執行此“分組”的行為稱為劃分（或者更進一步地明確地根據關係 ~ 將集合 S 劃分成等價類）。在上面，我們根據模 2 同餘關係將Z 劃分成了等價類 [0] 和 [1]。

問題集

鑑於上述內容，請回答以下有關等價關係的問題（答案在偶數編號的問題後面給出）

1. 證明同餘如前所述是一個等價關係（見上面的提示）。
2. 將 {x | 1 ≤ x ≤ 9} 劃分成等價關係下的等價類

$x\sim y\ {\mbox{iff}}\ x\equiv y{\pmod {6}}$

答案

2. [0]={6}, [1]={1,7}, [2]={2,8}, [3]={3,9}, [4]={4}, [5]={5}

偏序

我們還看到“≥”和“≤”服從上面的一些規則。這些也是特殊型別的關係嗎，就像等價關係一樣？是的，事實上，這些關係是我們將在此部分中描述的另一種特殊型別關係的具體例子：偏序。

顧名思義，這種關係對數字進行某種排序。

偏序的特徵

為了使關係 R 成為偏序，它必須具有以下三個屬性，即 R 必須是

• 自反的
• 反對稱的
• 傳遞的

（一個有用的助記符，R-A-T）

我們一般用 $x\preceq y$ 表示偏序。

問題

1. 假設 R 是整數集 Z 上的關係，那麼證明 R 是 Z 上的偏序關係當且僅當 a=b 的 r 次方。

示例證明

假設我們要證明“≤”是一個偏序。然後我們依次證明上面的每個屬性（通常，傳遞性的證明是最難的）。

自反

顯然，對於所有值 a，a ≤ a 都是成立的。所以 ≤ 是自反的。

反對稱

如果a ≤ b 且 b ≤ a，那麼a 必須等於b。所以 ≤ 是反對稱的

傳遞

如果a ≤ b 且 b ≤ c，這意味著a 小於b 和c。所以a 小於c，所以a ≤ c，因此 ≤ 是傳遞的。

因此 ≤ 是一個偏序。

問題集

鑑於上述關於偏序的內容，請回答以下問題

1. 證明可除性 | 是一個偏序（a | b 表示 a 是 b 的因子，即在用 a 除 b 時，沒有餘數）。
2. 證明以下集合是一個偏序：（a, b) $\preceq$ (c, d) 意味著 ab≤cd，其中 a,b,c,d 是從 0 到 5 的整數。

答案

2. 簡單的證明；證明的形式化是一個可選練習。

自反性：（a, b) $\preceq$ (a, b)，因為 ab=ab。

反對稱性： (a, b) $\preceq$ (c, d) 且 (c, d) $\preceq$ (a, b) ，因為 ab≤cd 且 cd≤ab 意味著 ab=cd。

傳遞性： (a, b) $\preceq$ (c, d) 且 (c, d) $\preceq$ (e, f) 意味著 (a, b) $\preceq$ (e, f) ，因為 ab≤cd≤ef ，因此 ab≤ef

偏序集

偏序關係賦予了集合中元素某種“順序”。例如，我們只知道 2 ≥ 1，這是因為偏序關係 ≥。

我們稱在一個一般偏序關係 $\preceq$ 下有序的集合 A 為一個偏序集，簡稱為poset，並將其記為 (A, $\preceq$).

術語

一些特定的術語將有助於我們理解和視覺化偏序關係。

當我們有一個偏序關係 $\preceq$，使得 a $\preceq$ b，我們寫 $\prec$ 來表示 a $\preceq$ 但 a ≠ b。在這種情況下，我們說 a先於b，或者a是b的前驅。

如果 (A, $\preceq$) 是一個 poset，我們說 a 是 b 的直接前驅（或 a 直接先於 b），如果 A 中不存在 x 使得 a $\prec$ x $\prec$ b。

如果我們有相同的 poset，並且 A 中也存在 a 和 b，那麼如果 a $\preceq$ b 或 b $\preceq$ a，我們說 a 和 b 是可比較的。否則，它們是不可比較的。

哈斯圖

哈斯圖是特殊的圖，使我們能夠視覺化偏序關係的結構。它們使用上一節中的一些概念來繪製圖。

poset (A, $\preceq$) 的哈斯圖的構造方法是

• 將 A 的元素作為點放置
• 如果 a 和 b ∈ A，且 a 是 b 的直接前驅，則從 a 到 b 畫一條線
• 如果 a $\prec$ b，將 a 的點放在 b 的點下方
• 不從 a 到 a 畫環路（由於自反性，這在偏序關係中是假設的）

關係上的運算

在關係上可以執行一些有用的運算，這些運算可以更簡潔地表達上面提到的某些性質。

反轉

設 R 為一個關係，則其反轉 R^-1 定義為

R^-1 := {(a,b) | (b,a) in R}.

連線

設 R 是集合 A 和 B 之間的關係，S 是集合 B 和 C 之間的關係。我們可以透過定義以下方式連線這些關係：

R • S := {(a,c) | (a,b) ∈ R 且 (b,c) ∈ S，對於 B 中的某個 b}

集合的對角線

設 A 是一個集合，我們定義 A 的對角線 (D) 為：

D(A) := {(a,a) | a ∈ A}

簡短的記號

使用上面的定義，我們可以說（假設 R 是 A 和 B 之間的關係）：

R 是傳遞的當且僅當 R • R 是 R 的子集。

R 是自反的當且僅當 D(A) 是 R 的子集。

R 是對稱的當且僅當 R^-1 是 R 的子集。

R 是反對稱的當且僅當 R 和 R^-1 的交集是 D(A)。

R 是非對稱的當且僅當 D(A) 和 R 的交集為空。

R 是一個函式當且僅當 R^-1 • R 是 D(B) 的子集。

在這種情況下，它是一個 A → B 的函式。假設 R 滿足函式的條件，那麼：

R 是單射的當且僅當 R • R^-1 是 D(A) 的子集。

R 是滿射的當且僅當 {b | (a,b) ∈ R} = B。

函式

函式是兩個數字集合之間的關係。我們可以將其視為一種對映；函式將一個集合中的一個數字對映到另一個集合中的一個數字。請注意，函式將值對映到一個且只有一個值。一個集合中的兩個值可以對映到一個值，但一個值永遠不能對映到兩個值：這將是一個關係，而不是一個函式。

例如，如果我們將一個函式定義為：

$f(x)=x^{2}$

那麼我們說：

'f of x 等於 x 的平方'

我們有：

$f(-1)=1$

$f(1)=1$

$f(7)=49$

$f(1/2)=1/4$

$f(4)=16$

等等。

這個函式 f 將數字對映到它們的平方。

值域和陪域

如果 D 是一個集合，我們可以說：

$f(D)=\{f(x)|\ x\in D\}$

這形成了 f 的值域，通常是更大集合的子集。這個集合被稱為函式的陪域。例如，對於函式 f(x)=cos x，f 的值域是 [-1,1]，但陪域是實數集合。

符號

當我們有一個函式 f，其定義域為 D，值域為 R 時，我們寫：

$f:D\longrightarrow R$

如果我們說，例如，x 對映到 x²，我們也可以新增：

$f:D\longrightarrow R;\ x\longmapsto x^{2}$

請注意，我們可以有一個函式將點 (x,y) 對映到一個實數，或者其他一些兩個變數的函式 - 我們有一組有序對作為定義域。回想一下集合論，這是由笛卡爾積定義的 - 如果我們想表示所有實值有序對的集合，我們可以將實數與它自身進行笛卡爾積，以得到：

$\mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}=\{(x,y)|\ x\ {\mbox{and}}\ y\in \mathbb {R} \}$.

當我們有一個由n元組組成的集合作為域時，我們就說這個函式是n元的（對於數字n=1,2，我們分別稱為一元和二元）。

其他函式表示法

函式可以用上面提到的方式寫，但我們也可以用兩種其他方式寫。一種方式是使用箭頭圖來表示每個元素之間的對映關係。我們把域中的元素寫在一側，把值域中的元素寫到另一側，然後畫箭頭表示域中的元素對映到值域中的元素。

例如，對於函式f(x)=x³，域為{1,2,3}的箭頭圖將是：

另一種方法是使用集合符號。如果f(x)=y，我們可以用對映關係來表示函式。這個概念最好用例子來解釋。

讓我們取域D={1,2,3}，並且f(x)=x²。那麼，f的值域將是R={f(1),f(2),f(3)}={1,4,9}。對D和R取笛卡爾積，我們得到F={(1,1),(2,4),(3,9)}。

因此，使用集合符號，函式可以表示為其域和值域的笛卡爾積。

f(x)

這個函式被稱為f，它接受一個變數x。我們用某個值替換x，得到第二個值，也就是函式將x對映到的值。

函式的型別

函式可以是一對一（單射）、映上（滿射）或雙射。

單射函式是指域中的每個元素都對映到陪域中唯一的元素的函式。

滿射函式是指陪域中的每個元素都被域中的某個元素對映的函式。

'雙射 函式是指既是單射又是滿射的函式。

---滿射函式 從A到B的函式f是滿射的，