Consistent.html

For other uses, see Consistency (disambiguation).

In logic, a theory is consistent if it does not contain a contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if it has a model; this is the sense used in traditional Aristotelian logic, although in contemporary mathematical logic the term satisfiable is used instead. The syntactic definition states that a theory is consistent if there is no formula P such that both P and its negation are provable from the axioms of the theory under its associated deductive system.

If these semantic and syntactic definitions are equivalent for a particular logic, the logic is complete. The completeness of sentential calculus was proved by Paul Bernays in 1918 and Emil Post in 1921, while the completeness of predicate calculus was proved by Kurt Gödel in 1930. Stronger logics, such as second-order logic, are not complete.

A consistency proof is a mathematical proof that a particular theory is consistent. The early development of mathematical proof theory was driven by the desire to provide finitary consistency proofs for all of mathematics as part of Hilbert's program. Hilbert's program was strongly impacted by incompleteness theorems, which showed that sufficiently strong proof theories cannot prove their own consistency.

Although consistency can be proved by means of model theory, it is often done in a purely syntactical way, without any need to reference some model of the logic. The cut-elimination (or equivalently the normalization of the underlying calculus if there is one) implies the consistency of the calculus: since there is obviously no cut-free proof of falsity, there is no contradiction in general.

1 Consistency and completeness
2 Formulas
3 See also
4 References

Consistency and completeness

The fundamental results relating consistency and completeness were proven by Kurt Gödel:

Gödel's completeness theorem shows that any consistent first-order theory is complete with respect to a maximal consistent set of formulae which are generated by means of a proof search algorithm.
Gödel's incompleteness theorems show that theories capable of expressing their own provability relation and of carrying out a diagonal argument are capable of proving their own consistency only if they are inconsistent. Such theories, if consistent, are known as essentially incomplete theories.

By applying these ideas, we see that we can find first-order theories of the following four kinds:

Inconsistent theories, which have no models;
Theories which cannot talk about their own provability relation, such as Tarski's axiomatisation of point and line geometry, and Presburger arithmetic. Since these theories are satisfactorily described by the model we obtain from the completeness theorem, such systems are complete;
Theories which can talk about their own consistency, and which include the negation of the sentence asserting their own consistency. Such theories are complete with respect to the model one obtains from the completeness theorem, but contain as a theorem the derivability of a contradiction, in contradiction to the fact that they are consistent;
Essentially incomplete theories.

In addition, it has recently been discovered that there is a fifth class of theory, the self-verifying theories, which are strong enough to talk about their own provability relation, but are too weak to carry out Gödelian diagonalisation, and so which can consistently prove their own consistency. However as with any theory, a theory proving its own consistency provides us with no interesting information, since inconsistent theories also prove their own consistency.

Formulas

A set of formulas $Φ$ in first-order logic is consistent (written Con $Φ$ ) if and only if there is no formula $φ$ such that $\Phi \vdash \phi$ and $\Phi \vdash \lnot\phi$ . Otherwise $Φ$ is inconsistent and is written Inc $Φ$ .

$Φ$ is said to be simply consistent iff for no formula $φ$ of $Φ$ are both $φ$ and the negation of $φ$ theorems of $Φ$ .

$Φ$ is said to be absolutely consistent or Post consistent iff at least one formula of $Φ$ is not a theorem of $Φ$ .

$Φ$ is said to be maximally consistent if and only if for every formula $φ$ , if Con $\Phi \cup \phi$ then $\phi \in \Phi$ .

$Φ$ is said to contain witnesses if and only if for every formula of the form $\exists x \phi$ there exists a term $t$ such that $(\exists x \phi \to \phi {t \over x}) \in \Phi$ . See First-order logic.

Basic results

1. The following are equivalent:

(a) Inc $Φ$

(b) For all $\phi,\; \Phi \vdash \phi.$

2. Every satisfiable set of formulas is consistent, where a set of formulas $Φ$ is satisfiable if and only if there exists a model $\mathfrak{I}$ such that $\mathfrak{I} \vDash \Phi$ .

3. For all $Φ$ and $φ$ :

(a) if not $\Phi \vdash \phi$ , then Con $\Phi \cup \{\lnot\phi\}$ ;

(b) if Con $Φ$ and $\Phi \vdash \phi$ , then Con $\Phi \cup \{\phi\}$ ;

4. Let $Φ$ be a maximally consistent set of formulas and contain witnesses. For all $φ$ and $ψ$ :

(a) if $\Phi \vdash \phi$ , then $\phi \in \Phi$ ,

(b) either $\phi \in \Phi$ or $\lnot \phi \in \Phi$ ,

(d) if $(\phi\to\psi) \in \Phi$ and $\phi \in \Phi$ , then $\psi \in \Phi$ ,

(e) $\exists x \phi \in \Phi$ if and only if there is a term $t$ such that $\phi{t \over x}\in\Phi$ .

Henkin's theorem

Let $Φ$ be a maximally consistent set of formulas containing witnesses.

Define a binary relation on the set of S-terms $t_0 \sim t_1 \!$ if and only if $\; t_0 = t_1 \in \Phi$ ; and let $\overline t \!$ denote the equivalence class of terms containing $t \!$ ; and let $T_{\Phi} := \{ \; \overline t \; |\; t \in T^S \}$ where $T^S \!$ is the set of terms based on the symbol set $S \!$ .

Define the S-structure $\mathfrak T_{\Phi}$ over $T_{\Phi} \!$ the term-structure corresponding to $Φ$ by:

(1) For $n$ -ary $R \in S$ , $R^{\mathfrak T_{\Phi}} \overline {t_0} \ldots \overline {t_{n-1}}$ if and only if $\; R t_0 \ldots t_{n-1} \in \Phi$ ,

(2) For $n$ -ary $f \in S$ , $f^{\mathfrak T_{\Phi}} (\overline {t_0} \ldots \overline {t_{n-1}}) := \overline {f t_0 \ldots t_{n-1}}$ ,

(3) For $c \in S$ , $c^{\mathfrak T_{\Phi}}:= \overline c$ .

Let $\mathfrak I_{\Phi} := (\mathfrak T_{\Phi},\beta_{\Phi})$ be the term interpretation associated with $Φ$ , where $\beta _{\Phi} (x) := \bar x$ .

$(*) \;$ For all

φ

, $\; \mathfrak I_{\Phi} \vDash \phi$ if and only if $\; \phi \in \Phi$ .

Sketch of proof

There are several things to verify. First, that $\sim$ is an equivalence relation. Then, it needs to be verified that (1), (2), and (3) are well defined. This falls out of the fact that $\sim$ is an equivalence relation and also requires a proof that (1) and (2) are independent of the choice of $t_0, \ldots ,t_{n-1}$ class representatives. Finally, $\mathfrak I_{\Phi} \vDash \Phi$ can be verified by induction on formulas.

References

The Cambridge Dictionary of Philosophy, consistency
H.D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic
Jevons, W.S., Elementary Lessons in Logic, 1870

Logic portal

v • d • e

Logic

History and core topics

History	General · Chinese · Greek · Indian · Islamic

Core topics	Reason · Philosophical logic · Philosophy of logic · Mathematical logic · Metalogic · Logic in computer science

Key concepts and logics

Reasoning	Deduction · Induction · Abduction

Informal	Proposition · Inference · Argument · Validity · Cogency · Term logic · Critical thinking · Fallacies · Syllogism · Argumentation theory

Philosophy of logic	Platonic realism · Logical atomism · Logicism · Formalism · Nominalism · Fictionalism · Realism · Intuitionism · Constructivism · Finitism

Mathematical	Formal language · Formal grammar · Formal system · Deductive system · Formal proof · Formal interpretation · Formal semantics · Formula · Wff · Set · Element · Class · Axiom · Rule of inference · Relation · Theorem · Logical consequence · Consistency · Soundness · Completeness · Decidability · Satisfiability · Independence · Set theory · Axiomatic system · Proof theory · Model theory · Recursion theory · Type theory · Syntax

Propositional	Boolean functions · Monadic predicate calculus · Propositional calculus · Logical connectives · Quantifiers · Truth tables

Predicate	First-order · Quantifiers · Second-order

Modal	Alethic · Axiologic · Deontic · Doxastic · Epistemic · Temporal

Other non classical	Computability · Fuzzy · Linear · Relevance · Non-monotonic

Controversies

Paraconsistent logic · Dialetheism · Intuitionistic logic · Paradoxes · Antinomies · Is logic empirical?

Key figures

Alfarabi · Algazel · Alkindus · Al-Razi · Aristotle · Averroes · Avicenna · Boole · Cantor · Carnap · Church · Dharmakirti · Dignāga · Frege · Gentzen · Kanada · Gödel · Gotama · Hilbert · Ibn al-Nafis · Ibn Hazm · Ibn Taymiyyah · Kripke · Mozi · Nagarjuna · Pāṇini · Peano · Peirce · Putnam · Quine · Russell · Skolem · Suhrawardi · Tarski · Turing · Whitehead · Zadeh

Lists

Topics	General · Basic · Mathematical logic · Boolean algebra · Set theory

Other	Logicians · Rules of inference · Paradoxes · Fallacies · Logic symbols

Portal · Category · WikiProject · Logic stubs · Mathlogic stubs · Cleanup · Noticeboard

Gory • Gory • Wczasy • Wczasy • Wczasy • Teslar • Unikalne • Gryzmoly • Gryzmoly • Wpisy • Imiennik • Imiennik • Imiennik • Imiennik • Imiennik