Set Theory

Set Theory

These diagrams represent ways of grouping objects, or elements, of two sets. R is a subset of S if every element in R also belongs in S (top left). For example, the odd numbers R = {1,3,5,7,9} are a subset of the set of whole numbers S = {1,2,3,4,5,6,7,8,9,10}. The union of A and B consists of all the elements in A and all the elements in B (top right). For example, if A = {2,3,4,5} and B = {4,5,6,7}, then A È B = {2,3,4,5,6,7}. The intersection of A and B consists of their common elements (bottom left). For example, A Ç B = {4,5}. The difference between B and A consists of the elements in B that are not also contained in A (bottom right). For example, B - A = {6,7}.

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, S₁ = {2, 4}; S₂ = {2, 4, 6, ..., 2n,...} = {all positive even integers}; S₃ = {x | x² - 6x + 11 ≥ 3}; S₄ = {all living males named John}. In S₃ and S₄ it is implied that x is a number; S₃ is read as the set of all xs such that x² - 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, S₁ is a proper subset of S₂.

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 2ⁿ elements. Larger and larger sets are obtained by taking the derived set D₂ of D, the derived set D₃ of D₂, 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.