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<b.}

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

Given {0<n\in{\mathbb N},} 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

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

598- Some links

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.

Other links of possible interest:

  • The AMS, including MathSciNet. (You might need to consult the library about login and passwords.)
  • 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.)

Read the rest of this entry »