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:
“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 (18591952)
“The most distinct and beautiful statement of any truth must take at last the mathematical form.”
—Henry David Thoreau (18171862)
“The new statement is always hated by the old, and, to those dwelling in the old, comes like an abyss of skepticism.”
—Ralph Waldo Emerson (18031882)
“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 (19131960)