集合论—笛卡尔积与二元关系

笛卡尔积

笛卡尔积的定义

设$A$、$B$为集合，用$A$中的元素作为第一元素，$B$中的元素作为第二元素，构成有序对。所有这样的有序对组成的集合称作$A$和$B$的笛卡尔积，记作$A\times B$.$$A\times B=\{<x,y>|x\in A,y\in B\}$$由排列组合关系可知，若$A$中有$m$个元素，$B$中有$n$个元素，则$A\times B$或$B\times A$中有$mn$个元素。

例如，若$A=\{a,b\}$，$B=\{0,1,2\}$，则 $$A\times B=\{<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>\}$$$$B\times A=\{<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>\}$$

用图表表示：

集合A值集合B值元素一a元素一0元素二b元素二1元素三2

则可得：

$A\times B$第一元素(A)第二元素(B)$<a,0>$a0$<a,1>$a1$<a,2>$a2$<b,0>$b0$<b,1>$b1$<b,2>$b2

$n$阶笛卡尔积： 设$A_1,A_2,...,A_n$($n⩾2$)是集合，它们的$n$阶笛卡尔积记作$A_1\times A_2\times ,...,\times A_n$，其中$$A_1\times A_2\times ,...,\times A_n=\{<x_1,x_2,...,x_n>|x_1\in A_1\vee x_2\in A_2\vee ...\vee x_n\in A_n\}$$当$A_1=A_2=...=A_n$时，可将它们的$n$阶笛卡尔积简记为$A^n$ 例如，$A=\{a,b\}$，则$$A^3=\{<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,a>,<b,b,a>,<b,b,b>\}$$

笛卡尔积运算的性质：

若$A$、$B$中有一个空集，则它们的笛卡尔积是空集，即$$\varnothing \times B=A\times \varnothing =\varnothing$$当$A̸=B$且$A$、$B$都不是空集时，有$$A\times B̸=B\times A$$当$A$、$B$、$C$都不是空集时，有$$(A\times B)\times C̸=A\times (B\times C)$$笛卡尔积运算对交和并满足分配律$$A\times (B\cup C)=(A\times B)\cup (A\times C)$$$$(B\cup C)\times A=(B\times A)\cup (C\times A)$$$$A\times (B\cap C)=(A\times B)\cap (A\times C)$$$$(B\cap C)\times A=(B\times A)\cap (C\times A)$$

有序对、有序$n$元组、元素的定义

有序对： 由两个元素$x$和$y$按一定的顺序排列成的二元组称作一个有序对或序偶，记作$<x,y>$，平面直角坐标系中的坐标就是一个典型的有序对。 有序对的特征：

当$x̸=y$时，$<x,y≯=<y,x>$两个有序对相等($<x,y>=<u,v>$)的充分必要条件是$x=u$且$y=v$.

有序$n$元组： 一个有序$n$元组($n⩾3$)是一个有序对，其中第一个元素是一个有序$n-1$元组，一个有序$n$元组记作$<x_1,x_2,...,x_n>$，即$$<x_1,x_2,...,x_n>=<<x_1,x_2,...,x_{n-1}>,x_n>$$

元素： 在一个有序对$<x,y>$中，$x$是有序对的第一元素，$y$是有序对的第二元素。

二元关系

定义一： 如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作$R$。对于二元关系$R$，若$<x,y>\in R$，则记作$xRy$；若$<x,y>\notin R$，则记作$x̸Ry$

定义二： 设$A$、$B$为集合，$A\times B$的任何子集所定义的二元关系称作从 $A$到$B$的二元关系，特别当$A=B$时，则称作 $A$上的二元关系

关系上的计数及特殊关系：

通常集合$A$上不同关系的数目依赖于$A$的基数(即集合中元素的个数)，若$|A|=n$，那么$|A\times A|=n^2$，$A\times A$的子集有$2^{n^2}$个。

$A\times A$上的每一个子集就代表一个$A$上的关系，即表示$A$上有$2^{n^2}$个不同的二元关系，其中有三种特殊的关系，假设有集合$A=\{1,2\}$，则

空关系$$\varnothing =\{\varnothing \}$$全域关系$$E_A=\{<1,1>,<1,2>,<2,1>,<2,2>\}$$恒等关系$$I_A=\{<1,1><2,2>\}$$

关系矩阵和关系图：

设$A=\{x_1,x_2,...,x_n\}$，$R$是$A$上的关系，令$$r_{ij}=\{\begin{array}{ll}1,& \text{if xiRxj}\\ 0,& \text{if xi̸Rxj}\end{array}$$则$R$的关系矩阵为：$$(r_{ij})=\left[\begin{array}{cccc}{r}_{11}& r_{12}& \cdots & r_{1n}\\ r_{21}& r_{22}& \cdots & r_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ r_{n1}& r_{12}& \cdots & r_{1n}\end{array}\right]$$ 设$V$是一个顶点集，$E$是一个有向边集，令$V=A=x_1,x_2,...,x_n$。若$x_{i}R{x}_j$，则$x_i$到$x_j$的有向边$<x_i,x_j>\in E$，那么$G=<V,E>$就是$R$的关系图。