Ordinal Analysis - Definition

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:

    ... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.
    Adrienne Rich (b. 1929)

    Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.
    The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)

    It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.”
    Jane Adams (20th century)