二元关系完整版本.docVIP

第四章二元关系

宇宙万物之间存在着形形色色的联系，这种联系正是各门学科所关注的根本问题。例如，人与人之间有父子、兄弟、师生关系；两数之间有大于、等于、小于关系；电学中有电压、电阻与电流间的关系；元素与集合之间的属于关系；计算机科学中程序间的调用关系，程序执行过程中状态之间的转换关系,程序执行前变量取值状况和执行后变量取值状况的关系，文件与路径的关系……。集合论为刻划这种联系提供了一种数学模型——关系，它仍然是一个集合，以具有那种联系的对象组合为其成员。换言之，集合论中关系不是通过描述关系的内涵来刻划这种联系，而是通过列举其外延(具有那种联系的对象组合全体)来刻划这种联系。这使关系的研究可以方便地使用集合论概念、运算及研究方法和研究成果。

在离散数学中，“关系”被抽象为一个基本概念，在通常情况下，“关系”是至少由两个集合在给定条件下产生的新集合，它提供了一种描述事物间多值依赖的工具，为计算机科学提供了一种很好的数学模型。需要指出，集合论中的关系研究，并不以个别的关系为主要对象，而是关注关系的一般特性、关系的分类等。

4.1有序组与集合的笛卡尔积

定义4.1设a，b为任意对象，称集合｛｛a｝，｛a,b｝｝为二元有序组，或序偶（orderedpairs），简记为a，b。称a为a，b的第一分量，称b为第二分量。注意，第一、二分量未必不同。

定理4.1对任意序偶a，b,c,d,a，b=c,d当且仅当a＝c且b=d。

定义4.2递归定义n元序组a1，…an

a1，a2=｛｛a1｝，｛a1,a2｝｝

a1，…an=a1，…an-1,an

本质上,n元序组依然是序偶。ai称为n元序组的第i分量。

定理4.2对任意对象a1，…，an，b1，…，bn，

a1，…，an=b1，…，bn当且仅当

a1=b1，…，an=bn

显然，序偶和n元序组都是集合，但由于它们的特殊结构，把次序赋予了有关对象，我们以后更多关心的是它们的这种“序特性”。而较少谈论定义它们的原有的集合结构细节。

定义4.3对任意集合A1，A2,…，An，

（1）A1′A2，称为集合A1,A2的笛卡尔积(Cartesianproduct)，定义为

A1′A2=｛x|$u$v(x=u,v∧u?A1∧v?A2)｝

=｛u,v|u?A1∧v?A2｝

（2）递归地定义A1′A2′…′An

A1′A2′…′An=(A1′A2′…′An-1)′An

当A1=A2=…=An=A时，A1′A2′…′An简记为An

定理4.3对任意集合A1，A2,…，An，

A1′A2′…′An=｛a1,…,an|a1?A1∧…∧an?An｝

本定理同样可用归纳法给出证明，请读者完成之。

例4.1设A=｛1,2｝，B=｛a,b,c｝，C=｛?｝,R为实数集，

那么

（l）A′B=｛1,a，l,b，1,c，2,a，2,b，2,c｝

B′A＝｛a,1，b,1，c,1，a,2，b,2，c,2｝

（2）A′B′C=(A′B)′C=｛1,a,?，l,b,?，1,c,?，2,a,?，2,b,?，

2,c,?｝

A′(B′C)=｛1,a,?，l,b,?，1,c,?，2,a,?，2,b,?，

2,c,?｝

（3）A′?=?′A=?

（4）R2=｛u,v|u,v是实数｝，R2为笛卡儿平面。显然R3为三维笛卡儿空间．

我们注意到，一般地A′B1B′A，(A′B)′C1A′(B′C)。此外，?也用来表示不含任何序组的笛卡儿积。

关于笛卡儿积有以下性质。

定理4.4设A,B,C为任意集合，*表示è，?或–运算，

那么

A′(B*C)＝(A′B)*(A′C)

(B*C)′A＝(B′A)*(C′A)

证