↑ arvau

Wikipedia / Calculus of structures

In mathematical logic, the calculus of structures (CoS) is a proof calculus with deep inference for studying the structural proof theory of noncommutative logic. The calculus has since been applied to study linear logic, classical logic, modal logic, and process calculi, and many benefits are claimed to follow in these investigations from the way in which deep inference is made available in the calculus.

It was first introduced in 2001 in the paper A System of Interaction and Structure by Alessio Guglielmo of the University of Bath.

Definitions

A formula is a (well-formed is a formula.

An equational theory is a list of equations that describe an equivalence relation on the set of all formulas. The usual equations are associativity, commutativity, and equations for logical constants.

A structure is an equivalence class of formulas. The name "structure" emphasizes that CoS does not distinguish sequents and formulas, but uses a single object to do the job of both in a sequent calculus. Specifically, a structure can be regarded as an equivalence class of formulas.

A context.

An inference rule implicit. By default, contexts appearing in inference rules must have positive polarity.

A context has a polarity. The polarity of a context is either positive or negative is once again a positive context. The positivity or negativity of a context is called its polarity has negative polarity".

Two structures may be duals can also be duals. The classical contraposition is an example of this duality.

.

Ideas

Deep inference

In sequent calculus, each inference rule can only produce/eliminate logical connectives on the outermost level of a formula. In particular, this means that most subformulas remain unchanged. In deep inference, each inference rule can rewrite subformulas on any level.

and all their subformulas unchanged. Only the outermost logical connective is produced.

For deep inference, inference rules may apply to any subformula, arbitrarily deep within the syntax tree. In other words, out of all the nodes in the syntax tree, an inference rule can only manipulate the outermost node. Deep inference allows a rule to manipulate arbitrary node within the syntax tree.

Top-down symmetry

In sequent calculus and natural deduction, a proof is a tree of inference rules. This then produces a fundamental asymmetry: The top of a proof tree are made of many leaf-sequents, but the bottom of a proof tree is a single endsequent. However, many inference rules are symmetric: The top half and the bottom half are mutually derivable.

has a top-down symmetry.

is not itself a sequent. This means this top-down symmetry is not on the object-level of the proof calculus.

In the calculus of sequents, a proof is a line of inference rules. This places the top-down symmetry in the object level.

SKSg

Definition

SKSg is a CoS for classical propositional logic.

The symbols of SKSg consists of:

  • are atoms that are dual to each other.

  • .

  • .

Negation does not exist in SKSg, since we have demoted negation from a logical connective to merely a pairing between logical atoms.

A structure of SKSg has the following syntax in Backus–Naur formWithout negation, all contexts are positive.

The structural inference rules come in 3 dual pairs:The 2 logical inference rules are self-dual:All equations of the SKSg system can be replaced by inference rules. The resulting equation-less system is SKS.

Properties

This is a general principle in deep inference: structural rules on generic formulas can be replaced by the same structural rule on atoms. In this case, cocontraction.

A cut-free is not used. One can eliminate cuts by a technique called splitting.

MLL⁻

Define MLL⁻ to be the proof system of multiplicative linear logic without units.

.

The system has the following CoS:Each row is a pair of dual rules. The switch rule is dual to itself.

.

, etc.

.

.

. In general, an inference rule of a CoS can be read as a provable sequent in a sequent calculus, by "rotating it 90 degrees".

Interpretation

but it appears on the level of proofs.

.

. Then replace each use of inference rule in the sequent calculus with a use of several inference rules in the CoS. This shows that structures are not a mere replication of formulas or sequents, since it has features of both.

Cut elimination corresponds to i↓-elimination.

SLLS

The SLLS system is the CoS version of the full linear logic. It is much larger than the CoS for MLL⁻.

BV

The BV system (Basic System V) can be produced by this CoS:

References

Further reading

  • Kai Brünnler (2004). Deep Inference and Symmetry in Classical Proofs. Logos Verlag.