496 – Regressive functions on pairs

[Updated September 4, 2009.]

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

Here, For we denote by the set of unordered pairs of elements of We will use interval notation, with the understanding that our variables range over natural numbers so, for example,

Suppose that A function is regressive iff We will usually write for with the understanding that

A subset is min-homogeneous for iff whenever are in then

Given denote by the smallest integer such that whenever is regressive, there is a min-homogeneous set of size at least

We want to bound the function as precisely as possible.

Here are some exact values and bounds:

• 
• 
• 
•  
  (In the paper, I prove the weaker bound for )
• 

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

Typeset using LaTeX2WP.

502 – Formal systems (2)

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 whenever a string has a proof from of length at most then it has a proof of the required form.

This is clear if Suppose has a proof of length and the result holds for all proofs of length at most If is an axiom, it has a proof of length If in is the result of applying the extension rule to some then has (by the induction hypothesis) a proof of the required form, and is a proof of of the required form.

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

We can then assume that extension is neither used in nor in So, for where consists of applications of the axioms rule, and consists of applications of compression. Then is a proof of of the required form.

175 – Homework, updates

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

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)

We continue with the example of domino systems.

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

 

Of course, for specific systems 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.

598- Some links

Harvey J. Greenberg’s A simplified introduction to 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. 

Other links of possible interest:

• The AMS, including MathSciNet. (You might need to consult the library about login and passwords.)
• The MAA.

175- Update

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

(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

Math 598: Graduate Student Seminar.

 

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.

Grading:

• 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.)

I will use this website to post additional information, and encourage you to use the comments feature. If you leave a comment, please use your full name, which will simplify my life filtering spam out.

502- Syllabus

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.  

Grading: Based on homework. 

I will use this website to post additional information, and encourage you to use the comments feature. If you leave a comment, please use your full name, which will simplify my life filtering spam out.