Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Definition of Set
1.2.
Representation of set
1.2.1.
Roaster form
1.2.2.
Set Builder Form
2.
Types of Set 
3.
Venn Diagram 
4.
Set operations 
4.1.
Union of sets
4.1.1.
Venn diagram for AUB
4.1.2.
Number of Elements in A union B
4.2.
Intersection of sets
4.2.1.
Venn diagram for A∩B
4.2.2.
The formula for the intersection of two sets
4.3.
Complement of sets
4.3.1.
Venn diagram of the complement of a set
4.4.
Difference of sets
4.4.1.
Venn diagram for the difference of set
4.5.
Cartesian Product
5.
Inclusion Exclusion Principle
6.
Derangement
7.
Frequently Asked Questions
7.1.
What is a superset?
7.2.
Write an example of a finite and infinite set in set builder form.
7.3.
What are the Properties of Union of Sets?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Set Theory

Author Shivani Singh
1 upvote
gp-icon
Discrete Mathematics
Free guided path
3 chapters
31+ problems
gp-badge
Earn badges and level up

Introduction

G. Cantor, a German mathematician, introduced the idea of sets. He identified a set as a compendium of definite and distinguishable objects chosen using specific rules or descriptions.

Set theory is the foundation of many other fields of study, including counting theory, relations theory, graph theory, and finite state machines. we will talk more about sets in this blog. 

Definition of Set

A set is an unsorted collection of various elements. A set can be explicitly written by listing its elements inside a set bracket. If the sequence of the elements is altered or any element of a set is reiterated, the set remains unchanged.

Some Sets Examples

  • A set of all positive integers.
  • A set of all negative integers.
  • A set of all capital letters of the alphabet.
  • A group of players in a cricket team.

 

Let us understand this concept with an example.

Consider the following scenario. You decided to take notes on the names of cafes on your way to school from home. The cafes were listed in the following order: C1, C2, C3, and C4. The previous list is a collection of objects. It is also well-defined. By well-defined, we mean that anyone should be able to tell whether or not an object belongs to a specific collection. A library, for example, cannot be classified as a cafe. A set is a collection of objects that is well-defined. The objects in a set are regarded as set elements. A set's elements can be finite or infinite. 

You wanted to be sure of the list you had made earlier on your way back from school. You wrote the list in the sequence in which the restaurants arrived this time. C4, C3, C2, and C1 were added to the list.

This is an entirely different list. Is it, however, a different set? No, it does not. Because the order of the elements in a set is irrelevant, it is still the same set.

Representation of set

There are two ways to represent a set:

  1. Tabular or roster form
  2. Set Builder Form

 

Roaster form

All of the set's elements are listed in roster form, isolated by commas and enclosed by curly braces.

Set of vowels in the English alphabet, A = {a,e,i,o,u}

Set of even numbers less than 10, B = {2,4,6,8}

The elements between the braces are now written in ascending order. This could be in descending or random order. As previously stated, the order of a set defined in the Roster Form is irrelevant.

Set Builder Form

All elements in Set Builder Form share a common property. This property does not apply to objects that do not belong to a set.

For example: If set S contains all elements that are even prime numbers, it is defined as S= { x: x is an even prime number} 

where ‘x’ is a symbolic representation that is used to describe the elements of the set.

':' denotes ‘ such that ‘.

{} means ‘ the entire set ‘.

Another example can be 

The set { 2,4,6,8 } is written as −

B = { x : 1 ≤ x < 10 and (x % 2) = 0 }

Types of Set 

The sets are further classified into various types based on the elements or types of elements. the different types of sets are following:

  1. Finite set: A finite number of elements. For example S={x|x∈N and 100>x>60}
  2. Infinite set: There are an infinite number of elements. For example S={x|x∈N and x>15}
  3. Empty set: An empty set has no elements. For example S={x|x∈N and 10<x<9}=∅
  4. Singleton set: It contains only one element. For example S={x|x∈N, 8<x<10} = {9}
  5. Equal set: Two sets are equal if their elements are the same. For example, If A={4,1,5} and B={5,1,4}, they are equal as every element of set A is an element of set B and every element of set B is an element of set A.
  6. Equivalent set: If two sets have the same number of elements, they are equivalent. For example, If A={5,1,4} and B={10,11,,13}, they are equivalent as the cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3
  7. Power set: A collection of all possible subsets including the empty set. The cardinality of a power set of a set S of cardinality n is 2^n. The power set is represented as P(S). For example, let us compute the subsets of a set S={a,b,c,d}. 
    Subsets with single element − {a},{b},{c},{d}
    Subsets with two elements − {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}
    Subsets with three elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}
    Subsets with four elements − {a,b,c,d}
    Hence, P(S)= {{∅},{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c},{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}}
    |P(S)|=2^4=16
  8. Universal set: Any set that contains all of the sets under given consideration. For example, U can be defined as the set of all humans on the planet. In this case, the set of all women is a subset of U.
  9. Subset: A set is a subset of all of its elements belonging to another set. For example,  Let X={1,2,3,4,5,6} and Y={5,6}. Here set Y is a subset of set X as all the elements of set Y are in set X. Hence, we can write Y⊆X.
  10. Disjoint set: If two sets A and B have no elements in common, they are said to be disjoint. As a result, disjoint sets do have the following characteristics:
    → n(A∩B)=∅
    → n(A∪B)=n(A)+n(B)
    For example: Suppose A={ 3,5,7} and B={8,9,10} have no common element; thus, these sets are overlapping.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Venn Diagram 

The Venn diagram, invented by John Venn in 1880, is a template diagram that depicts all reasonable and logical relationships between various mathematical sets.

The above Venn diagram depicts the relationship between different sets. The first Venn diagram represents the elements that are common in both sets. The second Venn diagram represents all the common elements of the three sets. The third Venn diagram represents all the elements of the two sets. I.e. universal set.

Set operations 

The five most common set operations are as follows:

Union of sets

The set of elements that are in A, B, or both A and B (denoted by AUB) is the union of sets A and B. As a result, A∪B={x|x∈A OR x∈B}. 

Consider the following example: if A = {1, 5,6} and B = {1, 2, 3} then AUB = {1, 2, 3, 5, 6}

Venn diagram for AUB

Image source: union of two sets

The red portion of the Venn graph indicates the union of both sets A and B.

Number of Elements in A union B

Consider two sets, A and B, so the number of elements in the union of A and B is computed as:

n(A U B) = n(A) + n(B) – n(A ∩ B)

 

Where n(A U B) = Total number of elements in A U B. (cardinality of a set A U B)

n(A) = Number of elements in A. (cardinality of set A)

n(B) = Number of elements in B. (cardinality of set B)

n(A ∩ B) = The number of elements that are common to both A and B. (cardinality of set A ∩ B, i.e. A intersection B)

Intersection of sets

The set of elements that are in both A and B (denoted by A∩B) is the intersection of sets A and B. As a result,  A∩B={x|x∈A AND x∈B}. For example, if A is the set of even numbers less than ten and B is the set of the first five multiples of four, the intersection of these two can be found as follows:

 A = {2, 4, 6, 8}

 B = {4, 8, 12, 16, 20}

The common elements are 4 and 8.

As a result, A∩B = {4, 8}

Venn diagram for A∩B

 

The shaded area in the above graph indicates the intersection of two sets A and B.

The formula for the intersection of two sets

If A and B are two sets, then the intersection of two sets is represented by:

(A ∩ B) = n(A) + n(B) – n(A U  B) 

 

where n(A) = The cardinality set A,

n(B) = The cardinality of set B,

n(A U  B) = The cardinality of the union of sets A and B. 

Complement of sets

The complement of a set A (indicated by A′) is the set of elements that do not belong to set A. As a result, A′= {x|x∉A}.

More precisely, A′=(U-A), where U is a universal set containing all objects. Alternatively, the difference between the universal set U and the subset A yields the complement of set A.

Let us make it clear with an example. 

Consider a universal set U of all natural numbers less than or equal to 10.

Let set A which is a subset of U be defined as the set which consists of all the prime numbers. Thus we can see that

A= { 2,3,5,7}

Now the complement of this set A consists of all those elements which is present in the universal set but not in A.

Therefore, A′ is given by:

A′={ 1,4,6,8,9,10}

Venn diagram of the complement of a set

 

Difference of sets

The set difference (denoted by A–B) between sets A and B is the set of elements that are only in A but not in B. As a result, A−B={x|x∈A AND x∉B}. Let us understand this with an example. 

Let A = {3, 4, 8, 9, 11, 12} and B = {1, 2, 3, 4, 5, 6}. compute  A – B and B – A

Here, A – B = {8, 9, 11, 12} because these elements reside in A but not in B and

B – A = {1,2,5} because these elements are in to B but not A.

Venn diagram for the difference of set

Image source: difference of set

The region tinted in orange in the Venn diagram above refers to the difference between sets A and B. And the violet region refers to the difference between B and A.

Cartesian Product

The Cartesian product of n sets A1, A2,... An can be defined as all possible ordered pairs (x1,x2,...xn) where x1∈A1,x2∈A2,…xn∈An.

Consider an example, if we take two sets A={a,b} and B={1,2},

Then, the Cartesian product of A and B = A×B={(a,1),(a,2),(b,1),(b,2)}

Inclusion Exclusion Principle

The Principle of Inclusion and Exclusion is a method for determining the number of items in the union of two finite sets. When solving pairings and probability problems, this is used to find a counting method that ensures an object is not counted twice. It is a counting method used in combinatorics to calculate the cardinality of the union set.

Consider the following two finite sets: A and B. The Principle of Inclusion and Exclusion formula can be represented as follows: 

n(A U B) = n(A) + n(B) – n(A ∩ B) 

 

Where n(A U B) = Total number of elements in A U B. (cardinality of a set A U B)

n(A) = Number of elements in A. (cardinality of set A)

n(B) = Number of elements in B. (cardinality of set B)

n(A ∩ B) = The number of elements that are common to both A and B. (cardinality of set A ∩ B, i.e. A intersection B). This formula has also been discussed in the section: number of elements in A union B.

Let us see a picture to have a clear understanding of it.

Image source: inclusion-exclusion principle


Suppose A, B, C are finite sets. Then A ∪ B ∪ C is finite and it will be represented as : n (A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C).

Let us solve an example to understand the inclusion-exclusion principle more easily.

Question: In a town of 10,000 families, 40 percent of families buy newspaper A, 20 percent buy newspaper B, 10 percent buy newspaper C, 5 percent buy newspaper A and B, 3 percent buy newspaper B and C, and 4 percent buy newspaper A and C. If 2% of the population buys all of the newspapers. Determine the number of families that purchase

  1. The number of families who subscribe to all three newspapers.
  2. The number of families who only buy newspaper A
  3. The number of families who only buy newspaper B
  4. The number of families who only buy newspaper C
  5. The number of families who buy none of A, B, or C.

 

Solution: The Venn diagram for the above question will be 

 

  1. Number of families which buy all three newspapers:
    n (A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C) = n (A ∪ B ∪ C) = 40 + 20 + 10 - 5 - 3 - 4 + 2 = 60%  
  2. Number of families which buy newspaper A only = 40 - 7 = 33%  
  3. Number of families which buy newspaper B only = 20 - 6 = 14%  
  4. Number of families which buy newspaper C only = 10 - 5 = 5%  
  5. Number of families which buy none of A, B, and C
    n (A ∪B ∪C)c = 100 - n (A ∪ B ∪ C)
    n (A ∪B ∪C)c = 100 - [40 + 20 + 10 - 5- 3- 4 + 2]
    n (A ∪B ∪C)c = 100 - 60 = 40 %

Derangement

Derangements are the number of rearrangements that occur when n things are arranged in a row so that none of them occupy their original positions. Dn represents the number of derangements of n distinct things.

Dn = n![1 – (1/1!) + (1/2!) – (1/3!) + …. + (-1)n(1/n!)] where n≥2

Derangement can also be defined as a permutation of objects that tends to leave no object in its initial position. Let us look at an example. Starting with 12345, 31254 is a derangement, but 23415 is not because 5 is in its original position. In order to count the derangements, inclusion-exclusion must be used.

Frequently Asked Questions

What is a superset?

If A ⊂ B and A ≠ B, it follows that A is a proper subset of B. In addition, it is known as the superset of set A.

Write an example of a finite and infinite set in set builder form.

Finite set = {x : x ∈ N and (x – 1) (x – 2) = 0}

Infinite Set = {x : x ∈ N and x is prime}

What are the Properties of Union of Sets?

Commutative law, associative law, the law of identity element, and idempotent law are some of the properties of the union of sets.

Conclusion

To summarise, we talked about sets and set theory in this blog. We also talked about set representation, set types, and the Venn diagram. Then we saw various set operations such as union, intersection, complement, difference, and cartesian product. Finally, we discussed the inclusion-exclusion principle and derangement.

Recommended Readings:

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Next article
Set Operations
Guided path
Free
gridgp-icon
Discrete Mathematics
3 chapters
31+ Problems
gp-badge
Earn badges and level up
Live masterclass