Skip to main content
MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

6
  • $\begingroup$ The pointer to natural deduction and $\exists$ elimination might be the kind of thing I was looking for. I'll follow up on this. $\endgroup$ Commented Jul 12, 2016 at 15:12
  • 2
    $\begingroup$ $\lor$ elimination also involves a choice. Harrop formulas are those which exclude both $\lor$ and $\exists$. Sometimes it's useful to allow $\lor$ and $\exists$ but only in the negative part (i.e., in hypotheses, but not in the conclusion). The cool thing is that the meaning of such formula is the same in classical logic as it is in intuitionistic logic. wikiwand.com/en/Harrop_formula $\endgroup$ Commented Jul 12, 2016 at 18:03
  • $\begingroup$ It's perhaps useful to add that the independence of the choice is built-in to the $\exists$-elimination rule. That rule says that in order to prove that $\exists x P(x) \to Q$ it suffices to show that $\forall x (P(x) \to Q)$. Since $x$ doesn't appear in the conclusion $Q$, its exactly the same conclusion $Q$ that holds regardless of the choice of $x$. There is a twist, where the conclusion might itself be existential. In that case, the witness for this existential quantifier produced might depend on $x$ but the existential quantifier washes away the distinction between different witnesses. $\endgroup$ Commented Jul 12, 2016 at 21:28
  • $\begingroup$ (continued) In this case, the hypothesis "$V$ is finite dimensional" is existential: "there is a finite basis for $V$". The conclusion is also existential: "there is an inverse to the natural map $V \otimes V^\ast \to \operatorname{Hom}(V,V)$". However, there is at most one inverse to this map, so the same witness is necessarily produced. $\endgroup$ Commented Jul 12, 2016 at 21:32
  • $\begingroup$ (addendum) I just read KConrad's comment on quotient groups and I think it illustrates part of the point. Consider instead the statement "there is a right inverse to the natural map $F(V \times V^\ast) \to \operatorname{Hom}(V,V)$, where $F(V \times V^\ast)$ is the free vector space on $V \times V^\ast$". Then different choices of bases will yield different right inverses. This illustrates the combined $\exists$-elim/intro rule: to prove $\exists x P(x) \to \exists y Q(y)$ it suffices to give construction $f$ such that $\forall x(P(x) \to Q(f(x)))$. $\endgroup$ Commented Jul 12, 2016 at 21:49