跳转至

2. 序列 & 关系

序列 (Sequences)

序列是按照特定顺序排列的事物列表。与集合不同，序列使用圆括号（而非大括号）来列出元素，如 $(1, 5, 8, −2, 3)$ 或者 $(Library, Python, Tuesday)$。序列可以是有限的也可以是无限的。例如，自然数的序列 $(1,2,3,4,…)$ 是无限的。

序列的重要特性包括：
顺序性：元素的顺序很重要，比如 $(1, 2, 3)$、$(1, 3, 2)$ 和 $(3, 1, 2)$ 是不同的序列。
重复性：元素的重复出现也很重要，比如 $(H,E,L,L,O)$、$(H,H,H,E,L,L,O)$ 和 $(H,E,L,O)$ 是不同的序列。

元组 (Tuples)

有限序列被称为元组。元组是一个固定大小的、有序的对象集合。与序列不同的是，元组的大小是固定的，即元组中的元素个数是确定的。元组中的元素可以是不同类型的。

有 $k$ 个元素的序列称为 $k$-元组，$k$ 称为元组的长度。两个元组相等的条件是它们有相同的长度，且对应位置的元素也相同，例如：$(x_1, x_2, \ldots, x_k) = (y_1, y_2, \ldots, y_n)$ 意味着 $k = n$ 且 $x_1 = y_1$、$x_2 = y_2$，依此类推直到 $x_k = y_k$。2-元组也被称为有序对，比如 $(a, b) = (c, d)$ 意味着 $a = c$ 且 $b = d$。

集合的笛卡尔积 (Cartesian product of sets)

对于任意数量的集合，它们的笛卡尔积是一个由 所有由每个集合中的一个元素构成的元组 构成的集合。每个元组中的元素顺序对应于它们所属的集合的顺序。

$$A \times B = \lbrace (x, y) \mid x \in A \text{ and } y \in B \rbrace$$ $$A_1 \times A_2 \times \cdots \times A_k = \lbrace (x_1, x_2, \ldots, x_k) \mid x_i \in A_i \text{ for } i = 1, 2, \ldots, k \rbrace$$

2 个集合 $A$ 和 $B$ 的笛卡尔积是所有有序对 $(x, y)$ 的集合，其中 $x$ 属于 $A$ 且 $y$ 属于 $B$。笛卡尔积表示为 $A \times B$，例如：如果 $A = \{1,2\}$ 且 $B = \{a,b,c\}$，那么 $A \times B = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)\}$。

对于 $k$ 个集合的笛卡尔积，记为 $A_1 \times A_2 \times \ldots \times A_k$，它由所有 $k$-元组 $(x_1, x_2, \ldots, x_k)$ 组成，这里每个 $x_i$ 属于集合 $A_i$，对于所有 $i = 1, 2, \ldots, k$。例如，如果 $A = \{1, 2\}$，$B = \{a, b, c\}$ 且 $C = \{Q, P\}$，那么 $A \times B \times C$ 将包含所有可能的组合，如 $(1,a,Q)$, $(1,a,P)$, $(2,a,Q)$, $(2,a,P)$, $\ldots$, $(2,c,P)$。

关系 (Relations)

二元关系 (Binary relations)

在数学中，二元关系（Binary relations）是集合论和逻辑的基本概念，它描述了两个元素之间的关系。定义: 如果 $A$ 和 $B$ 是两个集合，那么在 $A$ 与 $B$ 上的一个二元关系 $R$ 是集合 $A \times B$ 的一个子集，即 $R \subseteq A \times B$。如果一个有序对 $(a, b) \in R$，我们说 $a$ 和 $b$ 之间存在关系 $R$，记作 $aRb$。这意味着关系 $R$ 是所有满足关系的有序对 $(a, b)$ 的集合，其中 $a$ 是集合 $A$ 中的元素，$b$ 是集合 $B$ 中的元素。

集合上的关系 (Relations on a Set)

“二元关系（Binary Relations）”和“集合上的关系（Relations on a Set）”这两个概念在数学中都是用来描述元素之间关系的，但它们有一些区别：

定义范围：
二元关系：它是定义在两个集合之间的关系。如果有两个集合 $A$ 和 $B$，那么从 $A$ 到 $B$ 的二元关系是 $A \times B$（即 $A$ 和 $B$ 的笛卡尔积）中的一部分。这意味着二元关系涉及两个可能不同的集合。
集合上的关系：这是定义在单个集合内部的元素之间的关系。对于一个集合 $A$，$A$ 上的关系是 $A \times A$ 的子集。这里，关系完全局限于一个集合内部的元素。

例子：
二元关系的例子：考虑集合 $A = \{1, 2, 3\}$ 和集合 $B = \{a, b\}$。一个从 $A$ 到 $B$ 的二元关系可能是 $\{(1, a), (2, b)\}$。
集合上的关系的例子：在集合 $A = \{1, 2, 3\}$ 上的一个关系可能是 $\{(1, 1), (2, 2), (3, 3)\}$，这是一个等价关系。

特殊性质：
二元关系：可以具有如函数性（functional）、左全性（left-totality）或右全性（right-totality）等特殊性质，这些性质关注的是关系如何连接两个不同的集合。
集合上的关系：通常关注的是等价关系或偏序关系这样的性质，这些性质关注的是集合内部元素之间的相互关系。

总之，二元关系强调的是两个可能不同集合之间的关系，而集合上的关系专注于单一集合内部的元素之间的关系。

表示关系 (Representing Relations)

有向图 (Directed graph): 集合 $A = \{1, 2, 3, 4\}$，关系 $R$ 包含元素对 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 1)$、$(2, 2)$、$(2, 4)$、$(3, 3)$。 有向图通过“点和箭头”来表示这些关系，其中每个点代表集合中的一个元素，箭头代表元素之间的关系。例如，箭头从点 1 指向点 2 表示 $(1, 2)$ 在关系 $R$ 中。

0-1 矩阵 (0-1 matrix): 0-1 矩阵是表示二元关系的另一种方法。矩阵的行和列对应集合 $A$ 中的元素，如果元素 $(i, j)$ 在关系 $R$ 中，则在矩阵的第 $i$ 行第 $j$ 列的位置上放一个 1，否则放一个 0。 例如，矩阵第一行第二列的 1 表示 $(1, 2)$ 在关系 $R$ 中。 幻灯片中展示了三种不同的矩阵，这说明我们可以选择任何顺序来列出集合 $A$ 的元素，但必须在矩阵的行和列中使用相同的顺序。

集合中元素间关系的图形和代数表示，是理解集合论和离散数学中关系概念的重要基础。

关系的性质 (Properties of Relations)

关系可以有多种性质，包括但不限于： - 自反性（Reflexive）：如果对于所有 $a \in A$，都有 $aRa$，则 $R$ 是自反的。
- 对称性（Symmetric）：如果对于所有 $a, b \in A$，$aRb$ 意味着 $bRa$，则 $R$ 是对称的。
- 反对称性（Antisymmetric）：如果对于所有 $a, b \in A$，$aRb$ 和 $bRa$ 同时成立意味着 $a = b$，则 $R$ 是反对称的。
- 传递性（Transitive）：如果对于所有 $a, b, c \in A$，$aRb$ 和 $bRc$ 同时成立意味着 $aRc$，则 $R$ 是传递的。

自反关系 (Reflexive Relations)

自反性 (Reflexive): 有向图 (Directed graph) 上的每个点都要有 loop. Every point loops.
一个二元关系 $R$ 在集合 $A$ 上是反射性的，如果对于集合 $A$ 中的每一个元素 $a$，都有 $(a, a)$ 在关系 $R$ 中，即每个元素都与自身在关系中。
例如，集合 $A = \{1, 2, 3\}$ 上的等于关系 = 是反射性的，因为 $(1, 1)$、$(2, 2)$、$(3, 3)$ 都在关系中。

非自反性 (Not Reflexive): 有向图 (Directed graph) 上有 有loop的点 和 没loop的点
如果一个二元关系 $R$ 在集合 $A$ 上至少有一个元素 $a$，使得 $(a, a)$ 不在关系 $R$ 中，则称 $R$ 是非反射性的。
这意味着关系不满足反射性的要求，但也不一定满足无反射性的定义。它可能对某些元素是反射的，对另一些则不是。
例如，如果有关系 $R$ 定义在集合 $A = \{1, 2, 3\}$ 上，并且 $R = \{(1, 1), (2, 2)\}$，则 $R$ 是非反射性的，因为它没有包括 $(3, 3)$。 如果至少有一个元素不与自己相关联，则关系不是自反的。

反自反性 (Irreflexive): 有向图 (Directed graph) 上的每个点都没有 loop.
一个二元关系 $R$ 在集合 $A$ 上是无反射性的，如果对于集合 $A$ 中的所有元素 $a$，$(a, a)$ 都不在关系 $R$ 中。
也就是说，没有任何元素与自身在该关系中。
例如，小于关系 $<$ 就是无反射性的，因为没有任何元素小于它自己。

在数学和逻辑中，这些概念对于定义和分析关系结构非常重要，它们帮助我们理解集合元素之间的内在联系。

对称关系 (Symmetric Relations)

对称性 Symmetric: 有向图 (Directed graph) 上任意两点之间只要有箭头 (arrow), 则箭头一定是双向的 (bidirectional). 当然没有要求任意两点之间必须有箭头. 每个单独的点是否有 loop 没有要求。

非对称性 Not Symmetric: 有向图 (Directed graph) 上任意两点之间的箭头里，有单向的 (unidirectional)，也有双向的。 当然没有要求任意两点之间必须有箭头。每个单独的点是否有 loop 没有要求。

反对称性 Antisymmetric: 有向图 (Directed graph) 上任意两点之间只要有箭头，则箭头一定是单向的 (unidirectional)。当然没有要求任意两点之间必须有箭头。每个单独的点是否有 loop 没有要求。

对称和反对称不是对立关系。 $R = \{(1,1),(2,2),(3,3)\}$ 在 $\{1,2,3\}$ 上既是对称也是反对称的。

传递关系 (Transitive Relations)

如果对于所有 $a, b, c \in A$，$aRb$ 和 $bRc$ 同时成立意味着 $aRc$，则 $R$ 是传递的。如果又有 $cRd$，则一定有 $aRd$。$R = \{(a, b)\}$ 也是传递的。$R = \{(1, 1), (1, 2), (2, 1)\}$ 不是传递的，因为没有 $(2, 2) \in R$。$\forall R$ 是 either transitive or not transitive 的。

传递闭包 (Transitive Closure)

传递闭包（Transitive Closure）是集合论和图论中的一个概念，它是关于二元关系传递性的扩展。如果你有一个二元关系，传递闭包将是最小的传递关系集合，包含原来的关系并且闭合于传递性。

在更直观的语言中，如果你想从一个关系 $R$ 出发，构建一个新的关系，使得只要 $R$ 里有 $(a, b)$ 和 $(b, c)$ 这样的元素对，新的关系就包含 $(a, c)$ 对，那么这个新的关系就是 $R$ 的传递闭包。

传递闭包可以通过多种方式计算，比如使用矩阵乘法在图论中，或者利用逻辑推理在集合论中。在有向图中，传递闭包相当于添加足够的箭头，使得如果存在一条从节点 $a$ 到 $b$、从 $b$ 到 $c$ 的路径，则必须存在一条直接从 $a$ 到 $c$ 的路径。例如，如果有一个关系 $R = \{(a, b), (b, c)\}$，那么 $R$ 的传递闭包将包括这些元素对，以及因为传递性添加的 $(a, c)$。

在计算机科学中，特别是在数据库和信息检索领域，传递闭包用来推断数据之间可能的连接关系，比如社交网络中的朋友的朋友，或者网络中可达的节点等。

假设 $R$ 是在集合 $A$ 上定义的一个二元关系。$R$ 的传递闭包是包含 $R$ 且是在 $A$ 上最小的传递关系。传递闭包用 $R^*$ 表示。如果 $R$ 本身已经是传递的 (transitive)，那么 $R^* = R$。

如何定义 $ R^* $：
- 基础步骤：所有在 $ R $ 中的元素对都在 $ R^* $ 中，即 $ R \subseteq R^* $。
- 递归步骤：如果 $ (a, b) $ 和 $ (b, c) $ 在 $ R^* $ 中，那么 $ (a, c) $ 也必须在 $ R^* $ 中。通过这种方式，我们逐步添加缺失的元素对来构建传递闭包。

沃舍尔算法 (Warshall's Algorithm)

沃舍尔算法（Warshall's Algorithm）是一种计算给定有向图的传递闭包的算法。它用于确定图中的所有顶点对之间是否存在路径。这个算法是以步骤方式逐渐构建传递闭包的0-1邻接矩阵。这里是沃舍尔算法的一个简化的描述：

  1. 初始化：从图的当前邻接矩阵开始，即矩阵 $R$。如果节点 $i$ 有一条边指向节点 $j$，则矩阵的 $R[i][j]$ 项为1，否则为0。

  2. 迭代更新：对于图中的每一个节点 $k$，重复以下步骤：对于每一对节点 $i$ 和 $j$，如果 $R[i][k]$ 和 $R[k][j]$ 都为1（意味着从 $i$ 到 $k$ 和从 $k$ 到 $j$ 都存在路径），则将 $R[i][j]$ 设置为1。

  3. 迭代完成：经过 $n$ 次迭代后（其中 $n$ 是图中节点的数量），矩阵 $R$ 变为 $R^*$，即传递闭包的邻接矩阵，表示图中所有节点对之间的可达性。

沃舍尔算法的一个关键特性是它是动态的，每次考虑一个节点作为中间节点，逐渐扩展可达性。算法结束时，如果 $R^*$[i][j] 为1，则意味着存在从节点 $i$ 到节点 $j$ 的路径。沃舍尔算法特别适用于稀疏图，因为它避免了不必要的计算。这个算法在计算复杂度上是 $O(n^3)$。

等价关系 (Equivalence Relations)

等价关系（Equivalence Relations）是数学中一种重要的关系类型，用于描述元素之间的一种等价性质。等价关系在集合上定义，并且必须满足以下三个条件：

  1. 自反性（Reflexivity）：对于集合中的任何元素 $a$，元素 $a$ 与其自身等价。用数学语言表达就是：对于所有 $a$，都有 $a \sim a$

  2. 对称性（Symmetry）：如果一个元素 $a$ 与另一个元素 $b$ 等价，则 $b$ 也与 $a$ 等价。即，如果 $a \sim b$，则必然有 $b \sim a$

  3. 传递性（Transitivity）：如果元素 $a$ 与 $b$ 等价，且 $b$ 与 $c$ 等价，那么 $a$ 也与 $c$ 等价。换句话说，如果 $a \sim b$ 且 $b \sim c$，那么 $a \sim c$

满足这些性质的关系称为等价关系。等价关系的一个典型例子是数学中的相等关系。例如，如果我们有一个集合包含数字 1, 2, 3，那么相等关系就是一个等价关系，因为每个数字等于自己（自反性），如果一个数字等于另一个数字，那么这两个数字相互等价（对称性），并且如果一个数字等于第二个数字，而第二个数字等于第三个数字，那么第一个和第三个数字也相等（传递性）。

在集合中定义等价关系可以将集合划分为若干个互不相交的子集，这些子集称为等价类。集合中的每个元素都属于且只属于一个等价类。等价类的概念在数学的许多分支中都非常重要，如抽象代数、数理逻辑和集合论等。

  • 同余关系 (Congruence Relation) 也是一种等价关系。

偏序 (Partial Orders)

偏序（Partial Orders）是数学中的一个基本概念，尤其在集合论、抽象代数和计算理论等领域中非常重要。偏序是定义在集合中元素之间的一种关系，它比全序（全序是指集合中的任意两个元素都可以比较，例如实数集上的“小于等于”关系）更加灵活，因为并非集合中的所有元素都必须相互可比。

一个偏序关系必须满足以下三个条件：

  1. 自反性（Reflexivity）
  2. 反对称性（Antisymmetry）
  3. 传递性（Transitivity）

Examples: $\leq, \geq$, and 'divisibility' on $\mathbb{N}^+$

偏序关系广泛应用于计算机科学（如数据结构中的堆）、抽象代数（如格理论）和其他数学分支。通过偏序关系，可以对复杂系统中的元素进行有效的组织和比较。

哈斯图 (Hasse Diagrams)

哈斯图（Hasse Diagrams）是一种用于表示偏序集（partially ordered sets，简称 posets）的图形工具。在偏序集中，元素之间的关系满足自反性、反对称性和传递性。哈斯图通过简洁的视觉方式展示了偏序集中元素之间的关系，特别是在集合的子集、整数的除法或其他任何具有偏序关系的场景中非常有用。

哈斯图的主要特点和绘制原则包括：

  1. 顶点表示：集合中的每个元素都由图中的一个顶点表示。

  2. 边表示顺序关系：如果元素 $a$ 小于元素 $b$（在偏序关系中，记作 $a \leq b$），并且没有第三个元素 $c$ 使得 $a < c < b$，那么在 $a$ 和 $b$ 之间画一条边。这意味着哈斯图中的边表示直接的顺序关系，而不是通过其他元素间接的关系。

  3. 无环和无向：哈斯图是一个无环的无向图。通常，较小的元素被放置在图的底部，较大的元素放置在图的顶部。

  4. 传递简化：在哈斯图中，如果可以通过一系列较短的步骤从一个元素到达另一个元素，则不绘制这两个元素之间的直接边。这是因为偏序关系的传递性意味着这种直接连接是多余的。

通过哈斯图，可以直观地看到一个偏序集的结构，识别出其中的最大元素、最小元素、上界和下界等。这种图形表示在数学的许多领域中都非常有用，如组合数学、格理论和代数结构分析等。

全序 (Total Order)

全序（Total Order），也称为线性序（Linear Order）、简单序（Simple Order）或非严格排序（(Non-Strict) Ordering），是集合上的一种特殊类型的二元关系。这些术语通常在数学的不同领域和上下文中交替使用，但它们指的是相同的概念。全序关系是一种特别强的偏序关系，它不仅满足偏序的所有属性，还具有额外的完全性属性。

全序关系的特点如下：

  1. 自反性（Reflexivity）
  2. 反对称性（Antisymmetry）
  3. 传递性（Transitivity）
  4. 完全性（Totality）：对于集合中的任意两个元素 $a$ 和 $b$，总是有 $aRb \vee bRa$。这意味着集合中的任意两个元素之间存在 1 或 2 种关系 $R$ 的方向

补充

Inclusive or 和 exclusive or 是两种逻辑运算符，它们用来连接两个命题，生成一个复合命题。它们的区别是：

Inclusive or (兼或、包含性或): 表示两个命题中至少有一个为真时，复合命题为真。数学符号 $\vee$，计算机符号 $OR$。缩写 $IOR$ 或 $OR$。 例如，如果 $A$ 表示“明天下雨”，$B$ 表示“明天不下雨”，那么 $A \vee B$ 表示“明天下雨或者不下雨”，这个命题是永真的，因为 $A 和 B$ 中必然有一个为真。

Exclusive or (异或、排他性或): 表示两个命题中只有一个为真时，复合命题为真。数学符号 $\oplus$，计算机符号 $XOR$。缩写 $EOR$ 或 $XOR$。 例如，如果 $A$ 表示“明天下雨”，$B$ 表示“明天晴天”，那么 $A \oplus B$ 表示“明天下雨或者晴天，但不会同时发生”，这个命题是有条件的，因为 $A$ 和 $B$ 中只能有一个为真。