Consistency Totally Explained

Everything about Inconsistency totally explained

In traditional Aristotelian logic, consistency is a semantic concept meaning that two or more propositions are simultaneously true under some interpretation.
   In modern logic there's a syntactic definition that also fits the complex mathematical theories developed since Frege's Begriffsschrift (1879): a set of statements are called consistent with respect to a certain logical calculus (also called a logical system or a formal system), if no formula of the form 'P and not-P' is derivable from those statements by the rules of the calculus. That is to say that the theory is free from contradictions and that P and not-P are not both theorems of that system.
   If these two definitions are equivalent for a particular logical calculus, then the system is said to have a complete set of rules. The crucial step in the proofs of completeness of the sentential calculus by Paul Bernays in 1918 and Emil Post in 1921, and the proof of the completeness of predicate calculus by Kurt Godel in 1930 is to show that the system's syntactic consistency implies its semantic consistency.
   A consistency proof is a mathematical proof that a logical system 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 fell to Gödel's insight, as expressed in his two incompleteness theorems, that sufficiently strong proof theories can't prove their own consistency.
   Although consistency can be proved by means of model theory, it's 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's one) implies the consistency of the calculus: since there's obviously no cut-free proof of falsity, there's no contradiction in general.

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're 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 can't 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're consistent;

Essentially incomplete theories. In addition, it has recently been discovered that there's 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

Phi

in first-order logic is consistent (written Con

Phi

) if and only if there's no formula

phi

such that

Phi vdash phi

and

Phi vdash lnotphi

. Otherwise

Phi

is inconsistent and is written Inc

Phi

Phi

is said to be simply consistent iff for no formula

phi

Phi

are both

phi

and the negation of

phi

theorems of

Phi

Phi

is said to be absolutely consistent or Post consistent iff at least one formula of

Phi

isn't a theorem of

Phi

Phi

is said to be maximally consistent if and only if for every formula

phi

, if Con

Phi cup phi

then

phi in Phi

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 	o phi  vDash Phi

can be verified by induction on formulas.

Further Information

Get more info on 'Inconsistency'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://consistency.totallyexplained.com">Consistency Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.