Equiconsistent
   HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, two
theories A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be s ...
are equiconsistent if the consistency of one theory implies the consistency of the other theory, and vice versa. In this case, they are, roughly speaking, "as consistent as each other". In general, it is not possible to prove the absolute consistency of a theory ''T''. Instead we usually take a theory ''S'', believed to be consistent, and try to prove the weaker statement that if ''S'' is consistent then ''T'' must also be consistent—if we can do this we say that ''T'' is ''consistent relative to S''. If ''S'' is also consistent relative to ''T'' then we say that ''S'' and ''T'' are equiconsistent.


Consistency

In mathematical logic, formal theories are studied as mathematical objects. Since some theories are powerful enough to model different mathematical objects, it is natural to wonder about their own consistency. Hilbert proposed a
program Program, programme, programmer, or programming may refer to: Business and management * Program management, the process of managing several related projects * Time management * Program, a part of planning Arts and entertainment Audio * Progra ...
at the beginning of the 20th century whose ultimate goal was to show, using mathematical methods, the consistency of mathematics. Since most mathematical disciplines can be reduced to
arithmetic Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
, the program quickly became the establishment of the consistency of arithmetic by methods formalizable within arithmetic itself. Gödel's incompleteness theorems show that Hilbert's program cannot be realized: if a consistent recursively enumerable theory is strong enough to formalize its own
metamathematics Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics (and perhaps the creation of the ter ...
(whether something is a proof or not), i.e. strong enough to model a weak fragment of arithmetic (
Robinson arithmetic In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q is ...
suffices), then the theory cannot prove its own consistency. There are some technical caveats as to what requirements the formal statement representing the metamathematical statement "The theory is consistent" needs to satisfy, but the outcome is that if a (sufficiently strong) theory can prove its own consistency then either there is no computable way of identifying whether a statement is even an axiom of the theory or not, or else the theory itself is inconsistent (in which case it can prove anything, including false statements such as its own consistency). Given this, instead of outright consistency, one usually considers relative consistency: Let ''S'' and ''T'' be formal theories. Assume that ''S'' is a consistent theory. Does it follow that ''T'' is consistent? If so, then ''T is consistent relative to S''. Two theories are equiconsistent if each one is consistent relative to the other.


Consistency strength

If ''T'' is consistent relative to ''S'', but ''S'' is not known to be consistent relative to ''T'', then we say that ''S'' has greater consistency strength than ''T''. When discussing these issues of consistency strength the metatheory in which the discussion takes places needs to be carefully addressed. For theories at the level of second-order arithmetic, the reverse mathematics program has much to say. Consistency strength issues are a usual part of
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, since this is a recursive theory that can certainly model most of mathematics. The most widely used set of axioms of set theory is called ZFC. When a set-theoretic statement is said to be equiconsistent to another , what is being claimed is that in the metatheory (
Peano Arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
in this case) it can be proven that the theories ZFC+ and ZFC+ are equiconsistent. Usually,
primitive recursive arithmetic Primitive recursive arithmetic (PRA) is a quantifier-free formalization of the natural numbers. It was first proposed by Norwegian mathematician , reprinted in translation in as a formalization of his finitist conception of the foundations of ar ...
can be adopted as the metatheory in question, but even if the metatheory is ZFC or an extension of it, the notion is meaningful. The method of
forcing Forcing may refer to: Mathematics and science * Forcing (mathematics), a technique for obtaining independence proofs for set theory *Forcing (recursion theory), a modification of Paul Cohen's original set theoretic technique of forcing to deal with ...
allows one to show that the theories ZFC, ZFC+CH and ZFC+¬CH are all equiconsistent (where CH denotes the continuum hypothesis). When discussing fragments of ZFC or their extensions (for example, ZF, set theory without the axiom of choice, or ZF+AD, set theory with the axiom of determinacy), the notions described above are adapted accordingly. Thus, ZF is equiconsistent with ZFC, as shown by Gödel. The consistency strength of numerous combinatorial statements can be calibrated by
large cardinal In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least Î ...
s. For example: * the negation of Kurepa's hypothesis is equiconsistent with the existence of an inaccessible cardinal, * the non-existence of special \omega_2- Aronszajn trees is equiconsistent with the existence of a
Mahlo cardinal In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. Mahlo cardinals were first described by . As with all large cardinals, none of these varieties of Mahlo cardinals can be proven to exist by ZFC (assuming ZFC is consist ...
, * the non-existence of \omega_2- Aronszajn trees is equiconsistent with the existence of a
weakly compact cardinal In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by ; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the standard axioms of set theory. (Tarski originally ...
.*


See also

* Large cardinal property


References

*
Akihiro Kanamori is a Japanese-born American mathematician. He specializes in set theory and is the author of the monograph on large cardinal property, large cardinals, ''The Higher Infinite''. He has written several essays on the history of mathematics, especia ...
(2003). ''
The Higher Infinite ''The Higher Infinite: Large Cardinals in Set Theory from their Beginnings'' is a monograph in set theory by Akihiro Kanamori, concerning the history and theory of large cardinals, infinite sets characterized by such strong properties that their ex ...
''. Springer. {{Metalogic Large cardinals Mathematical logic