Disjoint Set

What would you call a set between whom there is absolutely no intersection? The sets where there are no common elements between them? In Mathematical terms, it will be referred to as a disjoint set where the intersection of the set is completely empty or null. We can better understand this with the help of an example. Suppose you have two sets, set A consists of 1,2,3,4,5, and set B consists of 6,7,8,9,10.

Can you see anything common between the two sets? You cannot, because there are no similar elements between them. Therefore we can call it a disjoint set. Let us walk together and discuss a few more important things that we need to understand in order to get a stronghold of the concept we just discussed. As we move forward we would learn more about disjoint set along with disjoint set unions. Not only that, but we would also look at a few examples to firmly understand the concept of a disjoint set. 

Disjoint Set Definition

Disjoint set meaning can be framed as two sets having no common element between them. By the disjoint set definition, if there is a collection that has two or more sets, the intersection of the entire collection must be empty. 

To add a twist a group of sets might have a null intersection without being a disjoint set. Taking an example, consider three sets  { {11, 12}, {12, 13}, {11, 13} }. They do have a null intersection but we cannot call it a disjoint set because even though there are no pairs to be compared, the intersection of a group of one set is equal to that set which may be considered as a non-empty set.

Taking another simple example: consider two pairs A=  {1, 2, 3} and B= {4, 5, 6}. They are the perfect example of a disjoint set. In more accurate words, the intersection between set A and set B is empty and can be called an empty set or a null set. 

Therefore,  A ∩ B = \[\phi\]

There is one thing that needs to be clear in our head and that is we should know the difference between “ the intersection of two sets” and “ the difference of two sets”.

Here, we are just talking about the intersection only. 

Difference Between Joint and Disjoint Set

We already know the difference between a joint and a disjoint set. Let us confirm it with a disjoint union example.

We will take two sets X and Y. Now, consider both X and Y sets as non-empty sets. Therefore,  X ⋂ Y stands true and can be called as non-empty sets or joint set. But if  X ⋂ Y is an empty set then what should it be called? Yes, that’s right, we’ll call it a disjoint set. 

Here is an example:

X = {2, 5, 7} and Y = {1, 5, 6}

X ∩ Y = {5}

Therefore, X and Y are joint sets.

But if

X = {1, 3, 7} and Y = {2, 5, 6}

X ∩ Y = Ø

Therefore, X and Y will be considered as disjoint sets.

Disjoint Set Union

A binary operation of any two sets is called a disjoint set union. In a disjoint union, the element can be described on the basis of ordered pairs such as (x,j). Here, j plays the role of representing the origin of the element x. This operation, in turn, plays the role of joining all the different elements of a pair of sets. 

A disjoint demands two conditions. First, the most common indication would be the union of two or more disjoint sets. Second, if they remain disjointed, then the union of a disjoint set would be produced, adjusting the sets to obtain them before forming the union of the altered sets.

For example,  two sets can be presented as a disjoint set when the elements are exchanged by an ordered pair of elements. Also, a binary value symbolizes whether the element refers to the first set or the second set. If the group has two or more sets then each element will be substituted by an ordered pair of the element along with the set that contains it.

The disjoint union can be denoted as X U* Y = ( X x {0} ) U ( Y x {1} ) = X* U Y*

consider that,

The disjoint union of sets named  X = ( a, b, c, d ) and Y = ( e, f, g, h ) is as follows:

X* = { (a,0), (b,0), (c,0), (d, 0) } and Y* = { (e,1), (f,1), (g,1), (h,1) }

Then,

X U* Y= X* U Y*

Therefore, the disjoint union set will be { (a,0), (b,0), (c,0), (d, 0), (e,1), (f,1), (g,1), (h,1) }

Disjoint Set Example

Question 1) Prove that the given two sets are disjoint sets.

A = {5, 9, 12, 14}

B = {3, 6}

Solution1) Given that: A = {5, 9, 12, 14}, B = {3, 6}

The intersection of set A and B gives an empty set.

A ∩ B = {5, 9, 12, 14} ∩ {3, 6}

Therefore, set A and set B do not contain any common element

That is, A ∩ B = { }

Thus, we can say that the sets A and B are disjoint sets.