How Disjoint Sets Are Used in Problem Solving
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.
FAQs on Disjoint Set: Definition, Properties & Uses
1. What are disjoint sets in mathematics?
In set theory, two sets are defined as disjoint if they have no elements in common. In other words, their intersection results in an empty set. For example, if Set A = {1, 3, 5} and Set B = {2, 4, 6}, their intersection A ∩ B = ∅. Therefore, A and B are disjoint sets. They are also referred to as mutually exclusive sets.
2. How can you determine if two given sets are disjoint or not?
To determine if two sets, say P and Q, are disjoint, you must find their intersection (P ∩ Q). Follow these steps:
- List the elements of both sets.
- Identify any elements that are common to both set P and set Q.
- If there are no common elements, the intersection is the empty set (∅), and the sets are disjoint.
- If there is at least one common element, the sets are not disjoint; they are called overlapping sets.
3. What is the key difference between disjoint sets and overlapping sets?
The primary difference lies in their intersection.
- Disjoint Sets: Have absolutely no elements in common. Their intersection is the empty set (A ∩ B = ∅). In a Venn diagram, they are represented by two separate, non-touching circles.
- Overlapping Sets: Share at least one common element. Their intersection is a non-empty set (A ∩ B ≠ ∅). In a Venn diagram, they are shown as two circles that intersect, with the common elements located in the overlapping region.
4. How does the concept of disjoint sets simplify the formula for the union of sets?
The general formula for the cardinality (number of elements) of the union of two sets A and B is n(A ∪ B) = n(A) + n(B) – n(A ∩ B). However, when the sets are disjoint, we know that their intersection is empty, meaning n(A ∩ B) = 0. This simplifies the formula significantly to just n(A ∪ B) = n(A) + n(B). This principle is fundamental in probability and combinatorics for counting outcomes of mutually exclusive events.
5. Can two empty sets be considered disjoint? Why?
Yes, two empty sets are considered disjoint. The definition of disjoint sets is that their intersection must be the empty set (∅). When we take the intersection of two empty sets (∅ ∩ ∅), the resulting set is also the empty set. Since this satisfies the core condition, two empty sets are indeed disjoint.
6. What are some real-world examples that illustrate the concept of disjoint sets?
Disjoint sets are used to categorise distinct groups in real-world scenarios without any ambiguity. For example:
- The set of even numbers and the set of odd numbers are disjoint.
- In a school, the set of students in Class 10 and the set of students in Class 11 are disjoint.
- In a market survey, the group of customers who bought product A and the group of customers who bought product B (assuming no one bought both) would form disjoint sets, which is crucial for accurate sales analysis.
7. What is the meaning of 'pairwise disjoint' sets?
A collection of three or more sets is called pairwise disjoint (or mutually disjoint) if every pair of distinct sets within that collection is disjoint. This is a stricter condition than just having the intersection of all sets be empty. For example, consider sets A = {1, 2}, B = {3, 4}, and C = {5, 6}. This collection is pairwise disjoint because A ∩ B = ∅, A ∩ C = ∅, and B ∩ C = ∅. This concept is important in areas like partitioning a set, where a set is divided into non-overlapping subsets.
