Re: [math-fun] Canonical 1-1 correspondences between sets
I wrote:
Here's a very simple example of such a limitation: Let S be a set with n elements. Then the assertion that the alternating sum of the binomial coefficients n-choose-k (with k going from 0 to n) vanishes is equivalent to the assertion that there exists a bijection between the subsets of S with even cardinality and the subsets of S with odd cardinality. When n is odd, there is a simple bijection of this kind (namely, the bijection that maps each subset of S to its complement). When n is even, there is no such bijection. Indeed, one can show that singling out a bijection between the even-cardinality and odd-cardinality subsets of a set S is equivalent to singling out one odd-cardinality subset of S.
Let me clarify this. In one direction: If T is an odd-cardinality subset of S, then one can define a bijection between subsets of S of even cardinality (hereafter "even subsets") and subsets of S of odd cardinality ("odd subsets") simply by mapping each subset of S to its symmetric difference with T. So, if someone gives you a set S of indistinguishable elements and an odd subset T of S, then you can use T to specify a bijection between all the even subsets of S and all the odd subsets of S. In the other direction: If f is a bijection between the even and odd subsets of S, then in particular f of the empty subset of S is an odd subset of S. So, if someone gives you a set S of indistinguishable elements and a bijection f between the odd subsets and even subsets of S, then you can use f to specify an odd subset of S. (Note that in the preceding paragraph, I am not saying that every bijection f between the odd and even subsets of S is given by the symmetric difference construction. There are far more bijections between the odd and even subsets of S than there are odd subsets of S.) My impression is that one can put this analysis on a rigorous setting in topos theory, and that in a suitable topos, the finite sets that admit a bijection between odd subsets and even subsets are precisely the finite sets that have an odd subset. (I know this sounds weird: doesn't every non-empty finite set have at least one subset of odd cardinality? But things can be weird this way in topos theory. In particular, if there's no way to single something out with the information that one has in hand, then in a certain sense one can say it "fails to exist". So one could have a 4-element set with no 1-element subsets.) Please correct me if you actually know some topos theory and I'm misrepresenting the situation! 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.
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)? Jim Propp
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
participants (2)
-
James Propp -
John Conway