关系与映射
定义:由两个具有给定次序的和所组成的序列称为序偶(Ordered Pair),记作.其中,称为第1分量,称为第2分量。
当时,
的充分必要条件是:
, .
设是任意两个集合,用中元素为第1分量,中元素为第2分量构成序偶。
这样的序偶组成的集合称为和的笛卡尔积(Cartesian Product).
例如:
花色 大小的笛卡尔积是:
, , , , , , , , ,, .
由个具有给定次序的个体组成的序列,称为有序元组, 记作: , 其中称为第个分量。
当且仅当
设是任意给定的个集合,若有序元组的第1分量取自集合,第2分量取自,,第分量取自,则由所有这样的有序元组组成的集合称为集合的笛卡儿积,并用表示。
即
求证: 成立。
证明:对任意的, ,有:
所以.
对任意的,,有:
所以.
综上:
如果一个集合的全部元素都是序偶,则称这个集合为一个二元关系,记作.
例:设,定义
即:
表示集合上元素的大于关系。
设是任意两个集合,的任意一个子集所定义的二元关系称为从集合到集合的一个二元关系。
当时,称为上的二元关系。
例:设,则:
的任何子集都是一个二元关系。
设是任意给定的集合,笛卡儿积的任意一个子集称为, , , 上的一个元关系。特别的,当时,称为上的元关系。
设和是任意给定的两个集合, 是从到的二元关系。若对于任意的,存在唯一的,使得,则称关系为从到的一个函数或映射, 记作.
若有,则称是原像(或自变量),称为作用下的像。通常用表示.
二元关系和函数的区别如下:
(1)函数的定义域必须等于.二元关系的定义域可以是,也可以是的一个子集。
(2)作为二元关系,一个可以对应多个不同的.而作为函数,一个只能对应一个.
定理:设都是有限集,,则从到共有个不同的函数。
通常用表示从到的所有不同函数构成的集合,即:
对于函数
(1)若,则称是满射 (Surjection).
(2)对任意的,当时必有,则称是单射 (Injection).
(3)若既是满射的又是单射的,则称为双射 (Bijection).
例:以下是4个不同类型的函数:
例:设,定义:
, (单射但不是满射),那么是到的关系是的逆关系。
,所以并不是函数。
设是一个双射函数,称的逆关系为的逆函数 (Inverse Function),记作.
若的逆函数存在,则称是可逆的。
设有函数,则
称为和的复合函数(Composition).
即.
求证: 如果都是满射,那么也是满射。
证明: 设是的任意元素,因为是满射,所以存在使得.
又因为是满射,所以存在使得.
于是,所以是满射。