等价关系

维基百科,自由的百科全书
跳转至: 导航搜索

R是某個集合A上的一个二元关系。若R满足以下條件:

  1. 自反性:\forall x \in A,~~x R x
  2. 对称性:\forall x, y \in A,~~ x R y ~~ \implies ~~y R x
  3. 传递性:\forall x, y, z \in A, ~~~( x R y ~~ \wedge ~~ y R z) ~~\implies~~x R z

则称R是一個定义在A上的等价关系。習慣上會把等價關係的符號由R改寫為 \sim

例如,设A = \{1, 2, \ldots, 8\},定义A上的关系R如下:

xRy \iff \forall x, y \in A, ~ x \equiv y \pmod{3}

其中x \equiv y \pmod{3}叫做xy模3 同餘,即x除以3的餘数与y除以3的餘数相等。例子有1R4, 2R5, 3R6。不难验证RA上的等价关系。

不是所有的二元關係也是等價關係。一個簡單的反例子是比較兩個數中哪個較大

  • 沒有自反性:任何一個數不能比自身為較大(n \ngtr n
  • 沒有對稱性:如果m > n,就肯定不能有n > m

参见[编辑]