Definition
Ordinal analysis concerns true, effective (recursive) theories that can interpret a sufficient portion of arithmetic to make statements about ordinal notations. The proof theoretic ordinal of such a theory is the smallest recursive ordinal that the theory cannot prove is well founded — the supremum of all ordinals for which there exists a notation in Kleene's sense such that proves that is an ordinal notation. Equivalently, it is the supremum of all ordinals such that there exists a recursive relation on (the set of natural numbers) which well-orders it with ordinal and such that proves transfinite induction of arithmetical statements for .
The existence of any recursive ordinal which the theory fails to prove is well ordered follows from the bounding theorem, as the set of natural numbers which an effective theory proves to be ordinal notations is a set (see Hyperarithmetical theory). Thus the proof theoretic ordinal of a theory will always be a countable ordinal less than the Church-Kleene ordinal .
In practice, the proof theoretic ordinal of a theory is a good measure of the strength of a theory. 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.
Read more about this topic: Ordinal Analysis
Famous quotes containing the word definition:
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)