Chapter 3

The Concept of Sets and Their

Operations

3.1 Introduction
Definition 3.1. A set is an unordered collection of objects.

Often, the objects in a set have a common property. For instance, all the
students in this class make up a set. We denote to a set by uppercase letters like
A, B, C, .. etc.

Definition 3.2. The objects in a set are called the elements, or members, of the
set. A set is said to contain its elements.

We write a ∈ A to denote that a is an element of the set A. The notation

a∈/ A denotes that a is not an element of the set A. Note that lowercase letters
are usually used to denote elements of sets.
There are several ways to describe a set. One way is to list all the members
of a set between braces { } with comma between each two elements, when this
is possible. For example, the notation {a, b, c, d} represents the set with the four
elements a, b, c, and d.

Example 3.1.

1. The set V of all vowels in the English alphabet can be written as

V = {a, e, i, o, u}.

2. The set A of odd positive integers less than 10 can be expressed by

A = {1, 3, 5, 7, 9}.

3. B = {a, 15, Aden, T iger} is a set.

13
 4. The set of positive integers less than 100 can be denoted by {1, 2, 3, · · · , 99}.

Another way to describe a set is to use set builder notation. In this way, we
characterize all those elements in the set by stating the property or properties
they must have to be members. For instance, the set O of all odd positive integers
less than 10 can be written as

O = {x | x is an odd positive integer less than 10},

or by using the set of positive integer Z+ as

O = {x ∈ Z+ | x is odd and x < 10}.

We often use this type of notation to describe sets when it is impossible to list
all the elements of the set.
Example 3.2.
1. The set O of all odd integers can be described as

O = {x ∈ Z | x = 2k + 1, k ∈ Z}.

2. The set E of all even integers can be described as

E = {x ∈ Z | x = 2k, k ∈ Z}.

3. The set Q of rational numbers can be described as

p
Q = {x ∈ R | x = , q 6= 0, p, q ∈ Z}.
q

4. The set of positive integers less than 100, {1, 2, 3, · · · , 99} can be described
by
{x ∈ Z+ | x < 100}.

Remark 3.1. These sets, each denoted using a boldface letter, play an important
role in discrete mathematics:
N = {0, 1, 2, 3, · · · } the set of natural numbers
Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · } the set of integer numbers
Z+ = {1, 2, 3, · · · } the set of positive integers
 
p
Q= p ∈ Z, q ∈ Z, q 6= 0 the set of rational numbers
q
0
R = Q ∪ Q the set of real numbers.

14
Definition 3.3. Two sets A and B are equal if and only if they have the same
elements, and we write A = B.

Example 3.3. The sets {1, 3, 5}, {3, 1, 5} and {1, 1, 3, 3, 3, 5, 5, 5, 5} are equal
because they have the same elements.

Sets can be represented graphically using Venn diagrams. In Venn dia-

grams the universal set U , which contains all the objects under consideration,
is represented by a rectangle. Inside this rectangle, circles or other geometrical
figures are used to represent sets. Sometimes points are used to represent the
particular elements of the set.

Venn diagrams are often used to indicate the relationships between

sets.

Example 3.4. The Venn diagram that represents V , the set of vowels in the
English alphabet is as follows.

Figure 3.1: Venn Diagram for the Set of Vowels

There is a special set that has no elements. This set is called the empty set,
or null set, and is denoted by φ. The empty set can also be denoted by { }. A
set with one element is called a singleton set.

Definition 3.4. The set A is said to be a subset of B if and only if every element
of A is also an element of B. We use the notation A ⊆ B to indicate that A is a
subset of the set B.

15
 U

Figure 3.2: Venn digram showing A ⊆ B

Example 3.5.

1. {1, 3, 5, 7, 9} is a subset of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

2. Z is a subset of Q.

3. Q is a subset of R.

4. The set of people of Yemen is a subset of the people of Yemen (that is, it
is a subset of itself).

Theorem 3.1. For every set S

(i) φ ⊆ S.

(ii) S ⊆ S.

Proof. Let S be a set. Then

(i) To show that φ ⊆ S, we need to show that ∀x (x ∈ φ −→ x ∈ S) is true.

Because the empty set contains no elements, it follows that x ∈ φ is always
false. It follows that the conditional statement x ∈ φ −→ x ∈ S is always
true, because its hypothesis is always false and a conditional statement
with a false hypothesis is true. (This type of proofs is called the Vacuous
proof).

(ii) To show that S ⊆ S, we need to show that ∀x (x ∈ S −→ x ∈ S) is

true. Because the conclusion x ∈ S is always true (by hypothesis), then the
conditional statement x ∈ S −→ x ∈ S is always true. (This type of proofs
is called the Trivial proof).

16
 Actually, to prove that two sets A and B are equal, we must prove that A ⊆ B
and B ⊆ A.
Now, if a set A is a subset of a set B but A 6= B, we write A ⊂ B and say
that A is a proper subset of B.
Definition 3.5. Let S be a set. The cardinality of S denoted by |S| is the
number of distinct elements in S.

Example 3.6.
1. If A = {1, 3, 5, 7, 9}, then |A| = 5.

2. {1, 3, 3, 5, 5} = 3.

3. φ = 0.

3.2 The Power Set

Definition 3.6. Let S be a set with cardinality |S| = n. The power set of S is
the set of all subsets of the set S. The power set of S is denoted by P (S) and its
cardinality is given by |P (S)| = 2n .

Example 3.7. What is the power set of the set S = {0, 1, 2}?
Solution: By Definition 3.6, |P (S)| = 23 = 8. Therefore,
 
P (S) = φ, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, S .

Example 3.8. What is the power set of the empty set? What is the power set
of the set {φ}?
Solution: |P (φ)| = 20 = 1. Therefore, P
(φ) = {φ}.

1
|P ({φ})| = 2 = 2. Therefore, P ({φ}) = φ, {φ} .

3.3 Cartesian Products

Definition 3.7. Let A and B be sets. The Cartesian product of A and B,
denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B.
Hence,  
A × B = (a, b) | a ∈ A ∧ b ∈ B .

17
Example 3.9. What is the Cartesian product of A = {1, 2} and
B = {a, b, c}?

Solution: The Cartesian product A × B is

 
A × B = (1, a), (1, b), (1, c), (2, a), (2, b), (2, c) .

A subset R of the Cartesian product A × B is called a relation from the set

A to the set B. The elements of R are ordered pairs, where the first element
belongs to A and the second to B. For example, R = (1, a), (2, a), (1, b) is a
relation from A to B.

Example 3.10. Show that the Cartesian product B × A is not equal to the
Cartesian product A × B, where A and B are as in Example 3.9.

Solution: The Cartesian product B × A is

 
B × A = (a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2) ,

which is not equal A × B in Example 3.9.

18
 Exercises 4

1. List the members of these sets.

(i) {x | x is a real number such that x2 = 1}.

(ii) {x | x is a positive integer less than 12}.
(iii) {x | x is the square of an integer and x < 100}.
(iv) {x | x is an integer such that x2 = 2}.

2. Use set builder notation to give a description of each of these sets.

(i) {0, 3, 6, 9, 12}.

(ii) {−3, −2, −1, 0, 1, 2, 3}.
(iii) {m, n, o, p}.

3. Determine whether each of these pairs o f sets are equal.

(i) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1}.

 
(ii) {1} , 1, {1} .
(iii) φ, {φ}.

4. Suppose that A = {2, 4, 6}, B = {2, 6}, C = {4, 6} and D = {4, 6, 8}.
Determine which of these sets are subsets of which other of these sets.

5. Find two sets A and B such that A ∈ B and A ⊆ B.

6. For each of the following sets, determine whether 2 is an element of that

set.

(i) {x ∈ R | x is an integer greater than 1}.

(ii) {x ∈ R | x is the square of an integer }.

(iii) 2, {2} .
 

(iv) {2}, {2} .
 

(v) {2}, 2, {2} .
 

(vi) {2} .

7. For each of the sets in Exercise 6, determine whether {2} is an element of

that set.

19
 8. Determine whether each of these statements is true or false.

(i) 0 ∈ φ.
(ii) {0} ⊂ φ.

(iii) φ ∈ φ .

(iv) {φ} ⊂ φ, {φ} .
 
(v) {φ} ⊂ φ, {φ} .

(vi) φ ∈ φ, {φ} .
 
(vii) {φ} = {φ}, {φ} .

9. Determine whether each of these sets is the power set of a set, where a and
b are distinct elements.

(i) φ.

(ii) φ, {a} .

(iii) φ, {a}, {φ, a} .

(iv) φ, {a}, {b}, {a, b} .

10. Let A = {a, b, c, d} and B = {y, z}. Find

(i) A × B.
(ii) B × A.

11. Let A be a set. Show that φ × A = A × φ = φ.

20
3.4 Set Operations
In this section, some operations on sets are presented.

3.4.1 Union of two sets

Definition 3.8. Let A and B be two sets. The union of the sets A and B,
denoted by A ∪ B, is the set that contains those elements that are either in A or
in B, or in both.

An element x belongs to the union of the sets A and B if and only if x belongs
to A or x belongs to B. Hence,
 
A ∪ B = x|x ∈ A ∨ x ∈ B .

The Venn diagram shown in Figure 3.3 represents the union of two sets A
and B. The area that represents A ∪ B is the shaded area within either the circle
representing A or the circle representing B.

A B

Figure 3.3: Venn digram showing A ∪ B

Example 3.11. The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5};
that is, {1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}.

3.4.2 Intersection of two sets

Definition 3.9. Let A and B be two sets. The intersection of the sets A and B,
denoted by A ∩ B, is the set containing those elements in both A and B.

21
 An element x belongs to the intersection of the sets A and B if and only if x
belongs to A and x belongs to B. Hence,
 
A ∩ B = x|x ∈ A ∧ x ∈ B .

The Venn diagram shown in Figure 3.4 represents the intersection of two sets
A and B. The shaded area that is within both the circles representing the sets
A and B is the area that represents the intersection of A and B.

A B

A∩B

Figure 3.4: Venn digram showing A ∩ B

Example 3.12. The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3};
that is, {1, 3, 5} ∩ {1, 2, 3} = {1, 3}.

Definition 3.10. Two sets are called disjoint if their intersection is the empty
set.

Example 3.13. Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}. Because A ∩ B =

φ, A and B are disjoint.

We often are interested in finding the cardinality of a union of two finite sets
A and B. Note that |A| + |B| counts each element that is in A but not in B or in
B but not in A exactly once, and each element that is in both A and B exactly
twice. Thus, if the number of elements that are in both A and B is subtracted
from |A| + |B|, elements in A ∩ B will be counted only once. Hence,

|A ∪ B| = |A| + |B| − |A ∩ B|.

22
3.4.3 Difference of two sets
Definition 3.11. Let A and B be two sets. The difference of A and B, denoted
by A − B, is the set containing those elements that are in A but not in B. The
difference of A and B is also called the complement of B with respect to A.

An element x belongs to the difference of A and B if and only if x ∈ A and

x∈
/ B. Hence,  
A − B = x|x ∈ A ∧ x ∈ /B .

The Venn diagram shown in Figure 3.5 represents the difference of the sets A
and B. The shaded area inside the circle that represents A and outside the circle
that represents B is the area that represents A − B.

A B

A−B

Figure 3.5: Venn digram showing A − B

Example 3.14. The difference of the sets {1, 3, 5} and {1, 2, 3} is the set {5};
that is, {1, 3, 5} − {1, 2, 3} = {5}. This is different from the difference of {1, 2, 3}
and {1, 3, 5}, which is the set {2}.

3.4.4 Complement of a set

Once the universal set U has been specified, the complement of a set can be
defined.
Definition 3.12. Let U be the universal set. The complement of the set A,
denoted by A, is the complement of A with respect to U . In other words, the
complement of the set A is U − A.

An element x belongs to A if and only if x ∈

/ A. Hence,

A = x|x ∈ /A .

23
 In Figure 3.6, the shaded area outside the circle representing A is the area
representing A.

Figure 3.6: Venn digram showing A

Example 3.15. Let The universal set U be the set of letters of the English
alphabet. Then the complement of the set of vowels A = {a, e, i, o, u} is
A = {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}.

Example 3.16. Let A be the set of positive integers greater than 10 (where the
universal set U is the set of all positive integers). Then A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

3.5 Set Identities

Table 3.1 lists the most important set identities. We will prove several of these
identities here, using three different methods.
To show that two sets are equal we have three ways, the first way uses the
set builder notation (as in Example 3.17) and in the second way we show that
each side is a subset of the other. Recall that to show that one set is a subset
of a second set, we can show that if an element belongs to the first set, then it
must also belong to the second set. We generally use a direct proof to do this
(see Example 3.18).

24
 Identity Name of The Identity

A∪φ=A Identity Laws

A∩U =A

A∪U =U Domination Laws

A∩φ=φ

A∪A=A Idempotent Laws

A∩A=A

A=A Complementation Law

A∪B =B∪A Commutative Laws

A∩B =B∩A

Associative Laws



A ∪ B ∪ C
= A ∪ B
∪ C
A∩ B∩C = A∩B ∩C

A ∪ B ∩ C
= A ∪ B
∩ A ∪ C
Distributive Laws
A∩ B∪C = A∩B ∪ A∩C

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

A∩B =A∪B

A∪A=U Complement Laws

A∩A=φ

A ∪ A ∩ B
= A Absorption Laws
A∩ A∪B =A

Table 3.1: The Set Identities

25
 Finally, in the third way we can prove these identities by using a type of
tables is called a membership table. We illustrate the set builder type of proof
by establishing the second of De Morgan’s laws as follows:
Example 3.17. Use the set builder notation and logical equivalences to prove
that:
A ∩ B = A ∪ B.
Solution:  
A∩B = x x∈
/ A∩B
 


= x ∼ x∈A ∩B
 


= x ∼ x∈A∧ x∈B
 



= x ∼ x∈A ∨ ∼ x∈B
 
= x x∈
/A ∨ x∈
/B
 
= x x∈A ∨ x∈B

=A ∪ B.

Example 3.18 illustrates the second way of proving the set identities.

Example 3.18. Prove that

A∩ B∪C = A∩B ∪ A∩C .

Solution: Let



x ∈ A ∩ B ∪ C ⇒x ∈ A ∧ x ∈ B ∪ C


⇒x ∈ A ∧ x ∈ B ∨ x ∈ C



⇒ x∈A ∧ x∈ B ∨ x∈A ∧ x∈ C



⇒x ∈ A ∩ B ∨ x ∈ A ∩ C
 



⇒x ∈ A ∩ B ∪ A ∩ C .

Therefore,




A∩ B∪C ⊆ A∩B ∪ A∩C (1)

Now, let

26
  





x∈ A∩B ∪ A∩C ⇒x ∈ A ∩ B ∨ x ∈ A ∩ C



⇒ x∈A ∧ x∈ B ∨ x∈A ∧ x∈ C


⇒x ∈ A ∧ x ∈ B ∨ x ∈ C


⇒x ∈ A ∧ x ∈ B ∪ C


⇒x ∈ A ∩ B ∪ C

Thus,




A∩B ∪ A∩C ⊆ A∩ B∪C (2)

Hence, from (1) and (2) the proof is done.

As mentioned above, set identities can also be proved using membership

tables. We consider each combination of sets that an element can belong to and
verify that elements in the same combinations of sets belong to both the sets in
the identity. To indicate that an element is in a set, a 1 is used; to indicate that
an element is not in a set, a 0 is used.

Example 3.19. Use the membership table method to prove that:

A∩ B∪C = A∩B ∪ A∩C .

Solution: The membership table for these combinations of sets is shown in

Table 3.2. This table has eight rows (why?).

A B C B ∪C A∩ B∪C A∩B A∩C A∩B ∪ A∩C

1 1 1 1 1 1 1 1

1 1 0 1 1 1 0 1

1 0 1 1 1 0 1 1

1 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0

Table 3.2: A Membership Table for A ∩ B ∪ C = A ∩ B ∪ A ∩ C

27
 Additional set identities can be established using those that we have already
proved. Consider Example 3.20.

Example 3.20. Show that:

A ∪ B ∩ C = C ∪ B ∩ A.

Solution:


A ∪ B ∩ C =A ∩ B ∩ C


=A ∩ B ∪ C


=A ∩ C ∪ B


= C ∪ B ∩ A.

3.6 Generalized Unions and Intersections

The union A ∪ B ∪ C represents the set of elements that are in at least one of the
sets A, B, and C. Also, the intersection A ∩ B ∩ C represents the set of elements
that are in all of the sets A, B, and C. (see Figure 3.7 and Figure 3.8)

U
C

A B

Figure 3.7: Venn digram showing A ∪ B ∪ C

28
 U
C

A B

Figure 3.8: Venn digram showing A ∩ B ∩ C

Example 3.21. Let A = {0, 2, 4, 6, 8}, B = {0, 1, 2, 3, 4}, and C = {0, 3, 6, 9}.
What are A ∪ B ∪ C and A ∩ B ∩ C ?

Solution: The set A ∪ B ∪ C contains those elements in at least one of A, B,

and C. Hence, A ∪ B ∪ C = {0, 1, 2, 3, 4, 6, 8, 9}.
The set A ∩ B ∩ C contains those elements in all three of A, B, and C. Thus,
A ∩ B ∩ C = {0}.
We can also consider unions and intersections of an arbitrary number of sets.
We use these definitions.

Definition 3.13. The union of a collection of sets is the set that contains those
elements that are members of at least one set in the collection, i.e.
n
[
A1 ∪ A2 ∪ · · · ∪ An = Ai .
i=1

Definition 3.14. The intersection of a collection of sets is the set that contains
those elements that are members of all the sets in the collection, i.e.
n
\
A1 ∩ A2 ∩ · · · ∩ An = Ai .
i=1

The following example illustrates the generalized of unions and intersections.

n
[ n
\
Example 3.22. Let Ai = {i, i + 1, i + 2, · · · }. Find Ai and Ai ?
i=1 i=1

Solution: From the definition of the sets Ai , it can be seen that:

29
 A1 = {1, 2, 3, · · · }, A2 = {2, 3, 4, · · · }, . . . , An = {n, n + 1, n + 2, · · · }. Hence,
n
[ n
[
Ai = {i, i + 1, i + 2, · · · } = {1, 2, 3, · · · } = A1
i=1 i=1

and n n
\ \
Ai = {i, i + 1, i + 2, · · · } = {n, n + 1, n + 2, · · · } = An
i=1 i=1

We can extend the notation of generalized unions and intersection, respec-

tively, to an infinity number of sets as follows:
∞
[
A1 ∪ A2 ∪ · · · ∪ An ∪ · · · = Ai ,
i=1

and ∞
\
A1 ∩ A2 ∩ · · · ∩ An ∩ · · · = Ai .
i=1

The following example, illustrates these notations.

∞
[
Example 3.23. Suppose Ai = {1, 2, 3, · · · , i} for i = 1, 2, 3, · · · . Find Ai
i=1
∞
\
and Ai ?
i=1

Solution: From the definition of the sets Ai , it can be seen that:

A1 = {1}, A2 = {1, 2}, . . . , An = {1, 2, 3, · · · , n}. Hence,
∞
[ ∞
[
Ai = {1, 2, 3, · · · , i} = {1, 2, 3, · · · } = Z+ ,
i=1 i=1

and ∞ ∞
\ \
Ai = {1, 2, 3, · · · , i} = {1} = A1 .
i=1 i=1

3.7 Partitions of Sets

Definition 3.15. Let A be a set and S ⊆ P (A), where P (A) is the power set of
A. Then the set S is said to be a partition of the set A if and only if the following
conditions are satisfied:

30
  
(i) φ ∈
/ S or ∀ X ∈ S, X =
6 φ .

(ii) ∀ X, Y ∈ S, X ∩ Y = φ.
n
[
(iii) Xi = A, where Xi ∈ S, ∀ i = 1, 2, · · · , n.
i=1

Example 3.24. Suppose A = {1, 2, 3, 4, 5, 6}. Which of the following sets repre-
sent a partition of A.  
S1 = {1, 4, 5}, {2}, {3, 6}
 
S2 = φ, {1, 2}, {3, 4, 5, 6}
 
S3 = {1, 2, 3, 4}, {4, 5, 6}
 
S4 = {1, 2}, {4, 5, 6} .

Solution: First, for S1 :

(i) The first condition is satisfied, because φ ∈
/ S1 .
(ii) The second condition is satisfied, because
{1, 4, 5} ∩ {2} = φ, {1, 4, 5} ∩ {3, 6} = φ, and {3, 6} ∩ {2} = φ.
(iii) The third condition is satisfied, because
{1, 4, 5} ∪ {2} ∪ {3, 6} = A.
Hence, S1 is a partition of A.

Next, for S2 :

The first condition is not satisfied, because φ ∈ S2 . Therefore, S2 is not partition

of A.

Also, for S3 :

The second condition is not satisfied, because {1, 2, 3, 4} ∩ {4, 5, 6} = {4} 6= φ.

Thus, S3 is not partition of A.

Finally, for S4 :

The third condition is not satisfied, because

{1, 2} ∪ {4, 5, 6} = {1, 2, 4, 5, 6} =
6 A.

31
Therefore, S4 is not partition of A.

3.8 Computer Representation of Sets

Assume that the universal set U is finite (and of reasonable size so that the
number of elements of U is not larger than the memory size of the computer
being used). First, specify an arbitrary ordering of the elements of U , for instance
a1 , a2 , . . . , an . Represent a subset A of U with the bit string of length n, where
the ith bit in this string is 1 if ai belongs to A and is 0 if ai does not belong to
A. Example 3.25 illustrates this technique.

Example 3.25. Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements

of U has the elements in increasing order; that is, ai = i. What bit strings
represent the subset of all odd integers in U , the subset of all even integers in U ,
and the subset of integers not exceeding 5 in U ?

Solution: Let A denotes to the set of all odd integers in U , B denotes to the set
of all even integers in U and C denotes to the set of integers not exceeding 5 in
U . i.e. A = {1, 3, 5, 7, 9}, B = {2, 4, 6, 8, 10} and C = {1, 2, 3, 4, 5}. Therefore,
A : 1010101010, B : 0101010101, and C : 1111100000

Example 3.26. In Example 3.25, Find A ∪ B, A ∪ C, B ∩ C, A − C, B − C,

C − A and C − B, using the bit strings of A, B and C ?

Solution: Using the membership table technique for the corresponding positions
in the bit strings, it can be seen that:
A ∪ B : 1010101010 ∪ 0101010101 = 1111111111 : U .
A ∪ C : 1010101010 ∪ 1111100000 = 1111101010 : {1, 2, 3, 4, 5, 7, 9}.
B ∩ C : 0101010101 ∩ 1111100000 = 0101000000 : {2, 4}.
A − C = A ∩ C : 1010101010 ∩ 0000011111 = 0000001010 : {7, 9},

or directly we can find the difference A − C by doing the subtraction between

their corresponding positions with noting that the value −1 it must be 0 in the
bit string of the result set, as follows:
A − C : 1010101010 − 1111100000 = 0000001010 : {7, 9}.
B − C : 0101010101 − 1111100000 = 0000010101 : {6, 8, 10}.
Find C − A and C − B.

32
 Exercises 5

1. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find

(i) A ∪ B
(ii) A ∩ B
(iii) A − B
(iv) B − A

2. Assume that U be the universal set and A be a subset of U

(i) Prove that, A = A

(ii) Prove that, A ∪ φ = A and A ∩ U = A.
(iii) Prove that, A ∩ φ = φ and A ∪ U = U .
(iv) Prove that, A ∩ A = A and A ∪ A = A.
(v) Prove that, A ∪ A = U and A ∩ A = φ.
(vi) Show that, A − φ = A and φ − A = φ.

3. Find the sets A and B if A − B = {1, 5, 7, 8}, B − A = {2, 10}, and

A ∩ B = {3, 6, 9}.

4. Prove the first De Morgan law in Table 3.1 by showing that if A and B two
are sets, then A ∪ B = A ∩ B

(i) by showing each side is a subset of the other side.

(ii) using a membership table.

5. Let A and B be two sets. Show that

(i) A ∩ B ⊆ A.


(ii) A ⊆ A ∪ B .
(iii) A − B ⊆ A.


(iv) A ∩ B − A = φ.


(v) A ∪ B − A = A ∪ B.

6. Show that if A and B are two sets, then A − B = A ∩ B.

7. From Table 3.1, show that if A, B, and C are sets, then

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

33
 (iii) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

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

Find

(i) A ∩ B ∩ C
(ii) A ∪ B ∪ C
(iii) (A ∪ B) ∩ C
(iv) (A ∩ B) ∪ C

9. Let A and B be subsets of a universal set U . Show that A ⊆ B if and only

if B ⊆ A ?
n
[ n
\
10. Find Ai and Ai if
i=1 i=1

(i) Ai = {1, 2, 3, · · · , i} for i = 1, 2, 3, · · · .

(ii) Ai = {· · · , −2, −1, 0, 1, 2, · · · , i} for i = 1, 2, 3, · · · .
∞
[ ∞
\
11. Find Ai and Ai if for every positive integer i
i=1 i=1

(i) Ai = {i, i + 1, i + 2, · · · }.
(ii) Ai = {0, i}.
(iii) Ai = {−i, i}.
(iv) Ai = {−i, −i + 1, · · · , −1, 0, 1, · · · , i − 1, i}.

12. Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Express each of these sets with bit
strings

(i) A = {3, 4, 5}.

(ii) B = {1, 3, 6, 10}.
(iii) C = {2, 3, 4, 7, 8, 9}.

13. In Exercise 12, find by using the bit strings of the sets

(i) A ∩ B.
(ii) A ∪ B.
(iii) B − A.
(iv) C − A.
(v) C − B.

34
14. Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Find the set specified by each of these
bit strings

(i) 1111001111.
(ii) 0101111000.
(iii) 1000000001.

35