Carnegie Mellon University

# Mathematical Sciences

## Mellon College of Science

We offer the following graduate level courses. Some courses are taught annually, while others are taught less frequently. For some courses, the content may vary as determined by the instructor.

Fall: 12 units
The study of formal logical systems which model the reasoning of mathematics, scientific disciplines, and everyday discourse. Propositional Calculus and First-order Logic. Syntax, axiomatic treatment, derived rules of inference, proof techniques, computer-assisted formal proofs, normal forms, consistency, independence, semantics, soundness, completeness, Lowenheim-Skolem Theorem, compactness, equality.
Prerequisites: 21-373 or 21-484 recommended.

Fall: 12 units
The axioms of ZFC, ordinal arithmetic, cardinal arithmetic including Kőnig's lemma, class length induction and recursion, the rank hierarchy, the Mostowski collapse theorem, the H(λ) hierarchy, the Δ1 absoluteness theorem, the absoluteness of wellfoundedness, the reflection theorem for hierarchies of sets, ordinal definability, the model HOD, relative consistency, Gödel's theorem that HOD is a model of ZFC, constructibility, Gödel's theorem that L is a model of ZFC + GCH, the Borel and Projective hierarchies and their effective versions, Suslin representations for Σ11, Π11 and Σ12, sets of reals, Shoenfield's absoluteness theorem, the complexity of the set of constructible reals, the combinatorics of club and stationary sets (including the diagonal intersection, the normality of the club filter and Fodor's lemma), Solovay's splitting theorem, model theoretic techniques commonly applied in set theory (e.g., elementary substructures, chains of models and ultrapowers), club and stationary subsets of [X]ω (including a generalization of Fodor's lemma and and connections with elementary substructures), Jensen's diamond principles and his proofs that they hold in L, Gregory's theorem, constructions of various kinds of uncountable trees (including Aronszajn, special, Suslin, Kurepa), Jensen's square principles and elementary applications, the basic theory of large cardinals (including inaccesssible, Mahlo, weakly compact and measurable cardinals), Scott's theorem that there are no measurable cardinals in L, Kunen's theorem that the only elementary embedding from V to V is the identity.
Prerequisites for 21-602
The minimum background for 21-602 is the equivalent of undergraduate set theory (e.g., 21-329) and the fundamentals of logic (e.g., 21-600). Students should arrive with a working knowledge of basic ordinal and cardinal arithmetic, Gödel's completeness theorem and the downward Loewenheim-Skolem theorem. An understanding of the statement of Gödel's incompleteness theorem is also assumed. (This theorem is mentioned in 21-600 but proved in 21-700.)

Spring: 12 units
Similarity types, structures; downward Lowenheim Skolem theorem; construction of models from constants, Henkin's omitting types theory, prime models; elementary chains of models, basic two cardinal theorems, saturated models, basic results on countable models including Ryll-Nardzewski's theorem; indiscernible sequences, Ehrenfeucht-Mostowski models; introduction to stability, rank functions, primary models, and a proof of Morley's categoricity theorem; basic facts about infinitary languages, computation of Hanf-Morley numbers. Prerequisites are a familiarity with the basic concepts of predicate calculus, up to Henkin's proof to Gdel's completeness theoremn, and some knowledge of naive set theory.

Spring: 12 units
Syllabus covers: models of computation,computable functions, solvable and unsolvable problems, reducibilities among problems, recursive and recursively enumerable sets, the recursion theorem, Post's problem and the Friedberg-Muchnik theorm, general degrees and r.e. degrees, the arithmetical hierarchy, the hyperarithmetical hierarchy,the analytical hierarchy, higher type recursion. Prerequiste: 21-300 or its equivalent.

Fall, 2 units
This seminar is required of first-time teaching assistants. Topics discussed are: getting started the first day, how to help students learn, lecturing, and grading. Each new teaching assistant is videotaped, and her or his performance is reviewed.

Spring, 1 unit
This seminar treats syllabus writing, lecturing, test design and homework assignments. The seminar is a prerequisite for students interested in teaching their own course.

Spring: 12 units
The structure of finitely generated abelian groups, the Sylow theorems, nilpotent and solvable groups, simplicity of alternating and projective special linear groups, free groups, the Neilsen-Schreier theorem. Vector spaces over division rings, field extensions, the fundamental Galois correspondence, algebraic closure. The Jacobson radical and the structure of semisimple rings. Time permitting, one of the following topics will be included: Wedderburn~s theorem on finite division rings, Frobenius~ Theorem. Prerequisite: Familiarity with the content of an undergraduate course on groups and rings.

12 units
Content varies. May be taken more than once if content is sufficiently different.
Past topics: Fall 2001: p-adic Analysis

6 units
A review of one-dimensional, undergraduate analysis, including a rigorous treatment of the following topics in the context of the real numbers: sequences, compactness, continuity, differentiation, Riemann integration. (Mini-course. Normally combined with 21-621.)

6 units
Construction of Lebesgue measure and the Lebesgue integral on the real line. Fatou's Lemma, the monotone convergence theorem, the dominated convergence theorem. (Mini-course. Normally combined with 21-620.)

12 units
Linear spaces, linear transformations, duality, bilinearity, inner-product spaces. Convexity. Norms, limits, compactness. Gradients of mappings, divergence and curl. Implicit Function Theorem. Constrained extrema. Spectral theory. Volume and surface integrals, Divergence Theorem.

Offered occasionally: 12 units
The complex plane, holomorphic functions, power series, complex integration, and Cauchy's Theorem. Calculus of residues. Additional topics may include conformal mappings and the application of complex transforms to differential equations.

Offered occasionally: 12 units
Content varies. May be taken more than once if content is sufficiently different.
Past topics:
Fall 2001: Classical Descriptive Set Theory

12 units
Basic concepts covered are existence and uniqueness of solutions, continuation of solutions, continuous dependence, and stability. For autonomous systems, topics included are: orbits, limit sets, Liapunov's direct method, and Poincar-Bendixson theory. For linear systems, topics included are: fundamental solutions, variation of constants, stability, matrix exponential solutions, and saddle points. Time permitting, one or more of the following topics will be covered: differential inequalities, boundary-value problems and Sturm-Liouville theory, Floquet theory.

12 units
This course serves as a broad introduction to Ordinary and Partial Differential Equations for beginning graduate students and advanced undergraduate students in mathematics, engineering, and the applied sciences. Mathematical sophistication in real analysis at the level of 21-355/356 is assumed. Topics include: essentials of Ordinary Differential Equations, origins of Partial Differential Equations, the study of model problems including the Poisson and Laplace equations, the heat equation, the transport equation, and the wave equation. 3 hrs. lec.

Fall: 12 units
This course explores methods of solving ordinary differential equations and introduction to partial differential equations; reviews elementary concepts, series, solutions, boundary value problems, eigenfunction expansions, and Fourier, Bessel, and Legrendre functions; and addresses calculus of variations. Solutions of classical partial differential equations of mathematical physics, including Laplace transformation and the method of separation of variables, will be covered in this course.

12 units
Prerequisites: knowledge of (undergraduate) real analysis and general topology (having taken 21-651, or consent of instructor)

Description

• Linear spaces: Hilbert spaces, Banach spaces, topological vector spaces
• Hilbert spaces: geometry, projections, Riesz Representation Theorem, bilinear and quadratic forms, orthonormal sets and Fourier series.
• Banach spaces: continuity of linear mappings, Hahn-Banach Theorem, uniform boundedness, open-mapping theorem. Closed operators, closed graph theorem.
• Dual spaces: weak and weak-star topologies (Banach-Alaoglu Theorem), reflexivity. Space of bounded continuous functions and its dual, dual of $L^{p}$, dual of $L^{\infty}$
• Linear operators and adjoints: basic properties, null spaces and ranges. Compact operators. Sequences of bounded linear operators: weak, strong and uniform convergence.
• Introduction to spectral theory: Notions of spectrum and resolvent set of bounded operators, spectral theory of compact operators. Time permitting: Fredholm Alternative.
• Time permitting: Stone-Weierstrass Theorem.

Fall: 12 units

• Finite and infinite sets, Axiom of Choice, Zorn lemma
• Topological Spaces (basics of open/closed sets, bases, countability, product spaces, quotient spaces)
• Continuity
• Connectedness, Compactness, Tychonoff Theorem (time permitting: Stone-Cech compactification)
• Separation Axioms, Urysohn Lemma and Tietze Extension Theorems, Urysohn Metrization Theorem)
• Metric Spaces (Cauchy sequences, completeness, Baire Category Theorem, completion, separability, sequential compactness, total boundedness, compactness, Arzela-Ascoli Theorem, partition of unity)
• Brouwer's Fixed Point Theorem

Fall: 12 units
Finite precision arithmetic, interpolation, spline approximation, numerical integration, numerical solution of linear and nonlinear systems of equations, optimization in finite dimensional spaces.

6 units
Forming and solving elliptic difference equations. Relaxation, conjugate gradient and multigrid solution algorithms. Discrete maximum principles and error estimates. Explicit and implicit difference schemes for parabolic equations and systems. Stability of difference schemes. Parabolic free boundary problems. Stefan problems. Stochastic algorithms.

6 units
Finite element algorithms for elliptic equations and systems. Overview of error analysis for finite elements. Finite elements for parabolic equations and error estimates. First-order hyperbolic equations and systems in one space variable. Shocks and numerical methods for shock capturing. Stability in hyperbolic problems. Extensions to more space variables. Finite element methods for second-order hyperbolic equations. Error estimates for hyperbolic problems.

6 units
Probability spaces: random experiments; sets and classes of sets; conditional probability. Random variables: operations/transformations of random variables, distributions and distribution functions; transforms of random variables and vectors. Independence: criteria for independence; functions of independent random variables; independent events; applications to occupancy problems and stochastic processes. Expectation: fundamental properties; integrals with respect to distribution functions; computation of expectations; moments of random variables and vectors; stochastic inequalities.

6 units
Convergence of random sequences: modes of convergence and relations among them; convergence under transformations; applications. Classical limit theorems: series of independent random variables; the strong law of large numbers; the central limit theorem; the law of the iterated logarithm; applications. Conditional expectation: expectation given a finite set of random variables; expectation as minimum mean squared error; conditional distributions; computational aspects. Martingales: fundamentals; stopping times; optional sampling theorems; martingale convergence theorems; Wald's identity; applications.

Fall: 12 units
An introduction to the theory and algorithms of linear and nonlinear programming with an emphasis on modern computational considerations. The simplex method and its variants, duality theory and sensitivity analysis. Large-scale linear programming. Optimality conditions for unconstrained nonlinear optimization. Newton's method, line searches, trust regions and convergence rates. Constrained problems, feasible-point methods, penalty and barrier methods, interior-point methods.

Spring: 12 units
Introduction to higher-order logic (type theory) with primary emphasis on the typed lambda-calculus. Syntax and semantics, lambda-notation, axiomatic treatment, axioms of Descriptions, Choice, and Infinity, weak completeness, weak compactness, standard and non-standard models. Computer-assisted formal proofs. Formalization of mathematics, definability of natural numbers, representability of recursive functions, Church's Thesis. Godel's Incompleteness Theorems, undecidability, undefinability.
Prerequisite: 21-300 or 21-600, or permission of instructor.

12 units
This course gives a broad introduction to Discrete Mathematics.
Topics covered include elementary enumeration and graph theory, generating functions and Ramsey Theory. Introductions to Extremal Combinatorics, including the Erdős-Ko-Rado, Kruskal-Katona and Turán Theorems as well as linear algebraic methods, and the Probabilistic Method, including alterations, the second moment method, the Lovász local lemma and correlation inequalities are also included.

12 units
This course is a sequel to 21-602 Set Theory. The main goal is to prove Solovay's theorem that Con(ZFC + an inaccessible cardinal) implies Con(ZF + DC + every set of reals is Lebesgue measurable). Topics covered include absoluteness theorems, Borel codes, the Levy collapse, product forcing, relative constructibility, and the basics of iterated forcing up to the consistency of Martin's Axiom.

12 units
The course concentrates in what is considered "main stream model theory" which is Shelah's classicfication theory (known also as Stability). Among the topics to be presented are stability, superstability, the theory of various notions of primeness, rank functions, forking calculus, the stability spectrum theorem, finite equivalence relations theorem, stable groups (up to and including the Macintyre-Cherlin-Shelah theorem on super-stable fields), and some elementary geometric model theory. If time permits also: basic facts about infinitary languages, computation of Hanf-Morley numbers; some of the Ax-Kochen-Ershov theory of model theory for fields with valuations (will apply this to solve Artin's conjecture).

12 units
Commutative ideal theory: localization, prime spectrum, integral dependence, free and projective modules, primary decomposition, Krull dimension, fractional ideals, Dedekind domains, Hilbert finite basis theorem, Hilbert Nullstellensatz, affine algebraic varieties, coordinatization. Valuation theory: normed fields, completion, p-adic fields, Ostrowski's theorem, valuations, discrete valuations, Hensel's lemma, local fields.
Prerequisite: 21-610.

12 units
Prerequisites: knowledge of (undergraduate) real analysis

Description

• Outer measure, measure, $\sigma$-algebras, Dynkin $\pi-\lambda$ Theorem, Carathéodory's Extension Theorem
• Borel measures, Lebesgue measure
• Measurable functions, Lebesgue integral (Monotone Convergence Theorem, Fatou's Lemma, Dominated Convergence Theorem)
• Modes of Convergence (Egoroff's Theorem, Lusin's Theorem)
• Product Measures (Fubini-Tonelli Theorems), n-dimensional Lebesgue integral
• Signed Measures (Hahn Decomposition, Jordan Decomposition, Radon-Nikodym Theorem, change of variables)
• Differentiation (Lebesgue Differentiation Theorem)
• $L^p$ Spaces (Hölder's inequality, Minkowskii's inequality, completeness, equiintegrability (uniform integrability), Vitali's convergence theorem)

12 units
Prerequisites: Undergraduate Probability 21-325 and 21-720 Measure Theory and Integration. In particular, the measure-theoretic prerequisites for this course include:

• Carathéodory's Extension Theorem;
• Classical convergence theorems (Dominated Convergence, Monotone Convergence, Fatou);
• Modes of convergence: in measure, almost everywhere, in $L^p$, and their relations to each other;
• Products of measurable spaces and Fubini-Tonelli theorems;

Description

• Probability spaces, random variables, expectation, independence, Borel-Cantelli lemmas.
• Kernels and product spaces, existence of probability measures on infinite product spaces, Kolmogorov's zero-one law.
• Weak and strong laws of large numbers, ergodic theorems, stationary sequences.
• Conditional expectation: characterization, construction and properties. Relation to kernels, conditional distribution, density.
• Filtration, adapted and predictable processes, martingales, stopping times, upcrossing inequality and martingale convergence theorems, backward martingales, optional stopping, maximal inequalities.
• Various applications of martingales: branching processes, Polya's urn, generalized Borel-Cantelli, Levy's 0-1 law, martingale method, strong law of large numbers, etc.
• Weak convergence of probability measures, characteristic functions of random variables, weak convergence in terms of characteristic functions.
• Central limit theorem, Poisson convergence, Poisson process.
• Large deviations, rate functions, Cramer's Theorem.

12 units
This course is a sequel to 21-720 (Measure and Integration). It is meant to introduce students to a number of important advanced topics in analysis.Topics include: distributions, Fourier series and transform, Sobolev spaces, Bochner integration, basics of interpolation theory, integral transforms. 3 hrs. lec.
Prerequisites: 21-720 Corequisites: 21-640.

6 units
Weak derivatives, Sobolev spaces of integer order, embedding theorems, interpolation inequalities, traces.
Prerequisite: 21-720.

6 units
This half-semester course offers graduate students in analysis an introduction to topics which are of interest to departmental faculty, but without requiring the level of preparation necessary for the course 21-820 (Advanced Topics in Analysis). Possible topics are numerical partial differential equations, calculus of variations, algebraic topology, and geometric measure theory. This course may be taken more than once if the content is sufficiently different.

12 units
An introduction to the modern theory of partial differential equations, including functional analytic techniques. Topics vary slightly from year to year, but generally include existence, uniqueness and regularity for linear elliptic boundary value problems, and an introduction to the theory of evolution equations.

12 units
This course covers the probabilistic method for combinatorics in detail and introduces randomized algorithms and the theory of random graphs.
Methods covered include the second moment method, the Rödl nibble, the Lovász local lemma, correlation inequalities, martingale's and tight concentration, Janson's inequality, branching processes, coupling and the differential equations method for discrete random processes. Objects studied include the configuration model for random regular graphs, Markov chains, the phase transition in the Erdős-Rényi random graph, and the Barabási-Albert preferential attachment model.

12 units
Classical problems and results in extremal combinatorics including the Turán and Zarankiewicz problems, the Erdős-Stone theorem and the Erdős-Simonovits stability theorem. Extremal set theory including the Erdős-Rado sunflower lemma and variations, VC-dimension, and Kneser's conjecture. The Szemeredi regularity lemma. Algebraic methods including finite field constructions and eigenvalues and expansion properties of graphs. Shannon capacity of graphs. Chromatic number of Rn and Borsuk's conjecture. Graph decomposition including Graham-Pollack and Baranyai's theorem.

12 units
A selection of topics drawn from the following: calculus in Banach spaces, degree theory, Banach and Schauder fixed point theorems, bifurcation theory, monotone operators.
Prerequisite: 21-640.

12 units
Classical fixed endpoint examples. Fixed endpoint problems in classes of absolutely continuous functions: existence via lower semicontinuity. Tonelli's existence theorem. Euler-Lagrange and DuBois Reymond equations, transversality conditions, Weierstrass field theory, Hamilton-Jacobi theory. Problems with constraints.
Prerequisite: 21-630.

12 units
Formulation of control problems, observability, controllability, duality, the bang-bang principle, linear feedback. Solutions for problems with quadratic performance criteria, Pontryagin principle and solutions using dynamic programming.

12 units
Manifolds in Euclidean spaces, curves and surfaces, principal curvatures, geodesics. Surfaces with constant mean curvature, minimal surfaces. Abstract differentiable manifolds, tangent spaces, vector bundles, affine connections, parallelisms, covariant gradients, Cartan torsion, Riemann curvature. Riemannian geometry, Lie groups. Familiarity with analysis in finite dimensional spaces will be assumed.
Depending on the instructor, 21-622 may be required as a formal prerequisite.

12 units
Numerical methods of eigenvalue problems, initial and boundary value problems for ordinary differential equations, discrete Fourier transforms, iterative techniques for large sparse linear systems.

12 units
Review of difference methods for ordinary differential equations. Finite difference methods for elliptic, parabolic and hyperbolic partial differential equations, iterative methods for linear systems, analysis of stability and convergence of algorithms. Applications to computational mechanics, electromagnetics, and other areas.

12 units
Finite element methods for elliptic boundary value problems. Analysis of errors, approximation by finite element spaces. Efficient implementation of finite element algorithms, finite element methods for parabolic and eigenvalue problems, effects of curved boundaries. Numerical quadrature, non-conforming methods.

Spring: 9 units
Develops structural intuition of how the hardware and the software work, starting from simple systems to complex shared resource architectures.
Familiarizes the audience with the main parallel programming techniques and the corresponding software packages.
Provides practical guide to build a software package.
Course web site

12 units
General discussion of the behavior of continuous bodies with an emphasis on those concepts common to the description of all continuous bodies. Specific examples from elasticity and fluid mechanics. Familiarity with analysis in finite dimensional spaces will be assumed.
Depending on the instructor, 21-622 may be required as a formal prerequisite.

12 units
Flow, stream-lines, vorticity, circulation, ideal and viscous fluids, Beltrami's theorem, Bernoulli theorems. Potential flows, exterior domain flows, D'Alembert's paradox. Compressible flow, shock waves. Uniqueness, stability of viscous flow, low and high Reynold's flow, boundary layers.

12 units
Content varies. May be taken more than once if content is sufficiently different.

12 units
Content varies. May be taken more than once if content is sufficiently different.

12 units
This is a follow up of 21-703 . The main results to be discussed are orthogonality calculus, and the structure of regular types. This will be used in a proof to Shelah's "Main Gap Theorem" for countable theories. If time will permit I will discuss the solution to Morley's conjecture that the spectrum function is weakly monotonic. It is expected that the students will know the fundamentals of classification theory (including various equivalent properties to superstability, forking calculus, and the stability spectrum theorem).

12 units
The purpose of the seminar is to offer a forum for discussion of recent developments in logic. We concentrate in the areas of Model Theory and Set Theory. We meet weekly for two hours where faculty and students present papers (typically not authored by local people) at the level which is be appropriate to that of participants. It is possible to take this seminar for credit. In order to get a grade you must present at least one paper (usually 2-4 lectures). However, some students participate passively (without giving a talk - not for credit). Every few weeks the topic changes, and often the subjects of discussion are not related.
Course web site

12 units
This is a course in classical lambda calculus with special emphasis on syntax. Topics covered include the Church-Rosser theorem, standardization, cofinal reduction strategies, lambda definability of number theoretic functions, combinators, Bohm's theorem, labelled reduction, and types. The text is Barendregt's The Lambda Calculus, North Holland 1984.

12 units
Content varies, but extends material covered in 21-610 in greater depth and detail. May be taken more than once if content is sufficiently different.

12 units
Content varies. May be taken more than once if content is sufficiently different.

12 units
Content varies. May be taken more than once if content is sufficiently different.

12 units
Elliptic boundary value problems, Green's theorem calculations, integral equation methods, variational formulations and Galerkin's method, regularity theory, parabolic problems and semi-groups.
Prerequisite: 21-732.

12 units
Content varies. May be taken more than once if content is sufficiently different.

12 units
Content varies. May be taken more than once if content is sufficiently different.

12 units
This is a first Ph.D.-level course in stochastic calculus for continuous-time processes. It includes martingales and semi-martingales, Brownian motion, the Poisson process, representation of continuous martingales as time-changed Brownian motions, contruction of the Ito integral, and Ito's formula.
Prerequisite: 36-753

12 units
This is a continuation of 21-880. Topics include Girsanov's theorem, Brownian local time, strong and weak solutions of stochastic differential equations, linear stochastic differential equations, connections between partial differential equations and stochastic differential equations, optimal stopping and stochastic optimal control.
Prerequisite: 21-880.

Content varies. May be taken more than once if content is sufficiently different.
Past topics: Duality, Stochastic Control

12 units
Content varies, but may include computational complexity in linear and integer programming, probabilistic analysis of algorithms, and dynamic programming. May be taken more than once if content is sufficiently different.

21-901 Master Degree Research
21-902 Doctoral Thesis Research

# Selected Courses in:

47-720 Seminar in Finance I
47-721 Seminar in Finance II
47-724 Seminar in Finance IV
47-800 Microeconomics
47-830 Integer Programming (6 units)
47-831 Graphs and Network Flows in Operations Research (12 units)
47-832 Linear Programming (6 units)
47-838 Advanced Linear Programming (6 units)

### Department of Statistics

36-703 Intermediate Probability
36-705 Intermediate Statistics
36-707 Regression Analysis