Editing Contradiction (section)

== In formal logic ==
{{Hatnote|Note: The symbol <math>\bot</math> ([[falsum]])<!-- [[falsum]] hyperlink should redirect to the "[[False (logic)]] article... but I like the template I created so I will wait some days before correcting it:O)--> represents an arbitrary contradiction, with the dual [[tee (symbol)|tee]] symbol <math>\top</math> used to denote an arbitrary tautology.  Contradiction is sometimes symbolized by "O''pq''", and tautology by "V''pq''".  The turnstile symbol, <math>\vdash</math> is often read as "yields" or "proves".}}

In classical logic, particularly in [[propositional logic|propositional]] and [[first-order logic]], a proposition <math>\varphi</math> is a contradiction [[if and only if]] <math>\varphi\vdash\bot</math>. Since for contradictory <math>\varphi</math> it is true that <math>\vdash\varphi\rightarrow\psi</math> for all <math>\psi</math> (because <math>\bot\vdash\psi</math>), one may prove any proposition from a set of axioms which contains contradictions. This is called the "[[principle of explosion]]", or "ex falso quodlibet" ("from falsity, anything follows").<ref>{{Cite web|url=https://www.oxfordreference.com/view/10.1093/oi/authority.20110803095804354|title=Ex falso quodlibet - Oxford Reference|website=www.oxfordreference.com|language=en|access-date=2019-12-10}}</ref>

In a [[completeness (logic)|complete]] logic, a formula is contradictory if and only if it is [[unsatisfiable]].

===Proof by contradiction===
{{main|Proof by contradiction}}
For a set of consistent premises <math>\Sigma</math> and a proposition <math>\varphi</math>, it is true in [[classical logic]] that <math>\Sigma \vdash\varphi</math> (i.e., <math>\Sigma</math> proves <math>\varphi</math>) if and only if <math>\Sigma \cup \{\neg\varphi\} \vdash \bot</math> (i.e., <math>\Sigma</math> and <math>\neg\varphi</math> leads to a contradiction). Therefore, a [[proof (logic)|proof]] that <math>\Sigma \cup \{\neg\varphi\} \vdash \bot</math> also proves that <math>\varphi</math> is true under the premises <math>\Sigma</math>. The use of this fact forms the basis of a [[Proof techniques|proof technique]] called [[proof by contradiction]], which mathematicians use extensively to establish the validity of a wide range of theorems. This applies only in a logic where the [[law of excluded middle]] <math>A\vee\neg A</math> is accepted as an axiom.

Using [[minimal logic]], a logic with similar axioms to classical logic but without ''ex falso quodlibet'' and proof by contradiction, we can investigate the axiomatic strength and properties of various rules that treat contradiction by considering theorems of classical logic that are not theorems of minimal logic.<ref>Diener and Maarten McKubre-Jordens, 2020. [https://arxiv.org/abs/1606.08092 Classifying Material Implications over Minimal Logic]. [[Archive for Mathematical Logic]] 59 (7-8):905-924.</ref> Each of these extensions leads to an [[intermediate logic]]:
# Double-negation elimination (DNE) is the strongest principle, axiomatized <math>\neg\neg A \implies A</math>, and when it is added to minimal logic yields classical logic.
# Ex falso quodlibet (EFQ), axiomatized <math>\bot \implies A</math>, licenses many consequences of negations, but typically does not help to infer propositions that do not involve absurdity from consistent propositions that do. When added to minimal logic, EFQ yields [[intuitionistic logic]]. EFQ is equivalent to ''ex contradiction quodlibet'', axiomatized <math>A \land \neg A \implies B</math>, over minimal logic.
# [[Peirce's law|Peirce's rule]] (PR) is an axiom <math>((A \implies B) \implies A) \implies A</math> that captures proof by contradiction without explicitly referring to absurdity. Minimal logic + PR + EFQ yields classical logic. 
# The Gödel-Dummett (GD) axiom <math>A \implies B \vee B \implies A</math>, whose most simple reading is that there is a linear order on truth values.  Minimal logic + GD yields [[Gödel-Dummett logic]]. Peirce's rule entails but is not entailed by GD over minimal logic.
# Law of the excluded middle (LEM), axiomatised <math>A \vee \neg A</math>, is the most often cited formulation of the [[principle of bivalence]], but in the absence of EFQ it does not yield full classical logic. Minimal logic + LEM + EFQ yields classical logic. PR entails but is not entailed by LEM in minimal logic. If the formula B in Peirce's rule is restricted to absurdity, giving the axiom schema <math>(\neg A \implies A) \implies A</math>, the scheme is equivalent to LEM over minimal logic.
# Weak law of the excluded middle (WLEM) is axiomatised <math>\neg A \vee \neg\neg A</math> and yields a system where disjunction behaves more like in classical logic than intuitionistic logic, i.e. the [[disjunction and existence properties]] don't hold, but where use of non-intuitionistic reasoning is marked by occurrences of double-negation in the conclusion. LEM entails but is not entailed by WLEM in minimal logic. WLEM is equivalent to the instance of [[De Morgan's law]] that distributes negation over conjunction: <math>\neg(A \land B) \iff (\neg A) \vee (\neg B)</math>.

===Symbolic representation===<!-- This section is linked from [[Barbershop paradox]] -->
In mathematics, the symbol used to represent a contradiction within a proof varies.<ref>{{Cite web|url=http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf|title=The Comprehensive LATEX Symbol List|last=Pakin|first=Scott|date=January 19, 2017|website=ctan.mirror.rafal.ca|access-date=2019-12-10}}</ref> Some symbols that may be used to represent a contradiction include ↯, Opq, <math>\Rightarrow \Leftarrow</math>, ⊥, <math>\leftrightarrow \ \!\!\!\!\!\!\!</math>/ , and ※; in any symbolism, a contradiction may be substituted for the truth value "[[False (logic)|false]]", as symbolized, for instance, by "0" (as is common in [[Boolean algebra]]). It is not uncommon to see [[Q.E.D.]], or some of its variants, immediately after a contradiction symbol. In fact, this often occurs in a proof by contradiction to indicate that the original assumption was proved false—and hence that its negation must be true.

=== The notion of contradiction in an axiomatic system and a proof of its consistency ===
In general, a [[consistency proof]] requires the following two things:

# An [[axiomatic system]]
# A demonstration that it is ''not'' the case that both the formula ''p'' and its negation ''~p'' can be derived in the system.

But by whatever method one goes about it, all consistency proofs would ''seem'' to necessitate the primitive notion of ''contradiction.'' Moreover, it ''seems'' as if this notion would simultaneously have to be "outside" the formal system in the definition of tautology.

When [[Emil Post]], in his 1921 "Introduction to a General Theory of Elementary Propositions", extended his proof of the consistency of the [[propositional calculus]] (i.e. the logic) beyond that of ''[[Principia Mathematica]]'' (PM), he observed that with respect to a ''generalized'' set of postulates (i.e. axioms), he would no longer be able to automatically invoke the notion of "contradiction"{{mdash}}such a notion might not be contained in the postulates:

{{quote|The prime requisite of a set of postulates is that it be consistent. Since the ordinary notion of consistency involves that of contradiction, which again involves negation, and since this function does not appear in general as a primitive in [the ''generalized'' set of postulates] a new definition must be given.<ref>Post 1921 "Introduction to a General Theory of Elementary Propositions" in van Heijenoort 1967:272.</ref>}}

Post's solution to the problem is described in the demonstration "An Example of a Successful Absolute Proof of Consistency", offered by [[Ernest Nagel]] and [[James R. Newman]] in their 1958 ''[[Gödel]]'s Proof''. They too observed a problem with respect to the notion of "contradiction" with its usual "truth values" of "truth" and "falsity". They observed that:

{{quote|The property of being a tautology has been defined in notions of truth and falsity. Yet these notions obviously involve a reference to something ''outside'' the formula calculus. Therefore, the procedure mentioned in the text in effect offers an ''interpretation'' of the calculus, by supplying a model for the system. This being so, the authors have not done what they promised, namely, "'''to define a property of formulas in terms of purely structural features of the formulas themselves'''". [Indeed] ... proofs of consistency which are based on models, and which argue from the truth of axioms to their consistency, merely shift the problem.<ref>boldface italics added, Nagel and Newman:109-110.</ref>}}

Given some "primitive formulas" such as PM's primitives S<sub>1</sub> V S<sub>2</sub> [inclusive OR] and ~S (negation), one is forced to define the axioms in terms of these primitive notions. In a thorough manner, Post demonstrates in PM, and defines (as do Nagel and Newman, see below) that the property of ''tautologous'' – as yet to be defined – is "inherited": if one begins with a set of tautologous axioms (postulates) and a [[deduction system]] that contains [[substitution (logic)|substitution]] and [[modus ponens]], then a ''consistent'' system will yield only tautologous formulas.

On the topic of the definition of ''tautologous'', Nagel and Newman create two [[mutually exclusive]] and [[Collectively exhaustive events|exhaustive]] classes K<sub>1</sub> and K<sub>2</sub>, into which fall (the outcome of) the axioms when their variables (e.g. S<sub>1</sub> and S<sub>2</sub> are assigned from these classes). This also applies to the primitive formulas. For example: "A formula having the form S<sub>1</sub> V S<sub>2</sub> is placed into class K<sub>2</sub>, if both S<sub>1</sub> and S<sub>2</sub> are in K<sub>2</sub>; otherwise it is placed in K<sub>1</sub>", and "A formula having the form ~S is placed in K<sub>2</sub>, if S is in K<sub>1</sub>; otherwise it is placed in K<sub>1</sub>".<ref>Nagel and Newman:110-111</ref>

Hence Nagel and Newman can now define the notion of ''[[tautology (logic)|tautologous]]'': "a formula is a tautology if and only if it falls in the class K<sub>1</sub>, no matter in which of the two classes its elements are placed".<ref>Nagel and Newman:111</ref> This way, the property of "being tautologous" is described—without reference to a model or an interpretation.

{{quote|For example, given a formula such as ~S<sub>1</sub> V S<sub>2</sub> and an assignment of K<sub>1</sub> to S<sub>1</sub> and K<sub>2</sub> to S<sub>2</sub> one can evaluate the formula and place its outcome in one or the other of the classes. The assignment of K<sub>1</sub> to S<sub>1</sub> places ~S<sub>1</sub> in K<sub>2</sub>, and now we can see that our assignment causes the formula to fall into class K<sub>2</sub>. Thus by definition our formula is not a tautology.}}

Post observed that, if the system were inconsistent, a deduction in it (that is, the last formula in a sequence of formulas derived from the tautologies) could ultimately yield S itself. As an assignment to variable S can come from either class K<sub>1</sub> or K<sub>2</sub>, the deduction violates the inheritance characteristic of tautology (i.e., the derivation must yield an evaluation of a formula that will fall into class K<sub>1</sub>). From this, Post was able to derive the following definition of inconsistency—''without the use of the notion of contradiction'':

{{quote|Definition. ''A system will be said to be inconsistent if it yields the assertion of the unmodified variable p [S in the Newman and Nagel examples].''}}

In other words, the notion of "contradiction" can be dispensed when constructing a proof of consistency; what replaces it is the notion of "mutually exclusive and exhaustive" classes. An axiomatic system need not include the notion of "contradiction".<ref name=jstor1921 >Emil L. Post [https://www.jstor.org/stable/2370324 (1921) Introduction to a General Theory of Elementary Propositions] ''American Journal of Mathematics'' '''43''' (3):163—185 (1921)  The Johns Hopkins University Press </ref>{{rp|177}}