北大集合论与图论5.ppt

《集合论与图论》第5讲 第5讲 二元关系的基本概念北京大学 内容提要 1. 有序对与卡氏积 2. 二元关系 3. 二元关系的基本运算 有序对与卡氏积 有序对(有序二元组) 有序三元组, 有序n元组 卡氏积 卡氏积性质 有序对(ordered pair) 有序对: a,b = { {a}, {a,b} } 其中, a是第一元素, b是第二元素. a,b也记作(a,b) 定理1: a,b=c,d ? a=c?b=d 推论: a?b ? a,b?b,a 有序对(引理1) 引理1: {x,a}={x,b} ? a=b 证明: (?) 显然. (?) 分两种情况. (1) x=a. {x,a}={x,b} ? {a,a}={a,b} ? {a}={a,b} ? a=b. (2) x?a. a?{x,a}={x,b} ? a=b. # 有序对(引理2) 引理2: 若A=B ??, 则 (1) ∪A=∪B (2) ∩A=∩B 证明: (1) ?x, x?∪A ? ?z(z?A ? x?z) ? ?z(z?B ? x?z) ? x?∪B. (2) ?x, x?∩A ? ?z( z?A ? x?z ) ? ?z( z?B ? x?z ) ? x?∩B. # 有序对(定理1) 定理1: a,b=c,d ? a=c?b=d 证明: (?) 显然. (?) 由引理2, a,b=c,d ? {{a},{a,b}}={{c},{c,d}} ?∪{{a},{a,b}}=∪{{c},{c,d}}?{a,b}={c,d}. 又 {{a},{a,b}}={{c},{c,d}} ?∩{{a},{a,b}}=∩{{c},{c,d}} ? {a}={c} ? a=c. 再由引理1, 得b=d. # 有序对(推论) 推论: a?b ? a,b?b,a 证明: (反证) a,b=b,a?a=b, 与a?b矛盾. # 有序三元组(ordered triple) 有序三元组: a,b,c=a,b,c 有序n(?2)元组: a1,a2,…,an=a1,a2,…,an-1,an 定理2: a1,a2,…,an= b1,b2,…,bn ? ai = bi, i =1,2,…,n. # 卡氏积(Cartesian product) 卡氏积: A?B={x,y|x?A?y?B}. 例: A={?,a}, B={1,2,3}. A?B={?,1,?,2,?,3,a,1,a,2,a,3}. B?A={1,?,1,a,2,?,2,a,3,?,3,a}. A?A={ ?,?, ?,a, a,?, a,a}. B?B={ 1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3 }. # 卡氏积的性质 非交换: A?B ? B?A (除非 A=B ? A=? ? B=?) 非结合: (A?B)?C ? A?(B?C) (除非 A=? ? B=? ? C=?) 分配律: A?(B?C) = (A?B)?(A?C)等 其他: A?B=? ? A=??B=?等 卡氏积非交换性 非交换: A?B ? B?A (除非 A=B ? A=? ? B=?) 反例: A={1}, B={2}. A?B={1,2}, B?A={2,1}. 卡氏积非结合性 非结合: (A?B)?C ? A?(B?C) (除非 A=? ? B=? ? C=?) 反例: A=B=C={1}. (A?B)?C={1,1,1}, A?(B?C)={1,1,1}. 卡氏积分配律 1. A?(B?C) = (A?B)?(A?C) 2. A?(B?C) = (A?B)?(A?C) 3. (B?C)?A = (B?A)?(C?A) 4. (B?C)?A = (B?A)?(C?A) 卡氏积分配律(证明1) A?(B?C) = (A?B)?(A?C). 证明: ?x,y, x,y?A?(B?C) ? x?A?y?(B?C) ? x?A?(y?B?y?C) ? (x?A?y?B)?(x?A?y?C) ?(x,y?A?B)?(x,y?A?C) ?x,y?(A?B)?(A?C) ? A?(B?C) = (A?B)?(A?C). #