集合论/关系

有序对

为了定义集合上的关系，我们必须有一个有序对的概念，而不是配对公理给出的无序对。为了对有序对有一个严格的定义，我们旨在满足一个重要的性质，即对于集合a,b,c和d中的元素，$(a,b)=(c,d)\iff a=c\ \wedge \ b=d$.

就其本身而言，有许多方法可以定义有序对以满足此属性。然后定义是$(a,b)=\{\{a\},\{a,b\}\}$。（这只是一个定义或约定，对于集合论可能有用。）

定理

$(a,b)=(c,d)\iff a=c\ \wedge \ b=d$

证明

如果$a=c$和$b=d$，则$(a,b)=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=(c,d)$.
现在，如果$(a,b)=(c,d)$，则$\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$。然后$\cap \{\{a\},\{a,b\}\}=\cap \{\{c\},\{c,d\}\}$，所以$\{a\}=\{c\}$和$a=c$.
因此，我们有 $(a,b)=(a,d)$。因此，$\cup \{\{a\},\{a,b\}\}=\cup \{\{a\},\{a,d\}\}$，这意味着 $\{a,b\}=\{a,d\}$。

如果 $a=b$，我们有 $\{b\}=\{b,d\}$，因此，$d\in \{b\}$，所以 $b=d$。

如果 $a\neq b$，请注意 $b\in \{a,d\}$，所以 $b=d$

关系

利用有序对的定义，我们现在引入二元关系的概念。两个集合的笛卡尔积是 $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$，

二元关系最简单的定义是有序对的集合。更正式地说，如果 $z\in R\rightarrow z=(x,y)$ 对于某些x,y，则集合 $\ R\$ 是一个关系。我们可以简化符号并写成 $(x,y)\in R$ 或者简单地 $xRy$。

我们给出一些在谈论关系时使用的有用集合定义。

• 集合A 是源，B 是目标，其中 $R\subset A\times B.$
• 关系R 的定义域定义为 ${\mbox{dom}}\ R=\{x\in A\mid \exists y,(x,y)\in R\}$，或者包含在R 中的有序对的初始成员的集合。
• 关系R 的值域定义为 ${\mbox{ran}}\ R=\{y\in B\mid \exists x,(x,y)\in R\}$，或者包含在R 中的有序对的所有最终成员的集合。
• 域和值域的并集，${\mbox{field}}\ R={\mbox{dom}}\ R\cup {\mbox{ran}}\ R$，称为R的域。
• 如果 ${\mbox{field}}\ R\subseteq X$，则关系R是集合X上的关系。
• R的逆或反关系是集合 $R^{T}=\{(y,x)\mid (x,y)\in R\}$
• 集合E在关系R下的像定义为 $R[E]=\{y\in {\mbox{ran}}\ R\mid \exists x\in E,(x,y)\in R\}$。
• 集合F在关系R下的原像是F在R^T下的像，或者 $R^{T}[F]=\{x\in {\mbox{dom}}\ R\mid \exists y\in F,(x,y)\in R\}$。

亲属关系叔叔和阿姨表明，存在关系父亲和兄弟姐妹的组合。这样的组合表达了相对乘法

我们可以组合两个关系R和S，形成一个关系 $S\circ R=\{(x,z)\mid \exists y,(x,y)\in R\wedge (y,z)\in S\}$。所以 $xS\circ Rz$意味着存在某个y，使得 $xRy\wedge ySz$。

基准二元关系

1. A上的恒等关系，$I_{A}=\{(a,b)\mid a,b\in A,a=b\}$
2. 全关系或集合，其中A的每个元素都与A的每个其他元素相关。符号：，$A\times A$写为 $A^{2}.$

以下属性可能对集合X上的关系R成立，也可能不成立

• 如果 $xRx$对X中的所有x成立，则R是自反的。
• 如果 $xRy$意味着 $yRx$对X中的所有x和y成立，则R是对称的。
• 如果 $xRy$ 和 $yRx$ 同时成立，则意味着对于 X 中的所有 x 和 y，$x=y$。
• 如果 $xRy$ 和 $yRz$ 同时成立，则意味着对于 X 中的所有 x、y 和 z，$xRz$ 成立。
• 如果 R 的定义域是 A，源是
• 如果 xRy 和 xRz 同时成立，则意味着 y = z。
• 既是全关系又是单值关系的关系称为 函数。

异构关系

当 A 和 B 是不同的集合时，该关系称为 异构关系。然后，单个集合 A 上的关系称为 同构关系。

设 U 是给定上下文中的一个论域。根据幂集公理，存在一个包含所有 U 子集的集合，称为 U 的幂集，记为 ${\mathcal {P}}(U).$

集合成员关系 $x\ \in \ A,\ \ A\subseteq U$ 是一个常用的异构关系，其中定义域是 U，值域是 ${\mathcal {P}}(U).$

集合成员关系的逆关系用反射成员符号表示： $A\ \ni \ x.$

作为一个练习，证明从 A 到 B 的所有关系都是 $A\times B$ 的子集。

函数

定义

函数可以被定义为一种特殊的关联关系。我们定义一个偏函数 $f:X\rightarrow Y$ 作为从集合 $X$ 到另一个集合 $Y$ 的某种映射，它为每个 $x\in X$ 最多 映射一个 $y\in Y$。或者，f 是函数当且仅当 $f\circ f^{-1}\subseteq I_{Y}$

如果对于每个 $x\in X$，$f$ 正好 映射一个 $y\in Y$，那么 $f$ 被称为函数。在讨论函数时，通常使用以下定义。

• 如果 $f\subseteq X\times Y$ 并且 $f$ 是一个函数，那么我们可以用 $f:X\to Y$ 来表示它。集合 $X$ 被称为定义域，集合 $Y$ 被称为值域。
• 对于函数 $f:X\to Y$，元素 $x\in X$ 的像是 $y\in Y$，使得 $f(x)=y$。或者，我们可以说 $y$ 是 $f$ 在 $x$ 处取值。
• 对于一个函数 $f:X\to Y$，集合 $A$ 在 $X$ 中的 _像_ 是集合 $\{y\in Y:f(x)=y{\mbox{ for some }}x\in A\}$。这个集合用 $f(A)$ 表示。注意不要把它与 $f(x)$（对于 $x\in X$）混淆，后者是 $Y$ 中的一个元素。
• 函数 $f:X\to Y$ 的 _值域_ 是 $f(X)$，即所有满足 $f(x)=y$ 的值 $y\in Y$，其中可以找到一个 $x\in X$。
• 对于一个函数 $f:X\to Y$，集合 $B$ 在 $Y$ 中的 _原像_ 是集合 $\{x\in X:f(x)\in B\}$。它用 $f^{-1}(B)$ 表示。

函数的性质

一个函数 $f:X\rightarrow Y$ 被称为满射或映上，如果对于每个 $y\in Y$，都存在一个 $x\in X$ 使得 $f(x)=y$。很容易证明一个函数是满射的充要条件是其陪域等于其值域。它被称单射或一对一，如果不同的 $X$ 元素被映射到不同的 $Y$ 元素，也就是说 $f(x)=f(y)\Rightarrow x=y$。既是单射又是满射的函数直观地称为双射。

函数的复合

给定两个函数 $f:X\rightarrow Y$ 和 $g:Y\rightarrow Z$，我们可能对先对某个 $x\in X$ 求f的值，然后对 $f(x)$ 求g的值感兴趣。为此，我们定义这两个函数的复合，记作 $g\circ f$，定义为

$(g\circ f)(x)=g(f(x))$

注意，这两个函数的复合将 $X$ 中的元素映射到 $Z$ 中的元素，因此我们会写成 $g\circ f:X\rightarrow Z$。

函数的反函数

如果存在一个函数 $g:Y\rightarrow X$ 使得对于 $f:X\rightarrow Y$，$g\circ f=I_{X}$，我们称 $g$ 为 $f$ 的左逆。如果存在一个 $f$ 的左逆，我们说 $f$ 是左可逆的。类似地，如果存在一个函数 $h:Y\rightarrow X$ 使得 $f\circ h=I_{Y}$，那么我们称 $h$ 为 $f$ 的右逆。如果存在这样的 $h$，我们说 $f$ 是右可逆的。如果存在一个既是 $f$ 的左逆又是 $f$ 的右逆的元素，我们称这样的元素为 $f$ 的逆，并用 $f^{-1}$ 表示。注意不要将它与 f 的原像混淆；f 的原像总是存在的，而逆可能不存在。以下定理的证明留作习题。

定理： 如果一个函数既有左逆 $g$ 也有右逆 $h$，那么 $g=h=f^{-1}$。

定理： 一个函数可逆当且仅当它是双射的。