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
