1

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.)

fantasie
  • 1,781
  • @MauroALLEGRANZA But we do not have that from 1. – fantasie Feb 21 '22 at 13:46
  • @MauroALLEGRANZA 1. is a sentence of the form “if p then q”, which does not in general imply p. – fantasie Feb 21 '22 at 13:47
  • 1
    @MauroALLEGRANZA But the OP does not assume they have a derivation of $\Psi$ from $\Gamma$. – Alex Kruckman Feb 21 '22 at 13:59
  • 1
    Unless I miss something @MauroALLEGRANZA this is false, examples are easy to construct, just let them both be proportional symbols or something like that, and let Gamma be the set of tautologies. – Vivaan Daga Feb 21 '22 at 14:02
  • I see. The point is to let $\phi$ and $\psi$ be something $\Gamma$ cannot prove. I was thinking in the wrong direction. – fantasie Feb 21 '22 at 15:12
  • 1
    It may be worth noting that if $\Gamma$ is a complete theory, then 1. and 2. are equivalent. Assume 1. We have $\Gamma\vdash \phi$ or $\Gamma\vdash \lnot \phi$. In the first case, by 1. $\Gamma\vdash \psi$, so $\Gamma\vdash \phi\to\psi$. In the second case, since $\Gamma\vdash \lnot \phi$, we have $\Gamma\vdash \phi\to \psi$. – Alex Kruckman Feb 22 '22 at 15:04
  • Similarly, "$\Gamma\vdash \phi$ or $\Gamma\vdash \psi$" implies "$\Gamma\vdash \phi \lor \psi$". The converse is not true in general, but it is true if $\Gamma$ is a complete theory. – Alex Kruckman Feb 22 '22 at 15:06
  • 1
    Here is a propositional logic analogy of this question, which includes the solution mentioned by above comments. The answer by Z. A. K., however, provides an excellent first order logic example. – fantasie Feb 26 '22 at 15:42

1 Answers1

6

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.

Z. A. K.
  • 11,359