Cation–pi interaction: Difference between revisions
Jump to navigation
Jump to search
en>Bibcode Bot m Adding 0 arxiv eprint(s), 9 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot |
en>BD2412 m →Nature of the cation-π interaction: Fixing links to disambiguation pages using AWB |
||
| Line 1: | Line 1: | ||
In [[mathematics]], specifically [[set theory]], an [[ordinal number|ordinal]] <math>\alpha</math> is said to be '''recursive''' if there is a [[recursive set|recursive]] [[well-order]]ing of a [[subset]] of the [[natural numbers]] having the [[order type]] <math>\alpha</math>. | |||
It is trivial to check that <math>\omega</math> is recursive, the [[successor ordinal|successor]] of a recursive ordinal is recursive, and the [[Set (mathematics)|set]] of all recursive ordinals is [[closure (mathematics)|closed]] downwards. The [[supremum]] of all recursive ordinals is called the [[Church-Kleene ordinal]] and denoted by <math>\omega^{CK}_1</math>. Indeed, an ordinal is recursive if and only if it is smaller than <math>\omega^{CK}_1</math>. Since there are only countably many recursive relations, there are also only [[countable|countably]] many recursive ordinals. Thus, <math>\omega^{CK}_1</math> is countable. | |||
The recursive ordinals are exactly the ordinals that have an [[ordinal notation]] in [[Kleene's O|Kleene's <math>\mathcal{O}</math>]]. | |||
==See also== | |||
*[[Arithmetical hierarchy]] | |||
*[[Large countable ordinals]] | |||
*[[Ordinal notation]] | |||
== References == | |||
* Rogers, H. ''The Theory of Recursive Functions and Effective Computability'', 1967. Reprinted 1987, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1 | |||
* Sacks, G. ''Higher Recursion Theory''. Perspectives in mathematical logic, Springer-Verlag, 1990. ISBN 0-387-19305-7 | |||
[[Category:Set theory]] | |||
[[Category:Computability theory]] | |||
[[Category:Ordinal numbers]] | |||
{{settheory-stub}} | |||
Revision as of 22:46, 24 December 2013
In mathematics, specifically set theory, an ordinal is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type .
It is trivial to check that is recursive, the successor of a recursive ordinal is recursive, and the set of all recursive ordinals is closed downwards. The supremum of all recursive ordinals is called the Church-Kleene ordinal and denoted by . Indeed, an ordinal is recursive if and only if it is smaller than . Since there are only countably many recursive relations, there are also only countably many recursive ordinals. Thus, is countable.
The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's .
See also
References
- Rogers, H. The Theory of Recursive Functions and Effective Computability, 1967. Reprinted 1987, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
- Sacks, G. Higher Recursion Theory. Perspectives in mathematical logic, Springer-Verlag, 1990. ISBN 0-387-19305-7