这里是离散数学集合论的学习笔记qaq
让我们跳过高中部分的知识
一个集合的幂集为该集合所有子集所构成的集合,集合 \(A\) 的幂集记作 \(\mathcal{P}(A)\)。
我们通常将论域内所有元素的集合叫做全集。
集合的运算有:
交运算:\(A \cap B = \{x | x \in A \land x \in B \}\)
并运算:\(A \cup B = \{x | x \in A \lor x \in B \}\)
补运算:\(A - B = \{x | x \in A \land x \notin B \}\)
补集:\(\overline{A} = E - A\)
对称差:\(A \oplus B = (A \cup B) - (A \cap B)\)
显然我们有 \(A - B = A \cap \overline{B}\),那么对称差也可以表示为 \(A \oplus B = (A \cup B) \cap (\overline{A} \cup \overline{B}) = (A \cap \overline{B}) \cup (\overline{A} \cap B)\).
有两个元素 \(x, y\) 按照一定次序组成的二元组称为序偶,记作 \(\langle x, y \rangle\)。
定义两个序偶 \(\langle a, b \rangle, \langle c, d \rangle\) 相等,当且仅当 \(a = c, b = d\)。
我们可以递归定义 \(n\) 元序偶对,即由 \(n\) 个元素 \(a_1, a_2, \cdots, a_n\) 按照次序组成的 \(n\) 元序偶对,\(\langle a_1, a_2, \cdots, a_n \rangle = \langle \langle a_1, a_2, \cdots, a_{n - 1} \rangle, a_n \rangle\)。
我们定义两个集合的笛卡尔积运算,即 \(A \times B = \{\langle x, y \rangle | x \in A \land y \in B \}\)。
通常 \(A \neq B\) 时,\(A \times B \neq B \times A\)。
注意 \(A^n = A^{n - 1} \times A\),注意三元组的定义。即笛卡儿积既没有交换律也没有结合律。
任一序偶的集合确定了一个二元关系 \(R\),\(R\) 中任意序偶 \(\langle x, y \rangle\) 可以记作 \(\langle x, y \rangle \in R\) 或者 \(x R y\),不在 \(R\) 中的任意序偶 \(\langle x, y \rangle\) 可记为 \(\langle x, y \rangle \notin R\) 或者 \(x \not R y\)
其中 \(x\) 所属的集合称为二元关系的前域,记作 \(\operatorname{dom}(R)\),\(y\) 所属的集合称为二元关系的值域,记作 \(\operatorname{ran}(R)\),它们并在一起称作二元关系 \(R\) 的域,记作 \(\operatorname{FLD}(R)\)。
若 \(X, Y\) 为两个集合,笛卡尔积 \(X \times Y\) 的子集称为 \(X\) 到 \(Y\) 的关系。我们将 \(X \times Y\) 的两个平凡子集 \(X \times Y, \varnothing\) 称为全域关系和空关系。当 \(X = Y\) 时,我们将这个关系称为 \(X\) 上的二元关系。