Six choices make a seventh

Russell’s way of explaining the axiom of choice is well known. A millionaire has infinitely many pairs of shoes and infinitely many pairs of socks. He can pick one shoe from each pair by a rule: take the left. For socks there is no rule, since the two socks of a pair are indistinguishable, and so a set consisting of one sock from each pair exists only if the axiom of choice says so. The axiom’s full power is not at stake here. The socks only need choices from sets of size two.

Write $C(n)$ for the statement that every family of $n$-element sets has a choice function. Without any choice at all, $C(1)$ is trivially true, and each $C(n)$ for larger $n$ is independent of the other axioms of set theory. So there is a countable family of little axioms, one per size, and an obvious question about them. Which of them imply which?

The answer is that a few do, and for an unexpected reason. Alfred Tarski noticed that $C(2)$ implies $C(4)$. It is a matter of a small finite combinatorial fact, which can be checked by listing 64 cases, and it has nothing to do with infinite sets except that the same rule must work for each member of the family without being told their names. Then the question of what else follows depends on prime numbers, and in a way that nobody could have anticipated from Russell’s socks.

Where the infinite enters #

It helps to be clear about what is being asked, because within any single finite set there is nothing to prove. If a set has four elements, then it is not empty and an element can be picked from it, in one step of ordinary logic. So can one element from each of two such sets, or a hundred. A finite number of choices is a finite proof. The difficulty appears only with infinitely many sets at once, when the proof would have to contain infinitely many separate acts of picking, and that is what no finite proof can do without an axiom to summarise them.

That is why the trick above has to be a rule. What it produces is not a selection from any particular set of four, which was never in doubt. It is one instruction, written in terms of the given choice function for pairs, that works uniformly on every four-element set in the family, however many there are, without any information about their elements. Any argument that uses the names of elements cannot be applied. The test of a valid rule is whether it survives every renaming of the elements of each set, separately and all at once. Scores survive, because a tournament’s scores are a property of the tournament. “Take the smallest” does not survive, since it needs an order that was not supplied. The whole subject has this flavour, and it is close to the difficulties in the additive function that is nowhere a line and the set that has no size. In each, something can be done for each object taken singly, and the question is whether it can be done for them all at once.

Six choices #

Take a set $S$ with four elements. It has six two-element subsets. Applying a choice function for pairs picks one element from each. This data is a tournament: for each pair, one element beats the other. Now count, for each element, how many pairs it was chosen from. That is its score, and the scores sum to 6. Let $L$ be the set of elements with the lowest score.

What can $L$ be? It cannot have four elements, since that would mean all scores are equal and 4 does not divide 6. So $L$ has one, two or three elements. If it has one, take that element. If it has two, then $L$ is itself a pair, and the choice function for pairs applies to it. If it has three, there is exactly one element outside it, so take that one. In every case an element of $S$ has been picked. The whole procedure depends on the choice function for pairs and on nothing else. Applied to each set in a family of four-element sets, it gives a choice function for the whole family. That is the proof that $C(2)$ implies $C(4)$.

The argument can be tested exhaustively, and there are only 64 cases to test. Scores 0, 1, 2, 3 occur in 24 tournaments, and then the least score singles out one element. Scores 1, 1, 2, 2 occur in 24 tournaments and leave a pair. Scores 0, 2, 2, 2 occur in 8, and they single out the element with the score of 0. Scores 1, 1, 1, 3 occur in 8, and leave three, so the element outside is the winner. There are no other possibilities. The point of doing this is not to confirm such a short argument but to make the mechanism very plain: a rule is being applied that is symmetric under renaming the four elements, in the sense that it refers only to the tournament. That is what makes it usable for a family of unnamed sets.

The same trick does not work at three. Three elements have three pairs, and in the cyclic tournament $a$ beats $b$, $b$ beats $c$ and $c$ beats $a$, all scores are 1. That symmetric situation is the whole obstruction: when all scores are equal, nothing singles out any element. So the first failing case is the case where the number of pairs is divisible by the number of elements.

Which sizes the same trick reaches #

The figure lists all tournaments up to size 6, by the size of the least-score set. At three points, 2 of the 8 tournaments are regular, with all scores equal. At five points, 24 of the 1,024 are regular, the same obstruction. At six points, the number of pairs is 15, and 6 does not divide 15, so all-equal never occurs. The least-score set has 1, 2, 3, 4 or 5 elements. Sizes 1 and 2 are dealt with as before. Size 4 uses $C(4)$, which follows from $C(2)$. Size 5 leaves out a single element. But size 3 needs $C(3)$, and it does occur in 2,960 of the $2^{15}$ tournaments. So $C(2)$ and $C(3)$ together imply $C(6)$, and $C(2)$ alone does not reach it by this route.

Size 8 falls to the same argument: 8 does not divide its 28 pairs, and a least-score set can have any size up to 7. A size up to 3 is handled directly; size 4 by Tarski; size 5, 6 or 7 by taking the complement, which has 3, 2 or 1 elements. So $C(2)$ and $C(3)$ together give $C(8)$. At 9, there are 36 pairs, and 9 divides 36, so regular tournaments exist and the method of pairs fails. But the method does not have to stop at pairs. Take the 84 three-element subsets of a set of nine, choose an element from each by $C(3)$, and count: 9 does not divide 84, so all scores are not equal. So $C(2)$ and $C(3)$ give $C(9)$ too. This is the same trick with larger subsets, and how far it can go is determined by divisibility of binomial coefficients. Knowing whether $n$ divides $\binom{n}{k}$ is exactly the kind of statement that the row of Pascal’s triangle at a prime settles. If $n$ is prime, it divides every middle coefficient, and this whole family of tricks can never get started. It is natural, then, that primes are the sizes that do not follow from smaller ones.

A condition in terms of primes #

Andrzej Mostowski turned this into a sharp limit in 1937. Write $C(\le m)$ for choice from all sets of sizes up to $m$. His condition says: if $C(\le m)$ implies $C(n)$, then $n$ cannot be written as a sum of primes all larger than $m$. For $m = 2$, the primes above 2 are all odd. Writing $n$ as a sum of odd primes is possible for 3, for 5, for $6 = 3 + 3$, for 7, for $8 = 3 + 5$, and for every number from 5 on. Only $n = 4$ escapes. So 4 is the only size that can follow from pairs.

Computed up to size 24, the table has very few dark squares. From sizes up to 3, there are 4, 6, 8 and 9. From sizes up to 5, the primes above 5 start at 7 and 11, and so sizes such as 12 and 15 become available too. From sizes up to 7, the list is longer, and its largest entries are not large. Sums of primes are very flexible, so every large number can be written using the primes above any given $m$, and only finitely many sizes can possibly follow. That is really a fact about additive number theory, a version of the problem of the amounts that coins cannot pay, and the condition’s content is entirely arithmetical.

Mostowski’s condition is about what can fail, and it is the correct kind of statement to compare with what the scoring trick proves. A size that passes the test still needs a proof. The combinations tried above pass for the small sizes, and further work by Gauntt and others closed the problem in full by a more elaborate condition, involving the actions of groups on finite sets. The answer is a statement about whether every fixed-point-free group action on $n$ points has a suitable orbit-preserving subgroup. In most small cases it agrees with Mostowski’s test.

Why triples do not follow: a universe with its own symmetry #

To show that $C(2)$ really does not give $C(3)$, one needs a world where pairs have choices and triples do not. The proof technique is a permutation model, and it is one of the most intuitive constructions in set theory.

Begin with infinitely many objects, called atoms, with no internal structure, arranged in disjoint triples. Consider all permutations that rotate each triple among its own three elements, a separate choice for each triple. Now call a set real if it is fixed by all such permutations that leave some finite number of atoms alone. The real sets form a model of set theory with atoms. Each triple is real, as is the family of all of them, since a rotation preserves each triple. But a choice function for that family is not real. It would pick an element from each triple, and rotating an untouched triple would change the function. So $C(3)$ fails.

Pairs behave differently, and the reason is that the group has no elements of order two. Any two-element real set has its two elements swapped by no permutation in the group, since all elements of the group have order 3. So each element of a real pair is fixed whenever the pair is. In particular, a pair within a triple has an element distinguished by the direction of the rotation: the first in the cycle. So a choice function for pairs is real, and $C(2)$ holds. Transferring the result from set theory with atoms to ordinary set theory requires a theorem of Thomas Jech and Antonín Sochor, and it goes through for statements of this kind. The prime in Mostowski’s condition is exactly this: a sum of primes above $m$ allows a group acting without any orbit of a small length, and a permutation model can then refuse any small help.

This is why the condition has the shape it has. If $n$ is a sum of primes all above $m$, arrange atoms into sets of size $n$, each broken into orbits of those prime lengths under its own cyclic symmetries. All orbits are prime and larger than $m$. So sets of size up to $m$ are fixed pointwise by the group, and $C(\le m)$ holds, while no element of an $n$-set is singled out. Nothing could be neater. So the arithmetic of sums of primes is literally the arithmetic of how a set may be made to look symmetric.

Where this fits among the weak forms #

There are hundreds of weak forms of the axiom, catalogued by Paul Howard and Jean Rubin in a book that is largely a list. Forms for finite sets are special among them because finite combinatorics does the work and because they can often be decided outright. Several of them have clear uses. The choice inside a countable union concerned countable families of arbitrary sets, which is a different axis from the sizes here. Countable choice says nothing about uncountable families of pairs, and choice for all finite sets says nothing about countable families of infinite sets, so the two are independent, which is a reminder that the weak forms do not line up in a single order.

A spanning tree for every graph showed how a graph theory statement can force exactly this kind of choice, since the socks turn up as a graph whose only spanning trees need a selection from each pair. Choice for finite sets is what some versions of those graph theorems need when degrees are bounded, and there the question of which sizes are required is exactly the question discussed here. And the ultrafilters that break an infinite electorate sit at another level, with the Boolean prime ideal theorem implying choice for all finite families. That is the sense in which these little axioms are a real part of what larger ones say.

There is also a nice computational analogue in the idea of orderability: a rule for choosing from a pair in a uniform way is a tournament on the whole universe. From that perspective, $C(2)$ says that there is a tournament on every family of sets, in effect, while an actual total order would be much more. A tournament need not be transitive, and much of the point here is that one does not need a transitive tournament to do the work. A cyclic tournament is the only thing that defeats the scoring trick, and that is exactly the situation that the permutation model constructs. The structure of majority tournaments raises the same thing from another direction.

What has and has not been checked #

All the tournament counts are exact and exhaustive, from three to six points. Mostowski’s condition is computed directly from sums of primes for sizes up to 24, and the table says what passes the test. The positive results for 6, 8 and 9 were given as arguments above, and the argument for 9 has not been run through the same computation, though it is easy to confirm that 9 does not divide 84.

The permutation model is described in outline. Whether a transfer to ordinary set theory is legitimate is the content of the Jech–Sochor theorem, cited and not explained. The statement that the conditions completely describe all implications, including those with more complicated sets of assumed sizes, is a summary of work by Gauntt and others that is not reproduced here. And the table’s reading of “follows from sizes up to $m$” should not be mistaken for a statement about single assumptions: $C(3)$ on its own does not give $C(2)$, and the table does not claim otherwise.

Still open: how much the trick can see #

The problem of which $C(n)$ follow from which is essentially closed for finite assumption sets, thanks to the permutation-model analysis, so the open questions are about what the methods show. Is there a uniform combinatorial proof of each positive case? Each implication that survives Mostowski’s test and its refinements is known to hold. But the proofs vary in kind, and Gauntt’s characterisation works by a group-theoretic criterion, which is not obviously a recipe for a scoring rule of the kind above. Whether every such implication comes from counting $k$-subsets and scoring in some generalised way has not been shown.

A second question concerns strength. How much does the choice for bounded finite sets give in graph theory and in ordinary mathematics? Statements about colouring infinite graphs of bounded degree are tied to small forms of finite choice, and a growing list of such equivalences has been compiled. Which theorems of finite graph theory, once they are applied to infinite graphs, need precisely which $C(n)$ is a question with many cases still unsettled.

Six choices make a seventh #

A choice from each of the six pairs inside a set of four is a tournament, and because 4 does not divide 6, its scores cannot all be equal, so the least-score set has one, two or three elements, and each case yields a choice from the four. The same scoring works whenever $n$ does not divide the number of $k$-subsets and the smaller sizes are available. At three and at five, regular tournaments defeat it. Mostowski’s condition puts the limit exactly where a permutation model can hide: $n$ is out of reach whenever it is a sum of primes all above $m$, and so from pairs alone only 4 follows.

So an infinite question, whether a set of socks can be chosen from without a rule, comes down to a calculation about divisibility. It is one of the cleanest illustrations of how much of set theory’s independence is really about the symmetry of small finite sets.