All the King's philosophers: ultrafilters and Arrow's Theorem

(See part I, part II, part III.)

Given some set A, an ultrafilter on A is a nonempty family F of subsets of A such that

1. A belongs to F,
2. X belongs to F if and only if A−X does not belong to F,
3. if X belongs to F and Y is a superset of X, Y belongs to F,
4. if X and Y belongs to F, the intersection of X and Y does belong to F as well.

An ultrafilter is said principal if it is of the form {X included in A : a belongs to X} for some fixed element a of A.

Ultrafilters are used in Model Theory to construct new models for a logical theory out of a family of preexisting models. Principal ultrafilters are of little use in this context, as they yield models that are isomorphic to one of the elements of the given family. The following result basically tells us that finite ultrafilters are of no interest:

Theorem. If A is finite, every ultrafilter on A is principal.

This is the fundamental difficulty that al-Khwārizmī found when trying to build a Philosopher Rule for the Council. He could only have built a non-trivial rule if the Council were infinite!

Arrow's Theorem is a celebrated result by economist Kenneth Arrow that shows some inherent problems of certain voting systems:

Theorem. Let P be a population of voters each having an associated preference ordering a set of candidates C. A social welfare function is a rule that accepts any combination of individual orderings and generates a global ordering for the candidates. Suppose that the SWF has the following properties:

1. When all voters prefer candidate a over candidate b, the SWF must also have this preference.
2. If for a given voter input I the SWF prefers a over b and then we switch to a different input I' such that the individual voters favoring a over b are a superset of those in I, the new output of the SWF still favors a wih respect to b.

Then, if P is finite and there are more than two candidates, it turns out that the SWF necessarily implements a dictatorship, i.e. there is some individual d in P such that the results of the SWF are exactly the preferences expressed by d.

The similarities between Arrow's Theorem and the basic theorem on finite ultrafilters are not coincidental, and a quick search on the net reveals that some have indeed proved that both results are in fact equivalent.