Qualifying Exam Syllabus

Richard Dore

Committee:
W. Hugh Woodin, John Steel, Leo Harrington (chair),
Luca Trevisan (computer science)


Major topic: Combinatorial Set Theory and Forcing (Foundations)

Rank, trees, and posets. Club and stationary sets. Fodor's lemma.
Martin's Axiom. Diamond and square. Kurepa, Aronszajn,and Suslin 
trees and lines. Delta system lemma. Partition properties and
Erdos-Rado theorem. Generic model theorem. Forcing relation.
Mixing and fullness lemmata. Completeness, chain conditions and
homgeneity. Con(not AC). Product and iterated forcing.
Con(MA + not CH). Levy Collapse. Easton forcing. Prikry forcing.
Proper Forcing.


Major topic: Model theory of Sets (Foundations)

Mostowski collapse. Reflection. Schoenfield absoluteness.
Ultapowers of V and elementary embeddings. extenders. Elementary
embedding and first order definitions of measurable, strong,
Woodin, superstrong, supercompact, and huge cardinals. Kunen's
Theorem. HOD models ZFC. L models ZFC + GCH + Diamond + Delta12
well ordering of the reals. Condensation. L[U] models ZFC + GCH +
Delta13 well ordering of the reals. Uniqueness of L[U].


Minor topic: Computational Complexity Theory (Applied Mathematics)

Definitions and containments of L, NL, P, NP, PH, and PSPACE.
Hierarchy theorems for DTIME, NTIME, and DSPACE. NP-completeness
of SAT, 3-SAT, 3-Coloring, vertex cover, and Hamiltonian cycle.
PSPACE completeness of TQBF and geography. Karp-Lipton. Savitch's
Theorem. Immerman-Szelepcsnyi. Interactive Proofs and IP = PSPACE.