## Fall 2016

### Computability Theory (Ruizhi Yang)

#### H2107, R 18:30-20

This course is designed for senior undergraduates and graduates who want to understand more on the theory of computability and the formal conception of randomness. This is NOT a course on complexity, algorithm or pseudorandomness generators. Rather, this is a course about the pure conception of (un)computability and absolute randomness. Here are some key words you may encounter in the lectures: Turing degrees, Kolmogorov complexity, Martin-Löf randomness. Google it! Syllabus Lecture 01 Lecture 02 Lecture 03 Lecture 04 Lecture 05 Lecture 06 Revision 01 Lecture 07 Lecture 08 Lecture 09 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14

## Spring 2016

### Set theory II(Ruizhi Yang)

#### Room 2403, West Guanghua Tower, M 18:30-20

The topics are among constructibility, forcing, large cardinals, and some descriptive set theory. The textbooks are 《集合论:对无穷概念的探索》, Ralf Schindler's*Set Theory: Exploring Independence and Truth*, Kenneth Kunen's

*Set Theory (Studies in Logic: Mathematical Logic and Foundations)*. Lecture 01 Lecture 02, 03 Lecture 04 Lecture 05 Lecture 06 Lecture 07 Lecture 08 Lecture 09 Lecture 10 Lecture 11 Lecture 12 Lecture 13 the Truth Lemma Lecture 14

### Mathematical Logic II (Zhaokuan Hao)

#### HGX207, T 8:00-9:40

### Mathematical Logic (Ningyuan Yao)

#### HGX302, W 18:30-21

### Introduction to Model Theory (Ningyuan Yao)

#### HGX210, R 18:30-21

## Fall 2015

### Mathematical Logic (Zhaokuan Hao)

#### HGX204, R 8:00-9:40

### Mathematical Logic for Graduate Students (Ningyuan Yao)

#### HGW2403, M 18:30-20:10

### Set Theory (Ruizhi Yang)

#### HGX404, R 18:30-20:10

We will introduce axiomatic set theories, especially the ZFC system as a foundation of mathematics. We will define and study on the transfinite ordinal and cardinal numbers, discuss the properties of the sets of real numbers. The textbooks are 《集合论:对无穷概念的探索》, Ralf Schindler's*Set Theory: Exploring Independence and Truth*, Kenneth Kunen's

*Set Theory (Studies in Logic: Mathematical Logic and Foundations)*. Lecture 01 Lecture 02 Painting 01 Lecture 03 Lecture 04 Painting 02 Lecture 05 Painting 03 Lecture 06 Painting 04 Lecture 07 Painting 05 Lecture 08 Lecture 09 Painting 06 Lecture 10 Lecture 11 Painting 07 Lecture 12 Lecture 13 Painting 08

### Computability and Randomness (Ruizhi Yang)

#### HGX202, F 18:30-20:10

The course is navigated through three papers, which either initialize or significantly boost the research of our subject -- computability and randomness. They are Alan M. Turing's*On computable numbers, with an application to the Entscheidungsproblem*, Emil L. Post's

*Recursively enumerable sets of positive integers and their decision problems*, and Per Martin-Löf's

*The definition of random sequences*. There are an abundance of textbooks on this subject. Among them, we choose Robert I. Soare's

*Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets*as the main reference. The students are welcomed to have their own choice.

**Prerequisite: Mathematical Logic (I)**

### Reverse Mathematics Seminar (Yue Yang and Ruizhi Yang)

#### HGW2403, TF 10:00-12:00

We will discuss some recent developments in reverse mathematics. Poster### Set Theory Seminar (Zhaokuan Hao)

#### HGW2502, Stopped

We are trying to understand what professor W. Hugh Woodin was talking about at IMS in Summer 2015.

## Spring 2015

### Philosophy of Mathematics (Zhaokuan Hao)

#### HGX210, M 10-12

### Computability and Randomness (Yijia Chen)

#### HGX205, M 18:30-20

Course website: http://basics.sjtu.edu.cn/~chen/teaching/comprand/### Mathematical Logic II (Ruizhi Yang)

#### HGX401, T 18:30-20

Following Mathematical Logic I, in this semester, we will introduce Alan Turing's characterization of the concept of computability and look at its relationship with the concept of provability with respect to the axiomatic systems of arithmetic. We will present the proof of Gödel's first and second incompleteness theorems in detail, and discuss their mathematical and philosophical consequences. Lecture 01 Lecture 02 Lecture 03 Lecture 04 Lecture 05 Lecture 06 Lecture 07 Lecture 08 Lecture 09 Lecture 10 Lecture 11 Lecture 12 Lecture 13### Proof Theory (Ruizhi Yang)

#### HGX206, R 18:30-20

We will follow Gaisi Takeuti's textbook (2nd edition). I hope we can cover the first two parts of the book and discuss some recent results on reverse mathematics.

## Fall 2014

### Mathematical Logic I (Ruizhi Yang)

#### HGX501, T 18:30-20

This is a first course on mathematical logic. There is no prerequisite. During this semester, we will introduce the semantics and the syntax of first-order logic. That is Tarski's definition of truth on the semantic side, and both Hilbert system and the natural deduction system on the syntactic side. We will end with the soundness and completeness theorem for first-order logic. Lecture 01 Lecture 02 Lecture 03 Lecture 04 Lecture 05 Lecture 06 Lecture 07 Lecture 08 Lecture 09 Lecture 10 Lecture 11### Introduction to Computability and Randomness (Ruizhi Yang)

#### Room 2503, West Guanghua Tower, R 18:30-21

We will tell a story about three papers, which either initialize or significantly boost the research of our subject -- computability and randomness. They are Alan M. Turing's*On computable numbers, with an application to the Entscheidungsproblem*, Emil L. Post's

*Recursively enumerable sets of positive integers and their decision problems*, and Per Martin-Löf's

*The definition of random sequences*. There are an abundance of textbooks on this subject. Among them, we choose André Nies's

*Computability and Randomness*as the main reference. The students are welcomed to have their own choice.

#### Updates:

**Notice:**The meeting place has been moved to my office (room 2503, the west of Guanghua towers). (2014-10-15)- My note on Post's proof of the non-reducibility of a creative set to a simple set via a bounded-truth-table procedure. (2014-11-20)
- Refer to Dekker's paper for a proof of the failure of the concept of hypersimple sets as a solution of Post's problem. For the rest of this semester, we will focus on Robert I. Soare's paper on priority method. (2014-12-04)
- My note on Soare's proof of Sheonfield's Thickness Lemma, which is a simple case of the infinite injury priority method. (2015-01-12)

## Spring 2014

### Mathematical Logic II (Zhaokuan Hao)

#### HGX401/HGX205, T/R, 10-12

### Philosophy of Mathematics (Zhaokuan Hao)

#### HGX209, W 10-12

### Forcing (Ruizhi Yang)

#### HGX509, W 18:30-20

The main course textbook is Kenneth Kunen's*Set theory*. We will introduce the model theory of set theory, e.g. the concepts of relativization and absoluteness. After a brief introduction of Gödel's construction of $ { \mathbf{L} } $, we will proceed to introduce the method of forcing and the proof of the independence of the Continuum Hypothesis and the Axiom of Choice. We will also discuss iterated forcing and class forcing if time permits.

**Prerequisite: Set theory.**LectureNotes01

### Introduction to Model Theory (Ruizhi Yang)

#### HGX502, R 18:30-21

We introduce the basic concepts and techniques of model theory, e.g.formal language, model, elementary equivalence, homomorphism and isomorphism, category, type, elementary embedding and elementary chain, saturation, universality etc. If time permits, we will also talk about the application of model theory in set theory, modal logic, nonstandard mathematics etc.**Prerequisite: Mathematical Logic (I)**

## Fall 2013

### Mathematical Logic (Zhaokuan Hao)

#### HGX106, T/R 8:00-9:40

Lecture notes. pdf. ps.### Set Theory (Ruizhi Yang)

#### HGX501, W 18:30-20:10

We will introduce axiomatic set theories, especially the ZFC system as a foundation of mathematics. We will define and study on the transfinite ordinal and cardinal numbers, discuss the properties of the sets of real numbers and introduce the continuum hypothesis. If time permits, we may also get a glimpse of the theory of large cardinals.### Computability and Randomness (Ruizhi Yang)

#### HGX302, T 18:30-20:10

We will give a general introduction to the computability theory, a brief introduction of the randomness theory, and their interaction. The basic notion of Turing computability, reducibility, degrees etc. will be defined and discussed, and we will deal with Post's problem using finite injury priority argument. We will also introduce several characterization of randomness, discuss their relationship, and their relationship with notions in computability theory.

## Spring 2013

### Forcing (Zhaokuan Hao)

#### HGX201, W 18:30-20

### Philosophy of Mathematics (Zhaokuan Hao)

#### HGX209, T 8-10

### Mathematical Logic II (Ruizhi Yang)

#### HGX301/HGX201, T/R, 18:30-20

We will continue the introduction of first-order predicate logic. The main purpose of this course is to show G枚del's incompleteness theorems. We will also introduce some computability theory along the way.

### Introduction to Model Theory (Ruizhi Yang)

#### HGX203, M 18:30-21

We introduce the basic concepts and techniques of model theory, e.g.formal language, model, elementary equivalence, homomorphism and isomorphism, category, filter and ultrafilter; Skolem function, elementary embedding and elementary chain, ultraproduct and ultrapower, etc.. If time permits, we will also talk about the application of model theory in set theory, modal logic, nonstandard mathematics etc.