跳至內容

二元關係

維基百科,自由的百科全書

數學上,二元關係(英語:Binary relation,或簡稱關係)用於討論兩種物件的連繫。諸如算術中的「大於」及「等於」、幾何學中的「相似」或集合論中的「為……之元素」、「為……之子集」。

定義

為集合,的任何子集稱作的二元關係,特別是當時,稱作上的二元關係,一般記作。若, 是從的二元關係;若,那麼上的二元關係

或是以正式的邏輯符號表述為

例一:有四件物件 {} 及四個人 {丙,丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有車,則「擁有」的二元關係可以寫為

= {(), (), ()}

其中二元有序對的第一項是被擁有的物件,第二項是擁有者。

例二:實數系 上的「大於關係」可定義為

由於習慣上 通常都是寫為 ,更一般來說,不引起混淆的話會把 簡寫成

集合的關係

集合與集合上的二元關係則定義為 ,當中 ( 請參見笛卡兒積 ) ,稱為 。若 則稱 有關係 ,並記作

但經常地我們把關係與其圖等價起來,即若 是一個關係。

話雖如此,我們很多時候索性把集合間的關係 定義為 而 「有序對 」 即是 「 」。

特殊的二元關係

是一個集合,則

  1. 空集稱作上的空關係
  2. 稱作上的全域關係完全關係
  3. 稱作上的恆等關係

關係矩陣

上的關係,令

0,1矩陣

稱為關係矩陣,記作

關係圖

上的關係,令,其中頂點集合,邊集合為,且對於任意的,滿足若且唯若。則稱圖是關係關係圖,記作

運算

關係的基本運算有以下幾種:

  • 為二元關係,中所有有序對的第一元素構成的集合稱為定義域,記作。形式化表示為
  • 為二元關係,中所有有序對的第二元素構成的集合稱為值域,記作。形式化表示為
  • 為二元關係,定義域值域的併集稱作,記作,形式化表示為
  • 為二元關係,逆關係,簡稱,記作,其中
  • 為二元關係,合成關係記作,其中
  • 為二元關係,是一個集合。上的限制記作,其中
  • 為二元關係,是一個集合。下的記作,其中
  • 上的二元關係,在右複合的基礎上可以定義關係的冪運算

性質

關係的性質主要有以下五種:

  • 自反性
在集合X上的關係R,如對任意,有,則稱R是自反的。
  • 非自反性(自反性的否定的強型式):
在集合X上的關係R,如對任意,有,則稱R是非自反的。
  • 對稱性
在集合X上的關係R,如果有必有,則稱R是對稱的。
  • 反對稱性(不是對稱性的否定):
  • 非對稱性(對稱性的否定的強型式):
非對稱性是 滿足非自反性的反對稱性。
  • 傳遞性

為集合上的關係,下面給出的五種性質成立的充要條件:

  1. 上自反,若且唯若
  2. 上非自反,若且唯若
  3. 上對稱,若且唯若
  4. 上反對稱,若且唯若
  5. 上非對稱,若且唯若
  6. 上傳遞,若且唯若

閉包

是非空集合上的關係,的自反(對稱或傳遞)閉包上的關係,滿足

  1. 是自反的(對稱的或傳遞的)
  2. 上任何包含的自反(對稱或傳遞)關係

一般將的自反閉包記作,對稱閉包記作傳遞閉包記作

下列三個定理給出了構造閉包的方法:

對於有限集合上的關係,存在一個正整數,使得

求傳遞閉包是圖論中一個非常重要的問題,例如給定了一個城市的交通地圖,可利用求傳遞閉包的方法獲知任意兩個地點之間是否有路相連通。可以直接利用關係矩陣相乘來求傳遞閉包,但那樣做複雜度比較高;好一點的辦法是在計算矩陣相乘的時候用分治法降低時間複雜度;但最好的方法是利用基於動態規劃Floyd-Warshall算法來求傳遞閉包。

參見