Problems where we can't make a canonical choice, solved by looking at all choices at once - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T04:16:51Z http://mathoverflow.net/feeds/question/50025 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices Problems where we can't make a canonical choice, solved by looking at all choices at once Zev Chonoles 2010-12-21T04:04:38Z 2011-02-17T17:16:47Z <p>It's a common theme in mathematics that, if there's no canonical choice (of basis, for example), then we shouldn't make a choice at all. This helps us focus on the heart of the matter without giving ourselves arbitrary stuff to drag around.</p> <p>However, in this question, I'm looking for examples of problems solved by a specific type of "not making a choice" - namely, making all available choices, and looking at all the end results together as a whole. We can't necessarily discern any individual piece, but the average behavior, or some other information about the big picture, provides (or at least points towards) a solution.</p> <p>I really wish I had an example of this phenomenon to provide, but even one escapes me at the moment, which is what spurred me to ask this question. I imagine combinatorics is full of examples; unfortunately I haven't really studied that field in any depth yet.</p> <p>Something close to what I'm after is <a href="http://en.wikipedia.org/wiki/Burnside%27s_lemma" rel="nofollow">Burnside's (a.k.a. not-Burnside's) Lemma</a>. There's no good way of directly counting orbits, i.e. choosing to look at a particular orbit one at a time, so we just look at the average number of fixed points of elements of $G$ (I'm reluctant to call this an example of the kind of result I'm looking for because I'm not entirely clear on why the fixed points of an element should be thought of as substitutes for orbits. Perhaps that's a separate question).</p> <p><a href="http://mathoverflow.net/questions/21214/particular-problem-solved-by-solving-a-more-general-problem" rel="nofollow">This question</a> is in a similar vein.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50026#50026 Answer by Gerald Edgar for Problems where we can't make a canonical choice, solved by looking at all choices at once Gerald Edgar 2010-12-21T04:19:49Z 2010-12-21T04:19:49Z <p><strong>THEOREM 1.</strong> Let $f \colon \mathbb R \to \mathbb R$ and $a \in \mathbb R$. The following are equivalent (definitions of "$f$ is continuous at $a$"): </p> <ul> <li><p>For every $\epsilon > 0$ there is $\delta > 0$ such that for $x \in \mathbb R$, if $|x-a| &lt; \delta$ then $|f(x) - f(a)| &lt; \epsilon$. </p></li> <li><p>For every sequence $x_n \in \mathbb R$, if $x_n$ converges to $a$, then $f(x_n)$ converges to $f(a)$.</p></li> </ul> <p><em>PROOF</em> of this theorem involves CHOOSING a point in a neighborhood of $a$ (for example the $1/n$-neighborhood) to build a sequence. Of course there is no canonical choice.</p> <p><strong>THEOREM 2.</strong> Let $f \colon \mathbb R \to \mathbb R$ and $a \in \mathbb R$. The following are equivalent (definitions of "$f$ is continuous at $a$"): </p> <ul> <li><p>For every $\epsilon > 0$ there is $\delta > 0$ such that for $x \in \mathbb R$, if $|x-a| &lt; \delta$ then $|f(x) - f(a)| &lt; \epsilon$. </p></li> <li><p>For every net $x_n \in \mathbb R$, if $x_n$ converges to $a$, then $f(x_n)$ converges to $f(a)$.</p></li> </ul> <p><em>PROOF</em> of this can be done by building a net that makes all possible choices of points in all neighborhoods, avoiding the use of the Axiom of Choice.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50027#50027 Answer by Alex R. for Problems where we can't make a canonical choice, solved by looking at all choices at once Alex R. 2010-12-21T04:34:42Z 2010-12-23T15:22:32Z <p>It sounds like the probabilistic method fits your description. The following is an old Putnam problem (which has a detailed solution in the book, "The Probabilistic Method" by Alon and Spencer). Consider the following problem:</p> <p>You have an $n\times n$ matrix of lights, with a given initial configuration of some lights being on, and others being off. Now, each row and column has a switch which switches the lights from on to off (off to on) in that particular row or column (respectively). The question is: by pressing the switches in some fashion, how big can the number of lights on minus the number of lights off be? Indeed, one can show that REGARDLESS of the initial configuration, you can guarantee at least $(\sqrt{2/\pi}+o(1))n^{3/2}$ lights on minus lights off. </p> <p>The proof seems daunting at first, especially if one gets bogged down in the myriad of various initial configurations. The key idea is to go to each column switch, flip a coin and if it comes up heads you press the column switch. By the magic of probability, you can work out that now each row is UNIFORMLY distributed. Apply the Central Limit Theorem, and you're pretty much done (see the above reference for the gory details). </p> <p>The moral here is clear: look at all initial configurations at the same time!</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50029#50029 Answer by Steven Landsburg for Problems where we can't make a canonical choice, solved by looking at all choices at once Steven Landsburg 2010-12-21T04:43:57Z 2010-12-21T04:43:57Z <p>This is a standard example of what I think you're asking for:</p> <p>For any graph, there exists a 2-coloring for which at least half the edges have vertices of both colors.</p> <p>The problem here is to choose the right coloring. The way to prove it exists, is to consider <i>all</i> colorings. Pick an edge E. Then there's a bijection between colorings in which the vertices of E are colored the same and colorings in which they're colored differently. (Define the bijection by changing the color of one vertex.) This is true for each edge separately. Therefore, in the average covering, half of all edges are bi-colored. Therefore, in at least one covering, half of all edges are bi-colored.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50031#50031 Answer by Marty for Problems where we can't make a canonical choice, solved by looking at all choices at once Marty 2010-12-21T05:02:56Z 2011-02-17T17:16:47Z <p>A great example is found in the famous 1976 Annals (Vol. 103, No. 1) paper of Deligne-Lusztig, "Representations of Reductive Groups over Finite Fields".</p> <p>This paper begins (in Section 1) with the following:</p> <p>Suppose that in some category we are given a family $(X_i)$ ($i \in I$) of objects and a compatible system of isomorphisms $\phi_{ji}: X_i \rightarrow X_j$. This is as good as giving a single object $X$, the 'common value' or 'projective limit' of the family. This projective limit is provided with isomorphisms $\sigma: X \rightarrow X_i$ such that $\phi_{ji} \sigma_i = \sigma_j$.</p> <p>Where this is applied by Deligne-Lusztig, and how it relates to the question, is the following: In a connected reductive algebraic group $G$ over a field $k$, there is no canonical choice of maximal torus $T$. (A maximal torus in $GL_n$ corresponds to a choice of basis vectors up to scaling, so this is <em>very</em> similar to the original question). So Deligne-Lusztig consider the indexing set $I$ consisting of all pairs $(T,B)$ where $T$ is a maximal torus in $G$ and $B$ is a Borel subgroup containing $T$. For each $i = (T,B) \in I$, let $T_i = T$&mdash;the first entry in the ordered pair. For each pair $i,j \in I$, there is a unique isomorphism from $T_i$ to $T_j$ given by $\operatorname{Int}(g_{ij})$ (conjugation by $g_{ij}$) for some $g_{ij}$ satisfying $g_{ij} B_i g_{ij}^{-1} = B_j$. (Note that $g_{ij}$ and $\operatorname{Int}(g_{ij})$ are not unique, but the induced isomorphism from $T_i$ to $T_j$ is uniquely determined since $N_G(T) \cap B = T$ when $T \subset B$)</p> <p>This indexing set $I$ makes all possible choices and the extra data of the Borel subgroup allows for the definition of "THE" maximal torus $T$, the projective limit of the system $(T_i)$.</p> <p>I think this provides a good example to answer the original question. It also demonstrates how it is possible to make choices with extra data (in this case Borel subgroups in addition to tori), to "rigidify" and eventually define a universal choice. </p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50032#50032 Answer by Qiaochu Yuan for Problems where we can't make a canonical choice, solved by looking at all choices at once Qiaochu Yuan 2010-12-21T05:31:05Z 2010-12-21T05:31:05Z <p>Here's a basic but important example. In the modern approach to things like algebra we study objects like groups and rings in two stages: first we study their abstract structure, then we study their representations. Generally there is no way to pick a "canonical" representation. So instead we study all of them: the entire category of representations. And that gives us a lot of extra structure to work with and allows us to solve many, many problems.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50038#50038 Answer by Terry Tao for Problems where we can't make a canonical choice, solved by looking at all choices at once Terry Tao 2010-12-21T06:49:43Z 2010-12-21T06:49:43Z <p>Zagier's one-sentence proof of Fermat's two square theorem (discussed previously on MathOverflow <a href="http://mathoverflow.net/questions/31113/zagiers-one-sentence-proof-of-fermats-theorem" rel="nofollow">here</a>) seems to qualify.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50046#50046 Answer by Andrei Moroianu for Problems where we can't make a canonical choice, solved by looking at all choices at once Andrei Moroianu 2010-12-21T09:59:39Z 2010-12-21T09:59:39Z <blockquote> <p>A typical example: the set of Weyl structures in conformal geometry.</p> </blockquote> <p><strong>Background:</strong> In contrast to Riemannian manifolds which carry a unique torsion-free metric connection, a conformal manifold has many torsion-free connections preserving the conformal structure (they are in 1-1 correspondence with connections on the weight bundle, and thus form an affine space directed by the space of 1-forms). Any such connection is called a Weyl structure.</p> <p><strong>Application:</strong> Using Weyl structures one might define so-called <em>Gauduchon gauge</em> on conformal Hermitian manifolds. This is the unique metric $g$ in the conformal class whose Lee form is $g$-co-closed. Gauduchon gauges have important applications in geometry (e.g. Kobayashi-Hitchin correspondence, see <a href="http://www.cmi.univ-mrs.fr/~teleman/documents/universal-05.pdf" rel="nofollow">http://www.cmi.univ-mrs.fr/~teleman/documents/universal-05.pdf</a>).</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50053#50053 Answer by Keivan Karai for Problems where we can't make a canonical choice, solved by looking at all choices at once Keivan Karai 2010-12-21T11:23:49Z 2010-12-21T11:23:49Z <p>In defining the tangent space of a smooth manifold at a point $p$, one can consider a local coordinate $\phi: U \to \phi(U)$ with $p \in U$ and define the tangent space as the tangent space to $\phi(p)$ in $\phi(U)$ which is an open subset of ${\mathbb R}^n$. However this definition would depend on the choice of $\phi$, which is undesirable. Now, the idea is to use the natural isomorphisms between tangent spaces thus defined (the derivatives of the change of coordinate maps) to identify these spaces. </p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50055#50055 Answer by Dmitri Pavlov for Problems where we can't make a canonical choice, solved by looking at all choices at once Dmitri Pavlov 2010-12-21T11:40:22Z 2010-12-21T11:40:22Z <p>Here is an elementary example from measure theory.</p> <p>Usually L<sub>p</sub>-spaces of a <a href="http://mathoverflow.net/questions/20740/is-there-an-introduction-to-probability-theory-from-a-structuralist-categorical-p/20820#20820" rel="nofollow">measurable space</a> Z are defined with respect to some faithful measure μ on Z. More precisely, if p is a complex number with a nonnegative real part, then by definition L<sub>p</sub>(Z,μ) consists of all functions f on Z such that μ(|f|<sup>1/ℜp</sup>) is finite if ℜp>0. If ℜp=0, then L<sub>p</sub>(Z,μ) consists of all bounded functions on Z. (Here I use the algebraic convention for L<sub>p</sub>-spaces, namely L<sub>p</sub>=L<sup>1/p</sup>, in particular L<sub>0</sub>=L<sup>∞</sup>.)</p> <p>Even though p is assumed to be complex, L<sub>p</sub>(Z,μ) only depends on the real part of p. This will be fixed later.</p> <p>It turns out that all spaces L<sub>p</sub>(Z,μ) for different choices of a faithful measure μ are canonically isomorphic to each other. Suppose μ and ν are two faithful measures on Z and (Dμ:Dν) is the Radon-Nikodym derivative of μ with respect to ν, i.e., μ=(Dμ:Dν)ν. Then the map f∈L<sub>p</sub>(Z,μ)⁠↦f(Dμ:Dν)<sup>p</sup>∈L<sub>p</sub>(Z,ν) is an isomorphism. Observe that these isomorphisms are compatible with each other (i.e., passing from λ to μ and then from μ to ν is the same as passing from λ to ν and passing from μ to itself is identity). Hence we have a compatible system of isomorphisms as described in Marty's answer, therefore we can denote its limit (or colimit) by L<sub>p</sub>(Z). Thus we no longer need to choose a measure to define L<sub>p</sub>-spaces.</p> <p>Individual spaces L<sub>p</sub>(Z,μ) depend only on the real part of p, but the isomorphisms between them also depend on the imaginary part of p. Therefore, if p−q is real, then L<sub>p</sub>(Z) is isomorphic to L<sub>q</sub>(Z) <em>non-canonically</em>. There is no canonical isomorphism because such a canonical isomorphism would give us a canonical measure on Z.</p> <p>Thus we got rid of the dependence on the choice of a measure and obtained a meaningful definition of L<sub>p</sub>-space for compex values of p.</p> <p>The spaces L<sub>0</sub>(Z) and L<sub>1</sub>(Z) can be defined canonically without this procedure: L<sub>0</sub>(Z) is the space of all bounded functions on Z and L<sub>1</sub>(Z) is the space of all finite complex-valued measures on Z. However, all constructions of L<sub>p</sub>(Z) for p∉⁠{0,1} known to me involve some kind of limit/colimit over all measures.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50057#50057 Answer by Guillaume Brunerie for Problems where we can't make a canonical choice, solved by looking at all choices at once Guillaume Brunerie 2010-12-21T11:54:32Z 2010-12-21T11:54:32Z <p>I don’t know if this is what you are looking for, but in linear algebra, if you have a finite dimensional vector space $V$ and $f\in\mathrm{End}(V)$, then in order to define the trace of $f$, you choose a basis $(e_1,\dots,e_n)$ of $V$ and define $\mathrm{Tr}(f)=\mathrm{Tr}(M_{(e_1,\dots,e_n)}(f))$</p> <p>You have to make a choice but this definition does not depend on the basis.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50059#50059 Answer by Greg Graviton for Problems where we can't make a canonical choice, solved by looking at all choices at once Greg Graviton 2010-12-21T12:15:58Z 2010-12-21T12:15:58Z <p>I would like to mention <a href="http://www.ams.org/mathscinet/search/publications.html?pg1=MR&amp;s1=MR990772" rel="nofollow">Witten's idea</a> (marvelously explained by <a href="http://arxiv.org/abs/0808.2507v2" rel="nofollow">Freed</a>) of obtaining topological invariants of manifolds by "simply" integrating the Chern-Simons form over <em>all</em> possible connections. It doesn't solve a particular problem in the sense that it's a key step in some proof, but it does give rise to new mathematics.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50060#50060 Answer by Allen Knutson for Problems where we can't make a canonical choice, solved by looking at all choices at once Allen Knutson 2010-12-21T12:36:33Z 2010-12-21T12:36:33Z <p>Quantum computation algorithms, e.g. <a href="http://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow">Shor's algorithm</a>, are to some extent necessarily of this form -- trying out all possibilities, and integrating over them.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50061#50061 Answer by Johannes Hahn for Problems where we can't make a canonical choice, solved by looking at all choices at once Johannes Hahn 2010-12-21T13:19:59Z 2010-12-21T13:19:59Z <p>Another classical example of "looking at all choices instead of one" is the idea of the fundamental groupoid of a topological space. Instead of choosing one base point and letting all loops begin and end in this point one considers all paths between all points (modulo homotpy). This notion makes theorems like the Seifert-Van-Kampen-theorem much more natural. One does no longer have to add technical conditions that certain intersections contain the base point and are path connected.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50062#50062 Answer by David Corfield for Problems where we can't make a canonical choice, solved by looking at all choices at once David Corfield 2010-12-21T13:37:18Z 2010-12-21T13:37:18Z <p>You could say that treating all models of a first-order theory is a way of avoiding the arbitrary selection of a particular completion of that theory. There are other situations where it may be best to treat all completions - <a href="http://ncatlab.org/nlab/show/completion#nonunique" rel="nofollow">http://ncatlab.org/nlab/show/completion#nonunique</a>.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50066#50066 Answer by Keerthi Madapusi Pera for Problems where we can't make a canonical choice, solved by looking at all choices at once Keerthi Madapusi Pera 2010-12-21T15:01:30Z 2010-12-21T16:51:36Z <p>This is not exactly what you wanted, but in algebraic geometry it is often easier to prove something for a particular object by considering the moduli space parametrizing such objects. The example I have in mind is the following: Suppose you picked some random elliptic curve over $\mathbb{Q}$ and were wondering if it has a rational point of order $11$. It is possible to answer this for any particular curve with some computational facility, but we don't have to. We have <a href="http://planetmath.org/encyclopedia/MazursTheoremOnTorsionOfEllipticCurves.html" rel="nofollow">Mazur's Theorem</a>, which says that the answer is `no, it doesn't.' Mazur does this essentially by showing that the corresponding moduli space of elliptic curves with a choice of $11$-torsion point (which is a nice <a href="http://en.wikipedia.org/wiki/Modular_curve" rel="nofollow">modular curve</a>) has no rational points: so you can never have an elliptic curve over $\mathbb{Q}$ with an $11$-torsion point.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50067#50067 Answer by gowers for Problems where we can't make a canonical choice, solved by looking at all choices at once gowers 2010-12-21T15:20:44Z 2010-12-21T15:20:44Z <p>I don't know whether you would count this, but the proof of the existence of quotient groups seems to fit your description. Some people define the product of the cosets $gH$ and $g'H$ to be the coset $gg'H$, and then go on to prove that this is well-defined. Another approach is to define two elements $g$ and $h$ of $G$ to be equivalent if $gh^{-1}\in H$, to define cosets to be equivalence classes, and to define the product of two cosets to be ... their product. That is, if $A$ and $B$ are cosets then their product is $AB=\{ab:a\in A, b\in B\}$. Of course, we have to prove that that is a coset. But if $ac^{-1}\in H$ and $bd^{-1}\in H$, then $cbd^{-1}c^{-1}\in H$ so $ab(cd)^{-1}\in H$. Thus, if $a\sim c$ and $b\sim d$, then $ab\sim cd$.</p> <p>I can't quite decide whether this is a real example. I did have to take elements, but I wasn't exactly choosing them so much as proving something about all of them. The point of the example is that the product of cosets is defined by multiplying everything by everything -- that is the sense in which it does what the OP asks for.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50068#50068 Answer by gowers for Problems where we can't make a canonical choice, solved by looking at all choices at once gowers 2010-12-21T15:34:30Z 2010-12-21T15:34:30Z <p>Another thought is the path-integral formulation of quantum mechanics, where one integrates over all possible histories of a system, with appropriate weights.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50093#50093 Answer by James Borger for Problems where we can't make a canonical choice, solved by looking at all choices at once James Borger 2010-12-21T20:12:52Z 2010-12-21T20:12:52Z <p>In crystalline cohomology, you want to lift your variety in prime characteristic $p$ to a $p$-adic variety and then take its de Rham cohomology. But there's no natural lift. If you're Dwork, you just pick a lift and compute. But if you're Grothendieck, you look at the category of all lifts, and then things work by magic. </p> <p>In fact, here the failure of uniqueness is more extreme, because you might not even have existence. In other words, your variety might not lift at all. But it does always lift locally, so you need to do everything for all sufficiently small open subvarieties. This is a common theme in geometry, where the failure of a local construction to be unique can prevent the global construction from existing at all.</p> <p>I mentioned this example before <a href="http://mathoverflow.net/questions/8874/what-are-some-slogans-that-express-mathematical-tricks/40015#40015" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50094#50094 Answer by Noah Stein for Problems where we can't make a canonical choice, solved by looking at all choices at once Noah Stein 2010-12-21T20:58:58Z 2010-12-21T20:58:58Z <p>This is more properly a comment on gowers' quotient group example, but a little long for that.</p> <p>For me the canonical example of not making a choice by making all the choices is the quotient of a finite-dimensional vector space $V$ by a subspace $X$. Naively (imagine back to taking linear algebra for the first time) we might want this to again be a subspace of $V$. This is especially tempting when one has not yet been broken of the habit of thinking immediately of $V = \mathbb{R}^n$ with its extra inner product structure. With an inner product in the picture, the orthogonal complement of $X$ is a perfectly reasonable and natural quotient object.</p> <p>Ignoring this extra structure, any complement $Y$ (subspace such that $X+Y=V$, $X\cap Y = 0$) can play the role of the quotient $V/X$. Such a complement comes equipped with a natural map $V\to Y$ obeying the universal mapping property. So existence is not a problem for this "definition" of quotient like it would be with groups. Every quotient map of finite dimensional vector spaces splits.</p> <p>But without some extra structure lying around like an inner product on $V$, we have no natural way of choosing such a $Y$. So we instead define $V/X$ to be a set of cosets, each of which (except zero) contains one point of each possible $Y$. The resulting object is no longer a subspace of $V$, but it has the advantage of avoiding making the choices by making all the possible choices. This naturality makes the "real" definition extend to infinite dimensions, for example, without using choice.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50095#50095 Answer by Richard Stanley for Problems where we can't make a canonical choice, solved by looking at all choices at once Richard Stanley 2010-12-21T21:19:04Z 2010-12-21T21:19:04Z <p>Let $G$ be a finite bipartite graph with vertex bipartition $(V,W)$. Suppose we want to find a matching $f\colon V\to W$, i.e., an injective function such that for all $v\in V$, the vertices $v$ and $f(v)$ are adjacent. We may not be sure what to choose for $f(v)$, so we choose all possible vertices at once as follows. Let $K$ be a field and $KS$ the vector space with basis $S$. Define a linear transformation $\varphi\colon KV\to KW$ by letting $\varphi(v)$ be the sum of <em>all</em> vertices in $W$ adjacent to $v$ (or more generally, some linear combination of such vertices). It is easy to show that if $\varphi$ is injective, then a matching $f\colon V\to W$ exists. We can think of an injective $\varphi$ as a "quantum matching" (since it is in all possible "states" $f(v)$ at once). Choosing a nonzero term in a certain determinant "collapses" the wave function $\varphi$ to the matching $f$. For further details and some nice applications, see Sections 4-6 of <a href="http://math.mit.edu/~rstan/algcomb.pdf" rel="nofollow">http://math.mit.edu/~rstan/algcomb.pdf</a>.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50099#50099 Answer by David Roberts for Problems where we can't make a canonical choice, solved by looking at all choices at once David Roberts 2010-12-21T22:22:16Z 2010-12-21T22:22:16Z <p>This may be a little tangential to the original question, but it avoids Choice, and 'works with all choices at once'. In Makkai's theory of <a href="http://ncatlab.org/nlab/show/anafunctor" rel="nofollow">anafunctors</a>, one recognizes that 'the' functor $C^J \to C$ giving a limit of a (small) diagram $J \to C$ is only really defined via universal properties, and so requires Choice. However, there is a unique anafunctor $C^J$ &#x21F8; $C$ - which is a span $C^J \leftarrow D \to C$ where the left-pointing leg is fully faithful and surjective on objects - expressing the limit. The category $D$ is defined to consist of limit cones and maps between them. The functor to $C^J$ forgets the vertex of the cone, and the functor to $C$ forgets the diagram and keeps the vertex. The universal properties take care of functoriality, and if one can choose a limit for each diagram, or there are canonical constructions of limits, then this can be converted into an ordinary functor. The cost of working with anafunctors rather than functors is that one gets a bona fide bicategory of categories, rather than a 2-category, but otherwise the whole theory of categories goes through.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50104#50104 Answer by Vamsi for Problems where we can't make a canonical choice, solved by looking at all choices at once Vamsi 2010-12-21T23:07:43Z 2010-12-21T23:07:43Z <p>Sard's theorem provides such an example. Given a random smooth map between two manifolds (lets say compact and of the same dimension), there is no canonical way of constructing a regular value. But, Sard's theorem looks at this entire set and proves it is of full measure (and hence there exists atleast one regular value). This result enables us to prove many such results like (the transversality theorem for instance).</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50247#50247 Answer by Stanley Yao Xiao for Problems where we can't make a canonical choice, solved by looking at all choices at once Stanley Yao Xiao 2010-12-23T17:09:33Z 2010-12-23T17:09:33Z <p>I like Donald Newman's proof of the non-vanishing of Dirichlet series on the real line $\mathfrak{R}(s) = 1$, where for a given modulus $m$ one should not consider each series $\displaystyle \sum_{n=1}^\infty \frac{\chi(n)}{n^s} = \prod_p \left(\frac{1}{1 - \chi(p) p^{-s}} \right)$ separately, but instead consider the product $\displaystyle Z(s) = \prod_\chi \prod_{p} \left(\frac{1}{1 - \chi(p)p^{-s}} \right)$. Then the non-vanishing of the $L$-series follows almost immediately by first supposing the existence of a zero on the line $\mathfrak{R}(s) = 1$, say $1 + i\sigma$, then considering the product $Z(s)^2 Z(1 + i \sigma)Z(1 - i \sigma)$. This product is entire (by hypothesis) and its series has positive coefficients. This implies that the series in fact converges everywhere, which is plainly absurd. </p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/50310#50310 Answer by darij grinberg for Problems where we can't make a canonical choice, solved by looking at all choices at once darij grinberg 2010-12-24T22:15:14Z 2010-12-24T22:15:14Z <p>There is an example which seriously stunned me two years ago when I first learned about Hopf algebras. In hindsight it is not that much surprising...</p> <p>Hopf algebras are usually sold as generalizations of groups. Now, in a group, the notion of "inverse" is something that has to do with one element only: If $g$ is an element of a group $G$, then the inverse of $g$ is defined to be a $g^{-1}\in G$ satisfying $gg^{-1}=g^{-1}g=e$. In contrast, in a Hopf algebra, it is hard to tell whether one given element equals the antipode of another one just by looking at these elements: The axiom for the antipode is </p> <p>$S\left(x_{(1)}\right)x_{(2)}=x_{(1)}S\left(x_{(2)}\right)=\varepsilon\left(x\right)$ for all $x$,</p> <p>and checking this can only be done by checking it for all $x$ simultaneously. When I was a beginner with Hopf algebra, this fact foiled all my attempts at proving elementary properties of the antipode (such that: it is unique, it is an anti algebra homomorphism, any finite-dimensional sub-bialgebra of a Hopf algebra has an antipode, etc.), until I started considering the elements of a Hopf algebra as one big hive rather than a collection of detached things.</p> http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices/55748#55748 Answer by godelian for Problems where we can't make a canonical choice, solved by looking at all choices at once godelian 2011-02-17T16:06:44Z 2011-02-17T16:25:07Z <p>The point of view of making all choices at once instead of canonical choices is part of Grothendieck's philosophy. In SGA1, VI, 12, after considering the notions of fibered categories and cleavages, we can see the following remark at the end:</p> <p>"[...] Il est d’ailleurs probable que, contrairement à l’usage encore prépondérant maintenant, lié à d’anciennes habitudes de pensée, il finira par s’avérer plus commode dans les problèmes universels, de ne pas mettre l’accent sur une solution supposée choisie une fois pour toutes, mais de mettre toutes les solutions sur un pied d’égalité."</p> <p>which essentially qualifies the "canonical choice" approach as an old form of thinking, stressing the preference for the "making all choices at once" point of view. This is particularly well illustrated in the case of the concept of cleavages of Grothendieck fibrations. One of the first examples of fibered categories (probably the one upon which Grothendieck was thinking when coming up with this concept) is the one associated to the slice categories with pullback functors between them. Since generally there's no canonical choice of pullbacks, the existence of pullback functors usually appeals to the axiom of choice. This amounts to specifying a cleavage in the fibration considered, but Grothendieck wanted to avoid, when possible, working with cleavages. </p> <p>A case where the above is relevant is the following. In 1978 Joyal gave a series of lectures in Montréal exposing a categorical proof of the completeness theorem for many kinds of logic (including classical logic). It was essential for Joyal's proof, in the case of non classical logics, not to rely on the axiom of choice, and hence Grothendieck fibrations without cleavages was the solution for making his proof constructive. This has though the disadvantage of making the proof less intuitive, and in general related expositions (as can be seen for example at Johnstone's "Sketches of an Elephant", D1.5) prefer to use the "canonical choice" approach that is a bit less obscure. </p>