In
proof theory
Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding part ...
, a structural rule is an
inference rule
In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their syntax, and returns a conclusion (or conclusions). For example, the rule of ...
that does not refer to any
logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
, but instead operates on the
judgment
Judgement (or US spelling judgment) is also known as ''adjudication'', which means the evaluation of evidence to make a decision. Judgement is also the ability to make considered decisions. The term has at least five distinct uses. Aristotle s ...
or
sequent
In mathematical logic, a sequent is a very general kind of conditional assertion.
: A_1,\,\dots,A_m \,\vdash\, B_1,\,\dots,B_n.
A sequent may have any number ''m'' of condition formulas ''Ai'' (called " antecedents") and any number ''n'' of ass ...
s directly. Structural rules often mimic intended meta-theoretic properties of the logic. Logics that deny one or more of the structural rules are classified as
substructural logic
In logic, a substructural logic is a logic lacking one of the usual structural rules (e.g. of classical and intuitionistic logic), such as weakening, contraction, exchange or associativity. Two of the more significant substructural logics are r ...
s.
Common structural rules
Three common structural rules are:
* Weakening, where the hypotheses or conclusion of a sequent may be extended with additional members. In symbolic form weakening rules can be written as
on the left of the
turnstile
A turnstile (also called a turnpike, gateline, baffle gate, automated gate, turn gate in some regions) is a form of gate which allows one person to pass at a time. A turnstile can be configured to enforce one-way human traffic. In addition, a ...
, and
on the right.
* Contraction, where two equal (or unifiable) members on the same side of a sequent may be replaced by a single member (or common instance). Symbolically:
and
. Also known as factoring in
automated theorem proving
Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a ...
systems using
resolution. Known as
idempotency of entailment
Idempotency of entailment is a property of logical systems that states that one may derive the same consequences from many instances of a hypothesis as from just one. This property can be captured by a structural rule called contraction, and in s ...
in classical logic.
* Exchange, where two members on the same side of a sequent may be swapped. Symbolically:
and
. (This is also known as the ''permutation rule''.)
A logic without any of the above structural rules would interpret the sides of a sequent as pure
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
s; with exchange, they are
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s; and with both contraction and exchange they are
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
s.
These are not the only possible structural rules. A famous structural rule is known as
cut
Cut may refer to:
Common uses
* The act of cutting, the separation of an object into two through acutely-directed force
** A type of wound
** Cut (archaeology), a hole dug in the past
** Cut (clothing), the style or shape of a garment
** Cut (ea ...
. Considerable effort is spent by proof theorists in showing that cut rules are superfluous in various logics. More precisely, what is shown is that cut is only (in a sense) a tool for abbreviating proofs, and does not add to the theorems that can be proved. The successful 'removal' of cut rules, known as ''
cut elimination
The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for ...
'', is directly related to the philosophy of ''
computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An esp ...
as normalization'' (see
Curry–Howard correspondence
In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct rela ...
); it often gives a good indication of the
complexity
Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generally used to ch ...
of
deciding a given logic.
See also
*
*
*
*
*
{{Non-classical logic
Proof theory
Rules of inference