6 CHAPTER 1.PRELIMINARIES PROOF.(1)If AU B=0,then the theorem follows immediately since both A and B are the empty set.Otherwise,we must show that (AU B)'C A'n B'and (AUB)A'n B'. Let z(AU B).Then x AUB.So x is neither in A nor in B,by the definition of the union of sets.By the definition of the complement,x A'and x B'.Therefore, xE A'n B'and we have (AUB)'C A'n B'. To show the reverse inclusion,suppose that x∈A'∩B'.Then x∈A'andx∈B',and so x A and x丰B.Thus z年AUB and so x∈(AUB)'.Hence.,(AUB)'pA'nB'and s0(AUB)'=A'∩B. The proof of(2)is left as an exercise. 口 Example 1.4.Other relations between sets often hold true.For example, (A\B)n(B\A)=0. To see that this is true,observe that (A\B)0(BA)=(A0B)0(BOA) =A∩A'nBnB =0. Cartesian Products and Mappings Given sets A and B,we can define a new set A x B,called the Cartesian product of A and B,as a set of ordered pairs.That is, A×B={(a,b):a∈A and b∈B}. Example 1.5.If A={,y),B={1,2,3},and C=0,then A x B is the set {(x,1),(,2),(x,3),(y,1),(y,2),(y,3)} and A×C=0. We define the Cartesian product of n sets to be A1×…×An={(a1,.,an):a∈Ai for i=1,.,n} IfA=A=A2=·=An,we often write Am for A×·×A(where A would be written n times).For example,the set R3 consists of all of 3-tuples of real numbers. Subsets of Ax B are called relations.We will define a mapping or function f C Ax B from a set A to a set B to be the special type of relation where (a,b)E f if for every element a E A there exists a unique element bB.Another way of saying this is that for every element in A,f assigns a unique element in B.We usually write f:AB or A B. Instead of writing down ordered pairs (a,b)EA x B,we write f(a)=b or f:ab.The set A is called the domain of f and f(A)={f(a):a∈A}CB is called the range or image of f.We can think of the elements in the function's domain as input values and the elements in the function's range as output values.6 CHAPTER 1. PRELIMINARIES Proof. (1) If A ∪ B = ∅, then the theorem follows immediately since both A and B are the empty set. Otherwise, we must show that (A ∪ B) ′ ⊂ A′ ∩ B′ and (A ∪ B) ′ ⊃ A′ ∩ B′ . Let x ∈ (A ∪ B) ′ . Then x ∈/ A ∪ B. So x is neither in A nor in B, by the definition of the union of sets. By the definition of the complement, x ∈ A′ and x ∈ B′ . Therefore, x ∈ A′ ∩ B′ and we have (A ∪ B) ′ ⊂ A′ ∩ B′ . To show the reverse inclusion, suppose that x ∈ A′ ∩ B′ . Then x ∈ A′ and x ∈ B′ , and so x ∈/ A and x ∈/ B. Thus x ∈/ A ∪ B and so x ∈ (A ∪ B) ′ . Hence, (A ∪ B) ′ ⊃ A′ ∩ B′ and so (A ∪ B) ′ = A′ ∩ B′ . The proof of (2) is left as an exercise. Example 1.4. Other relations between sets often hold true. For example, (A \ B) ∩ (B \ A) = ∅. To see that this is true, observe that (A \ B) ∩ (B \ A) = (A ∩ B ′ ) ∩ (B ∩ A ′ ) = A ∩ A ′ ∩ B ∩ B ′ = ∅. Cartesian Products and Mappings Given sets A and B, we can define a new set A × B, called the Cartesian product of A and B, as a set of ordered pairs. That is, A × B = {(a, b) : a ∈ A and b ∈ B}. Example 1.5. If A = {x, y}, B = {1, 2, 3}, and C = ∅, then A × B is the set {(x, 1),(x, 2),(x, 3),(y, 1),(y, 2),(y, 3)} and A × C = ∅. We define the Cartesian product of n sets to be A1 × · · · × An = {(a1, . . . , an) : ai ∈ Ai for i = 1, . . . , n}. If A = A1 = A2 = · · · = An, we often write An for A × · · · × A (where A would be written n times). For example, the set R 3 consists of all of 3-tuples of real numbers. Subsets of A×B are called relations. We will define a mapping or function f ⊂ A×B from a set A to a set B to be the special type of relation where (a, b) ∈ f if for every element a ∈ A there exists a unique element b ∈ B. Another way of saying this is that for every element in A, f assigns a unique element in B. We usually write f : A → B or A f→ B. Instead of writing down ordered pairs (a, b) ∈ A × B, we write f(a) = b or f : a 7→ b. The set A is called the domain of f and f(A) = {f(a) : a ∈ A} ⊂ B is called the range or image of f. We can think of the elements in the function’s domain as input values and the elements in the function’s range as output values