Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
@JohnBaez: This discussion reminds me of a quotation of I. Kaplansky, speaking of himself and P. Halmos: "We share a philosophy about linear algebra: we think basis-free, we write basis-free, but when the chips are down we close the office door and compute with matrices like fury."
@JohnBaez: But even if one is okay using groupoids directly, there are lots of situations where it's useful to know what the Weyl group actually is ($S_n$, hyperoctahedral, Coxeter presentations, etc.), and as you say, for that it seems one still needs to pick a maximal torus (or, as in Jim Humphreys's comments, use a lot of theory including conjugacy of tori). I wonder how far into e.g. the representation theory of semisimple complex Lie groups one can get using the Weyl groupoid without ever determining the Weyl group, or at least the connectedness of the groupoid?
When considering actions of a monoid/semigroup on a set, I understand the desire for using partial maps, but when considering linear actions on a vector space, any partial linear map can be extended by 0 to a non-partial linear map. E.g. in the case of quivers, this extension by 0 preserves all of the compositions, etc. For linear actions, is there a potentially useful or interesting way in which the viewpoint of partial maps make you think about it differently?
Of possible interest: maximizing the number of matched edges over choice of maps $A \to B$ (an approximate version of graph isomorphism) can be approximated to within some constant factor in $n^{O(\log n)}$ time, but approximating it to within a factor better than 0.94 is NP-hard: link.springer.com/chapter/10.1007%2F978-3-642-32589-2_12 and eccc.hpi-web.de/report/2012/078/download.
I think the reason I'd consider diagonalization nontrivial is that essentially the same proof shows that the Halting problem is undecidable, yet this is a proof that undergrads often struggle with until they've seen it ~half a dozen times. (The first five times or so it never seems to stick...) But perhaps its use there is/feels more subtle, since you've got Turing machines eating Turing machines, which is a little more meta than lists of digits...
This would be far better suited for MathOverflow. (Sorry for the duplicate comment - it forces me to add a comment when voting to close, which I did because this question should really be migrated to MO.)
@FrançoisG.Dorais: He said the same thing in a class I took from him as an undergrad. I mostly agree with that statement most of the time :). How was it related to my previous comment though?
Although formally true, I wouldn't say your last paragraph indicates a lack of applications of Turing degree, but should be taken more positively as a whole range of applications of a slight variant of the notion, namely of Turing p-degrees (i.e. degree under polynomial-time reducibility).
Ah, I see. I wonder if there is some less refined data that one could get - analogous to the Hilbert polynomial of an invariant ring - that would suggest just how much more complicated such descriptions must grow with $n$... Thanks again!
On looking into it further, I think this is a great example of a description that's uniform in $p$, precisely because it depends on the mod p geometry of a single elliptic curve over $\mathbb{Z}$. This is the kind of behavior I meant to hint at with example (2), but I edited the question with this new example to help clarify.
