SET THEORY

Objectives:  To remember what sets are and basic operations with sets.

Recall 1.  A set is a collection of objects called elements.
For example, "car, apple, pencil" is a well defined set whose elements are a car, an apple, and a pencil. This set has three elements.
The set "1,2,3,4,5" has five elements.

1.1 Any set is denoted by capital letters: A, B, C,… There is an empty set (or the null set) denoted by Ø. This is a set that contains no elements.

1.2 Mostly letters will identify the elements of a set. Thus
A={a1, …,an}        (a)
means that the set A consists of the elements a1, …,an.
The roster notation is a complete or implied listing of all elements of the set. So A described by (a) and B={2,4,6,8,…,40} are examples of roster notation defining sets with n and 20 elements respectively.

1.3   The set builder notation is used when the roster method is cumbersome or impossible. Thus for
A={all positive integers}      (b)
the roster method would be impossible since there are too many integers to actually list out .

1.4 The notation aA means that a is an element of A.

1.5 The notation aA indicates non membership of a in A.

1.6 A subset B of a set A is another set whose elements are also elements of A. All sets under consideration will be subsets of the total set W (also called space or the universal set).

1.7 If a set consists only of n elements, then the total number of its subsets equals 2^n.

1.8 P(A) denotes the set of all subsets of a set A.

Note.
In probability theory we assign probabilities to the subsets (events) of W and we define various functions whose domain consists of elements of W. So we must be careful to distinguish between an element a, and the set {a} consisting of the single element a.

Examples

Example 1.  We shall denote by fi the faces of a die. These 6 faces are the elements of the total set W={f1,f2 ,f3,f4,f5,f6}, hence W has 2^6=64 subsets. Some of those would be:
Ø, {f1}, {f2},…., {f6}, {f1,f2},….., {f1,f2,f3}, ……, W.

Example 2.   Suppose a coin is tossed twice. The resulting outcomes are four objects: hh, ht, th, tt where hh is the abbreviation for the appearance of the head each time the coin is tossed, and tt is the abbreviation for the appearance of the tail each time the coin is tossed. So the total set is W={hh, ht, th, tt} and then it has 2^4=16 subsets, such as
A={head shows on the first toss}   A={hh, ht}
B={only one head shows}    B={ht, th}
C={head shows at least once}   C={hh, ht, th}.
In the first column the sets are represented by their properties as in (b), while in the second column they are expressed in terms of their elements, as in (a).

Recall 2.  A set and its subsets are represented by plane figures called Venn diagrams, as shown in the illustration below.

2.1
"B is a subset of A" means that every element of B is an element of A. The notation BA means that B is a subset of A.

2.2. ØAAW, for any A.

2.3  This relationship called inclusion has some properties:
* Transitivity: AB and BC, then AC.
* Reflexivity: AA;
* Anti symmetry: AB and BA then A=B.

2.4  A=B means that AB and BA and we say A is equal to B.

Recall 3. The sum (also called the union) of two sets A and B denoted by A+B (or AB) is also a set whose elements are all elements of A or B or both, as shown in the diagram below.

The set AB is defined to be {x|xA or xB}. The vertical bar "|" is read "such that" so this notation is read aloud as "the set of x such that x belongs to A or x belongs to B".

Here are some properties of union.
* Commutative: A+B=B+A
* Associative (A+B)+C=A+(B+C);
* If AB, then A+B=B;
* A+A=A;
* A+Ø=A;
* A+W=W.

Recall 4.  The product (also called the intersection) of two sets A and B denoted by AB (or AB) is also a set whose elements are all common elements of both A and B, as shown in the diagram below.

The set AB is defined to be {x|A and xB}.

4.1 Here are some properties of this operation:
* Commutative: AB=BA
* Associative (AB)C=A(BC);
* Distributive: A(B+C)=AB+AC;
* If AB, then AB=A;
* AA=A;
* AØ=Ø;
* AW=A.

4.2  If two sets were described by the properties of their elements as in (b), then their intersection AB is specified by including these properties between braces. For example, if W={1,2,3,4,5,6} and A={even} and B={less than five}, then
AB={even and less than five} so AB={2,4}.

Recall 5.  Two sets are called mutually exclusive sets (or disjoint sets) if they have no common elements, that is if AB=Ø.
Several sets A1, A2, ….are mutually exclusive iff AiAj=Ø for any i,j.

Recall 6. A partition of a set W is a collection of mutually exclusive subsets Ai of W whose union equals W:  A1+A2+...An=W and AiAj=Ø for any i,j.

Recall 7.  The complement  of a set A is a set consisting of all elements of W that are not in A.

7.1 From the definition it follows that:
* A+=W;
* A=Ø;

Example 3 If A={-3, pi, sqrt(2) } and it's obvious that the universal set W=R, then   consists of those real numbers that are not in A.

Recall 8.  De Morgan’s Laws.

See illustration below.

This law says that if we replace all sets by their complements, all union by intersections and all intersections by union, the identity is preserved.

Example 4  Let A={a,d,e,g} and B={c,d,f,g} in the universe W={a,b,c,d,e,f,g,h,i}. To verify the first of Morgan’s laws find each of these two sets independently to find that they are indeed the same. First
A+B={a,c,d,e,f,g} so  ={b,h,i}.
={b,c,f,h,i},  {a,b,e,h,i} is , hence the intersection of the complements is ={b,h,i}.
As predicted, {b,h,i}={b,h,i}!

Exercises

1. A={1,2,3,4,5}, B={1,2,3}, C={4,5,6}. True or False:
a) 1A and 1C;    f) B+C=A;
b) 1A or 1C;      g)AB=C;
c) 1B and 1C;     h) xA implies xB;
d) {1,2,3}A;          i) xB implies xA.
e) {1,3,4}B;

2. Find the set X using the following information:
X+{1,2}={1,2,3} and X{2,3}.

3. Find the set X using the following information:
X{1,2,3,4}={3,4} and X{1,3,4,5}.

4. Find the set X using the following information:
X{1,2,5,7}={5,7} and X+{5,7,9}={3,5,7,8,9}.

5. Find the element x from   {1,x, 5}{x, 5}={5,9}.

6. Find the element x from   {3,4,x, 7}={2,3,4,7}.

7. Find the element x from   {2,x, 11}{2,3,11,x}.

8. Find the element x from   {9,2x, 11}{7,15}=Ø.

9. Find the element x from   {2,3x, 12}{1,21}={21}.

10. A={xN, the remainder from the division of x by 3 is 1 and x<=16}.
B={yN, 7<=y<14}.
Find A+B, AB, A-B, B-A (A-B is defined as the set of all elements that are in A but not in B: A-B=A ).

Notes on Set theory