CMP208 - Discrete Structure 2023/2023 session October 1, 2023

SET THEORY
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}
The opening and closing curly braces denote a set, 2n specifies the members of the set, the
colon says, “such that” or “where” and everything following the colon are conditions that
explain or refine the membership. All correct mathematics can be spoken in English. The set
definition above is spoken “The set of twice n where n is an integer”.
The only problem with this definition is that we do not yet have a formal definition of the
integers. The integers are the set of whole numbers, both positive and negative: {0, ±1, ±2,
±3, . . .}. We now introduce the operations used to manipulate sets, using the opportunity to
practice curly brace notation.

Representation of a Set
Sets can be represented in two ways: The Roster form and the Set-Builder form. These two
forms can be used to represent the same data, just the style varies in both cases.
1.) Roster Form: In Roster Form, the elements are inside {} ⇢ Curly brackets. All the
elements are mentioned inside and are separated by commas. Roster form is the easiest
way to represent the data in groups. For example, the set for the table of 5 will be, A= {5,
10, 15, 20, 25, 30, 35….}.

2.) Set-Builder Form: In the Set-builder form, elements are shown or represented in
statements expressing relation among elements. The standard form for Set-builder, A= {a:
statement}. For example, A = {x: x = a3, a ∈ N, a < 9}.

Empty Set
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 ∅. The empty set is a handy object. It is also quite
strange. The set of all students that weigh at least eight tons, for example, is the empty set.
Sets whose definition contains a contradiction or impossibility are often empty.

Membership
The set membership symbol ∈ is used to say that an object is a member of a set. It has a
partner symbol ∈/ which is used to say an object is not in a set. The symbol, ∈, read as “is an
element of” or “is in,” indicates membership in a set. The symbol, ∉, read as “is not an
element of” or “is not in,” indicates lack of membership in a set.

1
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

Example:
1. 3 ∈ {1,2,3,4} is read as “3 is an element of the set containing 1, 2, 3, and 4” or “3 is in
the set containing 1, 2, 3, and 4.”
This statement is true, as 3 is listed in {1,2,3,4}
2. 3 ∉ {1,2,3,4} is read as “3 is not an element of the set containing 1, 2, 3, and 4” or “3
is not in the set containing 1, 2, 3, and 4.”
This statement is false, as 3 is listed in {1,2,3,4}
3. 5 ∉ {1,2,3,4} is read as “5 is not an element of the set {1,2,3,4}” or “5 is not in the
set {1,2,3,4}.”
This statement is true, as 5 is not in the listed in {1,2,3,4}.
4. 5 ∈ {1,2,3,4} is read as “5 is an element of the set {1,2,3,4}” or “5 is in the
set {1,2,3,4}.”
This statement is false, as 5 is not in the listed in {1,2,3,4}.
5. Y ∉ {a, e, i, o, u} is read as “y is not an element of the set containing “a, e, i, o and u”
This statement is true because y is not listed in {a, e, i, o, u}

Exercise: Decide whether the following statements are true or false.

Set Equality
Two sets are equal if they have exactly the same members. For example, A and B are equal if
each element in A is in B and if each element in B is in A. If two sets A and B are equal, we
write A = B. If two sets A and B are not equal, we write A≠B. For example, if:
A = {1, 2, 3}
B = {3 ,2, 1}
A is equal to B 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 i.e. The order in which
the elements are listed in roster form does not change the set. Othe examples include:
1. {1,2} ≠ {1,2,3}, as 3 is not in {1,2}.
2. {a, b, c} ≠ {1,2,3}, as a is not in {1,2,3}.
3. {} ≠ {1} as the number 1 is not contained in the empty set.
4.
Exercise: Let C = {1,3,5,6}. For each statement indicate whether it is true or false.

2
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

Cardinality
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.
For the set S = {1, 2, 3} we show cardinality by writing |S| = 3

Set Operation
Having got the basics of a set theory, we now move on to a few operations on sets. You are
already familiar with several operations on numbers such as addition, multiplication, and
negation.

Intersection
The intersection of two sets S and T is the collection of all objects that are COMMON 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 ∧. This lets us
write the formal definition of intersection more compactly: S ∩ T = {x: (x ∈ S) ∧ (x ∈ T)}

Example: Intersections of sets, Suppose:

S = {1, 2, 3, 5},
T = {1, 3, 4, 5}, and
U = {2, 3, 4, 5}

S ∩ T = {1, 3, 5},
S ∩ U = {2, 3, 5}, and
T ∩ U = {3, 4, 5}

If A and B are sets and A ∩ B = ∅ then we say that A and B are disjoint, or disjoint sets.

3
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

Union
The union of two sets S and T is the collection of all objects that are in either set. It is written
S ∪ T. Using curly brace notion 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: Unions of sets.
Suppose S = {1, 2, 3}, T = {1, 3, 5}, and U = {2, 3, 4, 5}. Then:
S ∪ T = {1, 2, 3, 5},
S ∪ U = {1, 2, 3, 4, 5}, and
T ∪ U = {1, 2, 3, 4, 5}

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.

Universal Set
The universal set, at least for a given collection of set theoretic computations, is the set of all
possible objects. If we declare our universal set to be the integers then {1.2, 2.3} is not a
well-defined set because the objects used to define it are not members of the universal set.
The symbols {1.2, 2.3} do define a set if a universal set that includes 1 2 and 2 3 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.

Compliment of Set
The compliment of a set S is the collection of objects in the universal set that are not in S.
The compliment is written Sc. In curly brace notation
Sc = {x: (x ∈ U) ∧ (x /∈ S)}
or more compactly as
Sc = {x: x /∈ S}
However, it should be apparent that the compliment of a set always depends on which
universal set is chosen. There is also a Boolean symbol associated with the complementation
operation: the not operation. The notation for not is ¬. There is not much savings in space as
the definition of compliment becomes Sc = {x: ¬ (x ∈ S)}
Example
(i) Let the universal set be the integers. Then the compliment of the even integers is
the odd integers.
(ii) Let the universal set, U={1, 2, 3, 4, 5}, S = {1, 2, 3}, T = {1, 3, 5}

4
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

then the compliment of S is Sc = {4, 5} while the compliment of T, is Tc = {2, 4}.

(iii) Let the universal set be the letters {a, e, i, o, u, y}. Then {y}c = {a, e, i, o, u}.

Venn Diagram
A Venn diagram is a way of depicting the relationship between sets. Each set is shown as a circle and
circles overlap if the sets intersect. For example, the following are Venn diagrams for the intersection
and union of two sets. The shaded parts of the diagrams are the intersections and unions
respectively.

Notice that the rectangle containing the diagram is labelled with a U representing the
universal set. We now have enough set-theory operators to use them to define more
operators quickly. We will continue to give English and symbolic definitions.

Difference
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. In curly brace notation
S − T = {x: x ∈ (S ∩ (T c))}, or alternately
S − T = {x: (x ∈ S) ∧ (x /∈ T)}
Notice how intersection and complementation can be used together to create the difference
operation and that the definition can be rephrased to use Boolean operations. There is a set

5
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

of rules that reduces the number of parentheses required. These are called operator
precedence rules.
(i) Other things being equal, operations are performed left-to-right.
(ii) Operations between parenthesis are done first, starting with the innermost of
nested parenthesis.
(iii) All complimentations are computed next.
(iv) All intersections are done next.
(v) All unions are performed next.
(vi) Tests of set membership and computations, equality or inequality are performed
last. Special operations like the set difference or the symmetric difference,
defined below, are not included in the precedence rules, and thus always use
parenthesis.

Example
Operator precedence Since complementation is done before intersection the symbolic
definition of the difference of sets can be rewritten:
S − T = {x: x ∈ S ∩ Tc}
If we were to take the set operations
A ∪ B ∩ Cc
and put in the parenthesis we would get:
(A ∪ (B ∩ (Cc)))

The Symmetric Difference

The symmetric difference of two sets S and T is the set of objects that are in one and only one of the
sets. The symmetric difference is written S∆T. In curly brace notation:

S∆T = {(S − T) ∪ (T − S)}

Example: Let S be the set of non-negative multiples of two that are no more than twenty-four.

Let T be the nonnegative multiples of three that are no more than twenty-four.

Then S∆T = {2, 3, 4, 8, 9, 10, 14, 15, 16, 20, 21, 22}

Another way to think about this is that we need numbers that are positive multiples of 2 or 3 (but
not both) that are no more than 24.

Another important tool for working with sets is the ability to compare them. We have already
defined what it means for two sets to be equal, and so by implication what it means for them to be
unequal. We now define another comparator for sets.

6
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

Subset of a Set
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≠T then we write S ⊂ T and we say S is a proper subset of T

Example:

Subsets 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.

Applications of Set in Computer applications

Set is selected over other data structures if you intend to add each item only once. Sets
never allow duplicates. You don't care about the order of the items in the set. Sets are
different from arrays in the sense that they only allow non-repeated, unique values within
them.
Set data structures are commonly used in a variety of computer science applications,
including algorithms, data analysis, and databases. The following are the specific
applications of sets.
 Sets are used in the music player app to list all the songs in proper order.
 Sets are used to determine the distinct values in an array.
 Sets are used to detect cycles in a Linked List.
 Sets are used in various database operations such as performing joins.

Set in Programming
A Set in Python programming is an unordered collection data type that is iterable, mutable
and has no duplicate elements.
Set are represented by { } (values enclosed in curly braces)
The major advantage of using a set, as opposed to a list is that it has a highly optimized
method for checking whether a specific element is contained in the set. This is based on a
data structure known as a hash table. Since sets are unordered, we cannot access items
using indexes as we do in lists.
var = {"Geeks", "for", "Geeks"}

7
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

type(var)
Output: set

Type Casting with Python Set method.

The Python set() method is used for type casting. The following demonstrate the use of such
method

# typecasting list to set

myset = set(["a", "b", "c"])
print(myset)

# Adding element to the set

myset.add("d")
print(myset)

Output:
Python set is an unordered datatype, which means we cannot know in which order the
elements of the set are stored.
{'c', 'b', 'a'}
{'d', 'c', 'b', 'a'}

Check unique and Immutable with Python Set

Python sets cannot have a duplicate value and once it is created, we cannot change its
value.

# Python program to demonstrate that

# a set cannot have duplicate values
# and we cannot change its items

# a set cannot have duplicate values

myset = {"Geeks", "for", "Geeks"}
print(myset)

# values of a set cannot be changed

myset[1] = "Hello"
print(myset)

Output:

8
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

The first code explains that the set cannot have a duplicate value. Every item in it is a
unique value.
The second code generates an error because we cannot assign or change a value once the
set is created. We can only add or delete items in the set.
{'Geeks', 'for'}
TypeError: 'set' object does not support item assignment.

Heterogeneous Element with Python Set

Python sets can store heterogeneous elements in it, i.e., a set can store a mixture of
string, integer, boolean, etc datatypes.

# Python example demonstrate that a set

# can store heterogeneous elements
myset = {"Geeks", "for", 10, 52.7, True}
print(myset)

Output:
{True, 10, 'Geeks', 52.7, 'for'}

Internal working of Set

This is based on a data structure known as a hash table. If Multiple values are
present at the same index position, then the value is appended to that index position,
to form a Linked List.
In, Python Sets are implemented using a dictionary with dummy variables, where
key beings the members set with greater optimizations to the time complexity.
# A Python program to
# demonstrate adding elements
# in a set

# Creating a Set
people = {"Jay", "Idrish", "Archi"}

print("People:", end = " ")

print(people)

# This will add Daxit

# in the set

9
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

people.add("Daxit")

# Adding elements to the

# set using iterator
for i in range(1, 6):
people.add(i)

print("\nSet after adding element:", end = " ")

print(people)

Output:
People: {'Idrish', 'Archi', 'Jay'}

Set after adding element: {1, 2, 3, 4, 5, 'Idrish', 'Archi', 'Jay',

'Daxit'}

Union operation on Python Sets

Two sets can be merged using union() function or | operator. Both Hash Table values
are accessed and traversed with merge operation perform on them to combine the
elements, at the same time duplicates are removed.

# Python Program to
# demonstrate union of
# two sets

people = {"Jay", "Idrish", "Archil"}

vampires = {"Karan", "Arjun"}
dracula = {"Deepanshu", "Raju"}

# Union using union()

# function
population = people.union(vampires)

print("Union using union() function")

print(population)

# Union using "|"

# operator
population = people|dracula

print("\nUnion using '|' operator")

print(population)

10
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

Output:
Union using union() function
{'Karan', 'Idrish', 'Jay', 'Arjun', 'Archil'}

Union using '|' operator

{'Deepanshu', 'Idrish', 'Jay', 'Raju', 'Archil'}

Intersection operation on Python Sets

This can be done through intersection() or & operator. Common Elements are
selected. They are similar to iteration over the Hash lists and combining the same
values on both the Table.

# Python program to
# demonstrate intersection
# of two sets

set1 = set()
set2 = set()

for i in range(5):
set1.add(i)

for i in range(3,9):
set2.add(i)

# Intersection using
# intersection() function
set3 = set1.intersection(set2)

print("Intersection using intersection() function")

print(set3)

# Intersection using
# "&" operator
set3 = set1 & set2

print("\nIntersection using '&' operator")

print(set3)

11
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

Output:
Intersection using intersection() function
{3, 4}

Intersection using '&' operator

{3, 4}

Finding Differences of Sets in Python

To find differences between sets. Like finding differences in the linked list. This is done
through difference() or – operator.

# Python program to
# demonstrate difference
# of two sets

set1 = set()
set2 = set()

for i in range(5):
set1.add(i)

for i in range(3,9):
set2.add(i)

# Difference of two sets

# using difference() function
set3 = set1.difference(set2)

print(" Difference of two sets using difference() function")

print(set3)

# Difference of two sets

# using '-' operator
set3 = set1 - set2

print("\nDifference of two sets using '-' operator")

print(set3)

Output:
Difference of two sets using difference() function

12
CMP208 - Discrete Structure 2023/2023 session October 1, 2023

{0, 1, 2}

Difference of two sets using '-' operator

{0, 1, 2}

Clearing Python Sets

Set Clear() method empties the whole set in place.

 Python3

# Python program to
# demonstrate clearing
# of set

set1 = {1,2,3,4,5,6}

print("Initial set")
print(set1)

# This method will remove

# all the elements of the set
set1.clear()

print("\nSet after using clear() function")

print(set1)

Output:
Initial set
{1, 2, 3, 4, 5, 6}

Set after using clear() function

set()

13