Set Theory – Mathematics for Algorithm
Set theory is a field of mathematical logic that examines sets, which may be defined informally as collections of objects. In the 1870s, German mathematicians Richard Dedekind and Georg Cantor pioneered the current discipline of set theory. Set theory starts with a basic binary relationship between an object o and a set, A.
Introduction to Sets
Set : Set is an unordered collection of objects. Members of the set are also called elements of the set.
Suggested Reading: Crisp Set – Complete Study
Typically, members of the set are represented using small letters, and the set itself is represented using a capital letter. If element a is a member of set A, it is denoted by a ∈ A. If element ‘a‘ is not a member of set A, it is denoted by a ∉ A.
Elements of a set are enclosed within the opening and closing curly braces and are separated by a comma. For example,
- Set of alphabets : A = {a, b, c, . . . , z}
- Set of digits : B = {0, 1, 2, . . . , 9}
Set Representation Methods
Listing method :
All the members of the set are exhaustively enumerated. A set of numbers greater than 100 is defined as, A = {101, 102, 103, 104, ….}.
This method does a listing of all elements. This is an inefficient way of writing big sets.
Describing properties:
Elements in a set are derived by stating the property of elements. The set of the first five perfect square numbers is defined as, B = {1, 4, 9, 16, 25}.
Recursion method:
Elements are defined in terms of recursion, they are not explicitly listed as previous methods.
The set of the first ten numbers is defined as C = { c | c ≤ 10 and c ∈ N}.
The recursion method is the best way of describing the set.
Types of Set
Subset
Set B is called a subset of set A if B is completely contained within A. In other words, if all members of B are also members of A, then B is called a subset of A. And it is denoted by B ⊆ A.
Example:
If A = {1, 2, 3, 4, 5}, B = {1, 3, 5}, then B ⊆ A
Every set is a subset of itself. In the above example, A ⊆ A and B ⊆ B.
Superset :
Set A is called a superset of set B if B is completely contained within A. In other words, if all the members of B are also members of A, then A is called a superset of A. And it is denoted by A ⊇ B.
Example:
If A = {1, 2, 3, 4, 5}, B = {1, 3, 5}, then A ⊇ B
Every set is a superset of itself. In the above example, A ⊇ A and B ⊇ B.
Proper subset :
If B ⊆ A and A ≠ B, then we say B is a proper subset of set A. This implies, B is a subset of A and A has at least one element which is not in B. It is denoted as B ⊂ A.
Example:
If A = {1, 2, 3, 4, 5}, B = {1, 2, 3, 4}, C = {1, 2, 3, 4, 5} holds following relations:
B ⊆ A, B ⊆ C, C ⊆ A
B ⊂ A, B ⊂ C, but C ⊄ A
Proper superset :
If A ⊇ B and A ≠ B, then we say A is a proper superset of set A. This implies, that A is a superset of B and A has at least one element which is not in B. It is denoted as A ⊃ B.
Example :
If A = {1, 2, 3, 4, 5}, B = {1, 2, 3, 4}, C = {1, 2, 3, 4, 5} holds following relations :
A ⊇ B, C ⊇ A, A ⊇ C,
A ⊃ B, but A is not a proper superset of C.
Empty set:
A set without any members is called an empty set. It is denoted as { } or Φ.
Example :
If A = {1, 2, 3} and B = {5, 6} then intersection of these two sets is empty set.
Power Set
Power set P(A) of set A is a collection of all possible subsets of A.
Example :
If A = {a, b} then P(A) = {f, {a}, {b}, {a, b}}
If B = {1, 2, 3} then P(B) = { f, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }
If the size of the set is n, the size of its power set would be 2n.
Equal set:
Two sets A and B are said to be equal if A ⊆ B and B ⊆ A i.e. A = B. If each member of set A is also a member of B and the converse is also true, we say that A and B are equal sets.
Example :
A = {1, 2, 3} and B = {1, 2, 3} are equal sets.
Operations on Sets
We can perform the following operations on sets
Union:
The union of two sets, A and B is defined as A ∪ B.
A ∪ B = { x : x ∈ A or x ∈ B}.
Example:
If A = {1, 2, 3, 4} and B = {2, 4, 6, 8}, then A ∪ B = {1, 2, 3, 4, 6, 8}
In union, common elements appear only once.
Intersection:
An intersection is a set of common elements from two sets. The intersection of two sets, A and B is defined as A ∩ B.
A ∩ B = { x : x ∈ A and x ∈ B}.
Example:
If A = {1, 2, 3, 4} and B = {2, 4, 6, 8}, then A ∩ B = {2, 4}
Difference:
The difference between two sets A and B is defined as A – B.
A – B = {x : x ∈ A and x ∉ B}.
Example:
If A = {1, 2, 3, 4} and B = {2, 4, 6, 8}, then A – B = {1, 3}, and B – A = {6, 8}
Complement:
Complement of set A with respect to some universal set U is defined as A’.
A’ = U – A = {x : x ∉ A }
Example :
If U = {1, 2, 3, 4, 5, 6} and A = {1, 4, 6} then A’ = {2, 3, 5}
Cartesian product:
The Cartesian product A x B of sets A and B is a collection of all possible ordered pairs (a, b) such that a ∈ A and b ∈ B.
A x B = {(a. b) : a ∈ A and b ∈ B}
Example :
If A = {1, 2, 3} and B = {x, y} then,
A x B = { (1, x), (2, x), (3, x), (1, y), (2, y), (3, y) }
Suggested Reading: Operations on crisp set
Venn diagram representation of sets
Sets and set operations are often represented using the Venn diagram, which is a graphical representation of the interaction between sets. Let us try to understand it with an example. Assume the use case of some universities having 100 students. To form the team for inter-college sports tournaments, the interests of the students were collected, and we got the following responses. Out of 100 students,
- 60 students were interested in football only
- 50 students were interested in cricket only
- 45 students were interested in volleyball only
- 30 students were interested in football and cricket both
- 50 students were interested in volleyball and cricket both
- 20 students were interested in football and volleyball both
- 5 students were interested in all three games
This fact can be easily and elegantly represented by the Venn diagram, as shown below, where each circle corresponds to one set. Their overlap shows the intersection of their respective sets. Graphical representation is easy to understand and quick to analyze compared to a textual representation.
Thus, the set theory provides a basic way of representing relations between objects or elements and the set.
Additional Reading: Introduction to Set Theory [YouTube Video]
Short Questions:
Q: What is a Set?
A set is an unordered collection of objects. Members of the set are also called elements of the set.
Enlist methods for describing sets
We can describe the set using the following ways:
- Listing method
- Describing properties
- Recursion method
Q: What do you mean by subset?
Set B is called a subset of set A if B is completely contained within A. In other words, if all members of B are also members of A, then B is called a subset of A. And it is denoted by B ⊆ A.
Q: Describe the term proper subset
If B ⊆ A and A ≠ B, then we say B is a proper subset of set A. This implies, B is a subset of A and A has at least one element which is not in B. It is denoted as B ⊂ A.
Q: Generate the power set of set A = {1, 2, 3}
Power set of set A would be: P(A) = { f, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }
Q: If set contains n elements, then what would be the cardinality of its power set?
Set with n elements has 2n elements in its power set
Q: Find the difference of A = {1, 2, 3, 4} and B = {2, 4, 6, 8}
A – B = {1, 3}, and B – A = {6, 8}
Q: Enlist the elements of cartesian product of A = {1, 2, 3} and B = {x, y}
A x B = { (1, x), (2, x), (3, x), (1, y), (2, y), (3, y) }