Ordinal notation (original) (raw)
In mathematical logic and set theory, an ordinal notation is a partial function mapping the set of all finite sequences of symbols, themselves members of a finite alphabet, to a countable set of ordinals. A Gödel numbering is a function mapping the set of well-formed formulae (a finite sequence of symbols on which the ordinal notation function is defined) of some formal language to the natural numbers. This associates each well-formed formula with a unique natural number, called its Gödel number. If a Gödel numbering is fixed, then the subset relation on the ordinals induces an ordering on well-formed formulae which in turn induces a well-ordering on the subset of natural numbers. A recursive ordinal notation must satisfy the following two additional properties:
| Property | Value |
|---|---|
| dbo:abstract | In mathematical logic and set theory, an ordinal notation is a partial function mapping the set of all finite sequences of symbols, themselves members of a finite alphabet, to a countable set of ordinals. A Gödel numbering is a function mapping the set of well-formed formulae (a finite sequence of symbols on which the ordinal notation function is defined) of some formal language to the natural numbers. This associates each well-formed formula with a unique natural number, called its Gödel number. If a Gödel numbering is fixed, then the subset relation on the ordinals induces an ordering on well-formed formulae which in turn induces a well-ordering on the subset of natural numbers. A recursive ordinal notation must satisfy the following two additional properties: 1. * the subset of natural numbers is a recursive set 2. * the induced well-ordering on the subset of natural numbers is a recursive relation There are many such schemes of ordinal notations, including schemes by Wilhelm Ackermann, Heinz Bachmann, Wilfried Buchholz, Georg Cantor, Solomon Feferman, Gerhard Jäger, Isles, Pfeiffer, Wolfram Pohlers, Kurt Schütte, Gaisi Takeuti (called ordinal diagrams), Oswald Veblen. Stephen Cole Kleene has a system of notations, called Kleene's O, which includes ordinal notations but it is not as well behaved as the other systems described here. Usually one proceeds by defining several functions from ordinals to ordinals and representing each such function by a symbol. In many systems, such as Veblen's well known system, the functions are normal functions, that is, they are strictly increasing and continuous in at least one of their arguments, and increasing in other arguments. Another desirable property for such functions is that the value of the function is greater than each of its arguments, so that an ordinal is always being described in terms of smaller ordinals. There are several such desirable properties. Unfortunately, no one system can have all of them since they contradict each other. (en) |
| dbo:wikiPageExternalLink | https://archive.org/details/prooftheoryintro0000pohl http://www.cs.fsu.edu/~levitz/ords.ps |
| dbo:wikiPageID | 6108552 (xsd:integer) |
| dbo:wikiPageLength | 15374 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123338742 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Mathematical_notation dbr:Computable_function dbc:Proof_theory dbr:Mathematical_logic dbr:Church–Kleene_ordinal dbr:Epsilon_numbers_(mathematics) dbr:Gaisi_Takeuti dbr:Georg_Cantor dbr:Ordinal_analysis dbr:Ordinal_arithmetic dbr:Arity dbr:Stephen_Cole_Kleene dbr:Feferman–Schütte_ordinal dbr:Wilhelm_Ackermann dbr:Gödel_numbering dbr:Heinz_Bachmann dbr:Large_Veblen_ordinal dbr:Nonrecursive_ordinal dbr:Oswald_Veblen dbr:Range_of_a_function dbr:Bachmann–Howard_ordinal dbr:Ackermann_ordinal dbc:Ordinal_numbers dbr:Transfinite_recursion dbr:PostScript dbr:Solomon_Feferman dbr:Kurt_Schütte dbr:Natural_number dbr:Ordinal_number dbr:Recursive_set dbr:Recursively_enumerable_set dbr:Set_theory dbr:Kleene's_O dbr:Small_Veblen_ordinal dbr:First_uncountable_ordinal dbr:Feferman-Schutte_ordinal dbr:Takeuti–Feferman–Buchholz_ordinal dbr:Veblen_ordinal_(disambiguation) dbr:Large_countable_ordinals |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Main dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Mathematical_notation dbc:Proof_theory dbc:Ordinal_numbers |
| gold:hypernym | dbr:Function |
| rdf:type | yago:WikicatOrdinalNumbers yago:Abstraction100002137 yago:DefiniteQuantity113576101 yago:Measure100033615 yago:Number113582013 yago:OrdinalNumber113597280 dbo:Disease |
| rdfs:comment | In mathematical logic and set theory, an ordinal notation is a partial function mapping the set of all finite sequences of symbols, themselves members of a finite alphabet, to a countable set of ordinals. A Gödel numbering is a function mapping the set of well-formed formulae (a finite sequence of symbols on which the ordinal notation function is defined) of some formal language to the natural numbers. This associates each well-formed formula with a unique natural number, called its Gödel number. If a Gödel numbering is fixed, then the subset relation on the ordinals induces an ordering on well-formed formulae which in turn induces a well-ordering on the subset of natural numbers. A recursive ordinal notation must satisfy the following two additional properties: (en) |
| rdfs:label | Ordinal notation (en) |
| owl:sameAs | freebase:Ordinal notation yago-res:Ordinal notation wikidata:Ordinal notation https://global.dbpedia.org/id/4t2hv |
| prov:wasDerivedFrom | wikipedia-en:Ordinal_notation?oldid=1123338742&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Ordinal_notation |
| is dbo:wikiPageRedirects of | dbr:Feferman's_function dbr:Buchholz's_notation dbr:Ordinal_diagram dbr:Ordinal_diagrams dbr:Ordinal_notations |
| is dbo:wikiPageWikiLink of | dbr:Limit_ordinal dbr:Notation dbr:Ordinal_collapsing_function dbr:Gaisi_Takeuti dbr:Gentzen's_consistency_proof dbr:Ordinal_analysis dbr:Ordinal_arithmetic dbr:Computable_ordinal dbr:Psi_(Greek) dbr:Wilhelm_Ackermann dbr:Large_countable_ordinal dbr:History_of_mathematical_notation dbr:Hyperarithmetical_theory dbr:Feferman's_function dbr:Buchholz_psi_functions dbr:Kleene's_O dbr:Buchholz's_notation dbr:Ordinal_diagram dbr:Ordinal_diagrams dbr:Ordinal_notations |
| is foaf:primaryTopic of | wikipedia-en:Ordinal_notation |