正文

笛卡尔积

笛卡尔积的定义

设A 、B 为集合，用A中的元素作为第一元素，B 中的元素作为第二元素，构成有序对。所有这样的有序对组成的集合称作A 和B 的笛卡尔积，记作A × B

由排列组合关系可知，若A 中有m 个元素，B 中有n 个元素，则A × B 或B × A B×A中有m n个元素。

例如，若A = { a , b } ，B = { 0 , 1 , 2 } 则

用图表表示

则可得：

n阶笛卡尔积：

设A 1 , A 2 , . . . , A n  (n⩾2)是集合，它们的n 阶笛卡尔积记作A 1 × A 2 × , . . . , × A n ，其中

当A 1 = A 2 = . . . = A n  时，可将它们的n nn阶笛卡尔积简记为An

例如，A = { a , b } ，则

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>}

笛卡尔积运算的性质：

若A 、B 中有一个空集，则它们的笛卡尔积是空集，即

当A ≠ B且AA、B 都不是空集时，有

当A 、B 、C 都不是空集时，有

笛卡尔积运算对交和并满足分配律

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

有序对：

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

有序对的特征：

当x ≠ y 时， ̸=

两个有序对相等=)的充分必要条件是x = u 且y = v

有序n 元组：

一个有序n 元组(n⩾3)是一个有序对，其中第一个元素是一个有序n − 1 元组，一个有序n 元组记作<x1,x2,...,xn>，即

元素：

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

二元关系

定义一：

如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作R 。对于二元关系R，若<x,y>∈R则记作x R y ；若<x,y>∈/R，则记z作xRy

定义二：

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

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

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

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

空关系

全域关系

恒等关系

关系矩阵和关系图：

设A = { x 1 , x 2 , . . . , x n }R是A 上的关系，令

则R 的关系矩阵为：

设V 是一个顶点集，E 是一个有向边集，令V = A = x 1 , x 2 , . . . , x n  。若x i R x j  ，则x i  到x j  的有向边< x i , x j > ∈ E ，那么G=就是R 的关系图。