定理8(证明(5) (5)(RS)个A=R(SA) 秦证明:1<xy>,x(ROS)个A)y 台XR0S)y∧X∈A分z( X SZAZRy)∧X∈A 2( XSZAZRy∧XEA) 日z(XSZ∧X∈A)∧ZRy) 台→丑(X(S↑A)z∧ZRy)分X(R(STA)y R个U=U{R个A|A∈小# 《集合论与图论》第6讲
《集合论与图论》第6讲 11 定理8(证明(5)) (5) (R○S)↑A = R○(S↑A) 证明: ∀<x,y>, x((R○S)↑A)y ⇔ x(R○S)y ∧ x∈A ⇔ ∃z(xSz∧zRy ) ∧ x∈A ⇔ ∃z(xSz∧zRy ∧ x∈A) ⇔ ∃z((xSz∧x∈A) ∧ zRy ) ⇔ ∃z( x(S↑A)z ∧ zRy ) ⇔ x(R○(S↑A))y. ∴ R↑∪A = ∪{ R↑A | A∈A}. #
定理9 定理9:设R,SAB,,为集合,4,则 RIAUB]=RAJURB] 2)R[U=U{RA]|A∈n} (3)RAS≤RA⌒RB (4)R[n≤∩{RA]A∈外 (5)]-R[B] C R[A-B; (6)(0S)A]=R[S[A] 《集合论与图论》第6讲
《集合论与图论》第6讲 12 定理9 定理9: 设R,S,A,B,A,为集合,A≠∅,则 (1) R[A∪B] = R[A]∪R[B]; (2) R[∪A] = ∪{ R[A] | A∈A }; (3) R[A∩B] ⊆ R[A]∩R[B]; (4) R[∩A] ⊆ ∩{ R[A] | A∈A}; (5) R[A]-R[B] ⊆ R[A-B]; (6) (R○S)[A] = R[S[A]].
定理9(证明2) (2)R[U列=U{R[A]|A∈} 证明:y,y∈R[U刚分彐X(XRyX∈U 分3X(XRy∧丑A(A∈∧X∈A) 台→A(A∈A∧丑X(XRy∧XEA)) →A(A∈Ay∈RA] 台y∈U{R[A]|A∈ R个U=U{R个A|A∈ 《集合论与图论》第6讲 13
《集合论与图论》第6讲 13 定理9(证明(2)) (2) R[∪A] = ∪{ R[A] | A∈A }; 证明: ∀y, y∈R[∪A] ⇔ ∃x(xRy∧x∈∪A) ⇔ ∃x( xRy ∧ ∃A( A∈A ∧ x∈A) ⇔ ∃A( A∈A ∧ ∃x( xRy ∧ x∈A ) ) ⇔ ∃A(A∈A∧y∈R[A]) ⇔ y∈∪{ R[A] | A∈A }. ∴ R↑∪A = ∪{ R↑A | A∈A}.
定理9(证明(4) (4)R∩列e∩{RA]A∈丹 证明:以y,y∈R台3X(XRyX∈∩ →X( XRyAVA(A∈a>X∈A) XA(XRyA(A∈a>X∈A) →Ax(yA(A∈a>X∈A)() →VA日XA∈A→>(xy∧X∈A)(*) A(A∈A)x( XRyAXEA)vAA∈A→yeR[A]) y∈∩{R[A|A∈a R[e∩{R闪A]|A∈外 《集合论与图论》第6讲
《集合论与图论》第6讲 14 定理9(证明(4)) (4) R[∩A] ⊆ ∩{ R[A] | A∈A}; 证明: ∀y, y∈R[∩A] ⇔ ∃x(xRy∧x∈∩A) ⇔∃x(xRy∧∀A(A∈A→x∈A)) ⇔∃x∀A(xRy∧(A∈A→x∈A)) ⇒∀A∃x(xRy∧(A∈A→x∈A)) (*) ⇒∀A∃x(A∈A→(xRy∧x∈A)) (**) ⇔∀A(A∈A→∃x(xRy∧x∈A))⇔∀A(A∈A→y∈R[A]) ⇔y∈∩{ R[A] | A∈A }. ∴ R[∩A] ⊆ ∩{ R[A] | A∈A}.
定理9(证明(4,续) ()XA(XRy(A∈4)∈A) →Ax(XRy(A∈a>∈A) 秦()VAx(∧(A∈>∈A) →VA丑X(A∈A>(xRy∧X∈A) 容易证明 秦(2)彐xyB(X,y)→ y=xB(X,) 秦()p∧(q→)→q→>(∧门) 《集合论与图论》第6讲 15
《集合论与图论》第6讲 15 定理9(证明(4),续) (*) ∃x∀A(xRy∧(A∈A→x∈A)) ⇒∀A∃x(xRy∧(A∈A→x∈A)) (**) ∀A∃x(xRy∧(A∈A→x∈A)) ⇒∀A∃x(A∈A→(xRy∧x∈A)) 容易证明: (*) ∃x∀yB(x,y) ⇒ ∀y∃xB(x,y) (**) p∧(q→r) ⇒ q→(p∧r)