笛卡尔积

笛卡尔积的定义

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

例如，若$A=\{a,b\}$A={a,b}，$B=\{0,1,2\}$B={0,1,2}，则
$A×B=\{&lt;a,0&gt;, &lt;a,1&gt;, &lt;a,2&gt;, &lt;b,0&gt;,&lt;b,1&gt;,&lt;b,2&gt;\}$A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}$B×A=\{&lt;0,a&gt;,&lt;0,b&gt;,&lt;1,a&gt;,&lt;1,b&gt;,&lt;2,a&gt;,&lt;2,b&gt;\}$B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}

$n$n阶笛卡尔积：
设$A_1,A_2,...,A_n$A1​,A2​,...,An​($n\geqslant 2$n⩾2)是集合，它们的$n$n阶笛卡尔积记作$A_1×A_2×,...,×A_n$A1​×A2​×,...,×An​，其中$A_1×A_2×,...,×A_n=\{&lt;x_1,x_2,...,x_n&gt;|x_1\in A_1\lor x_2\in A_2\lor...\lor x_n\in A_n\}$A1​×A2​×,...,×An​={<x1​,x2​,...,xn​>∣x1​∈A1​∨x2​∈A2​∨...∨xn​∈An​}当$A_1=A_2=...=A_n$A1​=A2​=...=An​时，可将它们的$n$n阶笛卡尔积简记为$A^n$An
例如，$A=\{a,b\}$A={a,b}，则$A^3=\{&lt;a,a,a&gt;,&lt;a,a,b&gt;,&lt;a,b,a&gt;,&lt;a,b,b&gt;,&lt;b,a,a&gt;,&lt;b,a,a&gt;,&lt;b,b,a&gt;,&lt;b,b,b&gt;\}$A3={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,a>,<b,b,a>,<b,b,b>}

笛卡尔积运算的性质：

1. 若$A$A、$B$B中有一个空集，则它们的笛卡尔积是空集，即$\emptyset ×B = A ×\emptyset = \emptyset$∅×B=A×∅=∅
2. 当$A\neq B$A̸​=B且$A$A、$B$B都不是空集时，有$A×B\neq B×A$A×B̸​=B×A
3. 当$A$A、$B$B、$C$C都不是空集时，有$(A×B)×C\neq A×(B×C)$(A×B)×C̸​=A×(B×C)
4. 笛卡尔积运算对交和并满足分配律$A×(B\cup C) = (A×B)\cup(A×C)$A×(B∪C)=(A×B)∪(A×C)$(B\cup C)×A=(B×A)\cup(C×A)$(B∪C)×A=(B×A)∪(C×A)$A×(B\cap C) = (A×B)\cap(A×C)$A×(B∩C)=(A×B)∩(A×C)$(B\cap C)×A=(B×A)\cap(C×A)$(B∩C)×A=(B×A)∩(C×A)

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

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

1. 当$x \neq y$x̸​=y时，$&lt;x,y&gt;\neq &lt;y,x&gt;$<x,y≯​=<y,x>
2. 两个有序对相等($&lt;x,y&gt;=&lt;u,v&gt;$<x,y>=<u,v>)的充分必要条件是$x=u$x=u且$y=v$y=v.

有序$n$n元组：
一个有序$n$n元组($n\geqslant 3$n⩾3)是一个有序对，其中第一个元素是一个有序$n-1$n−1元组，一个有序$n$n元组记作$&lt;x_1,x_2,...,x_n&gt;$<x1​,x2​,...,xn​>，即$&lt;x_1,x_2,...,x_n&gt;=&lt;&lt;x_1,x_2,...,x_{n-1}&gt;,x_n&gt;$<x1​,x2​,...,xn​>=<<x1​,x2​,...,xn−1​>,xn​>

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

二元关系

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

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

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

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

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

1. 空关系$\emptyset=\{\emptyset\}$∅={∅}
2. 全域关系$E_A=\{&lt;1,1&gt;,&lt;1,2&gt;,&lt;2,1&gt;,&lt;2,2&gt;\}$EA​={<1,1>,<1,2>,<2,1>,<2,2>}
3. 恒等关系$I_A=\{&lt;1,1&gt;&lt;2,2&gt;\}$IA​={<1,1><2,2>}

关系矩阵和关系图：

设$A=\{x_1,x_2,...,x_n\}$A={x1​,x2​,...,xn​}，$R$R是$A$A上的关系，令$r_{ij}= \begin{cases} 1, &amp; \text{if $x_iRx_j$} \\ 0, &amp; \text{if $x_i\not{R} x_j$} \end{cases}$rij​={1,0,​if xi​Rxj​if xi​̸​Rxj​​则$R$R的关系矩阵为：$(r_{ij})= \begin{bmatrix} r_{11}&amp;r_{12}&amp;\cdots&amp;r_{1n}\\ r_{21}&amp;r_{22}&amp;\cdots&amp;r_{2n}\\ \vdots&amp;\vdots&amp;\ddots&amp;\vdots\\ r_{n1}&amp;r_{12}&amp;\cdots&amp;r_{1n}\\ \end{bmatrix}$(rij​)=⎣⎢⎢⎢⎡​r11​r21​⋮rn1​​r12​r22​⋮r12​​⋯⋯⋱⋯​r1n​r2n​⋮r1n​​⎦⎥⎥⎥⎤​
设$V$V是一个顶点集，$E$E是一个有向边集，令$V=A={x_1,x_2,...,x_n}$V=A=x1​,x2​,...,xn​。若$x_i R x_j$xi​Rxj​，则$x_i$xi​到$x_j$xj​的有向边$&lt;x_i,x_j&gt;\in E$<xi​,xj​>∈E，那么$G=&lt;V,E&gt;$G=<V,E>就是$R$R的关系图。