关系与映射

定义:由两个具有给定次序的$x$$x$和$y$$y$所组成的序列称为序偶(Ordered Pair),记作$⟨x,y⟩$$\langle x,y\rangle$.其中,$x$$x$称为第1分量,$y$$y$称为第2分量。

当$x\ne y$$x\neq y$时, $⟨x,y⟩\ne ⟨y,x⟩$$\langle x,y\rangle\neq\langle y, x\rangle$

$⟨x,y⟩=⟨u,v⟩$$\langle x,y\rangle=\langle u, v\rangle$的充分必要条件是: $x=u$$x=u$, $y=v$$y=v$.

设$A,B$$A,B$是任意两个集合,用$A$$A$中元素为第1分量,$B$$B$中元素为第2分量构成序偶。 这样的序偶组成的集合称为$A$$A$和$B$$B$的笛卡尔积(Cartesian Product).

$A\times B=\{⟨x,y⟩|x\in A,y\in B\}.$$A\times B=\{\langle x,y\rangle |x\in A,y\in B\}.$

例如: 花色 $\times$$\times$ 大小的笛卡尔积是： $\{(\mathrm{♢},A)$$\{(\diamondsuit, A)$, $(\mathrm{♢},K)$$(\diamondsuit, K)$, $(\mathrm{♢},Q)$$(\diamondsuit, Q)$, $(\mathrm{♢},J)$$(\diamondsuit, J)$, $(\mathrm{♢},10)$$(\diamondsuit, 10)$, $\cdots \cdots$$\cdots\cdots$, $(\mathrm{♡},6)$$(\heartsuit, 6)$, $(\mathrm{♡},5)$$(\heartsuit, 5)$, $(\mathrm{♡},4)$$(\heartsuit, 4)$,$(\mathrm{♡},3)$$(\heartsuit, 3)$, $(\mathrm{♡},2)\}$$(\heartsuit, 2)\}$.

由$n$$n$个具有给定次序的个体$a_1,a_2,\cdots ,a_n$$a_1,a_2,\cdots,a_n$组成的序列,称为有序$n$$n$元组, 记作: $⟨a_1,a_2,\cdots ,a_n⟩$$\langle a_1,a_2,\cdots,a_n\rangle$, 其中$a_i$$a_i$称为第$i$$i$个分量。

$⟨a_1,a_2,\cdots ,a_n⟩=⟨b_1,b_2,\cdots ,b_n⟩$$\langle a_1,a_2,\cdots,a_n\rangle=\langle b_1,b_2,\cdots,b_n\rangle$

当且仅当

$a_i=b_i(i=1,2,\cdots ,n).$$a_i=b_i\,(i=1, 2,\cdots,n).$

设$A_1,A_2,\cdots ,A_n$$A_1,A_2,\cdots,A_n$是任意给定的$n$$n$个集合,若有序$n$$n$元组$⟨a_1,a_2,\cdots ,a_n⟩$$\langle a_1,a_2,\cdots,a_n\rangle$的第1分量取自集合$A_1$$A_1$,第2分量取自$A_2$$A_2$,$\cdots$$\cdots$,第$n$$n$分量取自$A_n$$A_n$,则由所有这样的有序$n$$n$元组组成的集合称为集合$A_1,A_2,\cdots ,A_n$$A_1,A_2,\cdots,A_n$的笛卡儿积,并用$A_1\times A_2\times \cdots \times A_n$$A_1\times A_2\times\cdots\times A_n$表示。 即 $A_1\times A_2\times \cdots \times A_n=\{⟨a_1,a_2,\cdots ,a_n⟩$$A_1\times A_2\times\cdots\times A_n=\{\langle a_1,a_2,\cdots,a_n\rangle$ $|a_i\in A_i,i=1,2,\cdots ,n\}.$$|a_i\in A_i, i=1,2,\cdots,n\}.$

求证: $A\times (B\cup C)=(A\times B)\cup (A\times C)$$A\times (B\cup C)=(A\times B)\cup (A\times C)$ 成立。

证明:对任意的$⟨x,y⟩$$\langle x,y\rangle$, $⟨x,y⟩\in A\times (B\cup C)$$\langle x,y\rangle\in A\times (B\cup C)$,有: $x\in A\wedge y\in (B\cup C)$$x\in A\wedge y\in (B\cup C)$ $x\in A\wedge (y\in B\vee y\in C)$$x\in A\wedge (y\in B\vee y\in C)$ $(x\in A\wedge y\in B)\vee (x\in A\wedge y\in C)$$(x\in A\wedge y\in B)\vee (x\in A\wedge y\in C)$ $⟨x,y⟩\in A\times B\vee ⟨x,y⟩\in A\times C$$\langle x,y\rangle\in A\times B\vee \langle x,y\rangle\in A\times C$ $⟨x,y⟩\in (A\times B)\cup (A\times C)$$\langle x,y\rangle\in (A\times B)\cup (A\times C)$ 所以$A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$$A\times (B\cup C)\subseteq(A\times B)\cup (A\times C)$.

对任意的$⟨x,y⟩$$\langle x,y\rangle$,$⟨x,y⟩\in (A\times B)\cup (A\times C)$$\langle x,y\rangle\in (A\times B)\cup (A\times C)$,有: $⟨x,y⟩\in A\times B\vee ⟨x,y⟩\in A\times C$$\langle x,y\rangle\in A\times B\vee \langle x,y\rangle\in A\times C$ $(x\in A\wedge y\in B)\vee (x\in A\wedge y\in C)$$(x\in A\wedge y\in B)\vee (x\in A\wedge y\in C)$ $x\in A\wedge (y\in B\vee y\in C)$$x\in A\wedge (y\in B\vee y\in C)$ $x\in A\wedge y\in (B\cup C)$$x\in A\wedge y\in (B\cup C)$ $⟨x,y⟩\in A\times (B\cup C)$$\langle x,y\rangle\in A\times (B\cup C)$ 所以$(A\times B)\cup (A\times C)\subseteq A\times (B\cup C)$$(A\times B)\cup (A\times C) \subseteq A\times (B\cup C)$.​

综上:$A\times (B\cup C)=(A\times B)\cup (A\times C).$$A\times (B\cup C)=(A\times B)\cup (A\times C).$

如果一个集合的全部元素都是序偶,则称这个集合为一个二元关系,记作$R$$R$.

例:设$A=\{2,3,4\}$$A=\{2,3,4\}$,定义 $R_1=\{⟨x,y⟩|x,y\in A\wedge x>y\}$$R_1=\{\langle x, y\rangle |x,y\in A \wedge x> y\}$ 即: $R_1=\{⟨4,3⟩,⟨4,2⟩,⟨3,2⟩\}$$R_1=\{\langle 4,3\rangle,\langle 4,2\rangle,\langle 3, 2\rangle\}$ 表示集合$A$$A$上元素的大于关系。

设$A,B$$A,B$是任意两个集合,$A\times B$$A\times B$的任意一个子集所定义的二元关系$R$$R$称为从集合$A$$A$到集合$B$$B$的一个二元关系。 当$A=B$$A=B$时,称$R$$R$为$A$$A$上的二元关系。

例:设$A=\{1,2,3\},B=\{a,b\}$$A=\{1,2,3\},B=\{a,b\}$,则: $A\times B=\{⟨1,a⟩,⟨1,b⟩,⟨2,a⟩,$$A\times B=\{\langle 1,a\rangle,\langle 1,b\rangle,\langle 2,a\rangle,$ $⟨2,b⟩,⟨3,a⟩,⟨3,b⟩\}$$\langle 2,b\rangle,\langle 3,a\rangle,\langle 3,b\rangle \}$ $A\times B$$A\times B$的任何子集都是一个二元关系。

设$A_1,A_2,\cdots ,A_n$$A_1,A_2,\cdots,A_n$是任意给定的集合,笛卡儿积$A_1\times A_2\times \cdots \times A_n$$A_1\times A_2\times\cdots\times A_n$的任意一个子集$R$$R$称为$A_1$$A_1$, $A_2$$A_2$, $\cdots$$\cdots$, $A_n$$A_n$上的一个$n$$n$元关系。特别的，当$A_1=A_2=\cdots =A_n=A$$A_1=A_2=\cdots=A_n=A$时,称$R$$R$为$A$$A$上的$n$$n$元关系。

设$A$$A$和$B$$B$是任意给定的两个集合, $f$$f$是从$A$$A$到$B$$B$的二元关系。若对于任意的$x\in A$$x{\in}A$,存在唯一的$y\in B$$y{\in}B$,使得$⟨x,y⟩\in f$${\langle}x,y{\rangle}{\in}f$,则称关系$f$$f$为从$A$$A$到$B$$B$的一个函数或映射, 记作$f:A\to B$$f:A{\rightarrow}B$.

若有$⟨x,y⟩\in f$${\langle}x,y{\rangle}{\in}f$,则称$x$$x$是原像(或自变量),称$y$$y$为$f$$f$作用下$x$$x$的像。通常用$y=f(x)$$y=f(x)$表示$⟨x,y⟩\in f$${\langle}x,y{\rangle}{\in}f$.

二元关系和函数的区别如下:

(1)函数的定义域必须等于$A$$A$.二元关系的定义域可以是$A$$A$,也可以是$A$$A$的一个子集。

(2)作为二元关系,一个$x$$x$可以对应多个不同的$y$$y$.而作为函数,一个$x$$x$只能对应一个$y$$y$.

定理:设$A,B$$A,B$都是有限集,$|A|=m,|B|=n$$|A|=m,|B|=n$,则从$A$$A$到$B$$B$共有$n^m$$n^m$个不同的函数。

通常用$B^A$$B^A$表示从$A$$A$到$B$$B$的所有不同函数构成的集合,即: $B^A=\{f|f:A\to B\}.$$B^A =\{f|f:A{\rightarrow}B\}.$ 对于函数$f:X\to Y$$f:X{\rightarrow}Y$

(1)若$V(f)=Y$$V(f)=Y$,则称$f$$f$是满射 (Surjection).

(2)对任意的$x_1,x_2\in X$$x_1,x_2{\in}X$,当$x_1\ne x_2$$x_1{\neq}x_2$时必有$f(x_1)\ne f(x_2)$$f(x_1){\neq}f(x_2)$,则称$f$$f$是单射 (Injection).

(3)若$f$$f$既是满射的又是单射的,则称$f$$f$为双射 (Bijection).

例:以下是4个不同类型的函数:

$f_1:\{a,b,c,d\}\to \{1,2,3\},$$f_1: \{a,b,c,d\} {\rightarrow}\{1,2,3\},$ $f_1=\{⟨a,1⟩,⟨b,2⟩,⟨c,3⟩,⟨d,3⟩\}$$f_1=\{{\langle}a,1{\rangle},{\langle}b,2{\rangle},{\langle}c,3{\rangle},{\langle}d,3{\rangle}\}$ $f_2:\{a,b,c\}\to \{1,2,3,4\},$$f_2: \{a,b,c\}{\rightarrow}\{1,2,3,4\},$ $f_2=\{⟨a,1⟩,⟨b,2⟩,⟨c,3⟩\}$$f_2=\{{\langle}a,1{\rangle},{\langle}b,2{\rangle},{\langle}c,3{\rangle}\}$ $f_3:\{a,b,c\}\to \{1,2,3\},$$f_3: \{a,b,c\} {\rightarrow}\{1,2,3\},$ $f_3=\{⟨a,1⟩,⟨b,2⟩,⟨c,3⟩\}$$f_3=\{{\langle}a,1{\rangle},{\langle}b,2{\rangle},{\langle}c,3{\rangle}\}$ $f_4:\{a,b,c\}\to \{1,2,3\},$$f_4: \{a,b,c\} {\rightarrow}\{1,2,3\},$ $f_4=\{⟨a,1⟩,⟨b,1⟩,⟨c,3⟩\}$$f_4=\{{\langle}a,1{\rangle},{\langle}b,1{\rangle},{\langle}c,3{\rangle}\}$

例:设$A=\{a,b\},B=\{c,d,e\}$$A=\{a,b\},B=\{c,d,e\}$,定义: $f:A\to B$$f:A{\rightarrow}B$, $f=\{⟨a,c⟩,⟨b,d⟩\}$$f=\{{\langle}a,c{\rangle},{\langle}b,d{\rangle}\}$ (单射但不是满射)，那么$f^{-1}$$f^{-1}$是$B$$B$到$A$$A$的关系是$f$$f$的逆关系。 $f^{-1}=\{⟨c,a⟩,⟨d,b⟩\},$$f^{-1}=\{{\langle}c,a{\rangle},{\langle}d,b{\rangle}\},$

$D(f^{-1})=\{c,d\}\ne B$$D(f^{-1})=\{c,d\} {\neq}B$，所以$f^{-1}$$f^{-1}$并不是函数。

设$f:X\to Y$$f:X{\rightarrow}Y$是一个双射函数,称$f$$f$的逆关系为$f$$f$的逆函数 (Inverse Function),记作$f^{-1}$$f^{-1}$.

若$f$$f$的逆函数$f^{-1}$$f^{-1}$存在,则称$f$$f$是可逆的。

设有函数$f:X\to Y,g:Y\to Z$$f:X{\rightarrow}Y,g:Y{\rightarrow}Z$,则 $g\circ f:X\to Z=\{⟨x,z⟩|x\in X\wedge z\in Z\wedge \mathrm{\exists }y\in Y,y=f(x)\wedge z=g(y)\}$$g{\circ}f:X{\rightarrow}Z=\{{\langle}x,z{\rangle}|x{\in}X{\wedge}z{\in}Z{\wedge}{\exists}y{\in}Y,y=f(x){\wedge}z=g(y)\}$ 称为$f$$f$和$g$$g$的复合函数(Composition). 即$(g\circ f)(x)=g(f(x))$$(g{\circ}f)(x)=g(f(x))$.

求证: 如果$f:X\to Y,g:Y\to Z$$f:X{\rightarrow}Y,g:Y{\rightarrow}Z$都是满射,那么$g\circ f:X\to Z$$g{\circ}f:X{\rightarrow}Z$也是满射。

证明: 设$z$$z$是$Z$$Z$的任意元素,因为$g$$g$是满射,所以存在$b\in B$$b{\in}B$使得$g(y)=z$$g(y)=z$. 又因为$f$$f$是满射,所以存在$a\in A$$a{\in}A$使得$g(x)=y$$g(x)=y$. 于是$(g\circ f)(x)=g(f(x))=z$$(g{\circ}f)(x) = g(f(x)) = z$,所以$g\circ f$$g{\circ}f$是满射。