Ω-consistent theory


Ω-consistent theory

In mathematical logic, an ω-consistent (or omega-consistent, also called numerically segregativeW.V.O. Quine, "Set Theory and its Logic"] ) theory is a theory (collection of sentences) that is not only (syntactically) consistent (that is, does not prove a contradiction), but also avoids proving certain infinite combinations of sentences that are intuitively contradictory. The name is due to Kurt Gödel, who introduced the concept in the course of proving the incompleteness theorem.

Definition

If "T" is a theory that interprets arithmetic (that is, there is a way to understand some of its objects of discourse as natural numbers), then "T" is ω-inconsistent (also called numerically insegregative) if, for some property "P" of natural numbers (defined by a formula in the language of "T"), "T" proves "P"(0), "P"(1), "P"(2), and so on (that is, for every natural number "n", "T" proves that "P"("n") holds), but "T" also proves that there is some natural number "n" such that "P"("n") "fails". This may not lead directly to an outright contradiction, because "T" may not be able to prove for any "specific" value of "n" that "P"("n") fails, only that there "is" such an "n".

"T" is ω-consistent if it is "not" ω-inconsistent.

There is a weaker but closely related property of Sigma_1-soundness. A theory "T" is Sigma_1-sound (or 1-consistent, in another terminology) if every Sigma^0_1-sentence [ The definition of this symbolism can be found at arithmetical hierarchy.] provable in "T" is true in the standard model of arithmetic mathbb N (i.e., the structure of the usual natural numbers with addition and multiplication). If "T" is strong enough to formalize a reasonable model of computation, Sigma_1-soundness is equivalent to demanding that whenever "T" proves that a computer program "C" halts, then "C" actually halts. Every ω-consistent theory is Sigma_1-sound, but not vice versa.

More generally, we can define an analogous concept for higher levels of the arithmetical hierarchy. If Γ is a set of arithmetical sentences (typically Sigma^0_n for some "n"), a theory "T" is Γ-sound if every Γ-sentence provable in "T" is true in the standard model. When Γ is the set of all arithmetical formulas, Γ-soundness is called just (arithmetical) soundness.If the language of "T" consists "only" of the language of arithmetic (as opposed to, for example, set theory), then a sound system is one whose model can be thought of as the set omega, the usual set of mathematical natural numbers. The case of general "T" is different, see ω-logic below.

Sigma_n-soundness has the following computational interpretation: if the theory proves that a program "C" using a Sigma_{n-1}-oracle halts, then "C" actually halts.

Examples

* Write PA for the theory Peano arithmetic, and Con(PA) for the statement of arithmetic that formalizes the claim "PA is consistent". Con(PA) could be of the form "For every natural number "n", "n" is not the Gödel number of a proof from PA that 0=1". (This formulation uses 0=1 instead of a direct contradiction; that gives the same result, because PA certainly proves ¬0=1, so if it proved 0=1 as well we would have a contradiction, and on the other hand, if PA proves a contradiction, then it proves anything, including 0=1.)

Now, assuming PA is really consistent, it follows that PA + ¬Con(PA) is also consistent, for if it were not, then PA would prove Con(PA) (since an inconsistent theory proves every sentence), contradicting Gödel's second incompleteness theorem. However, PA + ¬Con(PA) is "not" ω-consistent. This is because, for any particular natural number "n", PA + ¬Con(PA) proves that "n" is not the Gödel number of a proof that 0=1 (PA itself proves that fact; the extra assumption ¬Con(PA) is not needed). However, PA + ¬Con(PA) proves that, for "some" natural number "n", "n" "is" the Gödel number of such a proof (this is just a direct restatement of the claim ¬Con(PA) ).

In this example, the axiom ¬Con(PA) is Σ1, hence the system PA + ¬Con(PA) is in fact Σ1-unsound, not just ω-inconsistent.


*

Let "T" be PA together with the axioms "c" ≠ "n" for each natural number "n", where "c" is a new constant added to the language. Then "T" is arithmetically sound (as any nonstandard model of PA can be expanded to a model of "T"), but ω-inconsistent (as it proves exists x,c=x, and "c" ≠ "n" for every number "n").


* Σ1-sound ω-inconsistent theories using only the language of arithmetic can be constructed as follows. Let "I"Σ"n" be the subtheory of PA with the induction schema restricted to Σ"n"-formulas, for any "n" > 0. The theory "I"Σ"n" + 1 is finitely axiomatizable, let thus "A" be its single axiom, and consider the theory "T" = "I"Σ"n" + ¬"A". We can assume that "A" is an instance of the induction schema, which has the form::forall w, [B(0,w)landforall x,(B(x,w) o B(x+1,w)) oforall x,B(x,w)] .:If we denote the formula::forall w, [B(0,w)landforall x,(B(x,w) o B(x+1,w)) o B(n,w)] :by "P"("n"), then for every natural number "n", the theory "T" (actually, even the pure predicate calculus) proves "P"("n"). On the other hand, "T" proves the formula exists x, eg P(x), because it is logically equivalent to the axiom ¬"A". Therefore "T" is ω-inconsistent.:It is possible to show that "T" is Π"n" + 3-sound. In fact, it is Π"n" + 3-conservative over the (obviously sound) theory "I"Σ"n". The argument is more complicated (it relies on the provability of the Σ"n" + 2-reflection principle for "I"Σ"n" in "I"Σ"n" + 1).
* Let ω-Con(PA) be the arithmetical sentence formalizing the statement "PA is ω-consistent". Then the theory PA + ¬ω-Con(PA) is unsound (Σ3-unsound, to be precise), but ω-consistent. The argument is similar to the first example: a suitable version of the Hilbert-Bernays-Löb derivability conditions holds for the "provability predicate" ω-Prov("A") = ¬ω-Con(PA + ¬"A"), hence it satisfies an analogue of Gödel's second incompleteness theorem.

ω-logic

The concept of theories of arithmetic whose integers are the true mathematical integers is captured by ω-logic. Let "T" be a theory in a countable language which includes a predicate "N"("x") for the set of natural numbers, as well as a name for each natural number "n". ω-logic includes all axioms and rules of the usual first-order predicate logic, and the infinitary ω-rule::If "P"("n") is a theorem for every natural number "n", then forall x,(N(x) o P(x)) is also a theorem.An ω-model of "T" is a model of "T" in which "N" is interpreted by the set ω of the mathematical natural numbers, and each number "n" is interpreted by itself. The ω-rule is valid in every ω-model. As a corollary to the omitting types theorem, the converse also holds: the theory "T" has an ω-model if and only if it is consistent in ω-logic.

There is an obvious connection of ω-logic to ω-consistency. A theory consistent in ω-logic is also ω-consistent (and arithmetically sound). The converse is false, consistency in ω-logic is a much stronger notion than ω-consistency. However, the following characterization holds: a theory is ω-consistent if and only if its closure under "unnested" applications of the ω-rule is consistent.

Relation to other consistency principles

If the theory "T" is recursively axiomatizable, ω-consistency has the following characterization, due to C. Smoryński: [Craig Smoryński, "doi-inline|10.2307/2274450|Self-reference and modal logic", Springer, Berlin, 1985.] :"T" is ω-consistent if and only if T+mathrm{RFN}_T+mathrm{Th}_{Pi^0_2}(mathbb N) is consistent.Here, mathrm{Th}_{Pi^0_2}(mathbb N) is the set of all Π02-sentences valid in the standard model of arithmetic, and mathrm{RFN}_T is the uniform reflection principle for "T", which consists of the axioms:forall x,(mathrm{Prov}_T(ulcornervarphi(dot x)urcorner) ovarphi(x))for every formula varphi with one free variable. In particular, a finitely axiomatizable theory "T" in the language of arithmetic is ω-consistent if and only if "T" + PA is Sigma^0_2-sound.

Notes


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • ω-consistent theory — In mathematical logic, an ω consistent (or omega consistent, also called numerically segregative[1]) theory is a theory (collection of sentences) that is not only (syntactically) consistent (that is, does not prove a contradiction), but also… …   Wikipedia

  • Theory (mathematical logic) — This article is about theories in a formal language, as studied in mathematical logic. For other uses, see Theory (disambiguation). In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. Usually… …   Wikipedia

  • Theory of mind — is the ability to attribute mental states beliefs, intents, desires, pretending, knowledge, etc. to oneself and others and to understand that others have beliefs, desires and intentions that are different from one s own.[1] Though there are… …   Wikipedia

  • Consistent hashing — is a special kind of hashing. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped. By using consistent hashing, only K / n keys need to be remapped on average, where K is the… …   Wikipedia

  • Consistent histories — Quantum mechanics Uncertainty principle …   Wikipedia

  • Theory — The word theory has many distinct meanings in different fields of knowledge, depending on their methodologies and the context of discussion.In science a theory is a testable model of the manner of interaction of a set of natural phenomena,… …   Wikipedia

  • Consistent estimator — {T1, T2, T3, …} is a sequence of estimators for parameter θ0, the true value of which is 4. This sequence is consistent: the estimators are getting more and more concentrated near the true value θ0; at the same time, these estimators are biased.… …   Wikipedia

  • Theory of conjoint measurement — The theory of conjoint measurement (also known as conjoint measurement or additive conjoint measurement) is a general, formal theory of continuous quantity. It was independently discovered by the French economist Gerard Debreu (1960) and by the… …   Wikipedia

  • consistent — [[t]kənsɪ̱stənt[/t]] ♦♦♦ 1) ADJ GRADED Someone who is consistent always behaves in the same way, has the same attitudes towards people or things, or achieves the same level of success in something. Becker has never been the most consistent of… …   English dictionary

  • Theory of everything — A theory of everything (TOE) is a putative theory of theoretical physics that fully explains and links together all known physical phenomena. Initially, the term was used with an ironic connotation to refer to various overgeneralized theories.… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.