[FOM] Master Class in Mathematical Logic, 2006-7
Andreas Weiermann
weiermann at math.uu.nl
Tue Dec 6 19:11:52 EST 2005
Dear Colleagues,
concerning the Master class posting
to FOM from 25.11.2005 I would like to
make some additions from my personal point of view.
I will give there a course on proof and
recursion theory. Besides basic stuff
(Kleene normal form theorem, recursion theorem
cut elimination, Schuette style ordinal analysis of PA)
I will put special emphasis on independence
results for PA. Students who are eager to learn
more about Hydra games, Goodstein sequences,
computational complexities related to
Hilbert's basis theorem and Robson's basis
theorem, and about Paris Harrington,
Kanamori McAloon, Friedman
style independence results will
be in Utrecht at an appropriate place.
In particular I shall treat the following
two results on Ramsey functions.
Let PH^d_f be the assertion:
For all c,m there is an R so large
that for all partitions P:[R]^d\to c
there exists a P homogeneous set Y
contained in R such that card(Y)\geq max(m,f(min(Y)).
Let f^d_\alpha(i):=\frac{\log^d(i)}{F^{-1}_\alpha(i)}
where log^d denotes the d-th iterate
of log, where F_\alpha is from the Schwichtenberg
Wainer hierarchy and ^{-1} indicates functional inverse.
Then I\Sigma_d\vdash PH^{d+1}_{f^d_\alpha} iff
\alpha<\omega_d.
Let KM^d_f be the assertion:
For all m there is an R so large
that for all $f$-regressive partitions P:[R]^d\to Natnum
there exists a P minhomogeneous set Y
contained in R such that card(Y)\geq m.
Let g^d_\alpha(i):=\sqrt[F^{-1}_\alpha(i)]{\log^{d-1}(i)}
Then I\Sigma_d\vdash KM^{d+1}_{g^d_\alpha} iff
\alpha<\omega_d.
Thus there is a difference in the phase transition
for KM^d and PH^d.
The case d=2 has been treated in
a joint paper with Kojman, Lee and Omri (paper 31 on:
http://www.cs.bgu.ac.il/~kojman/paperslist.html)
Best regards,
Andreas Weiermann
More information about the FOM
mailing list