Formal relationship between rules of inference and the material conditional

Question

I am not $100\%$ clear as to what constitutes the difference between a rule of inference and the material conditional, at least in classical logic. I am using the truth-functional definition of the material conditional, commonly visualised through its truth table, but I'm not entirely sure what the formal definition of a rule of inference is. The wikipedia article defines it to be a particular kind of logical form, which seems to be a term from philosophical logic that I'm not familiar with, but reading that article didn't really answer my question. It pertains more to the mathematical side of things, and I am specifically interested in the interplay between the concepts on the syntactic and semantic level. As far as I can tell, any rule of inference can be 'captured' by a corresponding material conditional: if we take modus ponens as a well-known example, what is the difference between $$(a\land (a\to b))\to b$$ and $${a\to b,\text{ } a \over b}?$$ On a functional level, both statements seem to be expressing the same thing. What determines the need to use two separate terms and notations, and what, if anything, separates them?

Answer 1

Let's start with the notion of proof in a formal system. This is a sequence of formulas $A_1,\ldots,A_n$ such that each formula on the list is either an axiom, or follows from earlier items on the list via a rule of inference.

You mentioned modus ponens, which is the standard example of a rule of inference. It can almost serve as the only rule of inference, depending on how you set up your formal apparatus.

Now let's contrast this with the formula you gave as a translation, $(a\wedge(a\rightarrow b))\rightarrow b$. This is a single formula. It could be included in a proof as one of the $A_i$'s but it doesn't give you the power to add $b$ once you already have $a$ and $a\rightarrow b$.

Lewis Carroll gave a droll but profound explanation of why you need rules of inference, why axioms alone won't suffice: [What the Tortoise Said to Achilles]. 1. Here's an excerpt.

Achilles had overtaken the Tortoise, and had seated himself comfortably on its back.

“So you’ve got to the end of our race-course?” said the Tortoise. “Even though it does consist of an infinite series of distances? I thought some wiseacre or other had proved that the thing couldn’t be done?”

“It can be done,” said Achilles. “It has been done! ... You see the distances were constantly diminishing; and so—”

“But if they had been constantly increasing?” the Tortoise interrupted “How then?” ... [W]ould you like to hear of a race-course, that most people fancy they can get to the end of in two or three steps, while it really consists of an infinite number of distances, each one longer than the previous one?”

“Very much indeed!” said the Grecian warrior...

“That beautiful First Proposition of Euclid!” the Tortoise murmured dreamily. ...

(A) Things that are equal to the same are equal to each other.
(B) The two sides of this Triangle are things that are equal to the same.
(Z) The two sides of this Triangle are equal to each other.

"Readers of Euclid will grant, I suppose, that Z follows logically from A and B, so that any one who accepts A and B as true, must accept Z as true?” ...“Well, now, I want you to ... force me, logically, to accept Z as true.”

“I’m to force you to accept Z, am I?” Achilles said musingly. “And your present position is that you accept A and B, but you don’t accept the Hypothetical—”

“Let’s call it C,” said the Tortoise.

“—but you don’t accept

(C) If A and B are true, Z must be true.”

“That is my present position,” said the Tortoise.

“Then I must ask you to accept C.”

“I’ll do so,” said the Tortoise, “as soon as you’ve entered it in that note-book of yours. ... Now write as I dictate:—

(A) Things that are equal to the same are equal to each other.
(B) The two sides of this Triangle are things that are equal to the same.
(C) If A and B are true, Z must be true.
(Z) The two sides of this Triangle are equal to each other.”

“You should call it D, not Z,” said Achilles. “It comes next to the other three. If you accept A and B and C, you must accept Z.”

“And why must I?”

“Because it follows logically from them. If A and B and C are true, Z must be true. You don’t dispute that, I imagine?”

“If A and B and C are true, Z must be true,” the Tortoise thoughtfully repeated. “That’s another Hypothetical, isn’t it? And, if I failed to see its truth, I might accept A and B and C, and still not accept Z, mightn’t I?”

"I must ask you to grant one more Hypothetical.” ...

(D) If A and B and C are true, Z must be true.

You can see where this is going. We want to infer (C) from (A) and (B), not add a new formula $A\wedge (A\rightarrow B)\rightarrow B$ to the list.

Answer 2

Relation between semantic inference an material conditional

For classical logic, the deduction theorem holds:

$$A_1, \ldots, A_n \vDash B\ \Longleftrightarrow\ \vDash (A_1 \land \ldots \land A_n) \to B$$

i.e. the inference from premises $A_1, \ldots, A_n$ to conclusion $B$ is valid if and only if the material conditional $(A_1 \land \ldots \land A_n) \to B$ is a tautology.

Both are model-theoretic notions: $A_1, \ldots, A_n \vDash B$ means that the conclusion $B$ is true in every model in which the premises $A_1, \ldots, A_n$ are true; $\vDash B$ is a special case of that without the restriction on models of the premises.

---

Relation between formal proof/inference rule and semantic inference

An inference rule in a formal proof system is a rewrite rule: $\dfrac{a \to b \quad a}{b}$ says "If you have the string of symbols $a \to b$, and another string $a$ on on the same level, then you are allowed to draw a line beneath them and write the symbol $b$ below it". A formal proof system is "syntactic" in the sense that it only operates by manipulations of strings of symbols, without making implicit reference to "semantic" (actually more precisely, model-theoretic/truth conditional) notions such as models and truth values.

Of course, these manipulations of strings of symbols are not just random:

• A useful proof system will be sound w.r.t. the semantics, meaning that if there is a formal proof ($\vdash$) of some conclusion from a number of premises, then the inference is semantically valid ($\vDash$) in the sense that every model of the premises is also a model of the conclusion -- i.o.w., soundness guarantees that the system doesn't prove nonsense: $$A_1, \ldots, A_n \vdash B \Longrightarrow A_1, \ldots, A_n \vDash B$$
• In addition, many proof systems are semantically complete, meaning that the system makes it possible to find a formal proof ($\vdash$) for every semantic inference ($\vDash$): $$A_1, \ldots, A_n \vDash B \Longrightarrow A_1, \ldots, A_n \vdash B$$

Soundness and completness are useful properties which hold for many proof systems, but they are not self-evident; by itself, $\vdash$ is indpependent of $\vDash$, and one has two prove that the two actually match.

A proof system as a whole can only be sound if all its inference rules are sound, i.e. each step in a formal proof consitutes a semantically valid inference; that is, we have

$$\dfrac{A_1 \quad \ldots \quad A_n}{B} \Longrightarrow A_1, \ldots, A_n \vDash B$$

The converse direction does not hold directly, because not any semantically valid inference has a single inference rule corresponding to it; but any inference will have a derivation with several inference rules plugged together corresponding to it ($\vdash$).

---

Relation between formal prof and material conditional

Combining the soundness + completeness theorem with the deduction theorem, we have that

$$\dfrac{A_1 \quad \ldots \quad A_n}{B}\ \Longrightarrow\ A_1, \ldots, A_n \vDash B\ \Longleftrightarrow\ \vDash (A_1, \ldots, A_n) \to B$$

so also

$$\dfrac{A_1 \quad \ldots \quad A_n}{B}\ \Longrightarrow\ \vDash (A_1, \ldots, A_n) \to B$$

-- every formal inference rule is a tautological material implication --

and more generally,

$$ A_1, \ldots, A_n \vdash B\ \Longleftrightarrow\ A_1, \ldots, A_n \vDash B\ \Longleftrightarrow\ \vDash (A_1, \ldots, A_n) \to B$$

so in particular

$$ A_1, \ldots, A_n \vdash B\ \Longleftrightarrow\ \vDash (A_1, \ldots, A_n) \to B$$

-- every formal proof consisting of inference rules plugged together is a tautological material implication, and every tautological material implication has a formal proof consisting of inference rules plugged together.

---

For reasons why formal proof systems are at all needed, see Why should we care about syntactic proofs if we can show semantically that statements are true?.