# Examples of two different descriptions of a set that are not obviously equivalent?

I am teaching a course in enumerative combinatorics this semester and one of my students asked for deeper clarification regarding the difference between a "combinatorial" and a "bijective" proof. Specifically, they pointed out that when one is proving the validity of a combinatorial identity by counting a set in two different ways, this is a different activity than giving an explicit bijection between two different sets. However, in combinatorics we often use the phrases "combinatorial proof" and "bijective proof" as synonyms, and I have often heard people use the phrase "bijective proof" regarding a "count in two different ways" proof of an identity.

It seems to me that often a combinatorial proof arises from describing one set in two different ways; implicit in a proof of the equality of the two descriptions of this set is the identity bijection from the set to itself. In this sense, one might regard all "combinatorial" proofs as "bijective," but I feel that I am on quite shaky ground with this. These thoughts have led me to the following questions:

Question 1: What are some examples of combinatorial situations where the same set can be described in two different ways but it is not at all clear that the two descriptions yield the same object?

Question 2: What are some examples of situations where two bijective proofs have been given for a theorem or identity where the bijections turned out to be the same, but proving their equivalence was non-trivial?

I would also appreciate opinions regarding the distinction, if any, between combinatorial arguments where one proves identities by describing a set in two different ways and combinatorial arguments where one sets up bijections between genuinely different sets of objects.

EDIT

Thanks for the answers and comments so far. Here are two examples that will hopefully clarify what I am asking. One example of a bijective proof between two different sets are showing that Dyck paths and nonnesting partitions are both Catalan-enumerated objects (even preserving the Narayana statistic with a good bijection). On the other hand, the identity $\sum_{k=0}^nk{n\choose k}=n2^{n-1}$ is usually proved by describing $k$-subsets of $n$ with a distinguished element in two different ways: in the first way, pick the set then specify the element; in the second way, pick the element then specify the rest of the set. These are both referred to as bijective or combinatorial proofs, yet somehow they each have a different feel to them. In the second case, it is pretty easy to see that the two descriptions of these objects yield the same set of objects, but surely there must be more situations where the same set is described in two different ways and the equivalence of their descriptions is difficult to ascertain. Similarly, there must be times where there are several bijections between different sets, like the first example, where the bijections are the same but not obviously so. What I am wondering about are examples of these two situations.

A non-combinatorial example of an answer to Q1 is the compact-group vs reflection group definition of the Weyl group of a semi-simple Lie Algebra, where it isn't immediately clear that the same group is obtained. However, I am looking for more combinatorial examples.

-
The set of non-trivial integer solutions of the equation $x^{71}+y^{71}=z^{71}$ coincides with the empty set. –  Mariano Suárez-Alvarez Jan 23 '11 at 3:05
Do you want to perhaps limit your question to combinatorics? Because Question 1 is extremely vague, and almost any characterisation theorem will give an example. Generously interpreting the word "object", an example can be the Selberg trace formula; but these kinds of examples are probably useless for your pedagogical question. –  Willie Wong Jan 23 '11 at 3:09
I am confused what "same" means in this context, especially given that you are attempting to distinguish "combinatorial" from "bijective" proofs. –  Qiaochu Yuan Jan 23 '11 at 3:11
Noah Snyder's answer at mathoverflow.net/questions/4841/… is relevant: as he points out, the question "what do Catalan numbers count?" has many answers. The passage from combinatorial to bijective proofs is an important instance of categorification, and your first question is an instance of the question "what examples are there of structures that can be categorified in two different ways?" –  Tom Leinster Jan 23 '11 at 3:43
I'm fairly certain that Stanley's list of Catalan objects contains not-obviously-equivalent definitions of the same objects, but unfortunately I don't know of any specific examples off the top of my head: math.mit.edu/~rstan/ec/catadd.pdf I feel like the various forms of RSK are probably a good example for question 2. –  JBL Jan 23 '11 at 5:09

Here is a fact that I find interesting. Strictly speaking it is to say that a certain number counts three completely unrelated things, but it seems easy to make these into a combinatorial problem or to define an explicit bijection between two (or three) sets.

So, the concrete example is $168$, which

(1) the number of hours in a week;

(2) the number of primes under $1000$; and

(3) the size of the smallest simple group of Lie type.

$168$ is also $4 \times 42$, where $42$ is that famous number Douglas Adams wrote about. (How did he know?) Which is of course the reciprocal of the smallest positive number that can be written as $$1-\frac 1a -\frac 1b -\frac 1c$$ with $a,b,c\in \mathbb N$ and coincidentally (and relatedly) the largest size of the automorphism group of $C$ a smooth projective curve of genus at least $2$ is $42\cdot {\rm deg} K_C$ and of $S$ a smooth projective surface of general type is $(42 K_S)^2$.

So I guess one could add that $168$ is also

(4) the maximum value of $\frac 4{1 -\frac 1a -\frac 1b -\frac 1c}$ with $a,b,c\in \mathbb N$; and

(5) the largest possible size of the automorphism group of a smooth complex projective curve of genus $3$,

but I admit the last two are a little artificial...

-
Why this answer got $\geq 4$ votes is beyond me. –  Christian Blatter Jan 23 '11 at 16:24
There are more things in heaven and earth, Christian, than are dreamt of in your philosophy.... –  Sándor Kovács Jan 23 '11 at 19:50

In response to question 1, there is some subtlety involving use of the phrase "same object". This more or less immediately suggests to me the question of whether we are thinking of a bijective proof as establishing an isomorphism between structures, or not.

One of the simplest examples I can think of is the distinction between a permutation on an n-element set and a total ordering on the same set. There are $n!$ structures in each case, but in the one case we are counting the elements in a group, and in the other we are counting torsors over the same group. To see that these objects are truly distinct, imagine that we have a bijection $f: S \to T$ between n-element sets; how would we transport the structures in each case? In the total order case, we would simply apply $f$ directly to a total order $s_1 < s_2 < \ldots < s_n$ on $S$ to get a total order $f(s_1) < f(s_2) < \ldots < f(s_n)$ on $T$. In the other case, given a permutation $\phi: S \to S$ on $S$, we'd have to conjugate by $f$ to get a permutation $f \phi f^{-1}$ on $T$. These are very different actions; in the case where $S = T$, the action of $Aut(S)$ on total orders has just one orbit, and the action of $Aut(S)$ on permutations has many orbits given by cycle type decompositions.

In the language of category theory, the issue is whether a bijective proof means an isomorphism between Joyal species, or not. For example, if $Tot$ is the species of total orders and $Perm$ the species of permutations, there is a non-isomorphic bijection between them. In such cases, one must typically make a choice of standard structure in order to effect the bijection (for example, one may choose the standard order on $\{1, 2, \ldots, n\}$ to give an explicit bijection between total orders and permutations, but a choice of different order would lead to a different explicit bijection). Cf. David Feldman's answer, where choice also enters.

This is a simple example of course, but propagates more elaborate examples. Many readers here will know of Joyal's beautiful proof of Cayley's theorem (as discussed elsewhere at MO), that there are $n^{n-2}$ tree structures one can put on an n-element set. This also involves a non-isomorphic bijection between Joyal species; in compact form it involves a non-isomorphic bijection between two species

$$Tot \circ Arbor$$

$$Perm \circ Arbor$$

where $Arbor$ is the species of what Joyal calls "arborescences", in other words rooted trees. For details, consult Joyal's original article (in French) in Adv. Math. 42 (1981), 1-82. Or see the book Combinatorial Species and Tree-like Structures by Bergeron, Labelle, and Leroux (Cambridge U. Press, 1998).

Andreas Blass has an interesting paper "Seven Trees in One" where there is an in-depth discussion of issues of choice and constructivity. The paper by Conway and Doyle on 3A = 3B implies A = B also comes to mind here (this has also been discussed at MO).

-

I'm not entirely sure I get the question, but I think the theory of partitions has many examples of the kind of thing you want. The number of partitions of $n$ into (say) 17 parts equals the number of partitions of $n$ into parts the largest of which is 17. There's a bijection between the two sets of partitions; the bijection is so natural (once you've seen it) that it's tempting to say we're just talking about one set of partitions but looking at it two different ways. The number of partitions (of $n$) into odd parts equals the number of partitions into distinct parts; here, too, there's a bijective proof, but it's quite a bit harder to find. There is a host of these things in the Andrews and Eriksson book, Integer Partitions (and in many other places where partitions are discussed in detail).

-
Here's a bijection that equates partitions into odd parts and partitions into distinct parts. Start with any partition: pick two parts of the same size and combine them into a single part (twice as large, naturally); continue until there are no repeated part sizes. This maps partitions into odd parts into partitions into distinct parts. The inverse --- repeatedly taking even parts and splitting them into two, gives the inverse map. –  Kevin O'Bryant Jan 23 '11 at 12:49

At the risk of plugging one of my own papers, may I recommend

Producing New Bijections from Old by David Feldman and James Propp (published in Advances in Mathematics, volume 113 (1995), pages 1-44)

which you can find here http://jamespropp.org/cancel.ps.gz .

Establishing a definition of bijective proof turns out difficult since it hinges on the distinction between proving the existence of a bijection and using a bijection to establish an equality. One would like to trade in this syntactic problem (distinguishing a class of proofs) for a semantic problem - a mathematical universe where one can distinguish between mere numerical equality and the existence of a bijection.

Topos theory offers one approach. There one can have two sheaves with a bijection between every stalk of one and every stalk of the other, but no global isomorphism of the sheaves. Alternatively, one can have two sets of the same cardinality that carry different actions by the same finite group $G$.

This may all see to be getting away from the real world, but what Jim and I show in the paper is that it all does have bankable implications for relative questions about the existence of bijections. For example, if you have sets $A$ and $B$ and you find a bijection between $A^2$ and $B^2$, our paper gives you an concrete effective way to get a bijection between $A$ and $B$. We also give a group-theoretical criterion that predicts the existence of this effective reduction before you actually have it in your hands.

On the other hand, we show that a bijection between $2^A$ and $2^B$ does not effectively give rise to a bijection between $A$ and $B$. Such a bijection might be too symmetrical, and we actually write down a concrete example to show you how things can go wrong.

Pedagogically speaking, I have often encountered two diametrically opposite and equally difficult lessons. I have encountered many students who don't understand why you don't need the axiom of choice to pick out one element from one non-empty set (with more than one element)...in classical mathematics, say ZF. And I have encountered just as many students who don't understand why you do need the axiom of choice to pick out one element from a two element set...in effective, or intuitionistic mathematics, or in a topos.

-
You need full AC to pick an element out of a two element set? Color me skeptical. Are you sure you don't mean something like the law of excluded middle? Doesn't Diaconescu's theorem prove that the axiom of choice implies the law of excluded middle, so constructive ZF + AC is isomorphic to ZFC? –  Harry Gindi Jan 23 '11 at 8:30
Right Harry, I was being sloppy. I only meant a) you need something and AC will suffice. –  David Feldman Jan 23 '11 at 8:37
But I meant what I said: once an undergraduate understands that AC (over ZF) for a one set family amounts to the tautology "a nonempty set is a nonempty set" and that AC thus does not exactly model naive ideas about choosing, its hard to develop the intuition that in another context it doesn't turn out to be a tautology at all. I suppose some mathematicians see mathematical life beginning inside axiomatic systems and thus they prefer pass over in silence the question of grounding the value of the axiom systems that command the most attention. But some students hunger for meaning. –  David Feldman Jan 23 '11 at 9:20
Regarding your point about $2^A$ and $2^B$ in the penultimate paragraph, it is also known to be consistent with ZFC for infinite sets that $2^A$ and $2^B$ can have the same cardinality, even when $A$ and $B$ do not. For example, it is an easy matter to force $2^{\aleph_0}=\aleph_2=2^{\aleph_1}$, and this is true in Cohen's original $\neg CH$ model. See also mathoverflow.net/questions/1924/… –  Joel David Hamkins Jan 23 '11 at 17:10

Here is an example where the question of whether the two countings are the same is independent of the axioms of set theory.

Namely, if the Continuum Hypothesis holds, then the number of real numbers is the same as the number of countable ordinals. But if CH fails, then it is not.

-

I am not sure I understand the question, but I would like to share the following ingenious observation produced by (elder) László Lovász on live TV in a contest (when he was a high school student).

Question. Take a convex $n$-agon in which the mutual intersections of diagonals are all different. How many intersections are there?

Solution. The intersections are in bijection with the 4-tuples of the vertices: to any pair of intersecting diagonals assign their 4 endpoints. Hence the number in question is $\binom{n}{4}$.

-

You could discuss Beatty sequences. If $r>1$ is an irrational real define $\mathcal{B}_r =\{ \lfloor r \rfloor, \lfloor 2 r \rfloor, \dots\}$ a subset of the positive integers. The complement of $\mathcal{B}_r$ in the positive integers is $\mathcal{B}_s$, where $\frac{1}{r} + \frac{1}{s} = 1$. See, for example, http://en.wikipedia.org/wiki/Beatty_sequence

-

You should look up Catalan numbers in Enumerative Combinatorics by R. P. Stanley.

-

For Question 2, you may want to look at

http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAJ0146

(and the reference given in the abstract).

-