Disjoint Set

Disjoint set are those sets whose intersection with each other results in a null set. In Set theory, sometimes we notice that there are no common elements in two sets or we can state that the intersection of the sets is an empty set or null set. This type of set is called a disjoint set. For example, if we have X = {a, b, c} and Y = {d, e, f}, then we can say that the given two sets are disjoint since there are no common elements in these two sets X and Y. In this article, let us discuss what is disjoint set, disjoint set union, Venn diagram, pairwise disjoint set, examples in detail.

Disjoint sets have major applications data structures. In Maths we use to find the relation between two sets or functions. If elements in two sets are connected then they are not disjoint.

Disjoint Set Definition

Two sets are said to be disjoint when they have no common element. If a collection has two or more sets, the condition of disjointness will be that the intersection of the entire collection should be empty.

Yet, a group of sets may have a null intersection without being disjoint. Moreover, while a group of fewer than two sets is trivially disjoint, since no pairs are there to compare, the intersection of a group of one set is equal to that set, which may be non-empty. For example, the three sets { {11, 12}, {12, 13}, {11, 13} } have a null intersection but they are not disjoint. In fact, there are no two disjoint sets available in this group. Also, the empty family of sets is pairwise disjoint.

Consider an example, {1, 2, 3} and {4, 5, 6} are disjoint sets.

Two sets A and B are disjoint sets if the intersection of two sets is a null set or an empty set. In other words, the intersection of a set is empty.

i.e. A ∩ B = ϕ

Note: There is a difference between the intersection of two sets and the difference of two sets. In the case of disjoint, we are talking about the only intersection.

Properties of Intersection:

  • Commutative: A ∩ B = B ∩ A
  • Associative: A ∩ (B ∩ C) = (A ∩ B) ∩ C
  • A ∩ ∅ = ∅
  • A ∩ B ⊆ A
  • A ∩ A = A
  • A ⊆ B if and only if A ∩ B = A

Disjoint Set Union

A disjoint set union is a binary operation on two sets. The elements of any disjoint union can be described in terms of ordered pair as (x, j), where j is the index, that represents the origin of the element x. With the help of this operation, we can join all the different (distinct) elements of a pair of sets.

A disjoint union may indicate one of two conditions. Most commonly, it may intend the union of two or more sets that are disjoint. Else if they are disjoint, then their disjoint union may be produced by adjusting the sets to obtain them disjoint before forming the union of the altered sets. For example, two sets may be presented as a disjoint set by exchanging each element by an ordered pair of the element and a binary value symbolising whether it refers to the first or second set. For groups of more than two sets, one may likewise substitute each element by an ordered pair of the element and the list of the set that contains it.

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

Assume that,

The disjoint union of sets 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 is { (a,0), (b,0), (c,0), (d, 0), (e,1), (f,1), (g,1), (h,1) }

Pairwise Disjoint sets

We can proceed with the definition of a disjoint set to any group of sets. A collection of sets is pairwise disjoint if any two sets in the collection are disjoint. It is also known as mutually disjoint sets.

Let P be the set of any collection of sets and A and B are two sets in P

i.e. A, B ∈ P. Then, P is known as pairwise disjoint if and only if A ≠ B. Therefore, A ∩ B = ϕ

Examples:

  • P = { {1}, {2, 3}, {4, 5, 6} } is a pairwise disjoint set.
  • P = { {1, 2}, {2, 3} } is not pairwise disjoint set, since we have 2 as the common element in two sets

Disjoint Sets Examples

Question 1: Show that the given two sets are disjoint sets.

A = {5, 9, 12, 14}

B = {3, 6}

Solution:

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

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

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

Here, set A and B do not have any common element

That is, A ∩ B = { }

Hence, the sets A and B are disjoint sets.

Question 2: Draw a disjoint set Venn digram that represents the given two sets

X = {a, b, c, d, f} and Y = {e, g, h, i}

Solution:

Given: X = {a, b, c, d, f}, Y = {e, g, h, i}

In the given problem, we don’t have a common factor.

Therefore, the given sets are disjoint.

We find that A ∩ B = { }

The disjoint set Venn diagram is represented as:

Disjoint Set - Venn Diagram

The Venn diagram clearly shows that the given sets are disjoint sets.

Keep visiting BYJU’S – The Learning App to learn more Maths-related concepts and problems.