Set Theory.

Set Theory. Set Theory, branch of mathematics, first given formal treatment by the German mathematician Georg Cantor in the 19th century. The set concept is one of the most basic in mathematics, even more primitive than the process of counting, and is found, explicitly or implicitly, in every area of pure and applied mathematics. Explicitly, the principles and terminology of sets are used to make mathematical statements more clear and precise and to clarify concepts such as the finite and the infinite. A set is an aggregate, class, or collection of objects, which are called the elements of the set. In symbols, aeS means that the element a belongs to or is contained in the set S, or that the set S contains the element a. A set S is defined if, given any object a, one and only one of these statements holds: aeS or a?S (that is, a is not contained in S). A set is frequently designated by the symbol S = { }, with the braces including the elements of S either by writing all of them in explicitly or by giving a formula, rule, or statement that describes all of them. Thus, S1 = {2, 4}; S2 = {2, 4, 6, ..., 2n,...} = {all positive even integers}; S3 = {x x2 - 6x + 11 >= 3}; S4 = {all living males named John}. In S3 and S4 it is implied that x is a number; S3 is read as the set of all xs such that x2 - 6x + 11 >= 3. If every element of a set R also belongs to a set S,R is a subset of S, and S is a superset of R; in symbols, RÍS, or SÊR. A set is both a subset and a superset of itself. If RÍS, but at least one element in S is not in R,R is called a proper subset of S, and S is a proper superset of R; in symbols, RÌ S,SÉ R. If RÍS and SÍR, that is, if every element of one set is an element of the other, then R and S are the same, written R = S. Thus, in the examples cited above, S1 is a proper subset of S2. If A and B are two subsets of a set S, the elements found in A or in B or in both form a subset of S called the union of A and B, written AÈB. The elements common to A and B form a subset of S called the intersection of A and B, written AÇB. If A and B have no elements in common, the intersection is empty; it is convenient, however, to think of the intersection as a set, designated by Æ and called the empty, or null, set. Thus, if A = {2, 4, 6}, B ={4, 6, 8, 10}, and C = {10, 14, 16, 26}, then AÈB = {2, 4, 6, 8, 10}, AÈC = {2, 4, 6, 10, 14, 16, 26}, AÇB = {4, 6}, AÇC = Æ. The set of elements that are in A but not in B is called the difference between A and B, written A - B (sometimes A\B); thus, in the illustration above, A - B ={2}, B - A = {8, 10}. If A is a subset of a set l, the set of elements in l that are not in A, that is, l A, is called the complement of A (with respect to l), written l - A = A' (also written ?,Ã, ~ A). The following statements are basic consequences of the above definitions, with A,B,C,... representing subsets of a set l. 1. AÈB = BÈA. 2. AÇB = BÇA. 3. (AÈB) ÈC = AÈ (BÈC). 4. (AÇB) ÇC = AÇ (BÇC). 5. AÈÆ = A. 6. AÇÆ = Æ. 7. AÈl = l. 8. AÇl = A. 9. AÈ (BÇC) = (AÈB) Ç (AÈC). 10. AÇ (BÈC) = (AÇB) È (AÇC). 11. AÈA' = l. 12. AÇA' = Æ. 13. (AÈB)' = A'ÇB'. 14. (AÇB)' = A'ÈB'. 15. AÈA = AÇA = A. 16. (A')' = A. 17. A - B = AÇB'. 18. (A - B) - C = A - (BÈC). 19. If AÇB = Æ, then (AÈB) - B = A. 20. A - (BÈC) = (A - B) Ç (A - C). These are laws of the algebra of sets, which is an example of the algebraic system that mathematicians call Boolean algebra. If S is a set, the set of all subsets of S is a new set D, sometimes called the derived set of S. Thus, if S = {a,b,c}; D ={{},{a}, {b },{c}, {a,b}, {a,c}, {b,c}, {a,b,c}. Here,{} is used in place of the null set Æ, of S; it is an element of D. If S has n elements, the derived set D has 2n elements. Larger and larger sets are obtained by taking the derived set D2 of D, the derived set D3 of D2, and so on. If A and B are two sets, the set of all possible ordered pairs of the form (a,b), with a in A and b in B, is called the Cartesian product of A and B, frequently written A × B. For example, if A ={1, 2}, B ={x,y,z}, then A × B ={ (1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}. B × A ={ (x, 1), (y, 1), (z, 1), (x, 2), (y, 2), (z, 2)}. Here, A × B?B × A, because the pair (1, x) must be distinguished from the pair (x, 1). The elements of the set A = {1, 2, 3} can be matched or paired with the elements of the set B = {x,y,z} in several (actually, six) ways such that each element of B is matched with an element of A, each element of A is matched with an element of B, and different elements of one set are matched with different elements of the other. For example, the elements may be matched (1, y), (2, z), (3, x). A matching of this type is called a one-to-one (1-1) correspondence between the elements of A and B. The elements of the set A = {1, 2, 3} cannot be put into a 1-1 correspondence with the elements of any one of its proper subsets and is therefore called a finite set or a set with finite cardinality. The elements of the set B = {1, 2, 3, ...} can be put into a 1-1 correspondence with the elements of its proper subset C ={3, 4, 5, ...} by matching, for example, n of B with n + 2 of C,n = 1, 2, 3, .... A set with this property is called an infinite set or a set of infinite cardinality. Two sets having elements that can be placed in a 1-1 correspondence are said to have the same cardinality. Contributed By: James Singer Reviewed By: J. Lennart Berggren Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. All rights reserved.