有序偶和笛卡尔乘积

有序偶

定义

任给两个对象 x 和 y,将它们按规定的顺序构成的序列,称之为有序偶，记为<x,y >

其中,x 称为有序偶的第一元,y 称为第二元

表示方法

Kuratovski提出了一种有序偶的集合表示:\(\lt a,b\gt= \{ \{a\}, \{a,b\} \}\)

定理

\[ \begin{align} &唯一性定理:<u,v>=<x,y>\ \ iff\ \ u=x\wedge v = y\\\\ &证明:\\\\(充分性) &u=x,v=y时,有\{u\}=\{x\},\{u,v\}=\{x,y\}\\\\ &因此\{\{u\},\{u,v\}\}=\{\{x\},\{x,y\}\}\\\\ &即<u,v>=<x,y>\\\\ (必要性)&分情况讨论:\\\\ &(1)设u=v\\\\ &因为<u,v>=\{\{u\},\{u,v\}\}={ {u} }\\\\ &<u,v>=<x,y>=\{\{x\},\{x,y\}\}\\\\ &所以u=x=y\\\\ &u=x,v=y\\\\ &(2)设u\neq v\\\\ &\because\{\{u\},\{u,v\}\}=\{\{x\},\{x,y\}\}\\\\ &\therefore\{u\}=\{x\},\{u,v\}\}=\{x,y\}\\\\ &\therefore u=x,v=y\\\\ &\end{align} \]

笛卡尔乘积

定义

\[ A\times B=\{<x,y>|x\in A\wedge y\in B\} \]

性质

1. 不满足交换律
2. 不满足结合律
3. 当\(A=\emptyset\)或\(B=\emptyset\)时,\(A\times B=\emptyset\)
4. \(\sharp(A\times B)=\sharp A\cdot\sharp B\)

定理

\[ \begin{align} &A\times B=\emptyset\ \ iff\ \ A=\emptyset或 B=\emptyset\\\\ &证明:只需证明A\times B\neq \emptyset\ \ iff\ \ A\neq \emptyset 且B\neq\emptyset\\\\ &\because A \neq \emptyset,B\neq \emptyset\\\\ &\therefore 设x\in A,y\in B\\\\ &\therefore<x,y>\in A\times B\\\\ &\therefore A\times B\neq \emptyset\\\\ \end{align} \]

\[ \begin{align} &设A,B,C,D为任意四个非空集合,则\\\\ &A\times B\subseteq C\times D\ \ iff\ \ A\subseteq C且B\subseteq D\\\\ &证明:(充分性)任取x\in A,由于B\neq \emptyset,可取b\in B\\\\ &<x,b>\in A\times B\\\\ &因A\times B\subset C\times D\\\\ &<x,b>\in C\times D\\\\ &则x\in C,故A\subseteq C\\\\ &同理:B\subseteq D\\\\ &(必要性)任取<a,b>\in A\times B\\\\ &则a\in A且b\in B\\\\ &由A\subseteq C,B\subseteq D\\\\ &则a\in C,b\in D\\\\ &<a,b>\in C\times D\\\\ &A\times B\subseteq C\times D\\\\ \end{align} \]

关系

定义

\[ \begin{align} &关系的定义:\\\\ &R\subseteq X\times Y\\\\ &<x,y>\in R\Rightarrow x\ R\ y\\\\ &<x,y>\notin R\Rightarrow x\ \bar{R}\ y \end{align} \]

$$ \[\begin{align} &全域关系U_x=\{<x_i,x_j>|x_i,x_j\in X\}=X\times X\\\\ &恒等关系I_x=\{<x,x>|x\in X\} \end{align}\]

$$

\[ \begin{align} &定义域dom(R)=\{x\in X|\exists y\in Y:<x,y>\in R\}\\\\ &值域ran(R)=\{y\in Y|\exists x\in X:<x,y>\in R\}\\\\ &dom(R)\subseteq X,ran(R)\subseteq Y\\\\ \end{align} \]

\[ \begin{align} &R的关系矩阵M_R=(r_{ij})_{m\times n}\\\\ &r_{ij}= \begin{cases} 0\,\,若x_i\bar{R}y_i\\\\ 1\,\,若x_iRy_i \end{cases} \end{align} \]

\[ \begin{align} &R=\{<x_1,y_1>,<x_2,y_1>,<x_2,y_2>,<x_2,y_3>\}\\\\ &关系矩阵为 \begin{bmatrix} 1&0&0\\\\ 1&1&1\\\\ \end{bmatrix} \end{align} \]

\[ \begin{align} &R自反\Leftrightarrow \forall x(x\in X\rightarrow <x,x>\in R)\\\\ &在R的关系图中,每个顶点均有自环\\\\ &R的关系矩阵中,主对角线元素均为1\\\\ \end{align} \]

\[ \begin{align} &反自反\Leftrightarrow \\\\& \forall x(x\in X\rightarrow <x,x>\notin R)\\\\ \end{align} \]

\[ \begin{align} &对称矩阵:\forall x\forall y(x\in X\wedge y\in Y\wedge <x,y>\in R\rightarrow <y,x>\in R)\\\\ &在R的关系图中,任意两个不同顶点之间:或者无弧,或者有两条方向相反的弧\\\\ &关系矩阵为对称矩阵\\\\ \end{align} \]

\[ \begin{align} &R是反对称的\Leftrightarrow \forall x\forall y(x\in X\wedge y\in Y\wedge <x,y>\in R\wedge <y,x>\in R\rightarrow x=y)\\\\ &\Leftrightarrow\forall x\forall y(x\in X\wedge y\in Y\wedge <x,y>\in R\rightarrow <y,x>\notin R)\\\\ &在R的关系图中,任意不同顶点之间至多有一条弧\\\\ &R矩阵中,若i\neq j且iRj,则j\bar{R}i \end{align} \]

\[ \begin{align} &R是传递的 \Leftrightarrow \forall x\forall y\forall z\\\\&(x\in X\wedge y\in X\wedge z\in X\wedge <x,y>\in R\wedge <y,z>\in R\rightarrow <x,z>\in R) \end{align} \]

\[ \begin{align} &A有n个元素\\\\ &自反关系:2^{n^2-n}\\\\ &反自反关系:2^{n^2-1}\\\\ &对称关系:2^{\frac{n(n+1)}{2} }\\\\ &反对称关系:2^n\times 3^{\frac{n(n-1)}{2} } \end{align} \]

习题2.1.9

a)

\(dom(U\mathscr A)=\cup\{domR|R\in \mathscr A\}\)

b)

\(ran(U\mathscr A)=\cup\{ranR|R\in \mathscr A\}\)

三序偶的理解

\[ \begin{align} <a,b,c>=&<<a,b>,c>\\\\ =&<\{\{a\},\{a,b\}\},c>\\\\ =&\{\{\{\{a\},\{a,b\}\}\},\{\{\{a\},\{a,b\}\},c\}\} \\\\ \neq& \{\{a\},\{a,b\},\{a,b,c\}\} \end{align} \]