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.

Advertisement

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.

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.

175 -Syllabus

Math 175 Section 2: Calculus II.

(For a more detailed version, see here.)

Instructor: Andres Caicedo.
Time:  MTuWF 9:40-10:30 am.
Place: Multipurpose building, Room 208.
 

Text: Hass, Weir, Thomas, University Calculus, Addison-Wesley (2007). Part I suffices.
 

Contents: Chapters 6-9. I will frequently update the page for this syllabus with more detailed week to week descriptions. My general plan is a bit ambitious, and leaves a few additional hours free at the end of the semester, where additional topics could be covered. These hours will also act as a buffer in case some topics require more time than originally intended.

Roughly:

• We will begin with a (very quick) review of Calculus I. You are responsible for whatever material should have been covered in Calculus I (including Integration, Chapter 5), even if the course you took did not cover some of these topics; consult the online department course description for a brief outline. It will be particularly useful throughout the term if you review: Definitions of the notions of derivative and definite integral, and the definition of limit, trigonometric identities, and the material on polynomials typically covered in precalculus or algebra courses.
• We will continue with Chapter 6 (Applications of definite integration). 
• We will then jump to Chapter 9 (Polar coordinates and conics).
• We will then go back and cover Chapter 7 (Techniques of integration). While covering Section 7.7, we will also study part of Section 8.9 (the material concerning Taylor polynomials and error terms.)
• Finally, we will cover Chapter 8 (Infinite sequences and series). If there is some time left at the end, we will cover some additional topics related to this chapter or to Chapter 7.

Prerequisites: 170 (Calculus I) or equivalent.

 

Exams: There will be 2 in-class exams and a comprehensive final exam.

• Exam 1: Friday, September 25. Should cover Chapters 6 and 9.
• Exam 2: Friday, October 30. Should cover Chapters 7 and 8 (up to about half of section 8.7).
• Final exam: Monday, December 14, 10:30 am – 12:30 pm.

Dates and times are non-negotiable. Failure to take a exam will be graded as a score of 0. There will be no make up for the final exam. For the in-class exams, a make up can be arranged if I am notified prior to the exam date and a valid reason is presented; keep in mind that make up exams will be more difficult than regular in-class exams.

You need to provide me during the first week of classes with 3 blue books with your name on them, and the pages blank. One will be returned to you prior to each exam. You should solve the exams in these blue books, and won’t be allowed to turn in any other paper, even if it is a blue book that you bring to class the day of the exam. 

Quizzes: There will be bi-weekly quizzes, on the last 20 minutes of Friday’s lecture. Each quiz will evaluate, roughly, the material covered the last two weeks (except for the Friday of the quiz itself). You are not allowed to only show up about 20 minutes before the end of the lecture in order to take the quiz. If you fail to take a quiz, it will be graded as 0. There are no make-up quizzes. I may increase the frequency, if need be. In that case, I will notify at least a week in advance, both during lecture and in the syllabus page.

For each quiz, I will provide you with a page with the question(s) printed. You may use this page to solve the questions. You need to bring any additional pages you may require.

Notes from class, textbooks, and calculators, are allowed during exams and quizzes. Bring your own pen, pencil, eraser, etc.

Homework: I will frequently assign homework. This is not to be graded, or collected, but rather a guide for you to have an idea of what material to focus on, and what kind of skills are required from you. It is a very good idea to do all of the assigned homework. During office hours, you are welcome to ask about problems from the assigned sets. Some of the problems from the quizzes will be fairly close, if not outright identical, to homework problems. 

Grading:

• Quizzes: 35%. (Each quiz will weigh the same towards the final grade.)
• Exam 1: 20%.
• Exam 2: 20%.
• Final exam: 25%.

I will then grade on a linear scale:

• If your final score is 90% or higher, you receive an A.
• If it is between 80 and 89%, you receive a B.
• If it is between 70 and 79%, you receive a C.
• If it is between 60 and 69% you receive a D.
• If it is 59% or lower, you receive an F.
• There may be a small curve up if the distribution of scores warrants this. Plus and minus grades might be used for grades near the top or bottom of a grade range.

Attendance: Not required, but encouraged. I will use this website to post any additional information, and encourage you to use the comments feature, but (in general) I will not post here standard content covered in the textbook and in class. If you leave a comment, please use your full name, which will simplify my life filtering spam out.

Core outcomes: In this class you will be assessed on a wide range of skills. Among these, the following make Math 175 a part of the University Core. By the end of the course, you should be able to:

1. Identify and appropriately apply different integration techniques.
2. Express solutions using (reasonably) correct mathematical language.
3. Know that integration is an inverse operation to differentiation, and can be used to measure lengths, areas, and volumes, among others.
4. Formally manipulate power series and justify rigorously these manipulations.
5. Solve (separable) differential equations using the integration techniques covered throughout the course.

In order, these correspond (among others) to the following University Core Outcomes:

1. Apply and evaluate a variety of strategies for solving a problem. / Interpret written materials.
2. Write clearly for specific purposes and audiences.
3. Demonstrate an understanding of the essential concepts underlying theories in the field. / Apply theories to typical problems in the field.
4. Demonstrate an understanding of the basic methods of inquiry used in this field. 
5. Apply theories to typical problems in the field.