1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ @MauroALLEGRANZA But we do not have that from 1. $\endgroup$
    – fantasie
    Feb 21, 2022 at 13:46
  • 1
    $\begingroup$ @MauroALLEGRANZA But the OP does not assume they have a derivation of $\Psi$ from $\Gamma$. $\endgroup$ Feb 21, 2022 at 13:59
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 21, 2022 at 14:02
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 22, 2022 at 15:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – fantasie
    Feb 26, 2022 at 15:42

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .