二元關係
| 二元關係 |
數學上，二元關係用於討論兩個數學對象的聯繫。諸如算術中的「大於」及「等於」，幾何學中的"相似"，或集合論中的"為...之元素"或"為...之子集"。二元關係有時會簡稱關係，但一般而言關係不必是二元的。
目錄
簡介
集合X與集合Y上的二元關係是R=(X,Y,G(R))，其中G(R)，稱為R的圖，是笛卡兒積X×Y的子集。若 (x,y) ∈G(R) ，則稱x是R-關係於y，並記作xRy或R(x,y)。否則稱x與y無關係R。但經常地我們把關係與其圖等同起來，即：若R⊆X×Y，則R是一個關係。例如：有四件物件 {球，糖，車，槍} 及四個人 {甲，乙，丙，丁}。 若甲擁有球，乙擁有糖，及丁擁有車，即無人有槍及丙一無所有— 則二元關係"為...擁有"便是R=({球，糖，車，槍}, {甲，乙，丙，丁}, {(球,甲), (糖,乙), (車,丁)})。其中 R 的首項是物件的集合，次項是人的集合，而末項是由有序對（物件，主人）組成的集合。比如有序對（球，甲）∈G(R)，所以我們可寫作"球R甲"，表示球為甲所擁有。不同的關係可以有相同的圖。以下的關係 ({球，糖，車，槍}, {甲，乙，丁}, {(球,甲), (糖,乙), (車,丁)} 中人人皆是物主，所以與R不同，但兩者有相同的圖。話雖如此，我們很多時候索性把R定義為G(R)， 而 "有序對 (x,y) ∈G(R)" 亦即是 "(x,y) ∈R"。二元關係可看作成二元函數，這種二元函數把輸入元x∈X及y∈Y視為獨立變量並求真偽值（即「有序對(x,y) 是或非二元關係中的一元」此一問題）。若X=Y，則稱R為X上的關係。
評價
求傳遞閉包是圖論中一個非常重要的問題，例如給定了一個城市的交通地圖，可利用求傳遞閉包的方法獲知任意兩個地點之間是否有路相連通。可以直接利用關係矩陣相乘來求傳遞閉包，但那樣做複雜度比較高；好一點的辦法是在計算矩陣相乘的時候用分治法降低時間複雜度；但最好的方法是利用基於動態規劃的Floyd-Warshall算法來求傳遞閉包。反自反關係和自反關係的數目一樣多。嚴格偏序（反自反的傳遞關係）的數目和偏序的一樣多。全序即是那些同時是全預序的偏序。透過容斥原理的想法，可知那些既不是偏序也不是全預序的預序數目是：預序的數目，減去偏序的數目，再減去全預序的數目，最後加上全序的數目，即0, 0, 0, 3, 85, ...等價關係的數目是集合劃分的數目，即貝爾數。各個二元關係之間可組成二元組（某關係及其補集），除了在n=0時，空關係的補集即其自身。那些不符合對稱性的二元關係也可組成四元組（某關係、補集、逆、逆的補集）。[1]