Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

"Pairwise disjoint" is stronger than "disjoint"; it sometimes happens that $\displaystyle\bigcap\limits_{i\in I} A_i=\varnothing$ but for every $i,j$, or at least for some, one has $A_i \cap A_j\ne\varnothing$.

Likewise, "pairwise coprime" is stronger than "coprime".

"Pairwise independent" (in the probabilistic sense) is weaker than "independent". For example, suppose $X_1,\ldots,X_n$ are independent and uniformly distributed on the sphere $S^n$; then the great-circle distances $d(X_i,X_j)$ and $d(X_k,X_\ell)$ are independent if $\{i,j\}\ne\{k,\ell\}$ even if $i=k$, but $d(X_i,X_j), d(X_j,X_k), d(X_k,X_i)$ are not independent even though each of the three pairs of these three random variables is a pair of independent random variables.

Question: Is there a somewhat general rule that says for which sort of X the qualified "pairwise X" is stronger than "X" and for which sort it is weaker than "X"?

Here's a guess: Some sort of category-theoretic viewpoint can make some kind of sense of this. (?)

share|cite|improve this question
Many people use "disjoint" and "pairwise disjoint" synonymously. I have seen "free" be used for families with nonempty intersection (as in "free ultrafilter"). The case of independence and pairwise independence is essentially about local and global properties. – Michael Greinecker Apr 16 '12 at 23:36
I am not entirely sure why this is tagged foundations. To me that tag suggests This feels to me more a question about (notation) or (terminology). – Willie Wong Apr 17 '12 at 5:24
@WillieWong : Maybe it's because as soon as I suspect category theory of being involved, I think "foundations". Maybe that's obsolete by 75 years or so? – Michael Hardy Apr 17 '12 at 12:37
I agree with Willie that the [foundation] tag seems off, and personally I am not sure there is a real need for this tag too. – Asaf Karagila Apr 17 '12 at 21:51
I don't think I've ever seen "disjoint" used (for sets) in any other way than as a synonym for "pairwise disjoint". – Robert Israel Apr 27 '12 at 2:31

It depends on which way the implication goes between the pairwise property and the property of the whole set.

More generally, sometimes if a property $P(S)$ holds for an entire set $S$, then we are assured that it also holds for all subsets of $T$ of $S$, such as pairs. In other words:

$$P(S) \implies \forall T:T \subset S \to P(T)$$

The implication sometimes goes the other way: if we know the property holds for subsets of $S$, then it holds for $S$:

$$\forall T:T \subset S \to P(T) \implies P(S)$$

Or it could be the case that the property of the whole is independent of the property of subsets.

It could also be the case that the relationship is actually $\Leftrightarrow$. For instance an equivalence relation is like this. If elements of a set are all equal pairwise, then necessarily, all elements are equal to each other, and vice versa.

Whether the subset-based proposition is weaker than the whole-set one depends on whether they are connected together logically, and, if so, how: which way does the implication point, or are they logically equivalent.

(Note that this is a very general idea; for instance I'm glossing over situations when, say, it is understood that the pairs in "pairwise" are formed by the cartesian product of the set with itself, and are tuples, rather than sets. The same principles apply, if not the exact formulas.)

share|cite|improve this answer
I've edited this answer without changing its content to remove my downvote, which I gave because I misunderstood the answer. (I thought it was completely trivial, which it's not.) I'm sorry. I'm changing it to an upvote. – user23211 May 1 '12 at 15:59

I used to ponder this question some time ago but didn't come up with a satisfactory answer. The problem seems to be that until someone gives a formal treatment of the adjective "pairwise" in mathematics, it must remain a linguistic problem.

For what it's worth, here's what I've got. It's just some examples and some loose thoughts. I'll be perhaps using some non-standard notation or terminology but I think it's all going to be clear from context. I may also be talking nonsense, and I would ask everyone to point that out. I'd like to know if what I've written is too vague, silly, or just false so I can try to correct this answer or delete it.

We have "pairwise disjoint" and "disjoint" (let's assume that people actually use "disjoint" without "pairwise" in the wanted sense). A non-empty family of sets $\mathcal A\subseteq 2^X$ for some set $X$ is pairwise disjoint iff $$(\forall A_1,A_2\in\mathcal A)\;\;A_1\cap A_2=\varnothing.$$

$\mathcal A$ is disjoint iff $$\bigcap \mathcal A=\varnothing.$$

So what we have here is the operation $\cap$ which we can feed as many sets as we like. We can feed it two, and we can feed it all.

We have "pairwise coprime" and "coprime". A non-empty set of natural numbers $S$ is pairwise coprime iff $$(\forall s_1,s_2\in\mathcal S)\;\;\gcd(s_1,s_2)=1.$$

$S$ is coprime iff $$\gcd(S)=1.$$

In both cases "pairwise" is stronger. $\cap$ and $\gcd$ are meet operations in complete lattices whose respective join operations are $\cup$ and $\operatorname{lcm},$ and $\varnothing$ and $1$ are the meets of those whole lattices. In such cases "pairwise" will always be stronger! Let $L$ be a complete lattice, $\varnothing\neq A\subseteq L$ and $a_1,a_2\in A.$ Then $$\bigwedge L\leq\bigwedge A\leq a_1\wedge a_2,$$

And so $\bigwedge L=a_1\wedge a_2$ implies $\bigwedge L=\bigwedge A.$ That is, even one pair, let alone all pairs, of elements of $A$ having $\bigwedge L$ as a meet implies that the meet $A$ is $\bigwedge L.$

What happens when we give dual definitions for the join operations?

Let's say $\varnothing\neq\mathcal A\subseteq 2^X$ is pairwise full (made-up term) iff $$(\forall A_1,A_2\in\mathcal A)\;\;A_1\cup A_2=X.$$

Let's say $\mathcal A$ is full iff $$\bigcup\mathcal A=X.$$

Again, "pairwise" is stronger, which is not surprising. For $\operatorname{lcm}$ the pairwise condition becomes too strong to be worth considering -- the join of the whole lattice is then $0$ and no two numbers have the least common multiple equal to $0$.

One more remark is that the non-emptiness I've kept assuming is necessary for the conclusions to be true. If we drop it, the "pairwise" conditions will stop being stronger! For example $$(\forall A_1,A_2\in\mathcal \varnothing)\;\;A_1\cap A_2=\varnothing$$ is true, but $\bigcap\varnothing$ is equal to $X.$

Now, an example of "pairwise" being weaker. These might be again made-up conditions, but I think they're justified enough linguistically. Let's again consider the family $\mathcal A$, and say that $\mathcal A$ is pairwise intersecting iff $$(\forall A_1,A_2\in\mathcal A)\;\;A_1\cap A_2\neq\varnothing.$$

Let's say that $\mathcal A$ is intersecting when $$\bigcap \mathcal A\neq\varnothing.$$

In fact, why not try making up some strange example and see what happens? All we need is a "formula" we can feed as many variables as we want (perhaps finitely many). Unfortunately, when I tried to define what I mean by "formula" here, it started becoming much more complicated than I wanted. But see if this example works. Let's say that a finite nonempty set $S$ of the set of positive integers "pairwise adds up to eight" iff $$(\forall s_1,s_2\in S)\;\;s_1+ s_2=8.$$ Let's say that $S$ "adds up to eight" iff $$\sum S=8.$$ Now $\{8\}$ adds up to eight, but not pairwise. Is the pairwise condition weaker then? No, the set $\{4\}$ adds up to eight pairwise, but doesn't add up to eight.

This seems very complicated. And I think I simplified some things above. I should have probably been talking about multisets instead of sets. (That is for example $\mathcal A$ should have been allowed to be a multiset.) Also, I used the operations $\cap$, $\cup$, $\gcd$ and $+$, which all yield results from the same set as the operands. This surely can't be necessary. I don't think the case of independence of random variables can be considered by using such operations.

share|cite|improve this answer
I understand why the intersection of no sets is the universe, but I don't understand why the intersection of any two members of the empty set is the empty set. – Michael Hardy May 2 '12 at 23:20
@MichaelHardy The formula can be rewritten as $(\forall A_1)(\forall A_2)((A_1\in\varnothing \wedge A_2\in\varnothing)\implies A_1\cap A_2=\varnothing)$ But there is no $A_1$ such that $A_1\in\varnothing.$ Therefore for every $A_1$ the antecedent is false. Therefore the whole quantified formula is true. – user23211 May 2 '12 at 23:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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