Introduction to Set Theory

Learn via video course
FREE
View all courses
DBMS Course - Master the Fundamentals and Advanced Concepts
DBMS Course - Master the Fundamentals and Advanced Concepts
by Srikanth Varma
1000
5
Start Learning
DBMS Course - Master the Fundamentals and Advanced Concepts
DBMS Course - Master the Fundamentals and Advanced Concepts
by Srikanth Varma
1000
5
Start Learning
Topics Covered

Overview

Set Theory is a branch of mathematics that describes the collections of objects. These objects are called as elements or members of the set, whereas a set is a collection of those objects.

This article covers the importance of Set Theory, which is helpful while learning SQL too. You’ll get to know what is set, subset and how to calculate the size of a set. All these concepts of Sets are visually represented by Venn Diagrams and that you’ll learn in this article.

Introduction to Set Theory

Set Theory, a branch of mathematics deals with the properties of collections of objects which may or may not be mathematical such as numbers, functions, or some texts too. For example, a team of cricket players can be considered a set, a set of all odd numbers, a set of all books based on financial independence, etc. Thus a set means a well-defined collection of objects.

The purpose of the sets is to group a collection of related objects. These are important everywhere in mathematics because every field of mathematics deals with the sets in some or the other way. In real world also the sets are used in various places.

For example, in the kitchen, you have seen that utensils are arranged in such a manner that plates are kept separately from the spoons. Here two sets are said to be formed, one is collection of plates and other one is collection of spoons. Another example is playlist of songs. You must have seen playlists that are based on specific genres, i.e., collection of classical songs is a different set, collection of rock songs is a different set.

Set Theory and Fundamentals

A set means a well-defined collection of distinct objects. A set is expressed by enclosing its members or objects within a pair of braces and separated by commas. For example, S = {a, b, c}, the set is labeled as S and a, b and c are the members or the elements of the set S.

Example of Sets:

  • A = { a, b, c }
  • S = { 2, 4, 6, 8, 10 }
  • F = { apple, orange, grapes }

The above examples of the set are displayed in the roster notation. Roster notation means the list of elements separated by commas and enclosed in curly braces which means elements written between the braces are the elements of a set.

Consider B = { a, a, b, c }, the B is not a set as it doesn't contain distinct objects that means all the elements must be different in the given set. In the given set B, the element 'a' is repeating which means the elements in set B are not unique hence it is not considered a set. For a collection to consider as a set, the elements in that collection must be unique or non-repetitive.

A set specifies the content, the order of the objects is not important. For example, the set A = {2, 4, 6} can also be written as A = { 6, 2, 4 } and still this is called a set because order is not important in a set.

Every object or element in a set is unique. The elements in a set are not repeated.

The objects or members of the set are also called elements of the set. Consider a set S = {a, e, i, o, u}. Here a, e, i, o, u are the elements of the set S. If e is the member or element of the set S, then you can write e ∈ S, which is read as 'e belongs to S', and b ∉ S, read as 'b does not belong to S' means b is not the member of set S.

Graphical Representation of a set

To represent the sets graphically, it's common to use Venn Diagrams. The Venn Diagrams helps to interpret the information very easily, you can also identify similarities and differences between the sets from Venn Diagrams. It is a diagram that shows the elements or the members in a set and all the possible logical relationships between the sets which you will get to know later in this section.

Consider S = { G, R, A, P, E, S }, all the elements are distinct and hence it can be considered as a set. The set S is represented graphically via Venn Diagram below:

Venn Diagram of a set

Subset

Let's say you want to compare two sets and find out similarities or how many elements in both sets are the same. One basic relation that does the exact same that is to find whether a set is a subset of another set.

A set A is said to be a subset of set B if every element of set A is also an element in set B. The notation A ⊆ B denotes that A is a subset of B.

For example, all natural numbers(N) are integers(Z) hence you can write N ⊆ Z. To understand more clearly, let us take an example of having sets A and B.

A=1,4,5B=1,5,7,9A = { 1, 4, 5 } B = { 1, 5, 7, 9 }

Here all the elements of set A are not present in set B, i.e., "4" is not present in set B hence A ⊄ B. ⊄ denotes "not subset".

Size of a set

The size of a set is often called the order of a set. The size of the set defines the total number of elements in a set. The size of a set or order of a set is also known as Cardinality number which is denoted as |S|.

The size of a set can be finite or infinite. The size of a set whether it is finite or an infinite set is said to be of finite order or an infinite order.

Let's take a few examples to understand the size of a set.

A=10,20,30,40A = { 10, 20, 30, 40 }
B=Asetofallrealnumbers.B = A set of all real numbers.

Here, set A is a finite set because it contains four elements and it is countable whereas set B is an infinite set because there are no fixed number of elements or countable elements in the set.

Power sets

For any set A, the set consisting of all the subsets of A is called the power set of A and it is denoted by P(A).

Let's take an example to understand the power set. Consider a set S = {3, 5, 7, 9}. The power set of set S according to the above definition can be given as:

{ Ø }, { 3 }, { 5 }, { 7 }, { 9 }, { 3, 5 }, { 3, 7 }, { 3, 9 }, { 5, 7 }, { 5, 9 }, { 7, 9 }, { 3, 5, 7 }, { 3, 5, 9 }, { 3, 7, 9 }, { 5, 7, 9 }, { 3, 5, 7, 9 }

If a given set has n elements, then its power set will contain 2^n elements. The number of elements in a power set can be written as | P(A) |. This also represents cardinality of the power set. So in the example above, the set S has 4 elements. Thus the cardinality of the power set is 2^4 ,i.e., 16.

Hence P(S) can be given as:

P(S) = { { Ø }, { 3 }, { 5 }, { 7 }, { 9 }, { 3, 5 }, { 3, 7 }, { 3, 9 }, { 5, 7 }, { 5, 9 }, { 7, 9 }, { 3, 5, 7 }, { 3, 5, 9 }, { 3, 7, 9 }, { 5, 7, 9 }, { 3, 5, 7, 9 } }

Here, n = number of elements in set S = 4 Therefore,

P(A)=24=16| P(A) | = 2^4 = 16

Note that the power set of a set also contains an empty set and the set itself.

Cartesian Products

Cartesian product means the product of two non-empty sets in an ordered way. Consider a set A and set B. The Cartesian product of set A and set B is a set of all ordered pairs (a, b) such that a is an element of set A and b is the element of set B. The Cartesian product of set A and set B is denoted by A x B.

As discussed above, for two non-empty sets A and B, the first element of pair is from set A and second element of pair is from set B and the collection of all such ordered pairs gives the Cartesian product of given two sets.

Let's take an example to see how the cartesian product can be calculated from the given sets.

A=1,2B=a,b,cA = { 1, 2 } B = { a, b, c }

The Cartesian product of the set A and set B can be given as

AxB=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)A x B = { ( 1, a ), ( 1, b ), ( 1, c ), ( 2, a ), ( 2, b ), ( 2, c ) }

Note that ( 1, a ) will be different from ( a, 1 ) i.e. order of the elements in a pair matters.

Number of ordered pairs

For two non-empty sets A and B, if the number of elements in set A is n, i.e., n( A ) = n and the number of elements in set B is m, i.e., n( B ) = m, then the number of ordered pairs in the Cartesian product of A and B, i.e., n( A x B ) = n( A ) x n( B ) = nm.

Set Operations

  • Union: The union of two sets A and B contains all the objects/elements that are in either set. The union of set A and set B is denoted by C = A ∪ B and can be read as, A union B. The operation of taking the union of two sets is called the union operation.

    Consider two sets P and Q, where P = { 1, 3, 5, 7, 9 } and Q = { 2, 4, 6, 8, 10 }. The union operation is applied on the sets P and Q such that the resultant set obtained is named as C. After performing union operation on the above given sets following resultant set is obtained.

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

    Therefore,

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

    As you can see in the above example, union of two sets, here set A and set B, results in a set, here set C, which contains all the members that are present in the either set.

  • Intersection: The intersection of two sets A and B contains all of the objects that are in both the sets. The intersection of set A and set B is denoted by A ∩ B and can be read as, A intersection B.

    Consider two sets L and M, where L = { 1, 5, 7, 9 } and M = { 1, 5, 7, 10 }. The intersection operation is applied on the sets L and M such that the resultant set obtained is named as O. After performing intersection operation on the above given sets following resultant set is obtained.

    O=LM=1,5,7,91,5,7,10O = L ∩ M = { 1, 5, 7, 9 } ∪ { 1, 5, 7, 10 }

    Therefore,

    O=1,5,7 O = { 1, 5, 7 }

    As you can see in the above example, intersection of two sets, here set L and set M, results in a set, here set O, which contains the elements that are present in both the sets.

  • Complementation: The complement of set A consists of all the elements that are in the universal set U but not in A. The complement of set A is denoted by A^c or A' and can be read as, A compliment.

    Consider a universal set 'U' of prime numbers up to 10, i.e., U = { 2, 3, 5, 7 } and the other set, A = { 1, 2, 5, 10 }. The complement of set A means the resultant set, here A', includes the elements of the universal set but not the elements of set A . After performing complement operation on the above given sets following resultant set is obtained.

    A=UA=2,3,5,71,2,5,10A' = U - A = { 2, 3, 5, 7 } ∪ { 1, 2, 5, 10 }

    Therefore,

    A=3,7 A' = { 3, 7 }
  • Difference Set: The difference between set A and set B consists of all the elements that are in set A but not in set B. The difference between set A and set B is denoted by A - B and can be read as, A minus B.

    Consider two sets P and Q, where P = { 10, 15, 20, 25, 30, 35 } and Q = { 10, 20, 30, 40, 50, 60 }. The difference between set P and set Q gives the resultant set R. After performing difference operation on the above given sets following resultant set is obtained.

    R=PQ=10,15,20,25,30,3510,20,30,40,50,60R = P - Q = { 10, 15, 20, 25, 30, 35 } - { 10, 20, 30, 40, 50, 60 }

Therefore, R=15,25,35 R = { 15, 25, 35 }

As you can see in the above example, difference of two sets, here set P and set Q, results in a set, here set R, which contains the elements that are present in set P but not in set Q.

Conclusion

  • Set Theory is a branch of mathematics where concepts such as Union, Intersection, complementation are found and these concepts are also used in programming techniques.
  • A set is a well defined collection of objects and its members are enclosed within curly braces and separated by commas.
  • A set can be visualized graphically using the Venn Diagram technique.
  • All the operations that can be performed on a set can be easily visualized using Venn Diagrams.
  • If every element of set A is also in the set B then A is called a subset of B and is denoted by A ⊆ B.
  • Size of a set also called as Cardinality of a set determines the number of elements in the set.
  • Power set is the set consisting of all the subsets of the given set.
  • A x B is called the Cartesian product of set A and set B that is also a set having ordered pairs (a, b) as the elements such that a is an element of set A and b is the element of set B.