Where are we working when we prove metamathematical theorems? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T23:23:24Z http://mathoverflow.net/feeds/question/11699 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11699/where-are-we-working-when-we-prove-metamathematical-theorems Where are we working when we prove metamathematical theorems? Zev Chonoles 2010-01-13T21:49:05Z 2010-01-14T16:00:26Z <p>I am posting my comment from <a href="http://mathoverflow.net/questions/8853/what-assumptions-and-methodology-do-metaproofs-of-logic-theorems-use-and-employ" rel="nofollow">this question</a> as a separate question, as was recommended to me. (EDIT: I'm sorry if it ended up being too similar a question, I just wanted to phrase it in the terminology I think of it in)</p> <p>First, let me mention that I agree with Hilbert's <a href="http://en.wikipedia.org/wiki/Formalism%5F%28mathematics%29" rel="nofollow">formalism</a> - when we make the claim "X is true", it is really a <em>shorthand</em> for: "If we label certain strings of symbols 'true', and we label certain rules for symbol manipulation 'truth-preserving', then we can manipulate our initial strings using our rules to reach X". If someone disagrees with our choice of initial strings, or our choice of manipulation rules (which, together, I'll call a "system"), then they will obviously come to some different conclusions. Now, mathematicians happen to have preferences about which systems to study, and those preferences are often motivated by apparent <em>analogies</em> between those systems and the real world, but no system is "right" or "wrong". </p> <p>I realize that this is not everyone's view of mathematics, but I wanted to explain my reasoning before asking my question:</p> <p>In what system do logicians usually "prove" metamathematical theorems - i.e., claims about systems? As I mentioned, all theorems, metamathematical or otherwise, are really of the form "In the system Y, X is true." The potential problem I feel with some results like Godel's theorems is that X is a claim about systems which are not necessarily consistent with Y - how does this make sense? </p> http://mathoverflow.net/questions/11699/where-are-we-working-when-we-prove-metamathematical-theorems/11734#11734 Answer by Charles Stewart for Where are we working when we prove metamathematical theorems? Charles Stewart 2010-01-14T08:36:58Z 2010-01-14T08:36:58Z <p>Real Logicians(*) use primitive recursive arithmetic as their metatheory. As a purely equational, and so unquantified, theory, it is agnostic about the distinction between classical and intuitionistic logic. It has enough power to support the kind of inferences about logical structure that are needed, and not much more. And it is very well understood.</p> <p>(*): If you will excuse even more flippancy: some logicians are even more real, and use even weaker metatheories like exponential function arithmetic. And many logicians are slightly less real, and use conservative extensions of PRA, with logical languages, such as the theory RCA0 used as a base theory in reverse mathematics, which uses the language of second-order arithmetic. The danger of using strong theories, is that one thinks one is doing logic, but is really doing formalised mathematics.</p> http://mathoverflow.net/questions/11699/where-are-we-working-when-we-prove-metamathematical-theorems/11756#11756 Answer by François G. Dorais for Where are we working when we prove metamathematical theorems? François G. Dorais 2010-01-14T14:50:11Z 2010-01-14T16:00:26Z <p>There are many flavors of "meta" in logic. Most make very minimal use of the metatheory. For example, the Montague Reflection Principle in Set Theory says the following: </p> <blockquote> <p><strong>Metatheorem.</strong> For every formula $\phi(x)$ of the language of Set Theory, the following is provable: If $\phi(a)$ is true then there is an ordinal $\alpha$ such that $a \in V_\alpha$ and $V_\alpha \vDash \phi(a)$.</p> </blockquote> <p>This is in fact an infinite collection of theorems, one for each formula $\phi(x)$. Gödel's theorem prevents ZFC from proving all of these instances at the same time. The proof of this metatheorem is by induction on the length of $\phi(x)$. The requirements on the metatheory are very minimal, all you need is enough combinatorics to talk about formulas, proofs, and enough induction to make sense of it all. This is by far the most common flavor of "meta" in logic. There really is not much to it. Most logicians don't worry about the metatheory in this context. Indeed, it is often irrelevant and, like most mathematicians, logicians usually believe in the natural numbers with full induction.</p> <p>However, sometimes there is need for a much stronger metatheory. For example, the metatheory of Model Theory is usually taken to be ZFC. Gödel's Completeness Theorem is a nice contrasting example.</p> <blockquote> <p><strong>Completeness Theorem.</strong> Every consistent theory is satisfiable.</p> </blockquote> <p>Recall that a theory is consistent if one cannot derive a contradiction form it, while a theory is satisfiable if it has a model. The consistency of a theory is a purely syntactic notion. When the theory is effective, consistency can be expressed in simple arithmetical terms in a manner similar to the one discussed above. However, satisfiability is not at all of this form since the models of a theory are typically infinite structures. This is why this theorem is usually stated in ZFC. For the Completeness Theorem, one can often get by with substantially less. For example, the system WKL<sub>0</sub> of second-order arithmetic suffices to prove the Completeness Theorem for countable theories (that exist in the metaworld in question), but such a weak metatheory would be nothing more than a major inconvenience for model theorists.</p> <p>Sometimes there are multiple choices of metatheory and no consensus on which is most appropriate. This happens in the case of Forcing in Set Theory, which has three common points of view:</p> <ul> <li><p>Forcing is a way to extend a countable transitive model of ZFC' to a larger model of ZFC' with different properties. Here ZFC' is a finite approximation to ZFC, which makes this statement non-vacuous in ZFC because of the Reflection Principle above.</p></li> <li><p>Forcing is a way to talk about truth in an alternate universe of sets. Here, the alternate universe is often taken to be a Boolean-valued model, formalized within the original universe.</p></li> <li><p>Forcing is an effective way to transform a contradiction some type of extensions of ZFC into contradictions within ZFC itself. Here, ZFC could be replaced by an extension of ZFC.</p></li> </ul> <p>The last point of view, which is the least common, is essentially arithmetical since it only talks about proofs. The second point of view is well suited for hard-core platonists who believe in one true universe of sets. The first point of view, which is probably most popular, essentially takes ZFC as a metatheory much like model theorists do.</p> <p>Since there is no consensus, set theorists will often talk as if both $V$ and its forcing extension $V[G]$ are absolutely real universes of sets. Although this point of view is hard to justify formally, it is possible to makes sense of it using any one of the three viewpoints above and it has the advantage that it makes it easier to express ideas that go into forcing constructions, which is what set theorists really want to talk about.</p> <p>Finally, the idea of analyzing which systems prove the consistency of other systems is very common in logic. In Set Theory, these systems often take the form of large cardinal axioms. In Second-Order Arithmetic these systems often take the form of comprehension principles. In First-Order Arithmetic these systems often take the form of induction principles. Together these form an incredibly long consistency strength hierarchy stretching from extremely weak basic arithmetical facts to incredibly deep large cardinal axioms. A very significant part of logic deals with studying this hierarchy and, as Andrej Bauer commented, logicians are usually very aware of where they are sitting in this hierarchy when proving metatheorems.</p>