Minimal logic

Summary

Minimal logic, or minimal calculus, is a symbolic logic system originally developed by Ingebrigt Johansson.[1] It is an intuitionistic and paraconsistent logic, that rejects both the law of the excluded middle as well as the principle of explosion (ex falso quodlibet), and therefore holding neither of the following two derivations as valid:

where and are any propositions. Most constructive logics only reject the former, the law of excluded middle. In classical logic, the ex falso laws

as well as their variants with and switched, are equivalent to each other and valid. Minimal logic also rejects those principles.

Note that the name has sometimes also been used to denote logic systems with a restricted number of connectives.

Axiomatization

edit

Minimal logic is axiomatized over the positive fragment of intuitionistic logic. Both of these logics may be formulated in the language using the same axioms for implication  , conjunction   and disjunction   as the basic connectives, but minimal logic conventionally adds falsum or absurdity   as part of the language.

Other formulations are possible, of course all avoiding explosion. Direct axioms for negation are given below. A desideratum is always the negation introduction law, discussed next.

Theorems

edit

Negation introduction

edit

A quick analysis of the valid rules for negation gives a good preview of what this logic, lacking full explosion, can and cannot prove. A natural statement in a language with negation, such as minimal logic, is, for example, the principle of negation introduction, whereby the negation of a statement is proven by assuming the statement and deriving a contradiction. Over minimal logic, the principle is equivalent to

 ,

for any two propositions. For   taken as the contradiction   itself, this establishes the law of non-contradiction

 .

Assuming any  , the introduction rule of the material conditional gives  , also when   and   are not relevantly related. With this and implication elimination, the above introduction principle implies

 ,

i.e. assuming any contradiction, every proposition can be negated. Negation introduction is possible in minimal logic, so here any contradiction moreover proves any double negation,  . Explosion would permit to remove the latter double negation, but this principle is not adopted.

Axiomatization via absurdity

edit

One possible scheme of extending the positive calculus to minimal logic is to treat   as an implication, in which case the theorems from the constructive implication calculus of a logic carry over to negation statements. To this end,   is introduced as a proposition, not provable unless the system is inconsistent, and negation   is then treated as an abbreviation for  . Constructively,   represents a proposition for which there can be no reason to believe it.

What follows are quick arguments showing which theorems still do hold in this logical theory, often making implicit use of the valid currying rule and the deduction theorem.

Implications

edit

By implication introduction,  , and this also already implies   showing directly how assuming   in minimal logic proves all negations. It may be expressed as

 

If absurdity is primitive, full explosion principle could likewise also be stated as  .

As for the adopted principles in the implication calculus, which do not involve negations, the page on Hilbert system presents it through propositional forms of the axioms of law of identity, implication introduction and a variant of modus ponens. Note the equivalence   proven there. For a first derivation, setting   here at once results in the schema

 .

In the intuitionistic Hilbert system, when not introducing   as a constant, this can be taken as the second negation-characterizing axiom. (The other being explosion.)

Now, firstly, with   taken as  , the above shows that

 .

But, secondly, this short implication may also more directly be derived from modus ponens in the propositional form   by considering  .

Thirdly, it follows from the valid weak form of consequentia mirabilis:  . In words, this theorem states that a statement cannot be rejected exactly when the negation of the statement implies that it cannot be rejected. In particular, one may prove   e.g. by proving  .

Fourthly, the double-negation implication above also follows from

 

which is related to the double-negation principle. This theorem may be established from  , by again reasoning with another variable   very similar to the above, proving  , and so on.

Contraposition of   gives

 .

Coming back to one of the earlier theorem, this can further also be seen as a special case of   with, again,  . Indeed, the general   can be derived from the general  . Alternatively, the same follows from  , all derivable from what has been pointed out above. Under the Curry-Howard correspondence, the last theorem here may also be justified by the lambda expression  , just to name one example.

Conjunctions

edit

Going beyond statements solely in terms of implications, the principles discussed previously can now also be established as theorems: With the definition of negation through  , the modus ponens statement in the form   itself specializes to the non-contradiction principle, when considering  . When negation is an implication, then the curried form of non-contradiction is again  . Further, negation introduction in the form with a conjunction, spelled out in the previous section, is implied as the mere special case of  

In this way, minimal logic can be characterized as a constructive logic just without negation elimination (a.k.a. explosion).

With this, most of the common intuitionistic implications involving conjunctions of two propositions can be obtained, including the currying equivalence.

Disjunctions

edit

It is worth emphasizing the important equivalence

 ,

expressing that those are two equivalent ways of the saying that both   and   imply  . From it, two of the familiar De Morgan's laws are obtained,

 .

The third valid De Morgan's law may also be derived.

The negation of an excluded middle statement implies its own validity. With reference to the weak variant of consequentia mirabilis above, it thus follows that

 

This result may also be seen as a special case of  , which follows from   when considering   for  .

Finally, case analysis shows

 

This implication is to be compared with the full disjunctive syllogism, discussed in detail below.

Axiomatization via alternative principles

edit

Another theorem only involving implications shall be noted: Related to the negation introduction principle, from

 .

minimal logic proves the contraposition

 ,

which like negation introduction again proves  . All the above principles can be obtained using theorems from the positive calculus in combination with the constant  .

Instead of the formulation with that constant, one may adopt as axioms the contraposition principle just stated, together with the double negation principle  . This gives an alternative axiomatization of minimal logic over the positive fragment of intuitionistic logic.

Relation to classical logic

edit

The tactic of generalizing   to   does not work to prove all classically valid statements involving double negations. In particular, unsurprisingly, the naive generalization of the double negation elimination   cannot be provable in this way. Indeed whatever   looks like, any schema of the syntactic form   would be too strong: Considering any true proposition for   makes this equivalent to just  .

The proposition   is a theorem of minimal logic, as is  . Therefore, adopting the full double negation principle   in minimal logic actually also proves explosion, and so brings the calculus back to classical logic, also skipping all intermediate logics.

As seen above, the double negated excluded middle for any proposition is already provable in minimal logic. However, it is worth emphasizing that in the predicate calculus, not even the laws of the strictly stronger intuitionistic logic enable a proof of the double negation of an infinite conjunction of excluded middle statements. Indeed,

 

In turn, the double negation shift schema (DNS) is not valid either, that is

 

Beyond arithmetic, this unprovability allows for the axiomatization of non-classical theories.

Relation to paraconsistent logic

edit

Minimal logic proves weaker variants of consequentia mirabilis, as demonstrated in that article. The full principle is, however, equivalent to excluded middle.

Relation to intuitionistic logic

edit

Any formula using only   is provable in minimal logic if and only if it is provable in intuitionistic logic. But there are also propositional logic statements that are unprovable in minimal logic, but do hold intuitionistically.

The principle of explosion is valid in intuitionistic logic and expresses that to derive any and all propositions, one may do this by deriving any absurdity. In minimal logic, this principle does not axiomatically hold for arbitrary propositions. As minimal logic represents only the positive fragment of intuitionistic logic, it is a subsystem of intuitionistic logic and is strictly weaker.

With explosion for negated statements, full explosion is equivalent to its special case  . The latter can be phrased as double negation elimination for rejected propositions,  . Formulated concisely, explosion in intuitionistic logic exactly grants particular cases of the double negation elimination principle that minimal logic does not have. This principle also immediately proves the full disjunctive syllogism.

Disjunctive syllogism

edit

Practically, in the intuitionistic context, the principle of explosion enables the disjunctive syllogism:

 

This can be read as follows: Given a constructive proof of   and constructive rejection of  , one unconditionally allows for the positive case choice of  . In this way, the syllogism is an unpacking principle for the disjunction. It can be seen as a formal consequence of explosion and it also implies it. This is because if   was proven by proving   then   is already proven, while if   was proven by proving  , then   also follows, as the intuitionistic system allows for explosion.

For example, given a constructive argument that a coin flip resulted in either heads or tails (  or  ), together with a constructive argument that the outcome was in fact not heads, the syllogism expresses that then this already constitutes an argument that tails occurred.

If the intuitionistic logic system is metalogically assumed consistent, the syllogism may be read as saying that a constructive demonstration of   and  , in the absence of other non-logical axioms demonstrating  , actually contains a demonstration of  .

In minimal logic, one cannot obtain a proof of   in this way. However, the same premise implies the double-negation of  , i.e.  . If the minimal logic system is metalogically assumed consistent, then that implication formula can be expressed by saying that   merely cannot be rejected.

Weak forms of explosion prove the disjunctive syllogism and in the other direction, the instance of the syllogism with   reads   and is equivalent to the double negation elimination for propositions for which excluded middle holds

 .

As the material conditional grants double-negation elimination for proven propositions, this is again equivalent to double negation elimination for rejected propositions.

Intuitionist example of use in a theory

edit

The following Heyting arithmetic theorem allows for proofs of existence claims that cannot be proven, by means of this general result, without the explosion principle. The result is essentially a family of simple double negation elimination claims,  -sentences binding a computable predicate.

Let   be any quantifier-free predicate, and thus decidable for all numbers  , so that excluded middle holds,

 .

Then by induction in  ,

 

In words: For the numbers   within a finite range up to  , if it can be ruled out that no case is validating, i.e. if it can be ruled out that for every number, say  , the corresponding proposition   will always be disprovable, then this implies that there is some   among those  's for which   is provable.

As with examples discussed previously, a proof of this requires explosion on the antecedent side to obtain propositions without negations. If the proposition is formulated as starting at  , then this initial case already gives a form of explosion from a vacuous clause

 .

The next case   states the double negation elimination for a decidable predicate,

 .

The   case reads

 ,

which, as already noted, is equivalent to

 .

Both   and   are again cases of double negation elimination for a decidable predicate. Of course, a statement   for fixed   and   may be provable by other means, using principles of minimal logic.

As an aside, the unbounded schema for general decidable predicates is not even intuitionistically provable, see Markov's principle.

Relation to type theory

edit

Use of negation

edit

Absurdity   is used not only in natural deduction, but also in type theoretical formulations under the Curry–Howard correspondence. In type systems,   is often also introduced as the empty type.

In many contexts,   need not be a separate constant in the logic but its role can be replaced with any rejected proposition. For example, it can be defined as   where   ought to be distinct. The claim of non-existence of a proof for that proposition is then a claim of consistency.

An example characterization for   is   in a theory involving natural numbers. This may also be adopted for in plain constructive logic. With this, proving   to be false, i.e.  , just means to prove  . We may introduce the notation   to capture the claim as well. And indeed, using arithmetic,   holds, but   also implies  . So this would imply   and hence we obtain  . QED.

Simple types

edit

Functional programming calculi already foremostly depend on the implication connective, see e.g. the calculus of constructions for a predicate logic framework.

In this section we mention the system obtained by restricting minimal logic to implication only, and describe it formally. It can be defined by the following sequent rules:

                     [2][3]

Each formula of this restricted minimal logic corresponds to a type in the simply typed lambda calculus, see Curry–Howard correspondence. In that context, the phrase minimal logic is sometimes used to mean this restriction of minimal logic.[4] This implicational fragment of minimal logic is the same as the positive, implicational fragment of intuitionistic logic since minimal Logic is already simply the positive fragment of intuitionistic logic.

Semantics

edit

There are semantics of minimal logic that mirror the frame-semantics of intuitionistic logic, see the discussion of semantics in paraconsistent logic. Here the valuation functions assigning truth and falsity to propositions can be subject to fewer constraints.

See also

edit

Notes

edit

References

edit
  • Colacito, Almudena (2016). Minimal and Subminimal Logic of Negation (PDF). MSc Thesis (Afstudeerscriptie). Institute for Logic, Language and Computation.
  • Huet, Gérard (May 1986). Formal Structures for Computation and Deduction. International Summer School on Logic of Programming and Calculi of Discrete Design. Archived from the original on 2014-07-14.
  • Johansson, Ingebrigt (1937). "Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus". Compositio Mathematica (in German). 4: 119–136.
  • Sørensen, Morten Heine B.; Urzyczyn, Paweł [in Polish] (May 1998). "Lectures on the Curry-Howard Isomorphism" (PDF).
  • Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2003) [1996]. Basic Proof Theory (2 ed.). Cambridge University Press. pp. XII, 417. ISBN 9780521779111.
  • Weber, Matthias; Simons, Martin; Lafontaine, Christine (1993). The Generic Development Language Deva: Presentation and Case Studies. Lecture Notes in Computer Science (LNCS). Vol. 738. Springer. p. 246. ISBN 3-540-57335-6.