Disjoint sets 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 say 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, you will learn what disjoint set is, disjoint set union, Venn diagram, pairwise disjoint set, examples in detail.
Table of Contents:
- Definition
- Disjoint sets union
- Pairwise disjoint
- Are two null sets disjoint
- Joint and Disjoint
- Example
- FAQs
Disjoint sets have major applications in 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 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}, and {11, 13} have a null intersection but they are not disjoint. 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, only intersection will be considered.
| Also, read: |
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 pairs 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.
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, since we have 2 as the common element in two sets.
Are Two Null Sets Disjointed?
We know that two sets are disjoint if they don’t have any common elements in the set. When we take the intersection of two empty sets, the resultant set is also an empty set. One can easily prove that only the empty sets are disjoint from itself. The following theorem shows that an empty set is disjoint with itself.
Theorem:
The empty set is disjoint with itself.
Difference Between Joint and Disjoint Set
Consider two sets X and Y.
Assume that both the sets X and Y are non-empty sets. Thus, X ⋂ Y is also a non-empty set, the sets are called joint set. In case, if X ⋂ Y results in an empty set, then it is called the disjoint set.
For example: X = {1, 5, 7} and Y = {3, 5, 6}
X ∩ Y = {5}
Hence, X and Y are joint sets.
Video Lesson on What are 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}
A ∩ B = {5, 9, 12, 14} ∩ {3, 6}
Here, set A and B do not have any common element
That is, A ∩ B = { }
The intersection of set A and set B gives an empty set.
Hence, the sets A and B are disjoint sets.
Question 2: Draw a disjoint set Venn diagram 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.
i.e. A ∩ B = { }
The disjoint set Venn diagram is represented as:
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.
