Q. For which finite sets X can one give a natural bijection f between the odd-cardinality subsets of X and the even-cardinality subsets of X? A. Precisely those sets X that come equipped with a natural subset S of odd cardinality (which could be X itself). For, given f, we can define S as f(nullset); and conversely, given S, we can define f(Y) to be the symmetric difference of Y and S, for every subset Y of X. This is explored (along with other questions of a similar flavor) in a paper I wrote with David Feldman many years ago, called "Producing New Bijections from Old" ( http://www.sciencedirect.com/science/journal/00018708/113/1). The sane way to make sense of the word "natural" is to impose a group action (like the group of permutations of X) and ask for maps that are G-equivariant. The insane way is to ingest topos theory and let it install non-classical logic in your brain. (Rimbaud merely sought systematic disordering of the senses; the modern mathematician kicks this up a notch by systematically disordering reason!) David and I never followed up on this work, and neither did anyone else as far as I know. An article in a similar vein is Conway and Doyle's "Division by Three" (http://arxiv.org/abs/math/0605779). And if you like this stuff, you might also enjoy Andreas Blass' "Seven Trees in One" ( http://www.sciencedirect.com/science/article/pii/002240499500098H). Jim Propp On Sunday, August 24, 2014, Dan Asimov <dasimov@earthlink.net> wrote:
Speaking of "bijective proofs", I'd like to bring up something that Jim (Propp) once mentioned I think on math-fun:
For any finite set X, it's easy to show that it has the same number of odd-sized subsets as of even-sized subsets.
But there doesn't seem to be a natural bijection between them.
(In fact the standard proof is this: pick any element x of X. Then for any subset not including x, add it; for any subset including x, remove it.)
What I'd like to know is, Is there a proof of the nonexistence of a "natural" bijection here? (Something like a proof that any bijection requires the use of the finite Axiom of Choice. Or maybe this can be expressed as the nonexistence of some kind of functor from the category of finite sets to the category of finite bijections.)
--Dan
On Aug 23, 2014, at 6:24 PM, Gareth McCaughan <gareth.mccaughan@pobox.com <javascript:;>> wrote:
A recent post on the (excellent) blog "Futility Closet" http://www.futilitycloset.com/2014/08/21/proizvolovs-identity/ cites without proof the following theorem:
Take the numbers 1..2n. Divide them into two subsets of size n. Write one in ascending order and the other in descending order. Then the sum of |a_i-b_i| is always n^2.
This isn't difficult to prove, but the proof I found not-difficult to find isn't terribly elegant. Is there a neat "bijective" proof?
(There are two proofs at http://www.cut-the-knot.org/Curriculum/Games/ProizvolovGame.shtml neither of which seems very elegant to me. Both are better than my proof, which proceeds by induction on n.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun