逻辑与公理化集合论(03)：序偶、直积、关系和函数
为了引出关系和函数的概念, 首先要继续介绍 ZF 公理系统, 在公理系统中构造序偶和两集合的直积, 并证明直积在ZF公理系统中是集合.\(\newcommand{\R}{\mathbb{R}}\newcommand{\C}{\mathbb{C}}\newcommand{\K}{\mathbb{K}}\newcommand{\exist}{\exists}\newcommand{\and}{\land}\newcommand{\or}{\lor}\newcommand{\set}[1]{\left\{ #1 \right\}}\renewcommand{\empty}{\varnothing}\newcommand{\abs}[1]{\left| #1 \right|}\renewcommand{\subset}{\subseteq}\renewcommand{\supset}{\supseteq}\)
无序偶, 序偶和直积
Axiomatic System ZF公理系统的4、5条
- 配对公理: 对任意\(X\)和\(Y\), 存在称为"\(X\)和\(Y\)的无序偶"的集合\(Z\), 其元素恰好只有\(X\)和\(Y\)
\[ \forall X\forall Y\exist Z \forall z (z\in Z\Leftrightarrow z=X\or z=Y) \]
- 幂集公理: 对于集合\(X\), 存在称为"\(X\)的幂集"的集合\(\mathcal{P}(X)\), 其元素是且仅是\(X\)的子集
\[ \forall X\exist\mathcal{P}(X)\forall Y(Y\in\mathcal{P}(X)\Leftrightarrow Y\subset X) \]
配对公理已经引入了无序偶\(\set{X,Y}\), 当\(X=Y\)时它只含一个元素. 还可以引入有序偶的概念
Def 序偶
由\(X\)和\(Y\)产生的如下集合是 序偶, 记作\((X,Y)\) \[ (X,Y):=\set{\set{X},\set{X,Y}} \]
容易证明, 这种序偶构造具有唯一性, 即如果\((X,Y)=(Z,W)\), 则一定有\(X=Z\and Y=W\).
序偶和无序偶的区别是, \((X,Y)=(Y,X)\)当且仅当\(X=Y\)成立, 而\(\set{X,Y}=\set{Y,X}\)恒成立.
现在可以考虑构造直积了. 从朴素的角度讲, 直积应该这么构造 \[ X\times Y=\set{(x,y)|x\in X\and y\in Y} \] 分离公理要求从母集出发, 添加一些性质来构造合法的集合. 现在需要找出\(X\times Y\)的这样一个母集合\(Z\).
幂集公理告诉我们, 幂集一定存在, 如果\(x\)和\(y\)都属于某个集合\(Z\), 则\(\set{x}\)和\(\set{x,y}\)是其子集, 因而属于\(Z\)的幂集: \[ x\in Z\and y\in Z \Rightarrow \set{x}\in\mathcal{P}(Z)\and\set{x,y}\in\mathcal{P}(Z) \] 进一步地, \(\set{x}\)和\(\set{x,y}\)又可以看作两个元素同属于新集合\(\mathcal{P}(Z)\), 因此 \[ \set{x}\in \mathcal{P}(Z)\and \set{x,y}\in \mathcal{P}(Z)\Rightarrow \set{\set{x},\set{x,y}}\in \mathcal{P}(\mathcal{P}(Z)) \] 根据并集公理(参照上一节), \(X\cup Y\)一定存在, 并且满足这里的\(Z\)要求. 任何满足\(x\in X\and y\in Y\)的序偶\((x,y)\)显然满足\(x\in X\cup Y\and y\in X\cup Y\), 从而序偶\((x,y)\)也在\(\mathcal{P}(\mathcal{P}(X\cup Y))\)中. 换言之, 可以利用分离公理构造严格定义的直积.
Def 集合的直积
两个集合\(X\)和\(Y\)的 直积 是这样一个集合(记作\(X\times Y\)), 它的元素是且仅是这样的序偶: 序偶的第一个元素来自\(X\), 第二个元素来自\(Y\). \[ X\times Y:=\set{(x,y)\in\mathcal{P}(\mathcal{P}(X\cup Y))| x\in X\and y\in Y} \]
关系和函数
有了直积就可以定义关系了, 它是其定义域和陪域的直积的子集; 而函数会作为一种单值关系被着重强调.
Def 关系
设\(X\)和\(Y\)为集合, 关系 是\(X\times Y\)的子集, 记作\(\mathcal{R}\). 且 \[ \forall x(x\in X\Rightarrow\exist y(y\in Y\and(x,y)\in \mathcal{R})) \] 其中\(X\)叫做关系\(\mathcal{R}\)的 定义域, 也记作\(\text{dom}(\mathcal{R})\); \(Y\)叫做关系\(\mathcal{R}\)的 陪域, 从而称\(R\)是"定义域为\(X\), 陪域为\(Y\)的关系". 常常把\((x,y)\in\mathcal{R}\)记作\(x\mathcal{R}y\), 并说"\(x\)和\(y\)具有关系\(\mathcal{R}\)".
在关系\(\mathcal{R}\)之下集合\(A\)的 像 是\(Y\)的一个子集, 记作\(\mathcal{R}[A]\), 其定义为 \[ \mathcal{R}[A]:=\set{y\in Y|\exist x(x\in A\and (x,y)\in\mathcal{R})} \] 如果\(A\)取定义域\(X\), 则像特别地称作 值域, 记作\(\mathcal{R}[X]\)或者\(\text{range}(\mathcal{R})\).
这里为了和后文的函数定义保持一致性, 将\(X\)直接取为了定义域. 常见的定义是\(\mathcal{R}\subset X\times Y\), 其中定义域是\(X\)的子集. 显然, 无论哪种定义, 值域是陪域\(Y\)的一个子集.
如果一个关系\(\mathcal{R}\subset X\times X\), 且满足自反、对称和传递性, 则称此关系为\(X\)上的 等价关系. 等价关系可以用\(\sim\)来特别地表示.
为了引出函数的逆, 需要先定义什么是关系的逆.
Def 关系的逆
关系\(\mathcal{R}\)的逆 是\(\mathcal{R}\)的序偶被颠倒顺序后的新序偶的集合, 也是另一个关系, 记作\(\mathcal{R}^{-1}\). 即 \[ \mathcal{R}^{-1}:=\set{(y,x)\in \text{range}(\mathcal{R})\times\text{dom}(\mathcal{R})|(x,y)\in \mathcal{R}} \]
为了定义函数, 需要对关系作出一些限制. 例如单值性.
Def 函数
函数 是一种特殊的关系, 其定义域的任意元素在陪域存在唯一对应. 即
存在性: \(\forall x(x\in X\Rightarrow\exist y(y\in Y\and(x,y)\in f))\)
唯一性: \(\forall x\forall y_1\forall y_2((x,y_1)\in f\and (x,y_2)\in f\Rightarrow y_1=y_2)\)
映射 是函数\(f\)、定义域\(X\)和陪域\(Y\)的三元组\(((f,X),Y)\), 记作\(f:X\to Y\), 读作"\(f\)是\(X\)到\(Y\)的函数". 在定义域和陪域明确的情况下, 也常常称\(f\)本身为映射. 通常称定义域的元素\(x\)为 自变量, 因为此时\(y\)由\(x\)和\(f\)唯一地决定, 也常将\(y\)记作\(f(x)\), 叫做 因变量, 也说\(y\)是\(x\)的 像, \(x\)是\(y\)的一个 原像. 与此同时集合\(A\)的像概念仍然保留, 记作\(f[A]\): \[ f[A]:=\set{y\in Y|\exist x(x\in A\and y=f(x))} \]
自然, 函数的逆关系也就从关系的逆关系中继承下来. 但应该指出, 函数\(f\)的逆\(f^{-1}\)一般地不是函数, 而只是普通的关系. 如果希望\(f^{-1}\)仍是函数, 必要条件是\(f\)具有如下性质: \[ \forall x_1\forall x_2(f(x_1)=f(x_2)\Rightarrow x_1=x_2) \] 具有这样性质的映射称作 单射. 单射只能保证任意\(y\in Y\)至多有一个原像, 不保证原像的存在性. 为了确保其存在性, 需要令\(f[X]=Y\), 即值域等于陪域. 具有这样性质的映射称为 满射. 换言之, 单射确保\(f^{-1}\)在\(Y\)上有定义的子集(\(f\)的值域)上保持单值性, 而满射确保\(f^{-1}\)的定义扩张到整个陪域\(Y\). 如果\(f\)既是单射又是满射, 称\(f\)为 双射. 双射才是函数的逆仍为函数的充要条件.