I don't believe I made a mistake. The set of odd-cardinality subsets of the empty set is a set with 0 elements, whereas the set of even-cardinality subsets of the empty set is a set with 1 element (that element being the empty set). So there's no bijection, unless I am the Pope. And if I'm the Pope, I'm infallible. So either way, I'm right. :-) Jim On Monday, August 25, 2014, Michael Kleber <michael.kleber@gmail.com> wrote:
Jim, I think Mike was pointing out that despite failing your criterion, the empty set *does* allow a natural bijection between its sets of odd- and even-sized subsets, both of which are empty.
--Michael
On Mon, Aug 25, 2014 at 7:24 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Note that the empty set does not come equipped with a natural subset of odd cardinality (or any unnatural ones either!). So it satisfies my two-way criterion. On the other hand, every finite set of odd cardinality comes equipped with a subset of odd cardinality, namely itself!
As I recall, there can be classically equivalent but topos-theoretically inequivalent ways to say what we mean by a set of even cardinality. It could be defined as a set that can be partitioned into disjoint sets of size two, or a set that can be partitioned into two subsets that are in bijection with each other. Similarly there's more than one way to define "odd". Worse yet, you could have a matching pair of definitions of odd vs. even and a finite set X that satisfies neither definition; that is, you can in some sense "have" a finite set without being able to decide whether its cardinality is even or odd! But cheer up: In your brain-damaged state, you also can't tell whether the set is finite or infinite. So the odd/even dichotomy still survives in weakened form.
(People who genuinely know topos theory should correct me if any of the above is wrong.)
Jim Propp
On Monday, August 25, 2014, Mike Speciner <ms@alum.mit.edu <javascript:;>> wrote:
Isn't the empty set a finite set ?
--ms
On 2014-08-24 18:28, Dan Asimov 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
_______________________________________________ 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
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun