12
$\begingroup$

I am posting my comment from this question 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)

First, let me mention that I agree with Hilbert's formalism - when we make the claim "X is true", it is really a shorthand 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 analogies between those systems and the real world, but no system is "right" or "wrong".

I realize that this is not everyone's view of mathematics, but I wanted to explain my reasoning before asking my question:

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?

$\endgroup$
5
  • 2
    $\begingroup$ This question would make more sense, or would at least be easier to answer, if you provided a couple more examples of what you have in mind. Logicians are pretty well aware of what sort of meta-theory is necessary to prove various meta-theorems. $\endgroup$ Commented Jan 13, 2010 at 22:49
  • $\begingroup$ Perhaps reading the introduction to Gödel's paper would clarify things for that particular case. A nice translation can be found here: research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf $\endgroup$ Commented Jan 13, 2010 at 23:41
  • $\begingroup$ See this post on building blocks and then this continuation about the incompleteness theorems. In short, if you accept only string manipulation and induction you are basically stuck at PA, which is insufficient to prove the incompleteness theorem in a form that is 'internally' meaningful, because the sentence Con(S) can be imbued with meaning only if your meta-system can talk about Σ1-sets, at which point you effectively have the halting oracle. $\endgroup$
    – user21820
    Commented Apr 12, 2018 at 15:59
  • 1
    $\begingroup$ Historically, Godel was careful to use 'finitistic' and 'constructive' reasoning in proving his incompleteness theorems, so that it would be indisputable that Hilbert's goal was impossible to achieve. It is true that philosophically there are some initial assumptions that must be made otherwise we cannot even get started (as I sketch in the linked post), but practically all modern logicians think that ACA is sound, and ACA is sufficient to prove Godel's incompleteness theorems and completeness theorems. (And note that whether X is meaningful or not is irrelevant to what ACA proves about X.) $\endgroup$
    – user21820
    Commented Apr 12, 2018 at 16:05
  • $\begingroup$ A simple comment: Most metatheorems are proved in the same theory as theorems, only when studying proofs, in order typically to find minimal requirements, does one use weak theories. Thus i would say that the majority of metatheorems are proved and thought about in set theory, possibly with urelements. In fact mathematics is nowadays the foundation, language of science, in particular of metamathematics, and set theory being the standard FOM it is by default also the FOmetaM. Standard logic textbooks, eg Enderton's, are formulated in set theory, with rare remarks on the axioms used or needed. $\endgroup$
    – plm
    Commented Oct 16 at 19:40

2 Answers 2

12
$\begingroup$

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:

Metatheorem. 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)$.

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.

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.

Completeness Theorem. Every consistent theory is satisfiable.

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 WKL0 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.

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:

  • 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.

  • 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.

  • 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.

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.

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.

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for your thorough response! I'm afraid my knowledge of logic and set theory was just barely enough to ask a good question, but unfortunately is not yet at the point where I can fully understand your answer :) I'll hit the books (and Wikipedia) and hopefully I will soon be able to appreciate it. $\endgroup$ Commented Jan 16, 2010 at 5:30
  • $\begingroup$ It's a good question, but difficult to answer as I illustrated. I guess the main point to retain is that "meta" usually means the first type, where the requirements are essentially just basic arithmetic. This is not always how things are actually done, but there is often a (somewhat impractical) way to do it using just basic arithmetic, as illustrated by the forcing example. $\endgroup$ Commented Jan 16, 2010 at 17:38
4
$\begingroup$

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.

(*): 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .