关系:

先来刷一大堆定义。。

  1. \left\{ (x,y)| x\in X, y\in Y \right\} 称为聚集X与聚集Y的 笛卡尔积 ,记作X \times Y,读作X叉乘Y。此中(x,y) 是一个 有序偶
  2. 有序偶 :单点集A (条件一 )和≤两个元素构成的 (条件二) 聚集B,构成集族 \left\{ A,B \right\} , 假如满意 A\subset B (条件三) ,则成为一个有序偶,记作(x,y),此中:

x为满意 X\cap Y 的惟一元素,y为满意 X\cup Y 的惟一元素。

  • 留意: X\times Y\ne Y\times X
  • 3. 假如聚集 R\subset X\times Y ,则称R是从X到Y的一个 关系 (two simple examples of R: X\times Y 和 空集) R是有序偶的聚集。

    • 假如 (x,y)\in R ,则称x与y是 R-相关 的,记作xRy。
    • 假如 A\subset X, 则Y的子集 \left\{ y\in Y| \exists x\in A 使得xRy  \right\} 称为 聚集A的R-像 记作R(A)。
    • R(X)成为关系R的值域。

    4. 对于3.中的关系xRy, Y\times X 的子集 \left\{ (y,x)\in Y \times X| xRy \right\} 成为 关系R的逆 ,记作

    R^{-1} .

    • 假如 B\in Y ,那么x的子集是聚集B的 R^{-1} ,或称为: R-原像
    • R^{-1} (Y)也称为关系R的定义域。

    5.对于 R\subset X\times Y, S \subset Y \times Z ,设 \left\{ (x,z) \in X\times Z| \exists y\in Y使得xRy且ySz \right\}X\times Z 的一个子集,称其为R与S的 复合

    6. \left\{ (x_{1},x_{2},...,x_{n})| x_{1}\in X_{1},x_{2}\in X_{2},...,x_{n}\in X_{n} \right\} 称为 X_{1},X_{2},...,X_{n} 的笛卡尔积,此中 (x_{1},x_{2},...,x_{n}) 称为 有序n元素组 X_{i} 称为笛卡尔积的第i个 坐标集


    定理一: 设:xRy,ySz,zTv,则 \forall :

      \left( R^{-1} \right)^{-1}=R (S\circ R)^{-1}=R^{-1}\circ S^{-1} T\circ(S\circ R)=(T\circ S)\circ R

    定理二: 设xRy, ySz,则 \exists A\subset X, B\subset X, \forall

      R(A\cup B)=R(A)\cup R(B) R(A\cap B)\subset R(A) \cap R(B) (S\circ R)(A)=S(R(A))

    (这两条定理的证实比较显然就不写啦...根据定义把LHS和RHS分别演算一下然后相称就行了)


    等价关系:

    恒同(关系)/对角线: 从聚集X到聚集X的一个关系: \left\{ (x,x)|x\in X \right\}

  • 满意(1) 自反性 ,(2) 对称性 与(3) 通报性 ,是X中的一个 等价关系
  • #这个也是等价关系的定义。

    嗯...关于这三条性子先瞎xx讲讲故事8.

    定义等价关系,首先要明白的是自反性。不然你想象一下,你看山不是山,看水不是水。名可名,非常名(划掉)那还van个球啊。再比方说对应到群的性子中就是幺元的观点。

    然后我们要确定对称性,emm比方说:A满意是B的同桌的性子,则反过来B也必须是A的同桌。这一条可以对应群内里的逆元的观点。

    最后再说通报性,拿室友举个例子:假如A是B的室友,B是C的室友,则A一定也是C的室友,那么'室友'这一性子就满意了通报性。但是'A嘻歡B,B嘻歡C'就不是一个具有通报性的性子....不然画面着实太哲♂学。。(迫真もうそんなんじゃホラ,心(こころ)は进化(しんか)するよ もっともっと...)这个可以对应群论内里的联合律。

    如今给出这些性子的正义化定义 [1]

    自反性:

    在全集U中全部子集的聚集中,包含关系 是自反的,相称关系=也是自反的;但是,真包含关系 不是自反的,整数聚集Z中,关系≤是自反的,而关系<不是自反的。

    反自反性:

    由定义说明中可知真包含关系 是反自反的,但包含关系不是反自反的;小于关系是反自反的,而≤不是反自反的。

    存在既不是自反的也不是反自反的二元关系。

    对称性:

    该定义表明了,在表现对称的关系R的有序对聚集中,如有有序对<x,y>,则肯定还会有有序对<y,x>。

    在全集U的全部子集的聚集中,相称关系是对称的,包含关系和真包含关系都不是对称的;在整数聚集Z中,相称关系=是对称的,而关系≤和<都不是对称的。

    阻挡称性:

    该定义表明了,在表现阻挡称关系R的有序对聚集中,若存在有序对<x,y>和<y,x>,则肯定是x=y。留意,若R中对u<x,y>到处不出现<y,x>,则仍满意阻挡称性(比方说<)

    在全集U的全部子集的聚集中,相称关系=,包含关系和真包含关系都是阻挡称的,但全域关系不是阻挡称的.在整数聚集Z中,=,≤和<也都是阻挡称的。

    通报性:

    该定义表明了,在表现可通报关系R的有序对聚集中,如有有序对<x,y>和<y,z>,则必有有序对<x,z>。

    显然,上述提到的关系中包含,真包含,≤,<,=都是通报的,在直线的聚集中,平行关系是通报的,但垂直关系不是通报的。

    (为了加深明白,可以列出一个聚集,对于此中一些运算验证以上性子的定义)


    PS:在有正常的直觉的底子上,万万不必到处套用正义化定义判定orz

    设R是聚集X中的一个等价关系,对 x\in X, y\in X ,假如xRy,则称 x与y是(R-)等价的

    等价类: X的子集 \left\{ y\in X|yRx \right\} ,记作 \left[ X \right]_{R}\left[ X \right]

    商集: \left\{ \left[ X \right]_{R}| x\in X \right\} 称为聚集X对于等价关系R而言的商集,记作X/R。


    定理一 (等价关系是把非空聚集分别成两两互不相交的等价类的分类原则):

    设R黑白空聚集X中的一个等价关系,则:

    1. 假如 x\in X ,则 x\in \left[ X \right]_{R} ,因而 \left[ X \right]_{R} 不为空。(证:由x有自反性可得)
    2. \exists x,y\in X ,则要么 \left[ X \right]_{R}=\left[ Y \right]_{R} ;要么 \left[ X \right]_{R}\cap\left[ Y \right]_{R}= Ø(证:由等价关系的三条性子显然.)

    相关:

    1. 群论中的商群(参考商集)
    2. 初等数论中的模p同余类(等价关系)
    3. 剖析几何中的自由向量(等价关系)
    • 将固定向量定义为n维Euclidean Space中的有序n元素组
    • 在全体固定向量组成的聚集X中定义一个关系T,使得对固定向量x,y有xTy当且仅当x可以或许通过平移与y重合
    • T是X中的一个等价关系.

    参考

  • ^ https://baike.baidu.com/item/关系/3785874?fr=aladdin
  • 自反对称传递的关系是什么

    @EtoDemerzel 2017-11-06T12:51:35.000000Z 字数 1664 阅读 3050

    离散数学第九章 关系(一)

    离散数学 关系

    part 1. 相关观点
    1. 用两个相关元素组成的有序对来表达两个聚集元素之间的关系。由有序对构成的聚集就叫做 二元关系
    2. 和 是聚集,一个从 到 的二元关系是 的子集。
    3. 时, 与 有 关系
    4. 函数作为关系: 是 到 的关系, 满意: 中每个元素 恰恰 是 中一个有序对的第一元素, 就可以定义一个 函数的图示 。(即对 中每个元素 可指定唯一的 , 使得 。)
    5. 聚集 上的关系是从 到 的关系。
    part 2. 性子
  • 关系的性子: 自反性, 对称性, 阻挡称性,非对称性, 通报性
    • 自反性 ,那么定义在 上的关系 成为 自反的(reflexive) .
    • 对称性 ,则称定义在聚集 上的关系 为 对称的(symmetric) .
    • 阻挡称性 ,则称定义在 上的关系 为 阻挡称的(antisymmetric) .
    • 非对称性 ,则称定义在聚集 上的关系 是 非对称的(asymmetric) .
    • 通报性 ,则称定义在聚集 上的关系 是 通报的(transitive) .
  • 来表现:
    example one
    自反
    example two
    对称
    example three
    通报+非对称+阻挡称
    example four
    自反+通报+阻挡称

    2. 关系的组合: 是从 到 的关系, 是从 到 的关系。 与 的 合成 是由有序对 组成的关系,此中 ,且存在 ,使得 。用 表现。
    3. 自身的合成: 的 次幂 递归定义为:

    4. 一个定理:聚集 上的关系 是通报的 对 .

    part 3. 表现方法
    1. 用矩阵表现关系

      • 自反 : 对于 .如下所示:
      • 对称 :只要 ,就有 ,也就意味着,只要 ,就有
        亦即,
      • 阻挡称 :当 时, 要么 (也就是说二者不能同时为 )。
        或 均可。
        Symmetric & Asymmetric
      • 非对称 :非对称和阻挡称的区别就是主对角线上不能为 .
      • 关系的合成 直接用矩阵的 布尔积 盘算即可,即:
    2. 用图的方法表现
      • 有向图 :由 极点 (或 结点 )集 和 (或 集 构成。
      • 自反 :图示见上。有向图每个极点都有 (loop)。
      • 对称 :图示见上。有向图差别极点之间的 每一条边 都存在一条 方向相反 的边。
      • 阻挡称 :图示见上。有向图两个差别极点之间 不存在 两条方向相反的边。(大概存在一条边或没有边)
      • 非对称 :图示见上。在 阻挡称 条件的底子上,每个极点都 不能有环

    自反关系 是在 逻辑学 和 数学 中一种特别的 二元关系 ,这样的二元关系被称为 自反的 ,也被称为具有 自反性 。自反关系的一个例子是关于实数聚集的“即是”关系,由于每个实数都即是它自己。 对称性 、 通报性 以及自反性是定义等价关系的三个属性。

    对于聚集X上的 二元关系 R,若满意:取X里任一元素a,且满意对于全部a皆存在(a,a)在R聚集中,则称二元关系R是 自反的 ,或称R具有 自反性 ,或称R为 自反关系

    相关观点 [ 编辑 ]

    a X {\displaystyle \forall a\in X} ,a = a,在一些系统中称为 相称正义

    一个非自反(irreflexive, anti-reflexive)的关系,是在一个聚集中没有元素与自身相关的二元关系。比方实数上的“大于”关系(x> y)。请留意,没有自反的种种关系,并不全都黑白自反的;可以定义一些元素与自己相关的关系,而另一些则不是(neither all nor none are)。比方,“x和y的乘积是偶数”的二元关系在偶数集上是自反的,在奇数集上黑白自反的,在自然数集上既不是自反,也不黑白自反。

    关于聚集S上的一个关系,假如与某个元素相关的每个元素也与它自己有关,情势上就称为准自反:∀x,y∈S:x〜y⇒(x〜x∧y〜y)。一个例子是关于实数序列聚集的“具有相同极限”的关系:并不是每个序列都有一个极限,因此这个关系不是自反的,但是假如一个序列与某个序列具有相同的极限,具有与其本身相同的限定。

    S上二元关系的自反闭包是S上最小的自反关系,它是〜的超集。等价地,它是S与S上的同一性关系的联合,情势如下:(≃)=(¯)∪(=)。比方,x <y的自反闭包是x≤y。

    在聚集S上的二元关系的自反性约化或非自反核是最小的关系≆,使得≆共享与〜相同的自反闭包。它可以被看作是自反关闭的反面。 它相当于S上关于〜的情势关系的增补,情势上是:(≆)=(〜)\(=)。也就是说,除了x〜x是真的,它相当于〜。比方,x≤y的自反淘汰是x <y。

    特别的自反关系 [ 编辑 ]

    满意 通报性 的自反关系称为 预序关系 。满意 阻挡称性 的预序关系称为 偏序关系 。满意 对称性 的预序关系称为 等价关系 。

    自反关系举例:

    n元素聚集之上的关系 [ 编辑 ]

    一个“n”-元素聚集上,自反关系的数量是2 n 2 n . [1]

  • ^ On-Line Encyclopedia of Integer Sequences A053763
  • 本文网址: http://www.appike.com/d/202091954428_6641_2450498849/home