Statement of The Theorem
Tennenbaum's theorem states that no countable nonstandard model of PA is recursive. Moreover, neither the addition nor the multiplication of such a model can be recursive. The strategy for proving Tennenbaum's Theorem is to assume that there exists a recursive non-standard model of PA and then show that this leads to a contradiction. This may be achieved by constructing a non-recursive set S and then showing - under the assumption that such a recursive non-standard model exists - that S is recursive, leading to a contradiction. Such a non-recursive set S must involve non-standard elements and be constructible for any non-standard model of PA
Read more about this topic: Tennenbaum's Theorem
Famous quotes containing the words statement of the, statement of, statement and/or theorem:
“Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individual’s sovereignty.”
—Mario Vargas Llosa (b. 1936)
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (1859–1952)
“A sentence is made up of words, a statement is made in words.... Statements are made, words or sentences are used.”
—J.L. (John Langshaw)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)