集合论 王智慧 复旦大学计算机学院
1 集合论 王智慧 复旦大学计算机学院
二元关系 有序对与笛卡儿积 二元关系 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系
2 二元关系 • 有序对与笛卡儿积 • 二元关系 • 关系的运算 • 关系的性质 • 关系的闭包 • 等价关系与划分 • 偏序关系
有序对 由两个元素x和y按一定顺序排列成的二元组叫做一个有 序对或序偶 Ordered pair),记作<x,y>,其中x是它的第 元素,y是它的第二元素 有序对<x,y>具有以下性质: 当x≠y时,x,y>≠<y,x>; <x,y>=<u,v>的充分必要条件是x=u且y=v 有序对中的元素是有序的,而集合中的元素是无序的 例如:当x≠y时,有{x,y}={y,X}.但是x,y>≠<y,x 3
3 有序对 z 由两个元素x和y按一定顺序排列成的二元组叫做一个有 序对或序偶(Ordered Pair), 记作<x, y>, 其中x是它的第 一元素, y是它的第二元素. z 有序对<x, y>具有以下性质: ¾ 当x ≠ y时, <x, y> ≠ <y, x>; ¾ <x, y> = <u, v>的充分必要条件是x = u且y = v. z 有序对中的元素是有序的, 而集合中的元素是无序的. ¾ 例如: 当x ≠ y时, 有{ x, y } = { y, x }. 但是<x, y> ≠ <y, x>
笛卡儿积 设A和B为集合,以A中元素为第一元素,B中元素为 第二元素构成有序对;所有这样的有序对组成的集合 叫做A和B的笛卡儿积( Cartesian product/ Product Set),记作AxB. ●笛卡儿积的符号化表示为: A×B={<X,y>|x∈A,y∈B} 例如,设A={a,b},B={0,1,2},则 A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>} B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>} 由排列组合的知识不难证明,如果A|=m,|B=n,则 A×B|=m*n
4 笛卡儿积 z 设A和B为集合, 以A中元素为第一元素, B中元素为 第二元素构成有序对;所有这样的有序对组成的集合 叫做A和B的笛卡儿积(Cartesian Product/Product Set), 记作A × B. z 笛卡儿积的符号化表示为: A × B = { <x, y> | x∈A, y∈B } z 例如, 设A = { a, b }, B = { 0, 1, 2 }, 则 ¾ A × B = { <a, 0>, <a, 1>, <a, 2>, <b, 0>, <b, 1>, <b, 2> } ¾ B × A = { <0, a>, <0, b>, <1, a>, <1, b>, <2, a>, <2, b> } z 由排列组合的知识不难证明, 如果|A| = m, |B| = n, 则 |A × B| = m*n
笛卡儿积 笛卡儿积运算具有以下性质 性质1:对任意集合A,根据定义有 A×φ=φ,φ×A=φ 性质2:不满足交换律,即 A×B≠BXA(当A≠B,A≠中B≠中时) 性质3:不满足结合律,即 (AxB)×C≠Ax(B×C)(当A≠中,B≠,C≠中时)
5 笛卡儿积 z 笛卡儿积运算具有以下性质: ¾ 性质1: 对任意集合A, 根据定义有 A × φ = φ, φ × A = φ ¾ 性质2: 不满足交换律, 即 A × B ≠ B × A (当A ≠ B, A ≠ φ, B ≠ φ时) ¾ 性质3: 不满足结合律, 即 (A × B) × C ≠ A × (B × C) (当A ≠ φ, B ≠ φ, C ≠ φ时)