Mathematics for Computing

Sets A and B are examples of finite sets, whereas C is an infinite set.  For any finite set A, |A| denotes the number of elements in A and is referred to as the cardinality, or size of A. In the example above |A| = 9 and |B| = 4.

If C, D are sets from a universe U, C is a subset of D, written C ⊆ D, or D ⊇ C, if every element of C is an element of D. Additionally, if D contains an element that is not in C, then C is called a proper subset of D, denoted C ⊂ D or D ⊃ C.

For the universe  U = {1,2,3,4,5}, consider the set A = {1,2}. If B ={x | x2 ∈ U } then the members of B are 1,2. Hence A and B contain the same elements – and no other,  thus sets A and B should be equal. It is also true that A ⊆ B and B ⊇ A giving us the following definition of equality.

For a given universe U, the sets C and D  (taken from U) are said to be equal, written C=D, when C ⊆ D, or D ⊇ C.

We can see that neither order nor repetition is relevant for a set. Consequently, we find that {1,2,3} = {3,2,1} = {2,2,1,3} = {1,2,1,2,3}.

We can define the negation of a subset. A /⊆ B if there is at least one element x in the universe where x is a member of A but x is not a member of B.

We have introduced four ideas so far:

1. set membership
2. set equality
3. subsets
4. proper subsets

Examples

Let U = {1,2,3,4,5,6,x,y,{1,2},{1,2,3},{1,2,3,4}} – where x,y are simply letters of the alphabet. Then | U | = 11.

1. If A = {1,2,3,4}, then |A| = 4 and:

1. A ⊆ U
2. A ⊂ U
3. A ∈ U
4. {A} ⊆ U
5. {A} ⊂ U, but
6. {A} ∉ U

2. Let B = {5,6,x,y,A} = {5,6,x,y,{1,2,3,4}}. Then |B| = 5 (not 8). Now

1. A ∈ B
2. {A} ⊆ B and
3. {A} ⊂ B, but
4. {A} ∉ B
5. A /⊆ B (A is not a subset of B)
6. A ⊄ B (A is not a proper subset of B)

1.4 The Empty Set and Powersets

The null set, or empty set, is the (unique) set containing no elements. It is denoted by ∅ or {}. Note that |∅| = 0 but {0} ≠ ∅. Also ∅ ≠ {∅} because {∅} is a set with one element, namely the null set.

Let us now consider the subsets of the set C = {1,2,3,4}. In constructing a subset of C, we have, for each member x of C, two distinct choices: either include it in the set, or exclude it. Consequently, there are 2 x 2 x 2 x 2 choices, resulting in 24 = 16 subsets of C. These include the empty set and the set C itself.

If A is a set from universe U, the power set of A, denoted P(A) is the collection (or set) of all subsets of A.

Example

For the set C given above, P(C)= {∅, {1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},C}

In general, for any finite set A with |A| = n ≥0, A has 2n subsets and that |P(A)| = 2n

Some Useful Sets

1. Z = the set of integers = {0,1,-1,2,-2,3,-3,…}
2. N = the set of non-negative integers of natural numbers = {0,1,2,3,…}
3. Z+ = the set of positive integers = {1,2,3,…}
4. Q = the set of rational numbers = {a/b | a,b ∈ Z, b ≠ 0}
5. Q+ = the set of positive rational numbers = {r | r ∈ Q, r>0)
6. R = the set of real numbers
7. R+ = the set of positive real numbers

1.5 Set Operations and the Laws of Set Theory

For A,B ⊆ U we define the following:

1. A ∪ B (the union of A and B) = {x | x ∈ A ∨ x ∈ B}
2. A ∩ B ( the intersection of A and B) = {x | x ∈ A  ∧ x ∈ B}
3. A Δ B  ( the symmetric difference of A and B) = {x | (x ∈ A ∨ x ∈ B) ∧ x ∉ A ∩ B} = {x | x ∈ A ∪ B ∧ x ∉ A ∩ B}

Note that if , A,B ⊆ U  then A ∪ B, A ∩ B, A Δ B ⊆ U  .Consequently, ∪, ∩ and Δ are closed binary operations on P(U) or that P(U) is closed under these binary operations.

Examples

With U = {1,2,3,4,5,6,7,8,9,10}, A = {1,2,3,4,5}, B= {3,4,5,6,7} and C = {7,8,9} we have:

1. A ∩ B = {3,4,5}
2. A ∪ B = {1,2,3,4,5,6,7}
3. B ∩ C = {7}
4. A ∩ C = ∅
5. A Δ B  = {1,2,6,7}
6. A ∪ C = {1,2,3,4,5,7,8,9}
7. A Δ C = {1,2,3,4,5,7,8,9}

Definition

Let A,B ⊆ U. The sets A and B are called disjoint, or mutually disjoint, when A ∩ B = ∅.

                                                                                            _      

For a set A ⊆ U, the complement of A, denoted U – A, or A is given by {x | x ∈ U ∧ x ∉ A}

Examples

Referring to sets A,B,C above:

_                          _                                 _

A = {6,7,8,9,10}, B = {1,2,8,9,10} and C = {1,2,3,4,5,6,10}

Definition

Let A,B ⊆ U. the relative complement of A in B, denoted B-A, is given by {x | x ∈ B ∧ x ∉ A}.

Examples

Referring to sets A,B,C above:

1. B-A = {6,7}
2. A-B = {1,2}
3. A-C = A
4. C-A = C                                         _
5. A-A = ∅                f) U –A = A

The Laws of Set Theory

For any sets A,B, and C taken from a universe U

    =

1. A = A                                Law of Double Complement

    _____      _     __

2. A ∪ B  = A ∩ B                        De Morgan’s Laws

    _____     __    __

    A ∩ B = A ∪ B  

3. A ∪ B  = B ∪ A                        Commutative Laws 

    A ∩ B  = B ∩ A

4. A ∪ (B ∪ C) = (A ∪ B) ∪ C                Associative Laws

    A ∩ (B ∩ C) = (A ∩ B) ∩ C

5. A ∪ (B ∩ C) =(A ∪ B) ∩ (A ∪ C)        Distributive Laws

    A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

6. A ∪ A = A                                Idempotent Laws

    A ∩ A = A

7. A ∪ U = U                                Identity laws

    A ∩  U  = A

            __

8. A ∪ A = U                                Inverse Laws

           __

    A ∩ A = ∅

9. A ∪ U = U                                Domination laws

    A ∩ ∅ = ∅

10. A ∪ (A ∩ B) = A                        Absorption Laws

      A ∩ (A ∪ B) = A

When we consider the relationships that exist between sets, we can investigate this graphically using something called a Venn diagram. A Venn diagram is constructed as follows: U is depicted as the interior of a rectangle, while subsets of  U  are represented by the interiors of circles.

The Venn diagram is a useful way of establishing set equalities. Another technique for establishing set equalities is the membership table.

We observe that for sets A,B ⊆ U, an element x ∈ U,satisfies exactly one of the following four situations:

1. x ∉A, x ∉B
2. x ∉A, x ∈B
3. x ∈A, x ∉B
4. x ∈A, x ∈B

This can then be written in tabular form, using a 0 when x is not in a set and a 1 when it is in a set.

Example

Use Membership Tables to establish the equality of A ∪ (B ∩ C) with (A ∪ B) ∩ (A ∪ C)

Set Theory – Tutorial Exercises

1. Which of the following sets are equal?

        a) {1,2,3}        b) {3,2,1,3}        c) {3,1,2,3}        d) {1,2,2,3}

2. Let A = {1, {1}, {2}}. Which of the following statements are true?

        a) 1 ∈ A        b) {1} ∈ A        c) {1} ⊆ A        d) {{1}} ⊆ A

        e) {2} ∈ A        f) {2} ⊆ A        g) {{2}} ⊆ A        h) {{2}] ⊃ A

3. Repeat question 2 using the set A = {1,2,{2}}

4. Determine all the elements in each of the following sets:

1. {1 + (-1)n | n ∈ N}
2. {n + (1/n} | n ∈ {1,2,3,5,7}}
3. {n3 + n2 | n ∈ {0,1,2,3,4}}
4. {1/(n2 + n) | n is an odd positive integer and n ≤11}

5. For A= {1,2,3,4,5,6,7}, determine the number of

1. Subsets of A
2. Nonempty subsets of A
3. Proper subsets of A
4. Nonempty proper subsets of A
5. Subsets of A containing 3 elements
6. Subsets of A containing 1,2
7. Subsets of A containing 5 elements including 1,2
8. Proper subsets of A containing 1,2
9. Subsets of A with an even number of elements
10. Subsets of A with an odd number of elements
11. Subsets of A with an odd number of elements, including the element 3

6. For U= {1,2,3,4,5,6,7,8,9,10}, let A={1,2,3,4,5}, B={1,2,4,8}, C={1,2,3,5,7} and D={2,4,6,8}. Determine each of the following:

        a) (A ∪ B) ∩ C

        b) A ∪ (B ∩ C)

                __     __

        c) C ∪ D

           ______

        d) C ∩ D

        e) (A ∪ B) –C

        f) A ∪ (B - C)

        g) (B – C) – D

        h) B – (C – D)

        i) (A ∪ B) - (C ∩ D)

7. Let U= {a,b,c,…x,y,z} with A={a,b,c} and C={a,b,d,e}. If | A ∩ B| =2 and (A ∩ B) ⊂ B ⊂ C, determine B.

8. Using Venn diagrams or Membership Tables, investigate the truth or falsity of the each of the following for sets A,B,C ⊆ U .

1. A Δ (B ∩ C) = (A  Δ B) ∩ (A  Δ C)
2. A ∩ (B  Δ C) = (A ∩ B) Δ (A ∩ C)

9. A supermarket discovers that from a sample of 50 shoppers, 30 buy tea, 25 buy coffee and 10 buy both coffee and tea. How many shoppers buy either coffee or tea.? (Hint – use Venn Diagrams)

---