In
mathematical logic, an ω-consistent (or omega-consistent, also called numerically segregative)
W. V. O. Quine W. may refer to:
* SoHo (Australian TV channel) (previously W.), an Australian pay television channel
* ''W.'' (film), a 2008 American biographical drama film based on the life of George W. Bush
* "W.", the fifth track from Codeine's 1992 EP ''Bar ...
(1971), ''Set Theory and Its Logic''. theory is a
theory (collection of
sentences) that is not only (syntactically)
consistent
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent i ...
(that is, does not prove a
contradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
), 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
A theory ''T'' is said to
interpret the
language of arithmetic if there is a translation of formulas of arithmetic into the language of ''T'' so that ''T'' is able to prove the basic axioms of the
natural numbers under this translation.
A ''T'' that interprets arithmetic is ω-inconsistent 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 standard natural number ''n'', ''T'' proves that ''P''(''n'') holds), but ''T'' also proves that there is some natural number ''n'' (necessarily
nonstandard in any
model
A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure.
Models c ...
for ''T'') such that ''P''(''n'') ''fails''. This may not generate a contradiction within ''T'' 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 Σ
1-soundness. A theory ''T'' is Σ
1-sound (or 1-consistent, in another terminology) if every Σ
01-sentence provable in ''T'' is true in the standard model of arithmetic 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
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An esp ...
, Σ
1-soundness is equivalent to demanding that whenever ''T'' proves that a
Turing machine ''C'' halts, then ''C'' actually halts. Every ω-consistent theory is Σ
1-sound, but not vice versa.
More generally, we can define an analogous concept for higher levels of the
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
. If Γ is a set of arithmetical sentences (typically Σ
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 ω, the usual set of mathematical natural numbers. The case of general ''T'' is different, see
ω-logic below.
Σ
''n''-soundness has the following computational interpretation: if the theory proves that a program ''C'' using a Σ
''n''−1-
oracle halts, then ''C'' actually halts.
Examples
Consistent, ω-inconsistent theories
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) (''reductio''), 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.
Arithmetically sound, ω-inconsistent theories
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
, 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
::
If we denote the formula
::