Should consistency be considered as a concept in the metatheory? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:51:11Z http://mathoverflow.net/feeds/question/55432 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55432/should-consistency-be-considered-as-a-concept-in-the-metatheory Should consistency be considered as a concept in the metatheory? godelian 2011-02-14T18:09:01Z 2011-02-15T11:10:58Z <p>Consider the statement: "ZFC is consistent". Normally this is considered at first sight as a statement in the metatheory. But if we follow Kunen's (informally) description of what the metatheory is (i.e., finitistic reasoning), there seem to be some problems to place that statement precisely at the metatheoretical level.</p> <p>First of all, since ZFC is not finitely axiomatizable, it seems the metatheory fails to absorb the theory ZFC as a whole, and instead we should first develop some finitely axiomatizable fragment of set theory within which we can correctly formulate the theory ZFC. </p> <p>But suppose we work with a finitely axiomatizable theory T. Does it make sense now to ask in the metatheory whether T is consistent? At first sight, the consistency of a theory as a concept supposes we can quantify over all possible formal proofs within the theory and assert that none of them actually ends in contradiction. But isn't this a set-theoretical analysis? Shouldn't we first develop some set theory and only then define set-theoretically the concept of consistency?</p> <p>Of course if T happens to have a finite model, we are inclined to assert, in the metatheory, that we can never find a proof of a contradiction. But instead of saying that T is consistent, shouldn't we just say that T has a finite model? Or is the conclusion of consistency from this a valid finitistic reasoning that should be part of the metatheory?</p> <p>Finally, what if T does not have a finite model? It seems to me that some intuitionistic approach should be taken in the metatheory, in the sense that concepts such as inconsistency are meaningless unless we can actually find a specific proof of a contradiction.</p> http://mathoverflow.net/questions/55432/should-consistency-be-considered-as-a-concept-in-the-metatheory/55507#55507 Answer by François G. Dorais for Should consistency be considered as a concept in the metatheory? François G. Dorais 2011-02-15T11:10:58Z 2011-02-15T11:10:58Z <p>Most people regard induction and recursion as finitistic. As Andrej Bauer commented:</p> <blockquote> <p>Induction and recursion are rules which tell you how to do something. They do not presuppose any kind of infinity or anything like that.</p> </blockquote> <p>As a consequence, the standard weak metatheory used in practice is <a href="http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic" rel="nofollow">Primitive Recursive Arithmetic</a> (PRA). </p> <p>Although very weak, PRA is strong enough to formalize <a href="http://en.wikipedia.org/wiki/G%C3%B6del_numbering" rel="nofollow">Gödel coding</a>. Using such coding, the axioms of ZFC (to take a concrete example) can be enumerated and recognized by primitive recursive functions. One can also recognize formal proofs from ZFC axioms using a primitive recursive function. </p> <p>Thus, there is a primitive recursive function \$B_{ZFC}(x,y)\$ which takes value \$0\$ if and only if the numeral \$x\$ is a Gödel code for a formal proof of the Gödel coded sentence \$y\$ from the axioms of ZFC. Taking \$y\$ to be the Gödel code for your favorite contradiction, say \$0 = 1\$. The consistency of ZFC can be expressed as \$\forall x (B_{ZFC}(x,y) \neq 0)\$. As Carl Mummert pointed out, this is a simple \$\Pi^0_1\$ statement in PRA. While we don't know whether it is true or false, it is a perfectly meaningful statement from the finitistic point of view.</p>