Ordinal logic

Ordinal logic

In mathematics, ordinal logic is a logic associated with an ordinal number by recursively adding elements to a sequence of previous logics.[1][2] The concept was introduced in 1938 by Alan Turing in his PhD dissertation at Princeton in view of Gödel's incompleteness theorems.[3][1]

While Gödel showed that every system of logic suffers from some form of incompleteness, Turing focused on a method so that from a given system of logic a more complete system may be constructed. By repeating the process a sequence L1, L2, … of logics is obtained, each more complete than the previous one. A logic L can then be constructed in which the provable theorems are the totality of theorems provable with the help of the L1, L2, … etc. Thus Turing showed how one can associate a logic with any constructive ordinal.[3]

References

  1. ^ a b Solomon Feferman, Turing in the Land of O(z) in "The universal Turing machine: a half-century survey" by Rolf Herken 1995 ISBN 3211826378 page 111
  2. ^ Concise Routledge encyclopedia of philosophy 2000 ISBN 0415223644 page 647
  3. ^ a b Alan Turing, Systems of Logic Based on Ordinals Proceedings London Mathematical Society Volumes 2–45, Issue 1, pp. 161–228.[1]

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Logic and the philosophy of mathematics in the nineteenth century — John Stillwell INTRODUCTION In its history of over two thousand years, mathematics has seldom been disturbed by philosophical disputes. Ever since Plato, who is said to have put the slogan ‘Let no one who is not a geometer enter here’ over the… …   History of philosophy

  • Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia

  • Ordinal notation — In mathematical logic and set theory, an ordinal notation is a finite sequence of symbols from a finite alphabet which names an ordinal number according to some scheme which gives meaning to the language. There are many such schemes of ordinal… …   Wikipedia

  • Ordinal analysis — In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. The field was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that… …   Wikipedia

  • Ordinal number — This article is about the mathematical concept. For number words denoting a position in a sequence ( first , second , third , etc.), see Ordinal number (linguistics). Representation of the ordinal numbers up to ωω. Each turn of the spiral… …   Wikipedia

  • Ordinal de Hartogs — En théorie des ensembles, l ordinal de Hartogs d un ensemble A désigne le plus petit ordinal qui ne s injecte pas dans A. Son existence utilise le remplacement et se démontre sans l axiome de choix, contrairement au théorème de Zermelo qui… …   Wikipédia en Français

  • logic, history of — Introduction       the history of the discipline from its origins among the ancient Greeks to the present time. Origins of logic in the West Precursors of ancient logic       There was a medieval tradition according to which the Greek philosopher …   Universalium

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

  • Large countable ordinal — In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of… …   Wikipedia

  • Church–Kleene ordinal — In mathematics, the Church–Kleene ordinal, , is a large countable ordinal. It is the smallest non recursive ordinal. It is named after Alonzo Church and S. C. Kleene. References Church, Alonzo; Kleene, S. C. (1937), Formal definitions in the… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”