May 2003 - mathfun@mailman.xmission.com

RE: [math-fun] Re: Canonical 1-1 correspondences
by Andy Latto 21 May '03

21 May '03

> -----Original Message----- > From: William Thurston [mailto:wpthurston@mac.com] > Sent: Wednesday, May 21, 2003 4:58 PM > To: math-fun > Subject: Re: [math-fun] Re: Canonical 1-1 correspondences > > > Come on, people. Epsilon more consideration. A linear isomorphism > between a vector space and its dual is equivalent to a > bilinear form on > the vector space. (mapping X to the set of maps from X to Y is the > same as giving a map of X x X to Y). When you map a basis to > its dual > basis, this gives a particular kind of isomorphism of X to X* > (provided X is finite dimensional) that is described by the identity > matrix. The bilinear form is symmetric, so not all isomorphisms are > represented in this way. Any orthogonal matrix describes a basis that > determines the same isomorphism. Right you are. The mistake I made is that I noticed that both the set of bases for X, and the set of linear isomorphisms from X to X*, were (non-canonically) isomorphic as sets to G, the set of linear bijections from X to X. But while these are the same set, they are different G-sets. The set of bases of X is isomorphic to the G-set G, acting on itself by multiplication, while the set of isomorphisms from X to X* is isomorphic to the G-set G, acting on itself by conjugation. So one shouldn't expect to find a canonical isomorphism between them. There is an obvious map from bases of X to isomorphisms of X and X*, but it is neither 1-1 nor onto. Andy Latto andy.latto(a)pobox.com > > On Wednesday, May 21, 2003, at 09:50 AM, John Conway wrote: > > > On Wed, 21 May 2003, Andy Latto wrote: > > > >> > >> > >>> -----Original Message----- > >>> From: John McCarthy [mailto:jmc@steam.Stanford.EDU] > >>> Sent: Tuesday, May 20, 2003 7:27 PM > >>> To: math-fun(a)mailman.xmission.com > >>> Cc: math-fun(a)mailman.xmission.com; jmclists(a)cs.Stanford.EDU > >>> Subject: Re: [math-fun] Re: Canonical 1-1 correspondences > >>> > >>> > >>> John Conway wrote > >>> > >>> > >>> But if you're going to allow infinite classes, then > >>> trivially the set of all correspondences is a canonical one. > >>> > >>> Yes, but consider the correspondences between X and X* you get > >>> when you choose a basis for X. A basis element b of X > >>> corresponds to the functional that is 1 on b and 0 on the other > >>> basis elements. It seems to me that these correspondences should > >>> be the canonical set of correspondences. However, I don't know > >>> of a general criterion for preferring them. > >> > >> Aren't these exactly the linear bijections between X and X*? > > > > Yes, they are. JHC > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

1 0

RE: [math-fun] Re: Canonical 1-1 correspondences
by Andy Latto 21 May '03

21 May '03

> -----Original Message----- > From: John McCarthy [mailto:jmc@steam.Stanford.EDU] > Sent: Tuesday, May 20, 2003 7:27 PM > To: math-fun(a)mailman.xmission.com > Cc: math-fun(a)mailman.xmission.com; jmclists(a)cs.Stanford.EDU > Subject: Re: [math-fun] Re: Canonical 1-1 correspondences > > > John Conway wrote > > > But if you're going to allow infinite classes, then > trivially the set of all correspondences is a canonical one. > > Yes, but consider the correspondences between X and X* you get > when you choose a basis for X. A basis element b of X > corresponds to the functional that is 1 on b and 0 on the other > basis elements. It seems to me that these correspondences should > be the canonical set of correspondences. However, I don't know > of a general criterion for preferring them. Aren't these exactly the linear bijections between X and X*? Andy Latto andy.latto(a)pobox.com

4 3

[math-fun] Re: Canonical 1-1 correspondences
by MCKAY john 21 May '03

21 May '03

Although for the symmetric group there is a canonical correspondence between the classes and irreducible representations (as has been pointed out) - my understanding is that it has been shown that for an arbitrary finite group no such correspondence exists. John McKAy

4 5

Re: [math-fun] Canonical 1-1 correspondences between sets
by James Propp 21 May '03

21 May '03

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

2 1

Re: [math-fun] Re: Canonical 1-1 correspondences
by asimovd＠aol.com 20 May '03

20 May '03

In a related vein, it's interesting that in math there exist things which are indistinguishable, yet not identical. Perhaps the simplest example of this is i and -i. Another simple example is the non-identity elements in the Klein 4-group (the isometry group of a rectangular solid having unequal sides). ------------------------------------------------------------------------------ -------------------------------------------- But back to the absence of canonical correspondences: Let V(p) be a 1-dimensional vector space over F_p (the field of size p prime), and V(p)* = Hom(V(p),F_p) its dual vector space. It's amusing that there's no canonical isomorphism between V(p) and V(p)* iff p > 2. Question: Is the absence of a canonical isomorphism between an arbitrary vector space V and its dual V* equivalent to the Axiom of Choice? --Dan

1 0

Re: [math-fun] Canonical 1-1 correspondences between sets
by James Propp 20 May '03

20 May '03

>> Does this phenomenon account for the fact that it is so often easier >> to establish that two sets are equipollent than to establish an >> elegant 1-1 correspondence? >> >> Is the question discussed in the literature on cominatorics? > >This is the life blood of a lot of combinatorics. Well, yes and no. The combinatorial literature is full of bijective arguments, but comparatively devoid of "meta-combinatorial" assertions about the limits of the bijective method. 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. A good way to think about these problems is define a canonical bijection as one that is invariant under relabellings of the underlying set of "points". So, as another example, the set of linear orderings of an n-element set S and the set of invertible maps from S to itself both have n! elements, but there can be no canonical bijection between them, because they are not the same S_n-set (where a G-set is a set together with an action of a group G on that set). This is the perspective taken by the theory of species. If there has been any important recent works on the limits of the bijective method, I'd be extremely interested in knowing about it! Jim Propp

2 1

[math-fun] Re 'Partition' and Mathematical Plays
by Guy Haworth 19 May '03

19 May '03

'Proof' with one G Paltrow ... how did I miss it?! http://www.londontheatre.co.uk/londontheatre/reviews/proof02.htm Stoppard's 'Arcadia' is excellent - ran in the West End, London, some years ago. http://math.bu.edu/DYSYS/arcadia/ refers. 'Breaking the Code' - Derek Jacobi as Alan Turing - ran in London and was filmed for (BBC) TV too. http://www.turing.org.uk/turing/scrapbook/btc.html 'Copenhagen' ran in London - more Physics than Maths ... got very good reviews http://www.aip.org/history/newsletter/spring2000/copenhagen.htm 'Beautiful Mind' was also excellent for me - despite departing from fact BBC did a program re Wiles/FLT, more of a documentary with tension - good. Guy

2 1

[math-fun] and the famous formula of A. Einstein (manuscript)
by Simon Plouffe 19 May '03

19 May '03

In one of the manuscripts, we can read, E= mc^2 on the top of the page. http://www.alberteinstein.info/gallery/images/01-148p01z_high.jpg Simon Plouffe

1 0

[math-fun] collected papers of Albert Einstein
by Simon Plouffe 19 May '03

19 May '03

hello, This site holds pretty much all of what he wrote I believe, it goes back to 1896. http://www.alberteinstein.info/ ...interesting! Simon Plouffe

1 0

[math-fun] "Canonical" 1-1 correspondences between sets
by John McCarthy 19 May '03

19 May '03

When two sets are proved to have the same number of elements, e.g. the number of partitions of n into odd parts and the number of partitions of n into distinct parts, it seems natural to ask whether the proof should be given by establishing a 1-1 correspondence between the sets. In the above example it was done but long after the equality was established. [Have I got the facts right?] Of course, whenever there is a 1-1 correspondence between two sets, there are k! of them. We can ask whether there is a "canonical" 1-1 correspondence. Here's a case where there are 1-1 correspondences but where it seems that none are canonical. Consider a vector space X of dimension n over a finite field. Also consider its dual space X* and its double dual X**. X has a canonical isomorphism F with X**, namely F(x)(f) = f(x), but it doesn't seem to have a canonical isomorphism with X*. Therefore, a proof that X and X* have the same number of elements wouldn't be as natural as a proof that X and X** have the same number of elements. Does this phenomenon account for the fact that it is so often easier to establish that two sets are equipollent than to establish an elegant 1-1 correspondence? Is the question discussed in the literature on cominatorics?

3 2