[math-fun] "Proizvolov's identity"
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
I'm not sure what you mean by "bijective", but if you graph the two sequences then they form an X pattern. The numbers in the upper branches are always {n+1, ..., 2n} in some order, and the numbers in the lower branches are always {1, ..., n} in some order, so the sum |a_i - b_i| is always (n+1 + n+2 + ... + 2n) - (1 + 2 + ... + n) = n^2 More formally, let a_i be the increasing sequence, let b_i be the decreasing sequence, and let k be the largest integer for which a_k < b_k (take k = 0 if a_1 > b_1). Then the branches of the X pattern are {a_1, ..., a_k}, {a_{k+1}, ..., a_n}, {b_1, ..., b_k}, {b_{k+1}, ..., b_n}. At the center we have: a_k < b_k, b_{k+1} < a_{k+1} (by choice of k) a_k < a_{k+1}, b_{k+1} < b_k (by monotonicity of a_i, b_i) Together with the monotonicity of the branches, this implies that every integer in the lower branches is smaller than every integer in the upper branches, from which the above assertion follows. J.P. On Sat, Aug 23, 2014 at 9:24 PM, Gareth McCaughan < gareth.mccaughan@pobox.com> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 24/08/2014 12:50, J.P. Grossman wrote:
I'm not sure what you mean by "bijective", but if you graph the two sequences then they form an X pattern. The numbers in the upper branches are always {n+1, ..., 2n} in some order, and the numbers in the lower branches are always {1, ..., n} in some order, so the sum |a_i - b_i| is always (n+1 + n+2 + ... + 2n) - (1 + 2 + ... + n) = n^2
More formally, [...]
Yes, this is basically the same as one of the proofs on the cut-the-knot page I linked to. It's not bad, but not quite what I was hoping for. By "bijective" I mean: We're trying to prove that one positive integer equals another. Perhaps there's a proof that makes it obvious that each of them is the size of some set, and exhibits a bijection between the two sets. -- g
I know an argument which I think is different from the other two. It shows that the value of the sum in question is the same regardless of how you split 1,2,...,2n into two sets of size n, but doesn't compute what that value is (though it's easy to compute it via a separate argument, using the odd-even split or the low-high split). You just need to show that if you swap two adjacent integers between the two sets, the value of the sum doesn't change; and that you can get from any split to any other via moves of this kind. This isn't what the OP asked for, but I find this approach very handy for many sorts of combinatorial problems. Jim Propp On Sunday, August 24, 2014, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 24/08/2014 12:50, J.P. Grossman wrote:
I'm not sure what you mean by "bijective", but if you graph the two sequences then they form an X pattern. The numbers in the upper branches are always {n+1, ..., 2n} in some order, and the numbers in the lower branches are always {1, ..., n} in some order, so the sum |a_i - b_i| is always (n+1 + n+2 + ... + 2n) - (1 + 2 + ... + n) = n^2
More formally, [...]
Yes, this is basically the same as one of the proofs on the cut-the-knot page I linked to. It's not bad, but not quite what I was hoping for.
By "bijective" I mean: We're trying to prove that one positive integer equals another. Perhaps there's a proof that makes it obvious that each of them is the size of some set, and exhibits a bijection between the two sets.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Will the following do as a proof? Just look! Draw a rectangle with 2n rows and n columns, Area 2n^2. In each column i (1 \leq i \leq n) draw two lines at levels a_i, b_i, so that there is just one line at every level from 1 to 2n. Then the answer is the area between the n pairs, i.e. the total area, 2n^2, minus the area above the higher lines, 0+1+2+...+(n-1) and the area below the lower lines, 1+2+3+...+n. 2n^2 - n^2 = n^2. P'raps this has already been said (more than once?) R. On Sun, 24 Aug 2014, James Propp wrote:
I know an argument which I think is different from the other two. It shows that the value of the sum in question is the same regardless of how you split 1,2,...,2n into two sets of size n, but doesn't compute what that value is (though it's easy to compute it via a separate argument, using the odd-even split or the low-high split). You just need to show that if you swap two adjacent integers between the two sets, the value of the sum doesn't change; and that you can get from any split to any other via moves of this kind.
This isn't what the OP asked for, but I find this approach very handy for many sorts of combinatorial problems.
Jim Propp
On Sunday, August 24, 2014, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 24/08/2014 12:50, J.P. Grossman wrote:
I'm not sure what you mean by "bijective", but if you graph the two sequences then they form an X pattern. The numbers in the upper branches are always {n+1, ..., 2n} in some order, and the numbers in the lower branches are always {1, ..., n} in some order, so the sum |a_i - b_i| is always (n+1 + n+2 + ... + 2n) - (1 + 2 + ... + n) = n^2
More formally, [...]
Yes, this is basically the same as one of the proofs on the cut-the-knot page I linked to. It's not bad, but not quite what I was hoping for.
By "bijective" I mean: We're trying to prove that one positive integer equals another. Perhaps there's a proof that makes it obvious that each of them is the size of some set, and exhibits a bijection between the two sets.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 25/08/2014 20:42, rkg wrote:
Will the following do as a proof? Just look!
Draw a rectangle with 2n rows and n columns, Area 2n^2.
In each column i (1 \leq i \leq n) draw two lines at levels a_i, b_i, so that there is just one line at every level from 1 to 2n. Then the answer is the area between the n pairs, i.e. the total area, 2n^2, minus the area above the higher lines, 0+1+2+...+(n-1) and the area below the lower lines, 1+2+3+...+n. 2n^2 - n^2 = n^2.
What seems to be missing is the proof that the higher lines are exactly {0,1,...,n-1} and the lower ones exactly {n,n+1,...,2n-1}. It turns out that this is true, and so far the neatest proofs all seem to go via this observation, but it's not instantly obvious to me and the proofs I've seen don't make it so. (It does have short clear proofs; so this may just be an observation about the limits of my own sense of the obvious.) -- g
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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For sets of odd size, there is a natural bijection; exercise for the reader to find it. For sets of even size, the proof that there is no natural bijection is simple; what set is paired with the empty set under the bijection? A "natural" bijection would be one where given a bijection between two sets, the obvious square commutes. Andy On Sun, Aug 24, 2014 at 6:28 PM, 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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
On Sun, Aug 24, 2014 at 6:28 PM, 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.
When |X| is odd, isn't s -> X - s a natural bijection between the odd-sized and even-sided subsets? -Thomas C
(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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
(In the same way, it's 'easy to show that' S_n has equally many odd permutations as even permutations. :)
Sent: Monday, August 25, 2014 at 2:24 PM From: "Mike Speciner" <ms@alum.mit.edu> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Bijective proofs
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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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> 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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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> 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> 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> 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
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
participants (10)
-
Adam P. Goucher -
Andy Latto -
Dan Asimov -
Gareth McCaughan -
J.P. Grossman -
James Propp -
Michael Kleber -
Mike Speciner -
rkg -
Thomas Colthurst