|
Feferman–Schütte Ordinal
In mathematics, the Feferman–Schütte ordinal (Γ0) is a large countable ordinal. It is the proof-theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion. It is named after Solomon Feferman and Kurt Schütte, the former of whom suggested the name Γ0. There is no standard notation for ordinals beyond the Feferman–Schütte ordinal. There are several ways of representing the Feferman–Schütte ordinal, some of which use ordinal collapsing functions: \psi(\Omega^\Omega), \theta(\Omega), \varphi_\Omega(0), or \varphi(1,0,0). Definition The Feferman–Schütte ordinal can be defined as the smallest ordinal that cannot be obtained by starting with 0 and using the operations of ordinal addition and the Veblen functions ''φ''''α''(''β''). That is, it is the smallest ''α'' such that ''φ''''α''(0) = ''α''. Properties This ordinal is sometimes said to be the first impredicative ordinal, though this is controversial, partly because there ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proof-theoretic Ordinal
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory. In addition to obtaining the proof-theoretic ordinal of a theory, in practice ordinal analysis usually also yields various other pieces of information about the theory being analyzed, for example characterizations of the classes of provably recursive, hyperarithmetical, or \Delta^1_2 functions of the theory. History The field of ordinal analysis was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that the proof-theoretic ordinal of Peano arithmetic is ε0. See Gentzen's consistency proof. Definition Ordinal analysis concerns true, effective (recursive) theories that can interpret a sufficient por ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 relevance to proof theory still have computable ordinal notations (see ordinal analysis). However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not (for reasons somewhat analogous to the unsolvability of the halting problem); various more-concrete ways of defining ordinals that definitely have notations are available. Since there are only countably many notations, all ordinals with notations are exhausted well below the first uncountable ordinal ω1; their supremum is called ''Church–Kleene'' ω1 or ω (not to be confused with the first uncountable ordinal, ω1), described below. Ordinal numbers below ω are the ''recursive'' ordinals (see below). Countable ordinals larger than this m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arithmetical Transfinite Recursion
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. A precursor to second-order arithmetic that involves third-order parameters was introduced by David Hilbert and Paul Bernays in their book ''Grundlagen der Mathematik''. The standard axiomatization of second-order arithmetic is denoted by Z2. Second-order arithmetic includes, but is significantly stronger than, its first-order counterpart Peano arithmetic. Unlike Peano arithmetic, second-order arithmetic allows quantification over sets of natural numbers as well as numbers themselves. Because real numbers can be represented as ( infinite) sets of natural numbers in well-known ways, and because second-order arithmetic allows quantification over such sets, it is possible to formalize the real numbers in second-order arithmetic. For this reason, se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solomon Feferman
Solomon Feferman (December 13, 1928July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. In addition to his prolific technical work in proof theory, computability theory, and set theory, he was known for his contributions to the history of logic (for instance, via biographical writings on figures such as Kurt Gödel, Alfred Tarski, and Jean van Heijenoort) and as a vocal proponent of the philosophy of mathematics known as predicativism, notably from an anti- platonist stance. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to the United States after World War I and had met and married in New York. Neither parent had any advanced education. The family moved to Los Angeles, where Feferman graduated from high school at age 16. He received his B.S. from the California Institute of Technology in 1948, and in 1957 his Ph.D. in mathematics from the University of California, Berkeley, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kurt Schütte
Kurt Schütte (14 October 1909 – 18 August 1998) was a German mathematician who worked on proof theory and ordinal analysis. The Feferman–Schütte ordinal, which he showed to be the precise ordinal bound for predicativity, is named after him. He was the doctoral advisor of 16 students, including Wolfgang Bibel, Wolfgang Maaß, Wolfram Pohlers, and Martin Wirsing. Publications * ** ''Beweistheorie'', Springer, Grundlehren der mathematischen Wissenschaften, 1960; new edition trans. into English as ''Proof Theory'', Springer-Verlag 1977 * ''Vollständige Systeme modaler und intuitionistischer Logik'', Springer 1968 * with Wilfried Buchholz: ''Proof Theory of Impredicative Subsystems of Analysis'', Bibliopolis, Naples 1988 * with Helmut Schwichtenberg''Mathematische Logik'' in Fischer, Hirzebruch et al. (eds.) ''Ein Jahrhundert Mathematik 1890-1990'', Vieweg 1990 References * * External links Kurt Schütteat the Mathematics Genealogy Project The Mathematics Genealogy Pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gaisi Takeuti
was a Japanese mathematician, known for his work in proof theory. After graduating from Tokyo University, he went to Princeton to study under Kurt Gödel. He later became a professor at the University of Illinois at Urbana–Champaign. Takeuti was president (2003–2009) of the Kurt Gödel Society, having worked on the book ''Memoirs of a Proof Theorist: Godel and Other Logicians''. His goal was to prove the consistency of the real numbers. To this end, Takeuti's conjecture speculates that a sequent formalisation of second-order logic In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory. First-order logic quantifies on ... has cut-elimination.. An erratum to this article was published in the same journal as . He is also known for his work on ordinal diagrams with Akiko Kino. Publications * * * 2013 Dover ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ordinal Collapsing Function
In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (Ordinal notation, notations for) certain Recursive ordinal, recursive large countable ordinals, whose principle is to give names to certain ordinals much larger than the one being defined, perhaps even Large cardinal property, large cardinals (though they can be replaced with Large countable ordinal#Beyond admissible ordinals, recursively large ordinals at the cost of extra technical difficulty), and then "collapse" them down to a system of notations for the sought-after ordinal. For this reason, ordinal collapsing functions are described as an Impredicativity, impredicative manner of naming ordinals. The details of the definition of ordinal collapsing functions vary, and get more complicated as greater ordinals are being defined, but the typical idea is that whenever the notation system "runs out of fuel" and cannot name a certain ordinal, a much larger ordin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ordinal Addition
In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations. Addition The sum of two well-ordered sets and is the ordinal representing the variant of lexicographical order with least significant position first, on the union of the Cartesian products and . This way, every element of is smaller than every element of , comparisons within keep the order they already have, and likewise for comparisons within . The definition of addition can also be given by transfinite recursion on . When the right ad ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Veblen Function
In mathematics, the Veblen functions are a hierarchy of normal functions ( continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If ''φ''0 is any normal function, then for any non-zero ordinal ''α'', ''φ''''α'' is the function enumerating the common fixed points of ''φ''''β'' for ''β''<''α''. These functions are all normal. Veblen hierarchy In the special case when ''φ''0(''α'')=ω''α'' this family of functions is known as the Veblen hierarchy. The function ''φ''1 is the same as the ε function: ''φ''1(''α'')= ε''α''. If then .M. Rathjen[...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Predicativity
In mathematics, logic and philosophy of mathematics, something that is impredicative is a self-referencing definition. Roughly speaking, a definition is impredicative if it invokes (mentions or quantifies over) the set being defined, or (more commonly) another set that contains the thing being defined. There is no generally accepted precise definition of what it means to be predicative or impredicative. Authors have given different but related definitions. The opposite of impredicativity is predicativity, which essentially entails building stratified (or ramified) theories where quantification over a type at one 'level' results in types at a new, higher, level. A prototypical example is intuitionistic type theory, which retains ramification (without the explicit levels) so as to discard impredicativity. The 'levels' here correspond to the number of layers of dependency in a term definition. Russell's paradox is a famous example of an impredicative construction—namely the set o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nachum Dershowitz
Nachum Dershowitz () is an Israeli computer scientist, known e.g. for the Dershowitz–Manna ordering and the Path_ordering_(term_rewriting), multiset path ordering used to prove Rewriting#Termination, termination of term rewrite systems. Education and career He obtained his B.Sc., ''summa cum laude'', in 1974 in computer science and applied mathematics from Bar-Ilan University, and his Ph.D. in 1979 in Applied Mathematics from the Weizmann Institute of Science. From 1978, he worked at the Department of Computer Science of the University of Illinois at Urbana-Champaign, and was hired as a full professor of the Tel Aviv University (School of Computer Science) in 1998. He was a guest researcher at Weizmann Institute, INRIA, ENS Cachan, Microsoft Research, and the universities of Stanford University, Stanford, Université de Paris Orsay, Paris, Hebrew University, Jerusalem, University of Chicago, Chicago, and Tsinghua University, Beijing. He received the Herbrand Award for Distingu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of Symbolic Computation
The ''Journal of Symbolic Computation'' is a Peer review, peer-reviewed monthly scientific journal covering all aspects of symbolic computation published by Academic Press and then by Elsevier. It is targeted to both mathematicians and computer scientists. It was established in 1985 by Bruno Buchberger, who served as its Editor-in-chief, editor until 1994. The journal covers a wide variety of topics, including: * Computer algebra system, Computer algebra, for which it is considered the top journal * Computational geometry * Automated theorem proving * Applications of symbolic computation in education, science, and industry According to the ''Journal Citation Reports'', its 2020 impact factor is 0.847. The journal is abstracted and indexed by Scopus and the Science Citation Index. See also * ''Higher-Order and Symbolic Computation'' * International Symposium on Symbolic and Algebraic Computation References External links * {{Official website, http://www.elsevier.com/l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
