Modus ponens as a rule of inference vs. tautology

axiomslogicproof-explanationpropositional-calculus

When I look up the mechanics of a propositional logic system here we have a collection of both rules of inference ($a \vdash b$) and axioms ($\vdash b$), if I understand right.

One such rule of inference is modus ponens, $p, (p\to q) \vdash q$ which on a metalogical level is "from $p$ and $p\to q$, infer $q$".

However I have also seen people "prove" it using truth tables or treating it as a tautology by stating it as $(p \land (p\to q)) \to q$.

Why do I see it stated these two ways if the latter is not technically modus ponens? Is it totally and utterly wrong to even ask the question how to "prove modus ponens" because it's considered a rule of inference, i.e. it has no proof since it's a metalogical assumption? Why do I sometimes see it stated the second way, if so, and how do we know that's the correct interpretation as a tautological claim?

I know informally it makes sense as "if $a$ then $b$" or "whenever $a$ is true, $b$ is true" but the whole $\vdash$ concept seems to be a little different from $\to$ (especially since $\vdash$ is metalogical) and so I'm trying to understand what's going on here.

Best Answer

As I stated in my previous answer, the rule modus ponens is part of the definition of many common proof systems. Let HPC stand for Hilbert's system for classical propositional logic whose only rule of inference is modus ponens and whose axioms are listed here after Frege's. This is a well-defined mathematical object. It is one proof system for classical propositional logic. Literally over a dozen others are mentioned on that page, and those are restricted to Hilbert-style proof systems. There are also many others in the style of natural deduction or the sequent calculus.

In HPC a (formal) proof is either an instance of one of the axioms, or it is a use of the rule modus ponens which combines two other proofs. This produces a binary-tree-like structure whose leaves are instances of axioms. This is the definition of a proof in HPC. A formula of classical propositional logic is proven by HPC if we can build a proof which has that formula as the conclusion (i.e. the root of the tree). This is an example of the syntactic approach to logic. We don't even need to formulate the idea of "truth tables" to completely specify this.

An alternate approach is semantics. Here there are no axioms or rules. Instead, we need to provide a way of interpreting formulas as some mathematical object (in a compositional way, but I won't elaborate on that). There are many possible semantics you could use. One possibility is to use a Boolean algebra, and, in particular, the simplest possible non-trivial Boolean algebra built on a two element set. Any two element set will do. Let's use $\{\mathsf{cat},\mathsf{dog}\}$ for concreteness. With this choice of semantics, formulas with $n$ (distinct) propositional variables become $n$-ary operations on that two element set. Now we define a formula to be "true" if its interpretation is function that constantly has the value $\mathsf{dog}$. Dually from before, we can completely specify this semantics without ever mentioning any notion of formal proof.

Now we can ask the question: are the formulas that HPC proves the same as the formulas that the Boolean algebra semantics calls "true"? The soundness theorem for HPC with respect to this Boolean algebra semantics states that the formulas that HPC proves are "true" in the semantics. The completeness theorem for HPC with respect to this Boolean algebra semantics states that every formula that is "true" in the semantics has a proof in HPC. These (meta-)theorems can be proven either with informal mathematical reasoning or formally within some richer logical framework.

At no point in this do you need to accept the rules or axioms of HPC or agree that the Boolean algebra semantics I gave correctly reflects some philosophical notion of truth. This is no different from studying any other mathematical object. If I'm studying the ring of square matrices, I don't have to reject my prior notions of addition and multiplication and accept matrix addition/multiplication as the One True Meaning of addition and multiplication. I don't need to have a first principles account of how there is no other way of adding and multiplying matrices. (There are other ways of adding and multiplying matrices!) The formulas proven by HPC are the same regardless of one's philosophical stance. The formulas that are "true" with respect to the Boolean algebra semantics are the same regardless of one's philosophical stance. One's philosophical stance simply doesn't come into it.1

The only time I would need to convince you of the axioms/rules of HPC is if I'm making a philosophical claim that they correspond to some philosophical notion of "truth". There are plenty of reasons to study classical propositional logic quite apart from philosophical notions of "truth" such as applications to digital circuits. Similarly, there are plenty of reasons to study intuitionistic logics unrelated to philosophical notions of truth such as extracting computational content from constructive proofs or proving theorems that hold for a much broader and mathematically important class of semantics than classical logics. There are good reasons to study both simultaneously, and there is no cognitive dissonance in doing so.

As to some people calling $(p\land(p\to q))\to q$ "modus ponens", it wouldn't be the first time in mathematics that two distinct but related concepts were given the same name. That said, I think many of the times you see that it is being said by someone who doesn't have (or at least hasn't demonstrated that they have) a clear understanding of the separation between logic and meta-logic. Like your earlier question, if you try to naively formalize the usual informal description of the rule modus ponens but don't take care to separate syntax from semantics and logic from meta-logic, then you readily get the above formula. If you do take care to keep these separate, it is readily apparent that treating the above formula as the formalization of the rule modus ponens is a mish-mash of logic and meta-logic.

Write $\vdash p$ for the meta-logical claim that HPC proves $p$. The typical informal description of the rule modus ponens is: "if $p$ is provable and $p\to q$ is provable, then $q$ is provable". Let me write that a bit more formally. To make the distinction between logic and meta-logic a bit clearer, I'll write $\curlywedge$ and $\leadsto$ for the meta-logical conjunction and implication. The informal "modus ponens" is then more formally: $((\vdash p)\curlywedge(\vdash(p\to q)))\leadsto(\vdash q)$. This has the form $(\varphi\curlywedge\psi)\leadsto \chi$ where $\varphi$, $\psi$, and $\chi$ are atomic propositions in the meta-logic. Saying $(p\land(p\to q))\to q$ is a tautology is via the soundness and completeness theorems equivalent to saying $\vdash ((p\land(p\to q))\to q)$. This is an atomic proposition of the meta-logic. It should be clear now why I speak of a mish-mash. Viewing these two meta-logical propositions as being the same leads to $\to$ being used for both the $\to$ connective of the logic and the meta-logical $\leadsto$.

Still, if someone wants to call $(p\land(p\to q))\to q$ "modus ponens", that's their prerogative. It's no different than saying you are going to call it $A$. If, however, they are claiming it is the formalization of the rule modus ponens, then they are simply wrong.

1 This isn't completely true as one's philosophical stance on truth impacts their informal reasoning. For example, an ultrafinitist might reject the claim that sufficiently large formulas of classical propositional logic can have proofs in HPC or can be shown to be "true" in the Boolean algebra semantics. However, a classical mathematician, an ultrafinitist, and an intuitionist will all agree that $p\lor\neg p$ is provable in HPC and is "true" with respect to the Boolean algebra semantics. They just may not agree that HPC is a good reflection of their (philosophical) notion of "truth".

Related Question