數學上,二元關係(英語:Binary relation,或簡稱關係)用於討論兩種物件的連繫。諸如算術中的「大於」及「等於」、幾何學中的「相似」或集合論中的「為……之元素」、「為……之子集」。
設為集合,的任何子集稱作到的二元關係,特別是當時,稱作上的二元關係,一般記作。若, 是從到的二元關係;若,那麼是上的二元關係
或是以正式的邏輯符號表述為
例一:有四件物件 {球,糖,車,槍} 及四個人 {甲,乙,丙,丁} 。若甲擁有球、乙擁有糖、丙一無所有但丁擁有車,則「擁有」的二元關係可以寫為
- = {(球,甲), (糖,乙), (車,丁)}
其中二元有序對的第一項是被擁有的物件,第二項是擁有者。
例二:實數系 上的「大於關係」可定義為
由於習慣上 通常都是寫為 ,更一般來說,不引起混淆的話會把 簡寫成 。
集合與集合上的二元關係則定義為 ,當中 ( 請參見笛卡兒積 ) ,稱為 的圖。若 則稱 與 有關係 ,並記作 或 。
但經常地我們把關係與其圖等價起來,即若 則 是一個關係。
話雖如此,我們很多時候索性把集合間的關係 定義為 而 「有序對 」 即是 「 」。
設及,是 和上的關係,令
則0,1矩陣
稱為的關係矩陣,記作。
設,是上的關係,令圖,其中頂點集合,邊集合為,且對於任意的,滿足若且唯若。則稱圖是關係的關係圖,記作。
關係的基本運算有以下幾種:
- 設為二元關係,中所有有序對的第一元素構成的集合稱為的定義域,記作。形式化表示為
- 設為二元關係,中所有有序對的第二元素構成的集合稱為的值域,記作。形式化表示為
- 設為二元關係,的定義域和值域的併集稱作的域,記作,形式化表示為
- 設為二元關係,的逆關係,簡稱的逆,記作,其中
- 設為二元關係,與的合成關係記作,其中
- 設為二元關係,是一個集合。在上的限制記作,其中
- 設為二元關係,是一個集合。在下的像記作,其中
- 設為上的二元關係,在右複合的基礎上可以定義關係的冪運算:
-
關係的性質主要有以下五種:
- 自反性:
- 在集合X上的關係R,如對任意,有,則稱R是自反的。
- 非自反性(自反性的否定的強型式):
- 在集合X上的關係R,如對任意,有,則稱R是非自反的。
- 對稱性:
- 在集合X上的關係R,如果有且必有,則稱R是對稱的。
- 反對稱性(不是對稱性的否定):
- 非對稱性(對稱性的否定的強型式):
- 非對稱性是 滿足非自反性的反對稱性。
- 傳遞性:
設為集合上的關係,下面給出的五種性質成立的充要條件:
- 在上自反,若且唯若
- 在上非自反,若且唯若
- 在上對稱,若且唯若
- 在上反對稱,若且唯若
- 在上非對稱,若且唯若
- 在上傳遞,若且唯若