Notes On Sets

1
1 Chapter 1 Algebra
1.1 Sets
Definition 1.1. A set is a collection of distinct objects.
This means that {1, 2, 3} is a set but {1, 1, 3} is not because 1 appears twice in
the second collection. The second collection is called a multiset. Sets are often
specified with curly brace notation. The set of even integers can be written:
{2n : n is an integer }.
Sets are fundamental discrete structures that form the basis of more complex
discrete structures like graphs.
The objects in a set are called elements or members of a set. A set is said
to contain its elements.
Recall the notation: for a set A, an element x we write;
x ∈ A if A contains x
and x ∈
/ A otherwise.
Definition 1.2. The empty set is a set containing no objects. It is written as
a pair of curly braces with nothing inside {} or by using the symbol ∅.
Definition 1.3. The set membership symbol ∈ is used to say that an object is
a member of a set. It has a partner symbol 3 which is used to say an object is
not in a set.
Definition 1.4. For two sets S and T we say that S is a subset of T if each
element of S is also an element of T . In formal notation S ⊆ T if for all x ∈ S
we have x ∈ T .
If S ⊆ T then we also say T contains S which can be written T ⊇ S. If

S ⊆ T and S 6= T then we write S ⊂ T and we say S is a proper subset of T .
Example 1.5. If A = {a, b, c} then A has eight different subsets:
∅ {a} {b} {c} {a, b} {a, c} {b, c} {a, b, c}.
Notice that A ⊆ A and in fact each set is a subset of itself. The empty set ∅ is
a subset of every set.
The set of all subsets of a given set is itself an imporant object and so has
a name.
Definition 1.6. The set of all subsets of a set S is called the powerset of S.
The notation for the powerset of S is P (S).
Definition 1.7. We say two sets are equal if they have exactly the same mem-
bers. Two sets, A and B are equal if they contain the same number of elements.
We thus write; A = B.
2
Example 1.8. If S = {1, 2, 3} then 3 ∈ S and 4 ∈ / S. The set membership

symbol is often used in defining operations that manipulate sets. The set T =
{2, 3, 1} is equal to S because they have the same members: 1, 2, and 3.
While we usually list the members of a set in a “standard” order (if one is
available) there is no requirement to do so and sets are indifferent to the order
in which their members are listed.
Similarly,
1. {2, 3, 5, 7} = {3, 2, 7, 5} since a set is unordered.
2. Also, {2, 3, 5, 7} = {2, 2, 3, 3, 5, 7} since a set contains unique elements.
3. However, {2, 3, 5, 7} =
6 {2, 3}.
Definition 1.9. A multi-set is a set where you specify the number of occur-
rences of each element: {m1 a1 , m2 a2 , ..., mr ar } is a set where m1 occurs a1
times, m2 occurs a2 times, etc.
Definition 1.10. The cardinality of a set is its size.
For a finite set, the cardinality of a set is the number of members it contains.
In symbolic notation the size of a set S is written | S |. We will deal with the
idea of the cardinality of an infinite set later.
Example 1.11. Set cardinality For the set S = {1, 2, 3} we show cardinality
by writing | S |= 3. We now move on to a number of operations on sets.
You are already familiar with several operations on numbers such as addition,
multiplication, and negation.
Definition 1.12. The intersection of two sets S and T is the collection of all
objects that are in both sets.
It is written S ∩ T . Using curly brace notation
S ∩ T = {x | (x ∈ S) and (x ∈ T )}.
The symbol and in the above definition is an example of a Boolean or logical

operation. It is only true when both the propositions it joins are also true. It
has a symbolic equivalent ∧. Let us write the formal definition of intersection
more compactly:
S ∩ T = {x | (x ∈ S) ∧ (x ∈ T )}.
Example 1.13. Intersections of sets Suppose S = {1, 2, 3, 5}, T = {1, 3, 4, 5}, and U =
{2, 3, 4, 5}. Then:
1. S ∩ T = {1, 3, 5},
2. S ∩ U = {2, 3, 5}, and
3
3. T ∩ U = {3, 4, 5}.
Definition 1.14. If A and B are sets and A ∩ B = ∅ then we say that A and
B are disjoint, or disjoint sets.
Definition 1.15. The union of two sets S and T is the collection of all objects
that are in either set. It is written as S ∪ T . Using curly brace notion we have;
S ∪ T = {x | (x ∈ S) or (x ∈ T )}.
The symbol or is another Boolean operation, one that is true if either of the
propositions it joins are true. Its symbolic equivalent is ∨ which lets us re-write
the definition of union as:
S ∪ T = {x | (x ∈ S) ∨ (x ∈ T )}.
Example 1.16. Unions of sets. Suppose S = {1, 2, 3}, T = {1, 3, 5}, and U =
{2, 3, 4, 5}. Then:
1. S ∪ T = {1, 2, 3, 5},
2. S ∪ U = {1, 2, 3, 4, 5}, and
3. T ∪ U = {1, 2, 3, 4, 5}.
Definition 1.17. The compliment of a set S is the collection of objects in the
universal set that are not in S.
The compliment is written S c . In curly brace notation
S c = {x | (x ∈ U) ∧ (x ∈
/ S)}
or more compactly as
S c = {x | x ∈
/ S}
however, it should be apparent that the compliment of a set always depends
on which universal set is chosen. When performing set theoretic computations,
you should declare the domain in which you are working. In set theory this is
done by declaring a universal set.
Definition 1.18. The universal set, at least for a given collection of set theoretic
computations, is the set of all possible objects.
Example 1.19. 1. Let the universal set be the integers. Then the compli-
ment of the even integers is the odd integers.
2. Let the universal set be {1, 2, 3, 4, 5}, then the compliment of S = {1, 2, 3}
is S c = {4, 5} while the compliment of T = {1, 3, 5} is T c = {2, 4}.
3. Let the universal set be the letters {a, e, i, o, u, y}. Then {y}c = {a, e, i, o, u}.
Definition 1.20. The difference of two sets S and T is the collection of objects
in S that are not in T . The difference is written S − T .
4
In curly brace notation
S − T = {x | x ∈ (S ∩ (T c ))},
or alternately
S − T = {x | (x ∈ S) ∧ (x ∈
/ T )}.
If we declare our universal set to be the integers then { 21 , 23 } is not a well
defined set because the objects used to define it are not members of the universal
set. The symbols { 12 , 23 } do define a set if a universal set that includes 12 and 23
is chosen. The problem arises from the fact that neither of these numbers are
integers. The universal set is commonly written U. Now that we have the idea
of declaring a universal set we can define another operation on sets.
1.2 Venn Diagrams

Definition 1.21. A Venn diagram is a way of depicting the relationship be-
tween sets. Each set is shown as a circle and circles overlap if the sets intersect.
For instance;
A B
1. Two sets A ∪ B
A B
2. Two sets A ∩ B
5
A B
3. Two sets (A ∪ B)c
A B
4. Two sets (A ∩ B)c
A B
5. Two sets (ArB). The complement of B in A.
A B
6. Two sets (BrA). The complement of A in B.

6
A B
7. Two sets Ac
A B
8. Two sets B c
A B
C
9. Three sets A ∪ B ∪ C
A B
C
10. Three sets Ac (B ∪ C)
7
A B
C
c
11. Three sets C
1.3 Questions
1. Suppose that we have the set U = {n | 0 ≤ n ≤ 100} of whole numbers
as our universal set. Let P be the prime numbers in U, let E be the even
numbers in U, and let F = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89}. Describe the
following sets either by listing them or with a careful English sentence.
(a) Ec.
(b) P ∩ F.
(c) P ∩ E.
(d) F ∩ E ∪ F ∩ Ec.
(e) (e) F ∪ F c .
2. Suppose S and T are sets. Prove that;
(a) (S ∪ T )c = S c ∩ T c .
(b) (S ∩ T )c = S c ∪ T c .
(c) A ∪ (B ∪ C) = (A ∪ B) ∪ C.
(d) A ∩ (B ∩ C) = (A ∩ B) ∩ C.
3. In a class of 100 students, 35 like science and 45 like Mathematics. 10 like
both.
(a) Represent the information on a venn diagram.
(b) How many students like either of them?
(c) How many students like neither?
4. There are 30 students in a class. Among them, 8 students are learning
both English and French. A total of 18 students are learning English. If
every student is learning at least one language, how many students are
learning French in total?
8
5. Which symbol is used to represent an element of?

(a) ⊂
(b) ∈
(c) ⊆
(d) 3
6. Given U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {2, 4, 6, 8}, B = {1, 3, 4, 5, 7} and C =
{7, 8} find:
(a) A ∩ B
(b) A ∪ B
(c) Ac ∪ B c
(d) B c
(e) (A ∩ C) ∩ (A ∪ B)
(f) A − B
(g) C c
7. Two sets are equal if and only if each is a subset of the other. In symbolic
notation: (A = B) ⇔ (A ⊆ B) ∧ (B ⊆ A). Prove.

Notes On Sets

Uploaded by

Copyright:

Available Formats

Notes On Sets

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Notes On Sets

Uploaded by

Copyright:

Available Formats

1

If S ⊆ T then we also say T contains S which can be written T ⊇ S. If

∅ {a} {b} {c} {a, b} {a, c} {b, c} {a, b, c}.

Example 1.8. If S = {1, 2, 3} then 3 ∈ S and 4 ∈ / S. The set membership

2. Also, {2, 3, 5, 7} = {2, 2, 3, 3, 5, 7} since a set contains unique elements.

The symbol and in the above definition is an example of a Boolean or logical

In curly brace notation

1.2 Venn Diagrams

3. Two sets (A ∪ B)c

4. Two sets (A ∩ B)c

5. Two sets (ArB). The complement of B in A.

6. Two sets (BrA). The complement of A in B.

5. Which symbol is used to represent an element of?

You might also like