Richard Zach

Ordinal Logics

Long time no blog. Sorry, been busy planning my 2006 world tour. Dates will be announced shortly.

While you’re waiting, there’s a neat little piece of metamathematics that should be more widely known than it is. You all know that if T is a consistent theory satisfying the usual assumptions, then Con(T) is undecidable in T. So T + Con(T) is properly stronger than T, and itself consistent and satisfies the conditions of Gödel’s theorems. Now a very interesting question is: what happens if you keep adding consistency statements to T, i.e., look at the union of T, T + Con(T), T + Con(T) + Con(T + Con(T)), etc.?

This question was first asked (and answered) by Turing in his 1938 Princeton dissertation. The answer is, if you do this ω + 1 many times, you get all true Π10 sentences of arithmetic (if you start with T = PA). It was subsequently cleared up by Feferman, and exteneded to progressions of theories where you add other undecidable sentences to T, such as the reflection principle (Prov(A) → A). The tricky part is defining the provability predicate for theories in these progressions; you have to use Kleene’s recursive ordinals to do this for transfinite ordinals.

If you haven’t seen this, look it up in Torkel Franzén’s book, or the original papers.

Alan M. Turing, 1939, ‘Systems of logic defined by ordinals’, Proceedings of the London Mathematical Society, ser. 2, 45:161-228

Solomon Feferman, 1962. Transfinite recursive progressions of axiomatic theories. Journal of Symbolic Logic, 27:259-316.

Posted

in

by

Richard Zach

Tags:

Comments

4 responses to “Ordinal Logics”

  1. Anonymous

    It might be usefull to those interested in these topics to have a look at Franzel’s short “introductory” article (BSL, septembre 2004. Online, free) :Transfinite progression : a second look at completness . It is noticed there, that Turing’s result (the one you mention in your post) might be misleading as stated in view of the following non-progressive version : For any theory T and any Pi_1 true sentence Phi, there is a Sigma_1 defining-formula Theta of T (ie roughly such that Phi(x) iff x is a axiom of T) yielding consistency extension T+CON(Theta) of T in which Phi is provable.This gives a taste of what is going on at limit stages when defining the “provability” predicate in the “progressive version”.For more palatable results, involving “reflexive extension” (which are just “generalisations” of “consistency extensions”), I found the following introduction helpfull :Lev Becklemishev: Provability and reflection( online, free). There, you might be intereted in learning that extending Elementary Arithmetics with a certain simple reflection principle yields Peano arithmetics (both stated in a language with “exp”, and EA being PA with induction restricted to Delta_0 formula, if I remenber well).More general results, involving theories of truth as expressive devices for reflection, are to be found in Feferman’s “Reflecting on Incompletness” (JSL, 1991. Well, that’s not free).(Sorry, I’m not a native speaker) Posted by Henri Galinon

    Reply
  2. Anonymous

    Richard wrote:”You all know that if T is a consistent theory satisfying the usual assumptions, then Con(T) is undecidable in T. So T + Con(T) is properly stronger than T, and itself consistent and satisfies the conditions of Gödel’s theorems. Now a very interesting question is: what happens if you keep adding consistency statements to T, i.e., look at the union of T, T + Con(T), T + Con(T) + Con(T + Con(T)), etc.?”One has to be a little careful here. If the base theory T happens to be unsound, though consistent, T + Con(T) may be inconsistent. You need to assume that T is 1-consistent (Sigma_1 sound). Anyway, what I really wanted to say was just to add a couple of references:For a beginner interested in this stuff, I recommend Feferman’s entry “Ordinal logics”, in Routledge Encyclopedia of Philosophy, as a first starting point.Also, Feferman’s ‘Turing in the Land of O(z)’, in R. Herken (ed.) The Universal Turing Machine: A Half-Century Survey, Oxford: Oxford University Press, (1988), 113–47, is very readable. Best, Panu Posted by Panu Raatikainen

    Reply
  3. Anonymous

    Just a bit of pedantrty; Turing’s completeness result does not say that you can get all true pi-1 sentences by adding consistency statements omega+1 times. If you want all of them, you need to go a bit further. this is because you can only squeeze in a new pi-1 truths at the limit ordinals – the trick is to pick perverse fundamental sequences for the limit ordinals in a way that makes the whole completeness proof utterly irrelevant to any epistemological concerns – and thus you need to go up to omega*omega.Things do get epistemologically interesting when instead of arbitrary progressions we concentrate on autonomous progressions. In an autonomous progression you’re allowed to go to the theory T_alpha only when you’ve already proved that alpha is really a notation for an ordinal in an earlier theory. This, unlike Turing’s and Feferman’s progressions, does give you a formal theory. Fefrman’s analysis of predicative acceptability and the determination of Gamma_0 (the Schutte-Feferman ordinal) as the proof theoretical ordinal of predicativity was obtained by means of such autonomous progressions. These autonomous progressions and the interesting philosophical questions they give rise to or help analyzing are the subject of Franzen’s Inexhaustibility book (which does contain the non-autonomous completeness results, too). Well, that’s it for now, I’m off to the Kurt Godel conference in Edinburgh University. Posted by Aatu Koskensilta

    Reply
  4. Anonymous

    Concerning the 2006 world tour: thanks for a great talk in Edinburgh yesterday. Posted by Ole Thomassen Hjortland

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *