Math and science::Theory of Computation::Modal theory

Deduction

The definition of a deduction tries to capture the essence of proof.

Deduction. Informal definition.

A deduction is a sequence of statements that justifies another mathematical statement. Each statement of the sequence is justified either by definition, or by the previous statements in the sequence. It must be possible for a machine to execute an algorithm to determine the validity of a deduction in finite steps.

The above informal definition does not explain how justification works. The following definition is more concrete.

Deduction. Definition.

A deduction in a first-order language $L$ is a finite sequence $(ϕ)_{n = 1}^{N}$ of $L$ -formulas from $L$ such that each $ϕ_{i}$ in the sequence satisfies one of the following 2 conditions:

$ϕ_{i}$ is an axiom (logical or non-logical).
$ϕ_{i}$ is the second component of some inference rule $(Γ, ϕ_{i})$ , where $Γ$ is a subset of the preceding terms of the sequence ( $Γ \subset {ϕ_{n} | n \in N \land 0 > n < i}$ ).

If $Σ$ is the set of non-logical axioms*, and $(ϕ_{i})_{n = 1}^{N}$ is a deduction ending in $ϕ_{N}$ , then we call this a deduction from $Σ$ of $ϕ_{N}$ and we write $Σ ⊢ ϕ_{N}$ .

*We care most about how the non-logical axioms enable a deduction (the logical axioms and the inference rules are normally the same standard ones).

The back side includes a recap of axioms and rules of inference.

Axioms. Logical and non-logical.

An axiom is an $L$ -formula.

We generally classify axioms into two categories:

Logical axioms: A very minimal collection of axioms covering equality, and the quantifier $\forall$ and $\exists$ . Don't change depending on circumstances (any others? are they really the same for modal theory for all first-order languages?)
Non-logical axioms: Axioms that change based on circumstances. For example, axioms for integer summation or axioms for integer summation and multiplication.

For first-order languages, an algorithm is specified that can check if an $L$ -formula is a logical axiom. The set of logical axioms is defined implicitly as the $L$ -formula for which the algorithm decides are logical axiom.

Rule of inference

A rule of inference is a pair $(Γ, ϕ)$ where $Γ$ is a set of $L$ -formula and $ϕ$ is an $L$ -formula.

Similar to the case for logical axioms, there is an algorithm for checking if a given ( $L$ -formula set, $L$ -formula) pair constitute an inference rule. This algorithm can be broken down into two steps:

convert all $L$ -formula to propositional forms
check for a tautology

Another card discusses axioms and inference rules in more detail.

Source

A friendly Introduction to Mathematical Logic, Leary and Kristiansen

p43

10.09.2021