Our cookies follow Google AdSense policy.

Theorem S.IS.1If X is a set, T is a set such that T != O, A:T->P(X), x:-X then (1) x:-u({A(t)|t:-T}) <=> \/(t:-T) x:-A(t), (2) x:-n({A(t)|t:-T}) <=> /\(t:-T) x:-A(t).ProofLet E = {A(t) | t:-T}. Notice that since T != O, E != O. (1) By Definition S.A.3 x:-u(E) <=> \/(e) e:-E and x:-e <=> (a) \/(e) e:-{A(t) | t:-T} and x:-e <=> (b) \/(e)(e:-{y:-P(X) | \/(t:-T) A(t)=y} and x:-e ) <=> (c) \/(e)( (e:-P(X) and \/(t:-T) A(t)=e) and x:-e ) <=> (d) \/(e)\/(t:-T) A(t)=e and x:-e <=> (e) \/(t:-T)\/(e) A(t)=e and x:-e <=> (f) \/(t:-T) x:-A(t). (a)<=>(b) by Definition S.C.15 (2) By Definition S.I.2 x:-n(E) <=> x:-{a:-u(E) | /\(e:-E) a:-e} <=> (g) x:-u(E) and /\(e:-E) x:-e <=> (h) /\(e:-E) x:-e <=> (i) /\(e) (e:-E => x:-e) <=> (j) /\(e) (e:-P(X) and \/(t:-T) A(t)=e) => x:-e <=> (k) /\(e) (\/(t:-T) A(t)=e)=> x:-e <=> (l) /\(e)/\(t:-T) A(t)=e => x:-e <=> (m) /\(t:-T)/\(e) A(t)=e => x:-e <=> (n) /\(t:-T) x:-A(t).Theorem S.IS.2 - De Morgan's lawIf X is a set, T is a set such that T != O, A:T->P(X) then X\u({A(t)|t:-T}) = n({X\A(t)|t:-T}).ProofLet L = X\u({A(t)|t:-T}). Let R = n({X\A(t)|t:-T}). We will show that R c L. Suppose to the contrary that there exists x:-X such that !(x:-L) and x:-R. We have x:-u({A(t)|t:-T}) and x:-n({X\A(t)|t:-T}). By Theorem S.SI.1 we have \/(t:-T) x:-A(t) and /\(t:-T) x:-X\A(t). Contradiction. So we showed that R c L. Now we will show that L c R. Suppose to the contrary that there exists x:-X such that x:-L and !(x:-R). Then we have !(x:-u({A(t)|t:-T}) and !(x:-n({A(t)|t:-T})). By Theorem S.SI.1 we have !(\/(t:-T) x:-A(t)) and !(/\(t:-T) x:-X\A(t)). /\(t:-T) !(x:-A(t)) and !(/\(t:-T) !(x:-A(t)). Contradiction. So we showed that L c R. Thus L = R.Theorem S.IS.3 - De Morgan's lawIf X is a set, T is a set such that T != O, A:T->P(X) then X\n({A(t)|t:-T}) = u({X\A(t)|t:-T}).ProofLet B:T->P(X) such that B(t) = X\A(t). By Theorem S.I.8 (3) X\A(t) = B(t). By Theorem S.IS.3 we have X\u({B(t)|t:-T}) = n({X\B(t)|t:-T}). So X\(X\u({B(t)|t:-T}) = X\n({X\B(t)|t:-T}). And then u({B(t)|t:-T}) = X\n({X\B(t)|t:-T}). Thus u({X\A(t)|t:-T}) = X\n({A(t)|t:-T}.Theorem S.IS.4If X,Y are sets, f:X->Y and A,B c X and T is a set, T!=O and A:T->P(X). then (1) A c B => f(A) c f(B), (2) f(A\B) c f(A)\f(B), (3) u({f(A[t])|t:-T}) = f( u({A[t]|t:-T}) ), (4) f( n({A[t]|t:-T}) ) c n({f(A[t])|t:-T}).Proof(1) Assume that AcB. Take y:-f(A). There exists x:-A such that f(x)=y. Since A c B, x:-B. Thus y:-f(B). We have shown that A c B. (2) Take y:-f(A)\f(B). Then y:-f(A) and !(y:-f(B)). So there exists x:-A such that and f(x)=y. Since !(y:-f(B)), /\(z:-B) f(z)!=y. Hence f(x)!=y. So x:-A\B. Thus y:-f(A\B). We have shown that f(A)\f(B) c f(A\B). (3) y:- u({f(A[t])|t:-T}) <=> \/(t:-T) y:-f(A[t]) <=> \/(t:-T)\/(x:-X)(x:-A[t] and f(x) = y) <=> \/(x:-X)\/(t:-T)(x:-A[t] and f(x) = y)<=> \/(x:-X)(\/(t:-T) x:-A[t]) and f(x) = y <=> \/(x:-X) x:-u({A[t]|t:-T) and f(x) = y <=> y :- f(u({A[t]|t:-T})). We have shown that u({f(A[t])|t:-T}) = f( u({A[t]|t:-T}) ). (4) Take any y:-f( n({A[t]|t:-T}) ). Then there exist x:-n({A[t]|t:-T}) such that f(x) = y. Take any d:-T. Since x:-n({A[t]|t:-T}), x:-A[d]. Then y:-f(A[d]). Since d:-T was arbitralily chosen, y:-n({f(A[t])|t:-T}). We have shown that f( {(A[t])|t:-T} ) c n({f(A[t])|t:-T}).Theorem S.IS.5If X,M are sets such that M!=O and M c P(X) then n(M) = {x:-X | /\(A:-M) x:-A}.ProofLet us recall that n(M) = {x:-u(M) | /\(A:-M) x:-A}. Take any y:-n(M). We have that y:-u(M) and /\(A:-M) y:-A. So we have B:-M such that y:-B. Since M c P(X), B c X, and so y:-X. Thus y:-{x:-X | /\(A:-M) y:-A}. We showed that n(M) c {x:-X | /\(A:-M) x:-A}. Take any y:-{x:-X | /\(A:-M) x:-A}. We have that (*) /\(A:-M) y:-A. Since M!=O we have some B:-M. By (*) y:-B and so y:-u(M). Thus y:-{x:-u(M) | /\(A:-M) x:-A}. We showed that {x:-X | /\(A:-M) x:-A} c {x:-u(M) | /\(A:-M) x:-A} = n(M). So we showed that n(M) = {x:-X | /\(A:-M) x:-A}.