Hierarchies of sets and functions play a central role in many areas of mathematical logic and theoretical computer science — e.g. the analytical hierarchy in descriptive set theory, the arithmetical hierarchy in computability theory, the fast growing hierarchy in proof theory, and the polynomial hierarchy in computational complexity theory.  This talk will explore how results which yield the non-collapse of several of these hierarchies are related simultaneously to incompleteness phenomena and to the formalization of paradoxes familiar from other philosophical contexts.  A central tool will be the application of the Arithmetized Completeness Theorem to obtain first-order interpretations of higher-order notions such as truth and satisfaction.

© UC Irvine School of Social Sciences - 3151 Social Sciences Plaza, Irvine, CA 92697-5100 - 949.824.2766