1983/06/01 by E. A. Cichon, Stanley S. Wainer · 1 citation
Computer Science · Mathematics · #Logic, programming, and type systems #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge #Mathematics #Cardinality (data modeling) #Countable set #Successor cardinal #Discrete mathematics #Natural number #Majorization #Hierarchy #Limit (mathematics) #Rank (graph theory) #Sequence (biology) #Set (abstract data type) #Function (biology) #Cardinal number (linguistics) #Combinatorics #Computer science
paper · doi:10.2307/2273557
openalex publication_date 1983/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
We give here an elementary proof of a recent result of Girard [4] comparing the rates of growth of the two principal (and extreme) examples of a spectrum of “majorization hierarchies”—i.e. hierarchies of increasing number-theoretic functions, indexed by (systems of notations for) initial segments I of the countable ordinals so that if α < β ∈ I then the β th function dominates the α th one at all but finitely-many positive integers x . Hardy [5] was perhaps the first to make use of a majorization hierarchy—the H α 's below—in “exhibiting” a set of reals with cardinality ℵ 1 . More recently such hierarchies have played important roles in mathematical logic because they provide natural classifications of recursive functions according to their computational complexity. (All the functions considered here are “honest” in the sense that the size of their values gives a measure of the number of steps needed to compute them.) The hierarchies we are concerned with fall into three main classes depending on their mode of generation at successor stages, the other crucial parameter being the initial choice of a particular (standard) fundamental sequence λ 0 < λ 1 < λ 2 < … to each limit ordinal λ under consideration which, by a suitable diagonalization, will then determine the generation at stage λ . Our later comparisons will require the use of a “large” initial segment I of proof-theoretic ordinals, extending as far as the “Howard ordinal”. However we will postpone a precise description of these ordinals and their associated fundamental sequences until later.