[math-fun] "Canonical" 1-1 correspondences between sets
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?
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.
In practice, most vector spaces come equipted with a "metric" (non-degenerate bilinear form) < , >. In this case there is the natural bijection from X to X* given by x-> f_x where f_x(y) = <x,y>.
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. A common question is to find a "bijective proof" between two sets which are known to have the same number of elements. The book "Constructive Combinatorics" by Dennis Stanton and Dennis White devotes considerable energy to establishing "listing algorithms" and their inverses. For example, they exhibit such a bijection between {1,2,..., n!} and the set S_n of all permutations on the n-element set {1,2,...,n}. They also give bijections for set partitions, integer partitions, etc...
Mensaje citado por: John McCarthy <jmc@steam.Stanford.EDU>:
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. ...
We can ask whether there is a "canonical" 1-1 correspondence. [...]
There is another nice example of this in group representation theory where the number of classes equals the number of irreducible representations. It is tempting to asssociate the identity class with the unit representation, but much anguish has been expended trying to extend such a concept. - hvm ------------------------------------------------- Obtén tu correo en www.correo.unam.mx UNAMonos Comunicándonos
participants (3)
-
Edwin Clark -
John McCarthy -
mcintosh＠servidor.unam.mx