On Tue, 20 May 2003, James Propp wrote:
I also wrote
If there has been any important recent works on the limits of the bijective method, I'd be extremely interested in knowing about it!
and John Conway replied
Not recent, but have you heard of the stuff on the finite axioms of choice? Also, the Lindenbaum-Tarski theorems that for cardinals n.S,T of which n is finite, nS = nT => S = T.
If I recall correctly, John himself did some work on this problem in the particular case n=3.
In fact it was on the general case, and with Peter Doyle. We used the case n = 3 merely as our "lead example", since in fact it includes all the ideas. Here's a sketch of the proof. Suppose we are given a bijection between {a,b,c} x S and {d,e,f} x T - I'll say things like "(a,s) joins (d,t)". Then there are all sorts of consequential at most 1:1 relationships, such as the one that relates s to t if and only if (a,s) joins some (d,t') for which (e,t') joins some (b,s') for which (c,s') joins (d,t). Without using the axiom of choice we can put these into some kind of preference order, say R1,R2,... . Then say "s hyperjoins t" if for some n we have s Rn t but no relation of the form s Rm t' holds for any m < n. Then hyperjoining is an at most 1:1 relation, that in each component of the joining graph must exhaust either S or T. Let's call the components that exhaust S but not T "first components", and the rest "seconds". This splits S = S1 + S2, T = T1 + T2 into disjoint unions of pairs of sets for which we have 3|S1| = 3|T1|, 3|S2| = 3|T2, and |S1| is at least |T1| and |S2| at most |T2|, so all we need to prove is Lindenbaum's lemma: If S = T + X and 3S = 3T, then S = T. But this boils down to If 3T additively absorbs 3X, then T additively absorbs X, which is trivial using the fact that A additively absorbs B just if A >= aleph0 times B. For we see that 3T >= aleph0 times 3X, which is the same as aleph0 times X. Now any for any particular point x in X, infinitely many of the points (n,x) must join things of the same one of the three types (a,t),(b,t),(c,t). This splits X into 3 parts Xa,Xb,Xc, each of which is absorbed by T, whence so is their sum.
Some of the theorems of Mostowski on non-derivability of some choice axioms from others are naturally construed as "limits on the bijective method". JHC
I'm not familiar with this. Can John or someone else supply references (or better still a summary)?
I think it was started by Tarski, who showed, for instance, that axioms [4] and [2] were equivalent. (Axiom [n] is the assertion that every set of n-element sets has a choice function.) Here's a quick proof. To see that [4] implies [2], just double up each couple, and allpy axiom [4]. To see that [2] implies [4], pick a point in each pair of points from each of the given 4-sets. This makes 6 choices in each 4-set {a,b,c,d}, and since this isn't a multiple of 4, some points must be chosen more often than others. If there's just one maximally-chosen point a, pick a. If there are three, say a,b,c, pick d. If there are two, say a and b, pick whichever one [2] picked from {a,b}. It's easy to exhibit more interesting implications, such as the fact that [6] => [9] and my own favorite, that [10]_5 is equivalent to the conjunction of axioms [2] and [3] and [7], where [10]_5 is the axiom that picks a 5-element subset from every 10-element set. Mostowski proved that a necessary condition for a given set of axioms [a],[b],[c],... to imply n is that for every way of making n up as a sum of primes (with repetitions allowed), one of a,b,c,... must be makable from those primes. I proved that this is sufficient if you replace "primes" by "prime powers". A case that was still unsettled when I joined the fray was whether [3]&[5]&[13] imply [15]. Here the prime condition holds, but the prime power one doesn't, since 15 can be made from 7 and 8, while 13 can't. I prove that [3]W & [5]W and [13]W do imply [15]W, where [n]W is the axiom that there's a choice function for every well-ordered collection of n-element sets. JHC