Counterexample: $\Gamma \vdash \phi$ implies $\Gamma\vdash\psi$, but not $\Gamma\vdash \phi\to\psi$

logic

Let $\Gamma$ be a collection of formula and $\phi,\psi$ be two formulas. Consider two statements:

  1. $\Gamma \vdash \phi\Rightarrow\Gamma\vdash\psi$
  2. $\Gamma\vdash \phi\to\psi$

2->1 is fairly easy, one step of modus ponens would suffice. But I cannot prove the inverse direction. I doubt that it is not even true, for there is no new information in 1. to start a derivation, and 2. is not tautology; nor does soundness theorem and completeness theorem seem to work.

What I tried to construct a counterexample: I tried to let $\Gamma$ be a familiar set of formulas, such as axioms of group theory or PA. But what is true in group theory is usually also a consequence of these axioms, so I doubt more subtle construction is needed.

Is 1->2 true? If not, what is a counterexample?

(This is asked by a friend of mine who is a graduate student in mathematics and have knowledge of some mathematical logic and set theory.)

Best Answer

Let $\Gamma$ consist of the axioms of group theory, and take the sentence $\forall x. \forall y. xy=yx$ as your $\varphi$.

Then $\Gamma \vdash (\forall x. \forall y. xy=yx)$ fails since not-Abelian groups exist. Since the antecedent is false, the implication $\Gamma \vdash (\forall x. \forall y. xy=yx) \:\:\Rightarrow\:\: \Gamma \vdash (\forall a.\forall b. a=b)$ is vacuously true.

However, $\Gamma \vdash (\forall x. \forall y. xy=yx) \rightarrow (\forall a. \forall b. a=b)$ does not hold, since Abelian groups with more than one element do exist.

Related Question