Timeline for What is an explicit bijection in combinatorics?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 22, 2019 at 22:41 | comment | added | Andrej Bauer | I always imagined that an explicit bijection would have an explicit inverse, but maybe I am wrong. | |
| Feb 22, 2019 at 19:16 | comment | added | Najib Idrissi | @AndrejBauer So you don't just want an "explicit bijection", you actually want an "explicit bijection with explicit inverse"? | |
| Feb 22, 2019 at 18:33 | comment | added | Andrej Bauer | @NajibIdrissi: Since we're discussing (finite) combinatorics, I suppose we ought to take a vector space over a finite field. If you can write down an explicit inverse, then we need not know ahead of time that $v \mapsto (\phi \mapsto \phi(v))$. I suspect this is going to revolve around a choice of base, isn't it? | |
| Feb 22, 2019 at 13:41 | comment | added | Najib Idrissi | So for example, the map $V \to V^{**}$, $v \mapsto (\phi \mapsto \phi(v))$, is not explicit? (It goes without saying, I'm not a logician or a combinatorist, so maybe I'm being hare-brained.) | |
| Feb 22, 2019 at 7:28 | comment | added | gowers | Indeed -- that is the difficulty I alluded to in my final sentence. | |
| Feb 22, 2019 at 7:13 | comment | added | Andrej Bauer | Yes, this is definitely an important aspect of the question. But note that we already have trouble formally expressing "one shouldn't need to know in advance that there exists a bijection". Given a proof, what does it mean that the proof "first proves existence"? | |
| Feb 21, 2019 at 22:50 | history | edited | gowers | CC BY-SA 4.0 |
added 30 characters in body
|
| Feb 21, 2019 at 22:49 | comment | added | gowers | Ah, I didn't express my criterion clearly. I'll edit it now. | |
| Feb 21, 2019 at 22:34 | comment | added | darij grinberg | I don't, but I know it exists :) | |
| Feb 21, 2019 at 22:32 | comment | added | gowers | I'm not sure I follow the first part of your comment: how do we know that the map you define is a bijection? | |
| Feb 21, 2019 at 22:25 | comment | added | darij grinberg | Hmm, what about "map the $k$-th smallest element of $A$ to the $k$-th smallest element of $B$ or to the largest one if there is no $k$-th smallest one"? I am being somewhat tongue-in-cheek here, as we are clearly looking for a rule to follow in spirit rather than in letter. On the other hand, if we take this idea too far in the other direction, then a bijection $f : A \to B$ whose bijectivity is only proven using the pigeonhole principle (i.e., by showing that it is injective or surjective, and that $\left|A\right| = \left|B\right|$) should not count as explicit either. (Perhaps rightfully!) | |
| Feb 21, 2019 at 22:18 | history | answered | gowers | CC BY-SA 4.0 |