Ugly Duckling Theorem - Basic Idea

Basic Idea

Suppose there are n things in the universe, and one wants to put them into classes or categories. One has no preconceived ideas or biases about what sorts of categories are "natural" or "normal" and what are not. So one has to consider all the possible classes that could be, all the possible ways of making sets out of the n objects. There are such ways, the size of the power set of n objects. One can use that to measure the similarity between two objects: and one would see how many sets they have in common. However one can not. Any two objects have exactly the same number of classes in common if they are only distinguished by their names with one another, namely (half the total number of classes there are). To see this is so, one may imagine each class is a represented by an n-bit string (or binary encoded integer), with a zero for each element not in the class and a one for each element in the class. As one finds, there are such strings.

As all possible choices of zeros and ones are there, any two bit-positions will agree exactly half the time. One may pick two elements and reorder the bits so they are the first two, and imagine the numbers sorted lexicographically. The first numbers will have bit #1 set to zero, and the second will have it set to one. Within each of those blocks, the top will have bit #2 set to zero and the other will have it as one, so they agree on two blocks of or on half of all the cases. No matter which two elements one picks. So if we have no preconceived bias about which categories are better, everything is then equally similar (or equally dissimilar). The number of predicates simultaneously satisfied by two non-identical elements is constant over all such pairs and is the same as the number of those satisfied by one. Thus, some kind of inductive bias is needed to make judgements; i.e. to prefer certain categories over others.

(A possible way to proceed is however correspondence analysis).