0
$\begingroup$

In first order logic, there can be different deductive systems:

A deductive system is used to demonstrate, on a purely syntactic basis, that one formula is a logical consequence of another formula. There are many such systems for first-order logic, including Hilbert-style deductive systems, natural deduction, the sequent calculus, the tableaux method, and resolution.

Boolos' Computability and Logic (5ed) says in Section 14.3 on p184

Despite the diversity of approaches possible, the aim of any approach is to set up a system of rules with the properties that if D is deducible from $\Gamma$, then D is a consequence of $\Gamma$ (soundness), and that if D is a consequence of $\Gamma$, then D is formally deducible from $\Gamma$ (completeness). Clearly, all systems of rules that achieve these aims will be equivalent to each other in the sense that D will be deducible from in the one system if and only if D is deducible from $\Gamma$ in the other system.

Is it correct that the equivalence between different deductive systems is defined in terms of derivability relations between (sets of) formulas?

Is it correct that derivability relations between (sets of) formulas are determined solely by inference rules, not by axioms?

Does the equivalence between different deductive systems disregard the choice of axioms? Different choices of axioms can lead to different sets of theorems, even with the same set of inference rules. So can different but equivalent deductive systems have different sets of axioms and therefore different sets of theorems?

Thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

Is it correct that the equivalence between different deductive systems is defined in terms of derivability relations between (sets of) formulas?

Yes, this is just what the previous sentence says:

D will be deducible from in the one system if and only if D is deducible from Γ in the other system

In formal notation, the derivability relation of a deductive system $A$ is

$$R_{\vdash_A} = \{\langle \Gamma, D \rangle: \Gamma \vdash_A D\}$$

where $\Gamma$ is a (possibly empty) set of formulas, $D$ is a formula, and $\Gamma \vdash_A D$ means "$D$ is derivable from assumptions $\Gamma$ in the deduction system $A$".

Two deduction systems $A, B$ are equivalent iff they give rise to the same derivability relation, i.e. iff for all sets of formulas $\Gamma$ and formulas $D$, $$\Gamma \vdash_A D\ \Longleftrightarrow\ \Gamma \vdash_B D$$

Is it correct that derivability relations between (sets of) formulas are determined solely by inference rules, not by axioms?

and

Does the equivalence between different deductive systems disregard the choice of axioms?

No. If the deduction system includes axioms, then the derivability relation will also be determined by these axioms. As you write below: Different choices of axioms can lead to different sets of theorems, i.e. to different derivability relations.

Different choices of axioms can lead to different sets of theorems, even with the same set of inference rules. So can different but equivalent deductive systems have different sets of axioms and therefore different sets of theorems?

If the different axioms lead to different sets of theorems, then by the very definition of equality they are not equivalent. Because then there are formulas $D$ such that $\vdash_A D$ but $\not \vdash_B D$.
If two deduction systems are equivalent, then, as a special instance of the above definition with $\Gamma = \emptyset$, for any formula $D$, $$\vdash_A D\ \Longleftrightarrow\ \vdash_B D$$ that is, A and B prove the same theorems.

Recall that $D$ being derivable without assumptions in a certain deduction system $A$ (written $\vdash_A D$) is the very definition of $D$ being a theorem in that system.

So the answer to your head question

Does equivalence between different deductive systems consider choices of axioms?

is yes: Choices of axioms may affect the derivability relation, and thereby the equivalence between deductive systems.

$\endgroup$

You must log in to answer this question.

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