Say I have a set, $\{a,mc,d\}$. Would $\{a,mc\}$, $\{a,d\}$, and $\{mc,d\}$ be pairwise disjoint? And what about $\{b,g\}$, is $\{b,b\}$, $\{g,g\}$ pairwise disjoint?

  • 2
    $\begingroup$ Pairwise disjoint means that any pair of the sets has empty intersection, i.e no overlap in elements. $\endgroup$ – rubikscube09 Mar 9 '19 at 18:32
  • $\begingroup$ Typically, pairwise disjoint means that no two sets in the collection have a member in common. The answer to your first question is no, in fact each pair of distinct subsets has a common element. For your second question, you may as well ask if $\{b\}$ and $\{g\}$ are disjoint, which they are (unless, of course, $b=g$). $\endgroup$ – Chris Leary Mar 9 '19 at 18:34
  • $\begingroup$ Related -math.stackexchange.com/q/3140228/588038 $\endgroup$ – Shivering Soldier Mar 9 '19 at 18:45

Say we have some collection of sets $S_1, S_2, S_3, ..., S_n$. We say that these sets are $k$-wise disjoint if any $k$ of these sets have empty intersection, that is $S_{x_1} \cap S_{x_2} \cap \dots \cap S_{x_k} = \varnothing$ for any choice of $x$'s. Note that the smaller $k$ is, the stronger the statement.

Pairwise disjoint is another way of saying $2$-wise disjoint, that is if you pick any two of these sets then they have empty intersection.

A related term is mutually disjoint, which also means $n$-wise disjoint. This just means that there does not exist a single element found in all of these sets.

Example: Consider the sets $\{1, 2\}, \{2, 3\}, \{3, 4\},$ and $\{4, 1\}$. They are not pairwise disjoint. For example, $\{1, 2\}$ and $\{2, 3\}$ share an element. However, they are $3$-wise disjoint (check yourself) and therefore also $4$-wise disjoint.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.