Minimal logic

Short description: Symbolic logic system

Minimal logic, or minimal calculus, is a symbolic logic system originally developed by Ingebrigt Johansson. 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:

[math]\displaystyle{ \vdash (B \lor \neg B) }[/math]

[math]\displaystyle{ (A \land \neg A) \vdash }[/math]

where [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are any propositions. Most constructive logics only reject the former, the law of excluded middle. In classical logic, the ex falso laws

[math]\displaystyle{ (A \land \neg A) \to B, }[/math]

[math]\displaystyle{ \neg(A \lor \neg A) \to B, }[/math]

[math]\displaystyle{ \neg A \to (A \to B), }[/math]

as well as their variants with [math]\displaystyle{ A }[/math] and [math]\displaystyle{ \neg A }[/math] 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

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 [math]\displaystyle{ \to }[/math], conjunction [math]\displaystyle{ \land }[/math] and disjunction [math]\displaystyle{ \lor }[/math] as the basic connectives, but Minimal Logic conventionally adds falsum or absurdity [math]\displaystyle{ \bot }[/math] 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

Negation introduction

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 it and deriving a contradiction. Over minimal logic, the principle is equivalent to

[math]\displaystyle{ (B\to (A\land \neg A))\to \neg B }[/math],

for any two propositions. For [math]\displaystyle{ B }[/math] taken as the contradiction [math]\displaystyle{ A\land \neg A }[/math] itself, this establishes the law of non-contradiction

[math]\displaystyle{ \neg(A\land \neg A) }[/math].

Assuming any [math]\displaystyle{ C }[/math], the introduction rule of the material conditional gives [math]\displaystyle{ B\to C }[/math], also when [math]\displaystyle{ B }[/math] and [math]\displaystyle{ C }[/math] are not relevantly related. With this and implication elimination, the above introduction principle implies

[math]\displaystyle{ (A\land \neg A)\to\neg B }[/math],

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, [math]\displaystyle{ \neg \neg B }[/math]. Explosion would permit to remove the latter double negation, but this principle is not adopted.

Axiomatization via absurdity

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

Implications

As for the adopted principles in the implication calculus, 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, for a first example, that setting [math]\displaystyle{ C=\bot }[/math] in the equivalence [math]\displaystyle{ \big(A\to(B\to C)\big)\leftrightarrow\big(B\to(A\to C)\big) }[/math] results in the schema

[math]\displaystyle{ \big(A\to\neg B\big)\leftrightarrow\big(B\to\neg A\big) }[/math].

In the intuitionistic Hilbert system, when not introducing [math]\displaystyle{ \bot }[/math] as a constant, this theorem can be taken as the second negation-characterizing axiom. (The other being explosion.) With [math]\displaystyle{ A }[/math] taken as [math]\displaystyle{ \neg B }[/math], this shows

[math]\displaystyle{ B\to \neg\neg B }[/math].

That may also be derived from modus ponens in the propositional form [math]\displaystyle{ B\to ((B\to C)\to C) }[/math]. Related to the double-negation principle is also

[math]\displaystyle{ \big(\neg\neg(A\to B)\big) \to \big(A\to \neg\neg B\big) }[/math]

This may be established from [math]\displaystyle{ A\to\big(B \leftrightarrow (A\to B)\big) }[/math], by again reasoning with another variable [math]\displaystyle{ C }[/math] very similar to the above, proving [math]\displaystyle{ A\to\big((\neg B)\leftrightarrow\neg(A\to B)\big) }[/math], and so on.

Generalizing some of the above in another way, one has [math]\displaystyle{ \big(((B\to C)\to C)\to D\big) \to (B\to D) }[/math]. Under the Curry-Howard correspondence, this, as one example, is justified by the lambda expression [math]\displaystyle{ \lambda f^{((B\to C)\to C)\to D}.\ \lambda b^B.\ f(\lambda g^{B\to C}. g(b)) }[/math]. Modus ponens further then really implies the equivalence [math]\displaystyle{ \big(((B\to C)\to C)\to C\big) \leftrightarrow (B\to C) }[/math], and so

[math]\displaystyle{ \neg\neg\neg B\leftrightarrow\neg B }[/math].

Finally, by implication introduction, [math]\displaystyle{ C\to (B\to C) }[/math], and this also already implies [math]\displaystyle{ \bot\to (B\to\bot) }[/math] showing directly how assuming [math]\displaystyle{ \bot }[/math] in minimal logic proves all negations. It may be expressed as

[math]\displaystyle{ \bot\to \neg B. }[/math]

If absurdity is primitive, full explosion principle could likewise also be stated as [math]\displaystyle{ \bot\to B }[/math].

Conjunctions

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 [math]\displaystyle{ \bot }[/math], the modus ponens statement in the form [math]\displaystyle{ (A \land (A\to C))\to C }[/math] itself specializes to the non-contradiction principle, when considering [math]\displaystyle{ C=\bot }[/math]. When negation is an implication, then the curried form of non-contradiction is again [math]\displaystyle{ A \to \neg\neg A }[/math]. Further, negation introduction in the form with a conjunction, spelled out in the previous section, is implied as the mere special case of [math]\displaystyle{ \big(B\to (A\land (A\to C))\big)\to (B\to C) }[/math]

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

It is worth emphasizing the important equivalence

[math]\displaystyle{ \big((A\lor B)\to C\big)\leftrightarrow\big((A\to C)\land (B\to C)\big) }[/math],

expressing that those are two equivalent ways of the saying that both [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] imply [math]\displaystyle{ C }[/math]. From it, two of the familiar De Morgan's laws are obtained,

[math]\displaystyle{ \neg(A\lor B)\leftrightarrow(\neg A\land\neg B) }[/math].

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

From the simpler [math]\displaystyle{ ((A\lor B)\to C)\to (B\to C) }[/math] follows [math]\displaystyle{ \big((B\lor(B\to C))\to C\big)\to C }[/math] when considering [math]\displaystyle{ B\to C }[/math] for [math]\displaystyle{ A }[/math]. This in turn reduces to the double negation of excluded middle

[math]\displaystyle{ \neg\neg(B\lor\neg B) }[/math].

Finally, case analysis shows

[math]\displaystyle{ \big((B\lor \neg A)\land \neg \neg A\big) \to \big((B\lor\neg B)\land\neg \neg B)\big) }[/math]

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

Axiomatization via alternative principles

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

[math]\displaystyle{ (B\to A)\to((A\to C)\to(B\to C)) }[/math].

minimal logic proves the contraposition

[math]\displaystyle{ (B\to A)\to(\neg A\to\neg B) }[/math],

which like negation introduction again proves [math]\displaystyle{ (A\land \neg A)\to \neg B }[/math]. All the above principles can be obtained using theorems from the positive calculus in combination with the constant [math]\displaystyle{ \bot }[/math].

Instead of the formulation with that constant, one may adopt as axioms the contraposition principle just stated, together with the double negation principle [math]\displaystyle{ B\to \neg\neg B }[/math]. This gives an alternative axiomatization of minimal logic over the positive fragment of intuitionistic logic.

Relation to classical logic

The tactic of generalizing [math]\displaystyle{ \neg A }[/math] to [math]\displaystyle{ A\to C }[/math] does not work to prove all classically valid statements involving double negations. In particular, unsurprisingly, the naive generalization of the double negation elimination [math]\displaystyle{ \neg \neg B\to B }[/math] cannot be provable in this way. Indeed whatever [math]\displaystyle{ A }[/math] looks like, any schema of the syntactic form [math]\displaystyle{ (A\to C)\to B }[/math] would be too strong: Considering any true proposition for [math]\displaystyle{ C }[/math] makes this equivalent to just [math]\displaystyle{ B }[/math].

The proposition [math]\displaystyle{ \neg\neg(B\lor \neg B) }[/math] is a theorem of minimal logic, as is [math]\displaystyle{ (A\land \neg A)\to \neg \neg B }[/math]. Therefore, adopting the full double negation principle [math]\displaystyle{ \neg\neg B\to B }[/math] in minimal logic 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,

[math]\displaystyle{ \nvdash\neg\neg\forall(n\in{\mathbb N}). Q(n)\lor\neg Q(n) }[/math]

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

[math]\displaystyle{ \nvdash\big(\forall(n\in{\mathbb N}).\neg\neg P(n)\big)\to\neg\neg\forall(n\in{\mathbb N}). P(n) }[/math]

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

Relation to intuitionistic logic

Any formula using only [math]\displaystyle{ \land, \lor, \to }[/math] 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 [math]\displaystyle{ ((\neg B) \land \neg(\neg B))\to B }[/math]. The latter can be phrased as double negation elimination for rejected propositions, [math]\displaystyle{ \neg B \to(\neg \neg B\to B) }[/math]. 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

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

[math]\displaystyle{ ((A \lor B)\land \neg A) \to B. }[/math]

This can be read as follows: Given a constructive proof of [math]\displaystyle{ A \lor B }[/math] and constructive rejection of [math]\displaystyle{ A }[/math], one unconditionally allows for the positive case choice of [math]\displaystyle{ B }[/math]. 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 [math]\displaystyle{ A \lor B }[/math] was proven by proving [math]\displaystyle{ B }[/math] then [math]\displaystyle{ B }[/math] is already proven, while if [math]\displaystyle{ A \lor B }[/math] was proven by proving [math]\displaystyle{ A }[/math], then [math]\displaystyle{ B }[/math] 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 ([math]\displaystyle{ A }[/math] or [math]\displaystyle{ B }[/math]), 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 [math]\displaystyle{ A\lor B }[/math] and [math]\displaystyle{ \neg A }[/math], in the absence of other non-logical axioms demonstrating [math]\displaystyle{ B }[/math], actually contains a demonstration of [math]\displaystyle{ B }[/math].

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

Weak forms of explosion prove the disjunctive syllogism and in the other direction, the instance of the syllogism with [math]\displaystyle{ A=\neg B }[/math] reads [math]\displaystyle{ \big((B \lor \neg B)\land \neg \neg B\big) \to B }[/math] and is equivalent to the double negation elimination for propositions for which excluded middle holds

[math]\displaystyle{ (B \lor \neg B)\to (\neg \neg B \to B) }[/math].

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

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, [math]\displaystyle{ \exists }[/math]-sentences binding a computable predicate.

Let [math]\displaystyle{ P }[/math] be any quantifier-free predicate, and thus decidable for all numbers [math]\displaystyle{ n }[/math], so that excluded middle holds,

[math]\displaystyle{ P(n)\lor\neg P(n) }[/math].

Then by induction in [math]\displaystyle{ m }[/math],

[math]\displaystyle{ \forall m.\ \neg\big(\forall(n\lt m).\neg P(n)\big)\to\exists(b\lt m).P(b) }[/math]

In words: For the numbers [math]\displaystyle{ n }[/math] within a finite range up to [math]\displaystyle{ m }[/math], if it can be ruled out that no case is validating, i.e. if it can be ruled out that for every number, say [math]\displaystyle{ n=a }[/math], the corresponding proposition [math]\displaystyle{ P(a) }[/math] will always be disprovable, then this implies that there is some [math]\displaystyle{ n=b }[/math] among those [math]\displaystyle{ n }[/math]'s for which [math]\displaystyle{ P(b) }[/math] 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 [math]\displaystyle{ m=0 }[/math], then this initial case already gives a form of explosion from a vacuous clause

[math]\displaystyle{ \bot\to\exists(b\lt 0). P(b) }[/math].

The next case [math]\displaystyle{ m=1 }[/math] states the double negation elimination for a decidable predicate,

[math]\displaystyle{ \neg\neg P(0)\to P(0) }[/math].

The [math]\displaystyle{ m=2 }[/math] case reads

[math]\displaystyle{ \neg\big(\neg P(0)\land \neg P(1)\big)\to \big(P(0)\lor P(1)\big) }[/math],

which, as already noted, is equivalent to

[math]\displaystyle{ \neg\neg \big(P(0)\lor P(1)\big)\to \big(P(0)\lor P(1)\big) }[/math].

Both [math]\displaystyle{ m=0 }[/math] and [math]\displaystyle{ m=1 }[/math] are again cases of double negation elimination for a decidable predicate. Of course, a statement [math]\displaystyle{ \exists(b\lt m).P(b) }[/math] for fixed [math]\displaystyle{ m }[/math] and [math]\displaystyle{ P }[/math] 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

Use of negation

Absurdity [math]\displaystyle{ \bot }[/math] is used not only in natural deduction, but also in type theoretical formulations under the Curry–Howard correspondence. In type systems, [math]\displaystyle{ \bot }[/math] is often also introduced as the empty type.

In many contexts, [math]\displaystyle{ \bot }[/math] 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 [math]\displaystyle{ a=b }[/math] where [math]\displaystyle{ a, b }[/math] 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 [math]\displaystyle{ \bot }[/math] is [math]\displaystyle{ 0=1 }[/math] in a theory involving natural numbers. This may also be adopted for in plain constructive logic. With this, proving [math]\displaystyle{ 3^4=8 }[/math] to be false, i.e. [math]\displaystyle{ \neg(3^4=8) }[/math], just means to prove [math]\displaystyle{ (3^4=8)\to(0=1) }[/math]. We may introduce the notation [math]\displaystyle{ 3^4 \neq 8 }[/math] to capture the claim as well. And indeed, using arithmetic, [math]\displaystyle{ \tfrac{3^4-8}{73}=1 }[/math] holds, but [math]\displaystyle{ (3^4=8) }[/math] also implies [math]\displaystyle{ \tfrac{3^4-8}{73}=0 }[/math]. So this would imply [math]\displaystyle{ 1=0 }[/math] and hence we obtain [math]\displaystyle{ \neg(3^4=8) }[/math]. QED.

Simple types

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:

[math]\displaystyle{ \dfrac{}{\Gamma \cup \{A\} \vdash A} \mbox{ axiom} }[/math]         [math]\displaystyle{ \dfrac{\Gamma \cup \{A\} \vdash B}{\Gamma \vdash A \to B} \mbox{ intro} }[/math]         [math]\displaystyle{ \dfrac{\Gamma \vdash A \to B ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ \Delta \vdash A}{\Gamma \cup \Delta \vdash B} \mbox{ elim.} }[/math]

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. 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

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

• Intuitionistic logic
• Paraconsistent logic
• Implicational propositional calculus
• List of logic systems

References

• Colacito, Almudena (2016). Minimal and Subminimal Logic of Negation. MSc Thesis (Afstudeerscriptie). Institute for Logic, Language and Computation. https://eprints.illc.uva.nl/id/eprint/986/1/MoL-2016-14.text.pdf. 
• Huet, Gérard (May 1986). Formal Structures for Computation and Deduction. International Summer School on Logic of Programming and Calculi of Discrete Design. http://yquem.inria.fr/~huet/PUBLIC/Formal_Structures.ps.gz. 
• Johansson, Ingebrigt (1937). "Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus" (in de). Compositio Mathematica 4: 119-136. http://www.numdam.org/item/CM_1937__4__119_0. 
• Sørensen, Morten Heine B.; Urzyczyn, Paweł (May 1998). "Lectures on the Curry-Howard Isomorphism". https://disi.unitn.it/%7Ebernardi/RSISE11/Papers/curry-howard.pdf. 
• Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2003). 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). 738. Springer. pp. 246. ISBN 3-540-57335-6.