本文へジャンプ

Understanding the difficulty and complexity of mathematical theorems

OGAWA Laboratory
Senior Lecturer:YOKOYAMA Keita

E-mail:
[Research areas]mathematical logic, foundations of mathematics, theoretical computer science
[Keywords]Mathematical logic, foundations of mathematics, proof theory, computability theory, arithmetic, nonstandard model, reverse mathematics

Skills and background we are looking for in prospective students

High motivation to keep working on mathematics and logic. Students need to examine mathematical discussions and proofs persistently. Basic skills of mathematics are also required, but they can improve those skills during the study.

What you can expect to learn in this laboratory

Mathematical and logical way of thinking. Through the seminars, students will learn the way of understanding in mathematics. This includes the understanding of difficulties and intelligibilities of various problems. Objective analyses of difficulties may help in many practical situations.

【Job category of graduates】NA

Research outline

One of my main research interests is calibrating the strength of mathematical theorems from the view point of mathematical logic. Many mathematical theorems are described within the axiomatic system for natural numbers (called arithmetic), and they can be classified by comparing with axioms of arithmetic. Those axioms reflect various types of strength of theorems such as computability and complexity of solutions and proof-theoretic strength of theorems measured by the increasing rate of functions on natural numbers. With this idea, one may measure the strength of mathematical theorems from several different view points. This sort of study is often called “reverse mathematics.” I am also interested in investigating the framework for reverse mathematics based on the computability theory and the proof theory. The following are some of the ongoing projects.

Reverse mathematics for combinatorics

It is known that many finite and infinite combinatorial principles such as Ramsey’s theorem involve very complicated structures. Reverse mathematical studies of combinatorics reveal the complicatedness of those structures from the view points of logical strength.

Axiomatic systems and lengths of proofs

The length of a proof is one of the most natural indicator to describe the difficulty of a proof. If you prove a theorem without using stronger axioms, you might need a longer proof. We will use lengths of proofs to compare the strength of various axiomatic systems.

Nonstandard models of arithmetic

The important features of the structure of natural numbers N can be captured by the system of arithmetic which consists of axioms for semi-ring and the induction axiom. On the other hand, there are many other structures (called nonstandard models) which enjoy the same properties as N. Deeper properties of the induction axiom are often revealed by using nonstandard models.

Key publications

  1. Ludovic Patey and Keita Yokoyama, The proof-theoretic strength of Ramsey's theorem for pairs and two colors, Advances in Mathematics 330, pages: 1034–1070, 2018.
  2. Alexander P. Kreuzer and Keita Yokoyama, On principles between Σ1- and Σ2-induction, and monotone enumerations, Journal of Mathematical Logic 16, no.1, 21 pages, 2016.
  3. Silvia Steila and Keita Yokoyama, Reverse mathematical bounds for the Termination Theorem, Annals of Pure and Applied Logic 167, pages: 1213–1241, 2016.

Equipment

Paper, pen and coffee

Teaching policy

Main activities are math style seminars and discussions. Students can choose various topic in mathematical logic as long as the supervisor is available for support. They will read a textbook or papers by themselves, examine the proofs and present them in the seminar. Students are also encouraged to attend other seminars in logic group and international workshops, schools, etc.

[Website] URL:http://www.jaist.ac.jp/~y-keita/

PageTop