The following excerpt is from page 357 of Logic: The Laws of Truth by Nicholas Smith:
Given a system of proof – say, the tree method for GPLI – we call propositions that can be proven using that method "theorems" of that system. So, for example, $(Pa \lor \neg Pa)$ is a theorem of out system of tree proofs for GPLI, because we can prove, using a GPLI tree, that $(Pa \lor \neg Pa)$ is a logical truth.
However, I'm not sure how to reconcile this with the notion of a theorem as introduced earlier in the book (page 253) in the context of axiomatisation:
Consider the predicates A, B and C, and suppose we lay down the following axioms governing these predicates:
- $\forall x (Ax \lor Bx)$
- $\neg \exists x (Ax \land Bx)$
- $\forall x (Cx \implies Ax)$
[…]
Axiomatization does not yield an unqualified notion of truth. Rather, the notion that emerges naturally in this context is that of a theorem: a wff that is true in every model that makes all the axioms true. In other words, a theorem is a logical consequence of the axioms. A set of wffs that is closed under logical consequence – that is, one for which every wff that is a logical consequence of some wffs in the set is also in the set – is a theory. A set of axioms generates theory: the set of all wffs that are true in every model in which all the axioms are true. A theorem of an axiomatic system is a wff that is a member of the theory generated by axioms. For example, in our example above, $\neg \exists x (Cx \land Bx)$ is a theorem of the system: it follows logically from axioms (2) and (3)$
Is the notion of a theorem in the first quote the same as the one in the second quote? If $(Pa \lor \neg Pa)$ is a theorem of the system of tree proofs, then by the definition in the first quote, does the set of all wffs that can be proven using tree proofs form a theory, with the tree rules serving as axioms?
Best Answer
GPLI (page 167) is general predicate logic with identity.
Ch.12.3 Trees for General Predicate Logic extends the tree method to predicate logic and Ch.13.4 Trees for General Predicate Logic extends it further to cover identity.
The tree method is a proof system (refutation proof procedure) that allows us to test for validity: in that context, we may call "theorem" every formula for which the tree method produces a "closed path", like e.g. $∀x(x=x)$ and $∀xPx \lor ¬∀xPx$. –
These are what we call "logical laws", i.e. formulas of predicate logic with identity that are universally valid.
In Ch.14 Metatheory the author will prove the usual Soundness and Completeness results, linking the proof system and the corresponding semantics, that amounts to showing that the tree method proves all and only the formulas that are universally valid.
See page 358:
When we define a "mathematical theory" for say predicates A, B and C, we add specific axioms, i.e. formulas that are not universally valid, like $∀x(Ax ∨ Bx)$. This facts allows use to produce new "theorems" (in addition to the universally valid formulas already available) that are not universally valid, i.e. they are not true in every model BUT, being consequences of the axioms, they will be true in every model of the axioms.
This means that, if $\Gamma$ is the set of axioms of our "A,B,C-theory" and $\varphi$ is a formula of the same theory, being $\varphi$ a theorem of the theory will be symbolized with: $\Gamma \vDash \varphi$ (see Logical consequence and Soundness and Completeness of predicate logic).