## 496 – Regressive functions on pairs

August 31, 2009

[Updated September 4, 2009.]

(For background, see my paper Regressive functions on pairs, in my papers page.)

Here, ${{\mathbb N}=\{0,1,\dots\}.}$ For ${X\subseteq{\mathbb N},}$ we denote by ${X^{[2]}}$ the set of unordered pairs of elements of ${X.}$ We will use interval notation, with the understanding that our variables range over natural numbers so, for example, ${[3,6)=\{3,4,5\}.}$

Suppose that ${0\notin X.}$ A function ${f:X^{[2]}\rightarrow{\mathbb N}}$ is regressive iff ${f(t)<{\rm min}(t).}$ We will usually write ${f(a,b)}$ for ${f(\{a,b\})}$ with the understanding that ${a

A subset ${H\subseteq X}$ is min-homogeneous for ${f}$ iff whenever ${a are in ${H,}$ then ${f(a,b)=f(a,c).}$

Given ${0 denote by ${g(n)}$ the smallest integer ${N}$ such that whenever ${f:[n,N]^{[2]}\rightarrow{\mathbb N}}$ is regressive, there is a min-homogeneous set ${H\subset[n,N]}$ of size at least ${4.}$

We want to bound the function ${g(n)}$ as precisely as possible.

Here are some exact values and bounds:

• ${g(1)=5.}$
• ${g(2)=15.}$
• ${g(3)=37.}$
• ${g(n)\le 2^{n-1}(n+7)-3.}$
(In the paper, I prove the weaker bound ${g(n)\le 2^n n+12\cdot 2^{n-3}+1}$ for ${n\ge3.}$)
• ${g(n+1)\ge 2g(n)+3.}$

I will be modifying the table above if additional results are found.

Typeset using LaTeX2WP.

## 502 – Formal systems (2)

August 31, 2009

Here is a different (more direct) presentation of the argument for Fact 2; the algorithm in the previous proof can be extracted from here as well:

Proof: We proceed by induction on the length of the proof to show that for all ${n,}$ whenever a string has a proof from ${\Sigma}$ of length at most ${n,}$ then it has a proof of the required form.

This is clear if ${n=1.}$ Suppose ${\tau}$ has a proof ${s}$ of length ${n+1}$ and the result holds for all proofs of length at most ${n.}$ If ${\tau}$ is an axiom, it has a proof of length ${1.}$ If in ${s,}$ ${\tau}$ is the result of applying the extension rule to some ${\sigma,}$ then ${\sigma}$ has (by the induction hypothesis) a proof ${t}$ of the required form, and ${t{}^\frown(\tau)}$ is a proof of ${\tau}$ of the required form.

Finally, suppose that in ${s,}$ ${\tau}$ is the result of applying compression to ${\tau0}$ and ${\tau1.}$ By the induction hypothesis, ${\tau0}$ and ${\tau1}$ have proofs ${s_0}$ and ${s_1,}$ respectively, of the required form. If in ${s_0}$ the extension rule is used, then it must in particular be used at the last step, so ${\tau}$ appears in ${s_0.}$ Restricting ${s_0}$ to its initial segment that ends in ${\tau}$ gives us a proof of ${\tau}$ of the required form. Similarly with ${s_1.}$

We can then assume that extension is neither used in ${s_0}$ nor in ${s_1.}$ So, for ${i\in2,}$ ${s_i=t_i{}^\frown r_i,}$ where ${t_i}$ consists of applications of the axioms rule, and ${r_i}$ consists of applications of compression. Then ${t_0{}^\frown t_1{}^\frown r_0{}^\frown r_1{}^\frown(\tau)}$ is a proof of ${\tau}$ of the required form. $\Box$

August 31, 2009

I was told that some people had a hard time finding the new homework set. It is posted on the syllabus, that I update each week. Click on the link above, next to my contact information, and look under “detailed week to week description.”

## 502 – Formal systems

August 28, 2009

1. Formal systems

Before introducing first order logic, I want to present a “toy example” of the issues we will face, and the results we are after.

In a formal system we present a set of rules about manipulation of finite strings of symbols, and attempt to study which strings can be obtained through these manipulations.

Informally, this corresponds to the syntactic part of logic, and the beginning of proof theory.

I will follow an example from Richard Kaye’s book The Mathematics of Logic.

## 502 – König’s lemma (2)

August 26, 2009

We continue with the example of domino systems.

Remark 1 There is no algorithm that determines whether a given ${D}$ can tile the plane or not.

Of course, for specific systems ${D,}$ we usually can tell by ad hoc methods which one is the case. What the remark above indicates is that there is no uniform way of doing this.

August 26, 2009

Harvey J. Greenberg’s A simplified introduction to $\LaTeX$ can be found here.

Terry Tao’s excellent blog is here; take special notice of his pages On Writing and Career Advice, and the many links listed there. Bookmark it and visit it frequently.

The list of Lester R. Ford Awards can be found here, with links to most of the papers. Try to let me know by next meeting which paper you want to work on.

• The MAA.

## 175- Update

August 26, 2009

We will have 7 quizzes through the term, and it seems unreasonable that they end up representing 60% of the grade. I have changed the percentage that quizzes, exams, and final weigh towards the total grade, to make each score reflect better the amount of work I expect to be involved (so each quiz will be about 5% of the total grade).

## 502 – König’s lemma

August 24, 2009

(The material on mathematical logic is covered in the textbook starting with Chapter 5; however, for the first few lectures, I will be providing some required background topics and will not be following the book. There are several references that you may find useful. For example,

• Kaye, Richard. The mathematics of logic, Cambridge University Press (2007).

I am also making use of a set of notes originally developed by Alexander Kechris for the course Math 6c at Caltech.)

## 598 -Syllabus

August 19, 2009

Instructor: Andres Caicedo.
Contact Information: See here.
Time: W 2:40-3:30 pm.
Place: Mathematics/Geosciences building, Room 124120.
Office Hours: MW 10:40-11:30 am.

Text:

• Steenrod, Norman; Halmos, Paul; Schiffer, Menahem; Dieudonné, Jean. How to write mathematics. AMS (1973).
• Krantz, Steven. A primer of mathematical writing. AMS (1997).

Although they are not required, I also recommend:

• Higham, Nicholas. Handbook of writing for the mathematical sciences. SIAM (1993).
• Lamport, Leslie. LaTeX: A Document Preparation System (2nd Edition). Addison-Wesley (1994).

These are books that will likely be useful to you for years.

Content: The goal of this Seminar is to get you acquainted with what Mathematical Research and Mathematical Writing are about, in general, and with mathematical research at BSU in particular. As you go through the Masters program, you are expected to become familiar with a specific field of mathematics, to obtain the required background knowledge and skills in order to do research in that field, and to write a Masters thesis, that you can think of as your first endeavor into the world of mathematical research.

Roughly, we will spend two meeting talking about research in different degrees of generality.

Then we will talk about mathematical writing. I recommend that you start right away reading the short essays from the first book listed above, I will later indicate what chapters to read from Krantz book.

An important component of mathematical writing nowadays is some degree of dexterity with the TeX program, and so we will talk about it and practice for a little bit. You are expected to write your thesis using LaTeX, so the sooner you become familiar with it, the easier this will be. You will need to write (Using LaTeX) a short summary of a journal paper of your choice (we will talk more about this during the first meeting).

Afterwards, you will have the chance to do a short presentation on  the journal paper you have chosen.

Finally, the faculty will give some talks on their own research. This may be a good opportunity for you to see first hand the faculty who will most likely be your advisors, and topics similar to those that may end up being part of your thesis.

• Attendance 40%.
• Presentation 30%.
• Summary 30%.

(It is unusual in graduate courses to grade attendance, but the success of this seminar definitely depends on it.)

## 502- Syllabus

August 19, 2009

Math 502: Logic and Set Theory.

Instructor: Andres Caicedo.
Contact Information: See here.
Time: MWF 12:40-1:30 pm.
Place: Mathematics/Geosciences building, Room 124.
Office Hours: MW 10:40-11:30 am.
Text: Just, Winfried and Weese, Martin. Discovering Modern Set Theory. Vol I: The Basics. American Mathematical Society (1996).

Contents: Math 502 is intended to provide an introduction to mathematical logic and set theory. I will supply additional notes and references for the material on logic, roughly corresponding to the first five weeks of lecture.  We will cover propositional and predicate (first-order) logic, completeness, compactness, and the basic theorems of model theory, before jumping into set theory proper. There, we will study the Zermelo-Fraenkel axioms, including the axiom of choice, with an emphasis on the development of the theory of ordinals and cardinals, and the notion of transfinite recursion. Depending on time, additional topics may be covered.