Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've come across the term "pairwise distinct" in many research papers. But, I don't understand how it differs from just saying that the elements of a set are unique instead of saying that they are pairwise distinct. Can someone please explain the difference, if any, to me?

share|improve this question
3  
Well, not a research-level question...But, here's my two cents: They are equivalent, but sometimes saying "pairwise distinct" saves you a few words. For instance, consider this sentence: "for any pairwise distinct $x_1, \ldots , x_n$". –  Sadeq Dousti Feb 27 '11 at 22:33
    
migrating to math.SE –  Suresh Venkat Feb 28 '11 at 0:53
    
I guess it is redundant to say "pairwise distinct" for a set since all the elements of a set are unique. –  PEV Feb 28 '11 at 1:03
    
There may also be a slight verbal advantage in saying "pairwise distinct" if you intend to use a result of the form "for distinct $a$ and $b$ ..." for each choice of $a=x_i$ and $b=x_j$, $i\neq j$. –  Zev Chonoles Feb 28 '11 at 1:05
add comment

migrated from cstheory.stackexchange.com Feb 28 '11 at 0:54

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer

The first problem is that, set-theoretically, what matters is only whether an element is in a set or not. That is, for sets $A$ and $B$, $$A=B\Longleftrightarrow\mbox{for all $x$, $x\in A$ if and only if $x\in B$.}$$

What this means, among other things, is that the set $\{1,1\}$ is equal to the set $\{1\}$, because every element in the first is in the second and vice-versa. The fact that $1$ shows up twice in the first set is completely immaterial and irrelevant, the two sets are equal. So there is no way, set-theoretically, to say that $1$ only shows up once in the second set but shows up twice in the first.

So it doesn't really make sense to say that "elements of a set are unique."

Instead, you really want to talk about either multisets (which introduces its own complications), or else you want to talk about ordered tuples and say that entries with distinct indices should be distinct. Something like: $$(a_i)_{i\in I}\text{ and }a_i\neq a_j\text{ if }i\neq j.$$ But this also introduces complications of its own, such as having to introduce an index set, not to mention lots of extra words.

So instead what we want to say is that given any pair of elements (and we want to say "pair", because in mathematics, if you simply say "any $x$ and $y$", you do not exclude the possibility that you selected the same element twice), the two elements are different. And this is what "pairwise distinct" means: every pair of elements consists of two different things.

Another potential problem is that the term "unique" is usually reserved for a different kind of meaning. For example, the Chinese Remainder theorem says that a certain system of congruences has solutions, and that the solutions are "unique modulo $M$" (where $M$ is a certain integer defined in terms of the hypothesis). That use of "unique" means that if you find any two solutions, then they are the same solution modulo $M$. That usage would be at odds with using unique in order to say "these list of things doesn't have any repeats".

share|improve this answer
add comment

Your Answer

 
discard

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.