We will first introduce Summer UMS and then decide on the logistics for the next weeks. We will go over some potential textbooks we could cover and then pick one by vote. Every member will then have the opportunity to sign up to give a talk.

We will begin with an overview of the topics we'll encounter in this seminar: Set Theory, Model Theory, Proof Theory, and Recursion Theory. We will then start discussing set theory, listing the axioms and discussing some particular ones such as Extensionality and Pairing using examples. By the end of the talk, we will get a sense of why all abstract math concepts are in fact set-theoretic.

We will learn how to use the axioms of ZF set theory (in particular Pairing, Union, and Comprehension) to go from the existence of an abstract set to more familiar and concrete objects, starting with the empty set, as well as discussing when sets cannot exist. Afterwards, we will move on to basic notions in mathematics, including binary relations, functions and well-orderings in the formal context of set theory.

We will introduce the concept of ordinals and arithmetics of ordinals by applying ZF. Later, we will cover induction and recursion on the ordinals. We will conclude with an application of ordinals in measure theory, showing why counting over natural numbers is meaningful.

We will begin with a quick look at the equivalents of the Axiom of Choice (AC) and define cardinal arithmetic (that is, addition, multiplication, and exponentiation) based on it. Then we will look at the Axiom of Foundation to refine the universe into the class of well-founded sets. In the end, we will see how to regard real numbers and finite boolean expressions within the axiomatic set theory.

We will begin by discussing the motivations behind model theory and draw connections between first order language, natural language, and mathematical structures. Following this, we will briefly examine some aspects of semantics in first-order logical systems. This will give us a strong foundation for further discussions in model theory.

We will learn about formal proof theory, with the goal of developing a system of representing proofs as formal objects that is easy to define and analyze. We begin by introducing modus ponens, the simple yet powerful rule of inference in formal proof theory. We then discuss some strategies for constructing proofs, establishing principles that show how informal mathematical arguments can be replicated in the context of formal proof theory. Finally, we connect the syntactic notions of formal proof theory to the semantic notions of model theory and further discuss the foundations of model theory, highlighting the Completeness Theorem and the notion of a complete set of axioms.

We will extend the foundations of model theory we heard about in the last 2 lectures. Specifically, we will define extensions by definitions, elementary submodels, elementary extensions, and model-completeness. We then prove some basic results about elementary submodels/extensions, specifically showing that a submodel is elementary if it satisfies the Tarski-Vaught criterion, and proving the downward/upward Löwenheim-Skolem-Tarski theorems. Finally, we discuss models of set theory, highlighting transitive models, and formulas that define set-theoretic properties that are absolute across transitive models, in particular.

Let us first take a short break from the development of set theory to discuss three primary philosophical views on mathematics. We will then work to understand the statement of the Church-Turing thesis and the formulation of undecidability using the theory we have developed this summer.

This week, we will depart from the textbook and explore the sorts of results which are of interest to recursion theorists. We will begin by defining (re-)defining a notion of computability, and exploring examples of computable and uncomputable sets, including Church and Turing’s famous solution to the Entscheidungsproblem. We will then move on to defining relative computability, which we will use to construct the partially-ordered set of Turing degrees. We will conclude by proving a theorem about the basic structure of the Turing degrees, which will showcase some of the techniques of recursion theory.