%%%\usepackage[all]{xy}
%\renewcommand{\implies}{\rightarrow}
%\newcommand{\gnf}{=_{NF}}
%%%%\newcommand{\la}{{\lambda}}
%\newcommand{\bee}{{{\beta}_1}}
%\newcommand{\bez}{{{\beta}_2}}
%\newcommand{\gals}{{\gamma'_l}}
%\input{tcilatex}
\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsopn}
\usepackage{amsthm}
\usepackage{latexsym}
\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2606}
%TCIDATA{}
%TCIDATA{BibliographyScheme=BibTeX}
%TCIDATA{LastRevised=Sunday, June 07, 2009 14:12:22}
%TCIDATA{}
%TCIDATA{Language=American English}
\newcommand\cf{\mathop{\rm cf}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Iff}{\Leftrightarrow}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\Implies}{\Rightarrow}
\newcommand{\on}{\operatorname}
\newcommand{\mc}{\mathcal}
\newcommand{\mb}{\mathbf}
\newcommand{\mf}{\mathfrak}
\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
\newcommand{\inter}{\cap}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersect}{\bigcap}
\newcommand{\Inter}{\bigcap}
\renewcommand{\to}{\rightarrow}
\newcommand{\from}{\leftarrow}
\newcommand{\restrict}{\upharpoonright}
\newcommand{\half}{\frac{1}{2}}
\renewcommand{\and}{\,\&\,}
\newcommand{\forces}{\Vdash}
\newcommand{\enters}{\searrow}
\renewcommand{\c}{2^{\aleph_0}}
%\renewcommand{\|}{\,|\,}
\newcommand{\eps}{\varepsilon}
\newcommand{\Bushiness}{n}
\newcommand{\nil}{\varnothing}
\renewcommand{\P}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\Om}{\Omega}
\newcommand{\gauss}[1]{{\lfloor #1\rfloor}}
\newcommand{\lh}[1]{{\lvert #1 \rvert}}
\newcommand{\ohp}{{\om_{h+1}}}
\newcommand{\ali}{\alpha_i}
\newcommand{\alj}{\alpha_j}
\newcommand{\vte}{\vartheta_1}
\newcommand{\vtn}{\vartheta_0}
\newcommand{\ot}{OT}
\newcommand{\ots}{OT'}
\newcommand{\otss}{OT''}
\newcommand{\ts}{T}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\alsum}{\Om^m_2\cdot \al_m+\cdots+\Om^0_2\cdot \al_0}
\newcommand{\halsum}{\Om^{m+1}_2\cdot (\vte h\al_m+m)+\cdots+\Om^1_2\cdot
(\vte h\al_0+0)}
\newcommand{\hsalsum}{\Om^{m+2}_2\cdot h\al_m+\cdots+\Om^2_2\cdot h\anu}
\newcommand{\hstalsum}{\vte(\Om^{m+2}_2\cdot
h\al_m+\cdots+\Om^2_2\cdot h\anu)}
\newcommand{\hsale}{\Om^{1}_2\cdot h\ale+h\alz}
\newcommand{\hstale}{\vte(\Om^{1}_2\cdot h\ale+h\alz)}
\newcommand{\besum}{\Om^{n}_2\cdot \be_n+\cdots+\Om^0_2\cdot \be_0}
\newcommand{\hbesum}{\Om^{n+1}_2\cdot \vte h\be_n+\cdots+\Om^1_2\cdot
\vte h\be_0}
\newcommand{\hsbesum}{\Om^{n+2}_2\cdot h\be_n+\cdots+\Om^2_2\cdot h\be_0}
\newcommand{\hstbesum}{\vte(\Om^{n+2}_2\cdot
h\be_n+\cdots+\Om^2_2\cdot h\be_0)}
\newcommand{\hstbee}{\vte(\Om^{1}_2\cdot h\bee+h\bez)}
\newcommand{\hsbee}{\Om^{1}_2\cdot h\bee+h\bez}
\newcommand{\hstbe}{\vtn\vte(\Om^{2}_2\cdot h\bee)}
\newcommand{\ompo}{\Om^\omega_2+ \Ome}
\newcommand{\ompa}{\Om^\omega_2+\al_1}
\newcommand{\ompb}{\Om^\omega_2+\be_1}
\newcommand{\hompa}{\Om^\omega_2+h\al_1}
\newcommand{\hompb}{\Om^\omega_2+h\be_1}
\newcommand{\hsompa}{\Om^\omega_2+h\al_1}
\newcommand{\hsompb}{\Om^\omega_2+h\be_1}
\newcommand{\SWP}{{\mathrm{CWO}}}
\newcommand{\IS}{{\mathrm{I}\Sigma}}
\newcommand{\Shk}{{S^h_k}}
\newcommand{\Shd}[1]{{S^h_d(#1)}}
\newcommand{\shd}[1]{{s^h_d}(#1)}
\newcommand{\Shdl}[1]{{S^h_d{(\leq #1)}}}
\newcommand{\shdl}[1]{{s^h_d{(\leq #1)}}}
\newcommand{\ii}{\lh i \sqrt[{2d}]{\lhm i}}
\newcommand{\zhli}{2^{\lh i}}
\newcommand{\bdh}[1]{{b^h_d(#1)}}
\newcommand{\bvdh}[1]{{b^h_{4d}(#1)}}
\newcommand{\bdvh}[1]{{b^h_{4d}(#1)}}
\newcommand\CAC{\ensuremath{\mathrm{CAC}}}
\newcommand{\EM}{\mathop{\mathrm{EM}}\nolimits}
\newcommand\RT{\ensuremath{\mathrm{RT}}}
\newcommand{\dkh}{D(K,h)}
\newcommand{\gwlnn}{\gauss{\sqrt{\ln(n)}}}
\newcommand{\lnzn}{\ln^{(2)}(n)}
\newcommand{\lndn}{\ln^{(3)}(n)}
\newcommand{\lnkn}{\ln^{(K)}(n)}
\newcommand{\lnkmen}{\ln^{(K-1)}(n)}
\newcommand{\flnnlnzn}{\frac{\ln(n)}{\ln^{(2)}(n)}}
\newcommand{\flnnlndn}{\frac{\ln(n)}{\ln^{(3)}(n)}}
\newcommand{\me}{{m_1}}
\newcommand{\Natp}{{\mathbb N}^+}
\newcommand{\mk}{{m_k}}
\newcommand{\emp}{{m_l}}
\newcommand{\ee}{\mathrm{e}}
\newcommand{\al}{\alpha}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\Ome}{\Omega_1}
\newcommand{\Omz}{\Omega_2}
\newcommand{\eo}{{\varepsilon_0}}
\newcommand{\ale}{{\al_1}}
\newcommand{\alz}{{\al_2}}
\newcommand{\bee}{{\be_1}}
\newcommand{\bez}{{\be_2}}
\newcommand{\aln}{{\al_n}}
\newcommand{\alm}{{\al_m}}
\newcommand{\anu}{{\al_0}}
\newcommand{\bin}{{\mathcal B}}
\newcommand{\cpz}{{C_{Q_2}}}
\newcommand{\cpzq}{{C_{Q_2}(n)}}
\newcommand{\cpd}{{C_{Q_3}(n)}}
\newcommand{\cpk}{{C_{Q_K}(n)}}
\newcommand{\pk}{{q_K}}
\newcommand{\pe}{{q_1}}
\newcommand{\pz}{{q_2}}
\newcommand{\cpkpe}{{C_{q_{K+1}}(n)}}
\newcommand{\hs}{{h'}}
\newcommand{\om}{\omega}
\newcommand{\omz}{{\omega\sp 2}}
\newcommand{\be}{\beta}
\newcommand{\bei}{{{\beta}_i}}
\newcommand{\bej}{{{\beta}_j}}
\newcommand{\bem}{{\beta_m}}
\newcommand{\ben}{{\beta_n}}
\newcommand{\berr}{{\beta_{r+r+1}}}
\newcommand{\bers}{{\beta'_{r+1}}}
\newcommand{\ber}{{\beta_{r}}}
\newcommand{\berp}{{\beta_{r+1}}}
\newcommand{\bek}{{\beta_k}}
\newcommand{\beks}{{\beta'_k}}
\newcommand{\bees}{{\beta'_1}}
\newcommand{\bets}{{\beta'_t}}
\newcommand{\bes}{{\beta'}}
\newcommand{\betps}{{\beta'_{t+1}}}
\newcommand{\gaes}{{\ga'_1}}
\newcommand{\gaus}{{\ga'_u}}
\newcommand{\gaups}{{\ga'_{u+1}}}
\newcommand{\gals}{{\ga'_l}}
\newcommand{\benm}{{\beta_{n-1}}}
\newcommand{\Nat}{{\mathbb N}}
\newcommand{\ce}{{\cal E}}
\newcommand{\gae}{{\gamma_1}}
\newcommand{\gam}{{\gamma_m}}
\newcommand{\gan}{{\gamma_n}}
\newcommand{\gar}{{\gamma_r}}
\newcommand{\garp}{{\gamma_{r+1}}}
\newcommand{\gal}{{\gamma_l}}
\newcommand{\gars}{{\gamma'_{r+1}}}
\newcommand{\gsar}{{\gamma_{r'}}}
\newcommand{\garsp}{\gamma_{r'}}
\newcommand{\garrs}{\gamma_{r'+r'+1}}
\newcommand{\gas}{{\gamma'}}
\newcommand{\gnf}{{=_{NF}}}
\newcommand{\lne}{\ln^{(1)}}
\newcommand{\de}{{\delta}}
\newcommand{\BI}{{\mathrm{BI}}}
\newcommand{\PA}{{\mathrm{PA}}}
\newcommand{\HR}{{\mathrm{HR}}}
\newcommand{\PRA}{{\mathrm{PRA}}}
\newcommand{\enum}{{\mathrm{enum}}}
\newcommand{\CA}{{\mathrm{CA}}}
\newcommand{\RCA}{{\mathrm{RCA}}}
\newcommand{\ATR}{{\mathrm{ATR}}}
\newcommand{\ACA}{{\mathrm{ACA}}}
\newcommand{\dee}{{{\delta}_1}}
\newcommand{\dem}{{{\delta}_m}}
\newcommand{\den}{{{\delta}_n}}
\newcommand{\der}{{{\delta}_r}}
\newcommand{\des}{{{\delta}_s}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cL}{{\cal L}^2}
\newcommand{\cM}{{\cal M}}
\newcommand{\PH}{{\mathrm P}{\mathrm H}}
\newcommand{\FKT}{{\mathrm F}{\mathrm K}{\mathrm T}}
\newcommand{\LWO}{{\mathrm L}{\mathrm W}{\mathrm O}}
\newcommand{\ZETA}{{\mathrm Z}{\mathrm E}{\mathrm T}{\mathrm A}}
\newcommand{\lrfloor}[1]{\lfloor\!\! #1\rfloor}
\newcommand{\card}[1]{{|#1|}}
\newcommand{\revmathfont}[1]{{\textsf{#1}}}
\def\ATRz{\revmathfont{ATR}$_0$}
\def\RCAz{\revmathfont{RCA}$_0$}
\def\WKLz{\revmathfont{WKL}$_0$}
\def\CAz{\revmathfont{CA}$_0$}
\def\ACz{\revmathfont{AC}$_0$}
\def\PCAz{$\Pi^1_1$-\revmathfont{CA}$_0$}
\def\FRA{\revmathfont{FRA}}
\def\indec{\revmathfont{INDEC}}
\def\St{\revmathfont{S}}
\def\Th{\revmathfont{T}}
\def\LL{{\mathbb L}}
\def\om{\omega}
\def\si{\sigma}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.25in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\itemsep}{0pt}
\renewcommand{\topfraction}{.9}
\renewcommand{\textfraction}{.1}
\setlength{\parskip}{\smallskipamount}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\CB}{{\mathcal B}}
\newcommand{\CC}{{\mathcal C}}
\newcommand{\CK}{{\mathcal K}}
\newcommand{\CZ}{{\mathcal Z}}
\newcommand{\CM}{{\mathcal M}}
\newcommand{\CN}{{\mathcal N}}
\newcommand{\CQ}{{\mathcal Q}}
\newcommand{\CR}{{\mathcal R}}
\newcommand{\CH}{{\mathcal H}}
\newcommand{\CP}{{\mathcal P}}
\newcommand{\sA}{{^*\varphi}}
\newcommand{\swkl}{\mathsf{{^*W}KL_0}}
\newcommand{\wkl}{\mathsf{WKL}_0}
\newcommand{\rca}{\mathsf{RCA}_0}
\newcommand{\aca}{\mathsf{ACA}_0}
\newcommand{\atr}{\mathsf{ATR}_0}
\newcommand{\pca}{\Pi^1_1\mbox{-}\mathsf{CA}_0}
\newcommand{\saca}{\mathsf{{^*A}CA_0}}
\newcommand{\srca}{\mathsf{{^*R}CA_0}}
\newcommand{\satr}{\mathsf{{^*A}TR_0}}
\newcommand{\spa}{{^*\Sigma}\mathsf{PA}}
\newcommand{\sda}{{^*\Delta}\mathsf{PA}}
\newcommand{\pa}{\mathsf{PA}}
\newcommand{\stp}{\mathsf{STP}}
\newcommand{\ba}{\mathsf{BA}}
\newcommand{\sba}{\mathsf{BNA}}
\newcommand{\pr}{\mathsf{PR}}
\newcommand{\sn}{{^*\CN}}
\newcommand{\sz}{{^*\CZ}}
\newcommand{\fot}{\mathsf{FOT}}
\newcommand{\Nn}{\mathbb{N}}
\def\ATRz{\revmathfont{ATR}$_0$}
\def\RCAz{\revmathfont{RCA}$_0$}
\def\WKLz{\revmathfont{WKL}$_0$}
\def\CAz{\revmathfont{CA}$_0$}
\def\ACz{\revmathfont{AC}$_0$}
\def\PCAz{$\Pi^1_1$-\revmathfont{CA}$_0$}
\def\FRA{\revmathfont{FRA}}
\def\indec{\revmathfont{INDEC}}
\def\St{\revmathfont{S}}
\def\Th{\revmathfont{T}}
\def\LL{{\mathbb L}}
\def\om{\omega}
\def\si{\sigma}
\def\buildbin#1\over#2{\mathbin{\mathop{\kern0pt #2}\limits^{#1}}}
\newcommand{\dotminus}{\buildbin{\textstyle\cdot}\over{\smash-}}
\input{tcilatex}
\begin{document}
\title{Computability, Reverse Mathematics and Combinatorics: Open Problems\\
Banff International Research Station\\
Alberta, Canada\\
Sunday, December 7--Friday, December 12, 2008}
\author{Organizers \\
%EndAName
Peter A. Cholak (University of Notre Dame) \\
Barbara F. Csima (University of Waterloo) \\
Steffen Lempp (University of Wisconsin-Madison) \\
Manuel Lerman (University of Connecticut-Storrs) \\
Richard A. Shore (Cornell University) \\
Theodore A. Slaman (University of California at Berkeley)}
\date{}
\maketitle
\section{Tim Carlson}
Fix a finite set $L$ and an infinite list of variables $v_{0},v_{1},v_{2},
\ldots ,v_{n},\ldots $. For $m,n\leq \omega $, $W(L,m,n)$ is the set of
sequences $w$ of elements of $L\cup \{v_{i}\,|\,iy)[f(x,y)=f(x,z)]$.
\end{definition}
\textbf{(RT$^{\mathbf{2}}_{\mathbf{2}}$)} Ramsey's Theorem for pairs: Every
2-coloring of $[\mathbb{N}]^{2}$ has a homogeneous set.
\medskip
\textbf{(SRT$^{\mathbf{2}}_{\mathbf{2}}$)} Stable Ramsey's Theorem for
pairs: Every \emph{stable} coloring of $[\mathbb{N}]^{2}$ has a homogeneous
set.
\medskip
\begin{definition}
If $\vec{R}=\langle R_{i} \mid i\in\mathbb{N}\rangle$ is a sequence of sets,
an infinite set $S$ is $\vec{R}$\emph{-cohesive} if $(\forall i)(\exists
s)[(\forall j>s)(j\in S\rightarrow j\in R_{i})\,\vee\,(\forall j>s)(j\in
S\rightarrow j\notin R_{i})]$.
\end{definition}
\textbf{(COH)} Cohesive Principle: For every sequence $\vec{R}=\langle R_{i}
\mid i\in\mathbb{N}\rangle$ there is an $\vec{R}$-cohesive set.
\medskip
\textbf{(CAC)} Chain-AntiChain: Every infinite partial order $(P,\leq_{P})$
has an infinite subset $S$ that is either a \emph{chain}, i.e.\ $(\forall
x,y\in S)(x\leq_{P} y\,\vee\, y\leq_{P} x)$, or an \emph{antichain}, i.e.\ $%
(\forall x,y\in S)(x \neq y \rightarrow(x\nleq_{P} y\,\wedge \,y\nleq_{P}
x)) $.
\medskip
\textbf{(ADS)} Ascending or Descending Sequence: Every infinite linear order
$(L,\leq_{L})$ has an infinite subset $S$ that is either an ascending
sequence, i.e.\ $(\forall ss)(j\in P\rightarrow
i<_{P}j)\,\vee\,(\forall j>s)(j\in P\rightarrow i \mid_{P}j)]
\end{equation*}
or
\begin{equation*}
(\forall i\in P)(\exists s)[(\forall j>s)(j\in P\rightarrow
i>_{P}j)\,\vee\,(\forall j>s)(j\in P\rightarrow i \mid_{P}j)]\text{.}
\end{equation*}
\end{definition}
\textbf{(SCAC)} Stable CAC: Every infinite stable partial order has an
infinite chain or antichain.
\medskip
\begin{definition}
An infinite linear order in which all nonfirst elements have immediate
predecessors and all nonlast ones have immediate successors has type
\begin{itemize}
\item $\omega$ if every element has finitely many predecessors;.
\item $\omega^{\ast}$ if every element has finitely many successors;
\item $\omega+\omega^{\ast}$ if it is not of type $\omega$ or $\omega^{\ast}$
and every element has either finitely many predecessors or finitely many
successors.
\end{itemize}
\end{definition}
\textbf{(SADS)} Stable ADS: Every linear order of type $\omega+\omega^{\ast}$
has a subset of order type $\omega$ or $\omega^{\ast}$.
\medskip
\textbf{(CADS)} Cohesive ADS: Every linear order has a subset $S$ of order
type $\omega$, $\omega^{\ast}$, or $\omega+\omega^{\ast}$.
\medskip
\begin{definition}
An infinite linear order $\mathcal{L}$ with first and last elements ($0$ and
$1$, respectively) in which all nonfirst elements have immediate
predecessors and all nonlast ones have immediate successors is \emph{%
strongly of type $\omega+\omega^{\ast}$} if, for every finite ascending
sequence $0=x_{0}<_{L}x_{1}<_{L}\cdots<_{L}x_{n}=1$, there is exactly one
infinite subinterval $[x_{i},x_{i+1})$, and both $[x_{0},x_{i}]$ and $%
[x_{i},x_{n}]$ are finite.
\end{definition}
\textbf{(PART)} Every linear order of type $\omega+\omega^{\ast}$ is
strongly of type $\omega+\omega^{\ast}$.
\bigskip
\noindent \textbf{Questions:}
All implications and nonimplications below are over RCA$_0$.
ADS and CAC are both natural principles provable in RT$^2_2$. In the same
way that RT$^2_2$ can be split into SRT$^2_2$ and COH (i.e., RT$^2_2$
implies both these principles, and together they imply RT$^2_2$), ADS can be
split into SADS and CADS, and CAC can be split into SCAC and a cohesive
version of CAC that is equivalent to COH (see \cite{HS}). As noted in \cite%
{HS}, CAC implies ADS, SCAC implies SADS, and COH implies CADS.
\begin{problem}
Does ADS imply CAC?
\end{problem}
\begin{problem}
Does SADS imply SCAC?
\end{problem}
\begin{problem}
Does CADS imply COH?
\end{problem}
A positive answer to the second question would imply a positive answer to
the first question, since, as shown in \cite{HS}, ADS implies COH. It was
also shown in \cite{HS} that CADS and COH are equivalent over B$\Sigma_2$.
In \cite{HS}, it is shown that SADS is not $\Pi^1_1$-conservative over RCA$%
_0 $ because it implies PART, which is implied by B$\Sigma_2$ but not
provable in RCA$_0$. These results raise the following related questions.
\begin{problem}
Does SADS imply B$\Sigma_2$?
\end{problem}
\begin{problem}
\emph{(Now solved [\cite{CLY}]) }Does PART imply B$\Sigma _{2}$ over RCA$%
_{0} $?
\end{problem}
Chong, Lempp, and Yang have now shown that, indeed, PART does imply B$%
\Sigma_2$ over RCA$_0$.
Finally, the following is an important proof theoretic question left open in
\cite{CJS}. See Section 6 in \cite{HS} for a discussion of the potential
difficulties in answering it.
\begin{problem}
Is RT$_{2}^{2}$ or SRT$_{2}^{2}$ $\Pi _{1}^{1}$-conservative over B$\Sigma
_{2}$?
\end{problem}
\begin{thebibliography}{}
\bibitem{CJS} Cholak, P. A., Jockusch, Jr., C. G. and Slaman, T. A., \emph{%
On the strength of Ramsey's Theorem for pairs}, J. Symbolic Logic 2001
\textbf{66}, 1--55.
\bibitem{HS} Hirschfeldt, D. R. and Shore, R. A., \emph{Combinatorial
principles weaker than Ramsey's Theorem for pairs}J. Symbolic Logic\}
\textbf{72} 2007, 171--206.
\bibitem{CLY} Chong, C.T., Lempp, S. and Yang, Y., The collection principle
for $\Sigma _{2}$-formulas and the partition principle PART, preprint.
\end{thebibliography}
\section{Jeff Hirst}
\noindent We introduce the following shorthand notation for combinatorial
principles:
\begin{list}{}{}
\item Ramsey's Theorem ${\sf RT}^n_k$: If $f: [\mathbb N ]^n \to k$, then
there is an infinite set $X\subset \mathbb N$ and a $c 1$ with $f(n + 1) = 2f(n)$?
\item What is the value of the limit $L$ defined above? Does $L = 2$?
\end{enumerate}
The third problem is by far the most significant of these.
\end{problem}
\subsection{\textbf{Well-known open problems about the strength of Ramsey's
Theorem for pairs.}}
\textbf{Background.} Let RT$_{k}^{n}$ be Ramsey's Theorem for $k$-colorings
of $n$-element sets. It was shown by Simpson \cite{S} that RT$_{k}^{n}$
follows from ACA$_{0}$ for each $n,k\in \omega $, and that it is provable in
RCA$_{0}$ that RT$_{k}^{n}$ implies ACA$_{0}$ in RCA$_{0}$ when $n\geq
3,k\geq 2$. It was shown by Seetapun \cite{SS} that RT$_{2}^{2}$ does not
imply ACA$_{0}$ in RCA$_{0}$. Also, it follows easily from \cite{J72} that RT%
$_{2}^{2}$ is not provable in WKL$_{0}$, so RT$_{2}^{2}$ is not equivalent
to any of the \textquotedblleft big five\textquotedblright\ systems of
reverse mathematics. The following results appear in \cite{CJS01}.
1. (J. Hirst) RT$^2_2$ implies $\Sigma^0_2$-Bounding in RCA$_0$
2. Every $\Pi^1_1$ sentence provable from RCA$_0$ + $\Sigma^0_2$-Induction +
RT$^2_2$ is provable from just RCA$_0$ + $\Sigma^0_2$-Induction.
3. RT$^2_2$ is equivalent over RCA$_0$ to SRT$^2_2$ + COH . Here a
two-coloring of pairs is called \emph{stable} if for every $a$, all but
finitely many pairs containing $a$ have the same color, and SRT$^2_2$ is
Ramsey's Theorem for pairs restricted to stable colorings. COH is a
cohesiveness principle.
\begin{problem}
(\cite{SS}) Does RT$_{2}^{2}$ imply WKL$_{0}$ in RCA$_{0}$ ?
\end{problem}
\begin{problem}
(\cite{CJS01}) Does SRT$_{2}^{2}$ imply RT$_{2}^{2}$ in RCA$_{0}$ ?
\end{problem}
\begin{problem}
(\cite{CJS01}) Does SRT$_{2}^{2}$ imply WKL$_{0}$ in RCA$_{0}$ ?
\end{problem}
\begin{problem}
(\cite{CJS01}) Does RT$_{2}^{2}$ imply $\Sigma _{2}^{0}$-Induction in RCA$%
_{0}$ ?
\end{problem}
\begin{problem}
(\cite{CJS01}) Is RT$_{2}^{2}$ $\Pi _{1}^{1}$-conservative (as above) over
RCA$_{0}$ + $\Sigma _{2}^{0}$-bounding?
\end{problem}
\begin{thebibliography}{}
\bibitem{CJS01} Peter A. Cholak, Carl G. Jockusch, Jr., and Theodore A.
Slaman, \emph{On the strength of Ramsey's theorem for pairs}, J. Symbolic
Logic \textbf{66} (2001), no. 1, 1--55.
\bibitem{DGJM1} Rod Downey, Noam Greenberg, Carl Jockusch, and Kevin Milans,
\emph{Binary subtrees with few labeled paths}, in preparation.
\bibitem{J72} Carl G. Jockusch, Jr., \emph{Ramsey's theorem and recursion
theory}, J. Symbolic Logic \textbf{37} (1972), no. 2, 268--280.
\bibitem{HJKta} Valentina S. Harizanov, Carl G. Jockusch, Jr., and Julia F.
Knight, \emph{Chains and antichains in partial orderings}, Archive for
Mathematical Logic \textbf{48} (2009), no. 1, 39--53.
\bibitem{H01} E. Herrmann, \emph{Infinite chains and antichains in
computable partial orderings}, J. Symbolic Logic \textbf{66} (2001),
923--934.
\bibitem{HS07} Denis R. Hirschfeldt and Richard A. Shore, \emph{%
Combinatorial principles weaker than Ramsey's Theorem for pairs}, J.
Symbolic Logic \textbf{72} (2007), 171--206.
\bibitem{JKLLSta} Carl G. Jockusch, Jr., Bart Kastermans, Steffen Lempp,
Manuel Lerman, and Reed Solomon, \emph{Stability and posets}, J. Symbolic
Logic \textbf{74}(2009), no. 2, 693--711.
\bibitem{SS} David Seetapun and Theodore A. Slaman, \emph{On the strength of
Ramsey's theorem}, Notre Dame Journal of Formal Logic, \textbf{36}, 570--582.
\bibitem{S} Stephen G. Simpson, \emph{Subsystems of Second Order Arithmetic}%
, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.
\end{thebibliography}
\section{H. Jerome Keisler}
The language ${^*L}_1$ of nonstandard arithmetic has sorts $N$ with
variables $m,n,\ldots$ and ${^*N}$ with variables $x,y,\ldots$, and the
vocabulary $0,1,+,\buildbin{\textstyle\cdot}\over{\smash-},\cdot,<$. In ${^*L%
}_1$, Basic Nonstandard Arithmetic ($\mathsf{BNA}$) has the axioms of $%
I\Sigma_1$ in sort $N$, the axioms of linear order in sort ${^*N}$, and the
Proper Initial Segment Axioms:
\begin{equation*}
\forall n\exists x (x=n),\quad \forall n\forall x[ x< n\rightarrow \exists
m\,x=m], \quad\exists y\forall n[n0\,\exists N\,\forall n>N\, \left| \frac{\text{the $\#$
of 1's up to $n$ in $X$}}{n}-\frac{1}{2}\right| <\varepsilon.
\end{equation*}
Suppose $X$ does not satisfy the SLLN, as witnessed by a number $%
\varepsilon_0$. Let
\begin{equation*}
U_N=\{Z: \exists n>N \, \left| \frac{\text{the $\#$ of 1's up to $n$ in $X$}%
}{n}-\frac{1}{2}\right| \ge \varepsilon_0\}.
\end{equation*}
Then $U_N$ is open; $\{(\sigma,n): [\sigma]\subseteq U_n\}$ is the range of
a computable function; and $\mu(U_N)$ goes computably quickly to $0$. Thus, $%
X$ is not Martin-L\"of random.
\end{example}
Some basic facts include:
\begin{itemize}
\item Almost all $X$ according to $\mu$ are Martin-L\"of random.
\item No computable set $X$ is Martin-L\"of random.
\item Some Martin-L\"of random sets are computable from $0^{\prime}$.
\end{itemize}
\begin{theorem}[Law of Weak Subsets \protect\cite{K:Law}]
\label{Law} Almost every $X\subseteq\mathbb{N}$, according to $\mu$, has an
infinite subset $Y\subseteq X$ such that $Y$ computes no Martin-L\"of random
set.
\end{theorem}
(Passing from $X$ to $Y$ we suffer a ``loss of randomness beyond algorithmic
repair''.) Equivalently, for almost all $X$, the Muchnik degree of
\begin{equation*}
\{Y: Y\text{ is infinite and }Y\subseteq X\}
\end{equation*}
is not above $\mathcal{R}_1$, the Muchnik degree of Martin-L\"of random sets.
This strengthens the result of Kjos-Hanssen \cite{K:MRL} that there exists a
Martin-L\"of random set of integers $X$ and an infinite subset $Y$ such that
$Y$ computes no Martin-L\"of random set.
\begin{problem}
How ``fat'' may the subset $Y$ in Theorem \ref{Law} be? Can we ensure that
it has positive relative density within $X$?
\end{problem}
\begin{theorem}[The Law of Weak Subsets is Arithmetical \protect\cite{K:Law}]
\label{main} Every $X$ that is Martin-L\"of random relative to $0^{\prime}$
has an infinite subset $Y\subseteq X$ such that $Y$ computes no Martin-L\"of
random set.
\end{theorem}
The following two examples illustrate how \emph{not} to try to prove Theorem %
\ref{main}.
\begin{example}
Let $X$ be Martin-L\"of random and let $Y$ be a ``computably chosen'' subset
of $X$. Say,
\begin{equation*}
Y=\langle X(0),0,X(2),0,X(4),0,\ldots\rangle.
\end{equation*}
Then $Y$ is an infinite subset of $X$, but $Y$ \emph{does} compute a
Martin-L\"of random set, namely,
\begin{equation*}
Z=\langle X(2),X(4),X(6),X(8),\ldots\rangle.
\end{equation*}
\end{example}
\begin{example}
Let $X$ be Martin-L\"of random and let $Y$ be a ``randomly chosen'' subset
of $X$. That, is each 1 in $X$ is converted to a 0 with probability $\frac{1%
}{2}$. Then $Y$ \emph{does} compute a Martin-L\"of random set, as observed
by John von Neumann. Namely, let $Z$ be obtained from $X$ by making the
following replacements:
\begin{equation*}
\langle X(2n),X(2n+1)\rangle \mapsto Z(n)
\end{equation*}
\begin{equation*}
\langle 0,0\rangle \mapsto \langle \rangle
\end{equation*}
\begin{equation*}
\langle 1,1\rangle \mapsto \langle \rangle
\end{equation*}
\begin{equation*}
\langle 0,1\rangle \mapsto \langle 0\rangle
\end{equation*}
\begin{equation*}
\langle 1,0\rangle \mapsto \langle 1\rangle
\end{equation*}
\end{example}
\begin{problem}
Is there a suitable genericity notion such that for each Martin-L\"of random
set $X$, if $Y$ is a ``generic subset'' of $X$ then $Y$ computes no
Martin-L\"of random set?
\end{problem}
\begin{definition}
A subset $C$ of $\mathbb{N}^*=\omega^{<\omega}$ is \emph{$n$-bushy} if the
empty string is in $C$ and every element of $C$ has at least $n$ many
immediate extensions in $C$.
\end{definition}
\begin{theorem}[\protect\cite{K:Law}]
\label{bushy} There is a 3-bushy subset $C$ of $\mathbb{N}^*$ such that
\begin{enumerate}
\item for each infinite path $Z$ through $C$, $Z$ does not compute any
Martin-L\"of random set; and
\item $C$ is computable from $0^{\prime}$.
\end{enumerate}
\end{theorem}
\begin{proof} A variation of a construction of Ambos-Spies, Kjos-Hanssen,
Lempp, and Slaman \cite{AKLS}. Now we ask for sets that are so bushy that
there is not just \emph{one} acceptable path through them, but a whole
3-bushy collection of such paths. Then the construction splits up into
subconstructions for each of these paths. The construction is still carried
out using only the oracle $0'$.
\end{proof}
(By Arslanov's completeness criterion, $C$ cannot be computable.)
\begin{proof}[Proof of Theorem \ref{main} from Theorem \ref{bushy}]
Let $X$ be a subset of $\N^*$ that is Martin-L\"of random relative
to $0'$. A birth-death process where everyone has 3 children, each
with a 50$\%$ chance of surviving and themselves having 3 children,
gives positive probability to the event of eventual nonextinction of
the tribe. Since $C$ is 3-bushy, almost all $X$ have some finite
modification that contains an infinite path through $\N^*$ that is
contained in $C$. Since $C$ is computable from $0'$, the event of
extinction is $\Sigma^0_1$ relative to $0'$. We apply an effective
bijection between $\N^*$ and $\N$.
\end{proof}
\begin{problem}
\label{q} Does every Martin-L\"of random set $X$ have an infinite subset $Y$
such that for all $Z$ computable from $Y$, $Z$ is not Martin-L\"of random?
\end{problem}
Theorem \ref{main} states that this is true if $X$ is Martin-L\"of random
relative to $0^{\prime}$. One can also ask Problem \ref{q} for Kurtz and
Schnorr randomness. If the answer to Problem \ref{q} should turn out to be
\begin{quote}
no, there is a counterexample $X$ that is computable from $0^{\prime}$,
\end{quote}
and more generally
\begin{quote}
for each $A$, there is an $X$ that is ML-random relative to $A$ and
computable from $A^{\prime}$, such that for all infinite subsets $Y$ of $X$,
there is a set $Z$ that is ML-random relative to $A$ and computable from the
join $Y\oplus A$,
\end{quote}
then
\begin{quote}
\emph{Stable Ramsey's Theorem for Pairs} implies \emph{Weak Weak K\"onig's
Lemma} for $\omega$-models.
\end{quote}
A major problem in Reverse Mathematics:
\begin{problem}
Does Stable Ramsey's Theorem for Pairs (SRT$^2_2$) imply Weak K\"onig's
Lemma, or at least Weak Weak K\"onig's Lemma?
\end{problem}
One can also ask a uniform version of Problem \ref{q}.
\begin{problem}
Given a Turing reduction $\Phi$, does every Martin-L\"of random set $X$ have
an infinite subset $Y$ such that $\Phi^Y$ is not Martin-L\"of random?
\end{problem}
Carl Jockusch's talk at the conference, on joint work with Downey,
Greenberg, and Milans \cite{DGJM}, inspired this problem, which may have an
easy ``yes'' answer whose proof is yet to be found.
Another problem about Ramsey theory and WWKL:
\begin{problem}
Does the conjunction of $G_\delta$-Regularity and Weak Weak K\"onig's Lemma
imply the Rainbow Ramsey Theorem for pairs (over RCA$_0$)?
\end{problem}
This is suggested by recent results of Miller \cite{wrong}, and would be
perhaps the first example in this part of Reverse Mathematics of
mathematical theorems $A$, $B$, $C$ such that
\begin{equation*}
A\not\Implies C
\end{equation*}
\begin{equation*}
B\not\Implies C
\end{equation*}
\begin{equation*}
A \And B\Rightarrow C
\end{equation*}
For those interested in attempting to answer this problem, we mention that
the Rainbow Ramsey Theorem was studied by Csima and Mileti \cite{CM}, and
relevant results about $G_\delta$-Regularity were given by Kjos-Hanssen,
Miller, and Solomon \cite{KMiS}.
\begin{thebibliography}{}
\bibitem[ASKHLS04]{AKLS} Klaus Ambos-Spies, Bj{\o }rn Kjos-Hanssen, Steffen
Lempp, and Theodore~A. Slaman, \emph{Comparing \textrm{DNR} and \textrm{WWKL}%
}, J. Symbolic Logic \textbf{69}(4), 1089--1104, 2004.
\bibitem[CM]{CM} Barbara~F. Csima and Joseph~R. Mileti, \emph{The strength
of the Rainbow Ramsey Theorem}, to appear.
\bibitem[DGJM]{DGJM} Rod Downey, Noam Greenberg, Carl~G. Jockusch, and Kevin
Milans, \emph{Binary subtrees with few path labels}, to appear.
\bibitem[KHa]{K:MRL} Bj{\o }rn Kjos-Hanssen, \emph{Infinite subsets of
random sets of integers}, Math. Res. Lett., to appear.
\bibitem[KHb]{K:Law} Bj{\o }rn Kjos-Hanssen, \emph{A law of weak subsets},
to appear.
\bibitem[KHMS]{KMiS} Bj{\o }rn Kjos-Hanssen, Joseph~S. Miller, and D.~Reed
Solomon, \emph{Lowness notions, measure, and domination}, to appear.
\bibitem[Mil]{wrong} Joseph~S. Miller, \emph{What good is always being wrong?%
}, to appear.
\end{thebibliography}
\section{Julia Knight}
Ketonen and Solovay \cite{KS} defined \textquotedblleft $\alpha$%
-largeness\textquotedblright , generalizing the largeness from the
Paris-Harrington Theorem \cite{PH}. The definition involves fundamental
sequences for ordinals.
\begin{definition}[Fundamental sequences]
To each ordinal $0 < \alpha < \epsilon_0$, we assign a \emph{fundamental
sequence} $\{\alpha\}(x)$ as follows.
\begin{enumerate}
\item For $\alpha = \beta+1$, $\{\alpha\}(x) = \beta$, for all $x$.
\item For $\alpha = \omega^{\beta+1}$, $\{\alpha\}(x) = \omega^\beta\cdot x$.
\item For $\alpha = \omega^\beta$, where $\beta$ is a limit ordinal, $%
\{\alpha\}(x) = \omega^{\{\beta\}(x)}$.
\item For $\alpha = \omega^\beta\cdot (a+1)$, where $a\not= 1$, $%
\{\alpha\}(x) = \omega^\beta\cdot a + \{\omega^\beta\}(x)$.
\item For $\alpha$ with Cantor normal form ending in $\omega^\beta\cdot a$,
say $\alpha = \gamma+\omega^\beta\cdot a$, $\{\alpha\}(x) =
\gamma+\{\omega^\beta\cdot a\}(x)$.
\end{enumerate}
\end{definition}
\begin{definition}[$\protect\alpha$-largeness]
The set $X$ is $\alpha$-large, for $\alpha <\epsilon_0$, if there is a
sequence $C =
(\alpha_0,x_0,\alpha_1,x_1,\ldots,\alpha_{r-1},x_{r-1},\alpha_r)$ such that
\begin{enumerate}
\item $\alpha_0 = \alpha$,
\item $\alpha_r = 0$,
\item $x_0$ is the first element of $X$,
\item for $0 < i < r$, $x_i$ is the first element of $X$ that is $> x_{i-1}$%
, and
\item for $i < r$, $\alpha_{i+1} = \{\alpha_i\}(x_i)$.
\end{enumerate}
\end{definition}
\noindent \textbf{Notation}: We write $\beta\rightarrow(\alpha)^n_r$ if for
any $\beta$-large set $X$ and any partition of the $n$-sized subsets of $X$
into $r$ classes, there is an $\alpha$-large homogeneous set $Y\subseteq X$.
\begin{theorem}[Ketonen-Solovay]
For each finite $n$ and $r$ and each $\alpha<\epsilon_0$, there exists $%
\beta<\epsilon_0$ such that $\beta\rightarrow(\alpha)^n_r$.
\end{theorem}
Ketonen and Solovay connected this version of Ramsey theory with the Wainer
functions \cite{W}.
\begin{definition}[Wainer hierarchy]
We define the Wainer hierarchy as Ketonen and Solovay did.
For $\alpha <\epsilon_0$, $F_\alpha(x)$ is defined as follows.
\begin{enumerate}
\item $F_0(x)=x+1$,
\item $F_{\alpha +1}(x)=F_{\alpha}^{(x+1)}(x)$,
\item for a limit ordinal $\alpha$, $F_{\alpha}(x) = \max\{ F_{
\{\alpha\}(j)}(x) : j\leq x \}$.
\end{enumerate}
\end{definition}
For a model $\mathcal{A}$ of $I\Delta_0$, $\mathcal{A}$ is a model of $PA$
iff in $\mathcal{A}$, $F_\alpha$ is total for all $\alpha<\epsilon_0$, and $%
\mathcal{A}$ is a model of $I\Sigma_n$ iff the $F_\alpha$ is total for all $%
\alpha<\omega_n$, where $\omega_n$ is a tower of $n$ $\omega$'s.
\begin{problem}
How much Ramsey theory is provable in $I\Sigma_n$?
\end{problem}
Sommer \cite{Som} developed the theory of ordinals in $I\Delta _{0}$. Using $%
I\Delta _{0}+\exp$, he developed the connections between $\alpha $-largeness
and the Wainer functions. However, Sommer did not do the Ramsey theory.
There is further related work by Kotlarski, Bigorajska, Ratajczyk, Piekart,
and Weiermann \cite{B-K1}, \cite{B-K2}, \cite{B-K3}, \cite{K-R1}, \cite{K-R2}%
, \cite{K-P-W}, \cite{We}.
\begin{thebibliography}{}
\bibitem{KS} Ketonen, J. and Solovay, R., \emph{Rapidly growing Ramsey
functions}, Annals of Mathematics \textbf{113}~(1981), 267--314.
\bibitem{Som} Sommer, R., \emph{Transfinite induction within Peano Arithmetic%
}, Annals of Pure and Appl. Logic \textbf{76}~(1995), 231--189.
\bibitem{B-K1} Bigorajska, T., and H.\ Kotlarski, \emph{A partition theorem
for $\alpha$-large sets}, Fund. Math. \textbf{160}~(1999), 27--37.
\bibitem{B-K2} Bigorajska, T., and H.\ Kotlarski, \emph{Some combinatorics
involving $\xi$-large sets}, Fund. Math. \textbf{175}~(2002), pp.\ 119--125.
\bibitem{B-K3} Bigorajska, T., and H.\ Kotlarski, \emph{Partitioning $\alpha$%
-large sets: some lower bounds}, Trans. Amer. Math. Soc. \textbf{358}%
~(2006), 4981--5001.
\bibitem{K-R1} Kotlarski, H., and Z.\ Ratajczyk, \emph{Inductive full
satisfaction classes}, Annals of Pure and Appl. Logic \textbf{47}~(1990),
199--233.
\bibitem{K-R2} Kotlarski, H., and Z.\ Ratajczyk, \emph{More on induction in
the language with a satisfaction class}, Zeitschr. f. math. Logik und
Grundlagen d. Math. \textbf{36}~(1990), 441--454.
\bibitem{K-P-W} Kotlarski, H., B.\ Piekart, and A.\ Weiermann, \emph{More on
lower bounds for partitioning $\alpha$-large sets}, preprint.
\bibitem{PH} Paris, J.\ B., and L.\ Harrington, \emph{A mathematical
incompleteness in Peano arithmetic}, in: \emph{Handbook of Math.\ Logic},
North-Holland, 1978, pp.\ 1133--1142.
\bibitem{W} Wainer, S.\ S., \emph{A classification of the ordinal recursive
functions}, Archiv f\"{u}r mathematische Logik \textbf{13}~(1970), 136--153.
\bibitem{We} Weiermann, A., \emph{A classification of rapidly growing Ramsey
functions}, Proc. Amer. Math. Soc. \textbf{132}~(2004), 553--561.
\end{thebibliography}
\section{Manuel Lerman}
A technique frequently used to separate combinatorial principles is to build
an ideal of degrees in which one principle always has a solution, but there
is an example of the other principle in the ideal with no solution in the
ideal. Usually, the ideals constructed are ad hoc. However, there are
natural ideals in the arithmetical degrees.
\begin{problem}
Can natural ideals in the arithmetical degrees be used to construct ideals
separating combinatorial principles?
\end{problem}
One candidate would be the downward closure of the cappable r.e. degrees.
\section{Alberto Marcone}
\subsection{The maximal linear extension theorem}
Recall that a poset $(P,{\leq_P})$ is a well-partial-order (wpo) if for
every $f: \mathbb{N} \to P$ there exists $i|\sigma |$ such that $\sigma $ has no successors on
$T$ at level $\gamma $ then there is a $\tau \subseteq \sigma $ of length a
successor ordinal such that $\tau $ has no successors on $T$ of length $%
\gamma$.
\end{definition}
\begin{definition}
The \emph{finite character tree property for a cardinal} $\kappa $, \emph{%
FCTP}$_{\kappa}$, says that every binary tree $T$ on $\kappa $ of finite
character has a path of length $\kappa $.
\end{definition}
\begin{theorem}
The following are computably equivalent in the sense of $\alpha $-recursion
theory for each cardinal $\kappa $:
\begin{enumerate}
\item FCTP$_{\kappa}$
\item Compactness for first order logic for languages and theories of size $%
\kappa $.
\item Every commutative ring of size $\kappa $ has a prime ideal.
\end{enumerate}
\end{theorem}
A natural candidate for the analog of $\Pi _{1}^{1}$-CA$_{0}$ is, of course,
closure under definability by formulas with a single second order
quantifier. We have not yet looked for any equivalences at this level.
\begin{problem}
What mathematical theorems are computably equivalent (in the sense of $%
\alpha $-recursion theory) to closure under definability over $L_{\kappa}$
by formulas with a single second order quantifier.
\end{problem}
It is not clear what the appropriate basic yardsticks corresponding to ATR$%
_{0}$ should be. A candidate for analysis here is K\"{o}nig's Duality
Theorem (KDT), which is equivalent to ATR$_{0}$ \cite{ams},\cite{simp}. The
arguments of \cite{ams} show that it is strictly stronger than closure under
first order definability for every $\kappa $.
\begin{problem}
What is the right standard in $\alpha $-recursion theory that corresponds to
ATR$_{0}$, and is it equivalent to KDT\ for every $\kappa $? What about
comparability of well-orderings (of subsets of $\kappa $)? (Note that if $%
\mathop{\rm cf}(\kappa )>\omega $ then being well-founded is a co-$\kappa $%
-r.e. relation, so the situation for well-orderings is quite different than
in the countable case.)
\end{problem}
Turning to analysis and related subjects about $\mathbb{R}$, we just note
that an old result of Grilliot \cite{gri} can be seen from our point of view
as showing that the existence of a noncontinuous functional is computably
equivalent to the existence of $^{2}E$. In this setting, there are also
proof theoretic approaches that correspond to Kleene recursion in higher
types as the classical proof theoretic systems do to Turing computability
(see \cite{kohl}).
\begin{problem}
Analyze the classical theorems of analysis in terms of computable entailment
and equivalence with computation taken to be Kleene Recursion in higher
types or Blum-Shub-Smale computation.
\end{problem}
\begin{thebibliography}{}
\bibitem{ams} Aharoni, R., Magidor, M., and Shore, R. A., \emph{On the
strength of K\"{o}nig's duality theorem for infinite bipartite graphs}, J.
Combin. Theory \emph{Ser. B} \textbf{54} (1992) 257--290.
\bibitem{bss} Blum, Lenore, Cucker, Felipe, Shub, Michael and Smale, Steve,
\emph{Complexity and Real Computation}, Springer-Verlag, New York, 1998.
\bibitem{chong} Chong, C. T., \emph{Techniques of Admissible Recursion Theory%
}, Lecture Notes in Mathematics \textbf{1106}, Springer-Verlag, Berlin, 1984.
\bibitem{fenstad} Fenstad, Jens Erik, \emph{General Recursion Theory: An
Axiomatic Approach}, Perspectives in Mathematical Logic, Springer-Verlag,
Berlin-New York, 1980.
\bibitem{gri} Grilliot, T. J., \emph{On effectively discontinuous type-$2$
objects}, J. Symbolic Logic \textbf{36} (1971) 245--248.
\bibitem{kohl} Kohlenbach, U., \emph{Higher order reverse mathematics}, in:
\emph{Reverse mathematics 2001}, S. Simpson ed., 281--295, Lect. Notes in
Logic \textbf{21}, Assoc. Symbol. Logic and A.K. Peters, Wellesley, MA, 2005.
\bibitem{mold} Moldestad, J., \emph{Computations in Higher Types}, Lecture
Note in Mathematics \textbf{574}, Springer-Verlag, Berlin, 1977.
\bibitem{sacks} Sacks, Gerald E., \emph{Higher recursion theory},
Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990.
\bibitem{sho} Shore, R. A., \emph{Reverse mathematics of the uncountable: a
computational approach}, in preparation.
\bibitem{simp} Simpson, S., \emph{On the strength of K\"{o}nig's duality
theorem for countable bipartite graphs}, J. Symbolic Logic \textbf{59}
(1994) 113--123.
\end{thebibliography}
\section{Stephen G. Simpson}
\subsection{The Lebesgue Differentiation Theorem}
The problem is to determine the computable analysis and/or reverse
mathematics status of the Lebesgue Differentiation Theorem, $\mathrm{LDT}$.
The textbook statement of $\mathrm{LDT}$ reads as follows.
\begin{quote}
Let $f$ be a Lebesgue measurable real-valued function on the $d$-dimensional
unit cube, $[0,1]^d$. Then for almost all $x\in[0,1]^d$ we have
\begin{equation*}
f(x)=\lim_{Q\to x}\frac{\int_Qfd\mu}{\mu(Q)}
\end{equation*}
where the limit is taken over all $d$-dimensional cubes $Q\ni x$ as the
diameter tends to $0$. Here $\mu$ is Lebesgue measure on $[0,1]^d$.
\end{quote}
We say that $f$ is \emph{$L_1$-computable} if there exists a computable
sequence $f_n$, $n=0,1,2,\ldots$, of polynomials with rational coefficients
such that $\|f-f_n\|_1\le1/2^n$ for all $n$. Here $\|f\|_1=%
\int_{[0,1]^d}|f|d\mu$. My student Noopur Pathak \cite{pathak} has proved
that if $x$ is Martin-L\"of random then $\mathrm{LDT}$ holds at $x$ for all $%
L_1$-computable $f$. It is open whether the converse holds. Instead of
Martin-L\"of randomness, I am now thinking that weaker notions of randomness
may be relevant here, e.g., Schnorr randomness.
\begin{problem}
Let $x$ be a point in $[0,1]^d$. If $\mathrm{LDT}$ holds at $x$ for all $L_1
$-computable $f$, does $x$ have to be random in the sense of Martin-L\"of?
\end{problem}
In reverse mathematics terms, $\mathsf{WWKL}_0$ proves $\mathrm{LDT}$, and
it is an open question whether the reversal holds. Here $\mathsf{WWKL}_0$ is
Weak Weak K\"onig's Lemma, a subsystem of $\mathsf{Z}_2$ which is strictly
between $\mathsf{RCA}_0$ and $\mathsf{WKL}_0$ and which has been very useful
in the reverse mathematics of measure theory. See, for instance, \cite[\S X.1%
]{sosoa,sosoa2}.
\begin{problem}
Is $\mathrm{LDT}$ equivalent to $\mathsf{WWKL}_0$ over $\mathsf{RCA}_0$?
\end{problem}
\subsection{The Density Theorem for Muchnik Degrees}
The problem is to prove or disprove the Muchnik degree analog of the Sacks
Density Theorem.
Background: If $P$ and $Q$ are sets of reals, $P$ is said to be \emph{%
Muchnik reducible} to $Q$ if for all $y\in Q$ there exists $x\in P$ such
that $x\le_Ty $. The \emph{Muchnik degrees} are the equivalence classes of
sets of reals under mutual Muchnik reducibility, partially ordered by
Muchnik reducibility. The Muchnik degrees form a complete distributive
lattice, denoted $\mathcal{D}_w$. The study of $\mathcal{D}_w$ was
originally motivated by intuitionistic considerations going back to
Kolmogorov. We define $\mathcal{P}_w$ to be the sublattice of $\mathcal{D}_w$
consisting of the Muchnik degrees of nonempty $\Pi^0_1$ sets of reals.
Note that $\mathcal{P}_w$ is the Muchnik degree analog of the recursively
enumerable Turing degrees. See also \cite{extre}, where it is shown that the
recursively enumerable Turing degrees are naturally embedded in $\mathcal{P}%
_w$. However, $\mathcal{P}_w$ is much better than the recursively enumerable
Turing degrees, because $\mathcal{P}_w$ contains many specific, natural
degrees which are closely related to foundationally interesting topics.
Among these topics are: algorithmic randomness, diagonal nonrecursiveness,
almost everywhere domination, Kolmogorov complexity, effective Hausdorff
dimension, and hyperarithmeticity. See the references below.
The Sacks Density Theorem says that given a pair of recursively enumerable
Turing degrees $\mathbf{a},\mathbf{b}$ such that $\mathbf{a}<\mathbf{b}$, we
can find a recursively enumerable Turing degree $\mathbf{c}$ such that $%
\mathbf{a}<\mathbf{c}<\mathbf{b}$. The problem that we are posing is to
prove or disprove the same statement with the recursively enumerable Turing
degrees replaced by $\mathcal{P}_w$.
\begin{problem}
Prove or disprove the following conjecture. Given $\mathbf{a},\mathbf{b}\in%
\mathcal{P}_w$ such that $\mathbf{a}<\mathbf{b}$, we can find $\mathbf{c}\in%
\mathcal{P}_w$ such that $\mathbf{a}<\mathbf{c}<\mathbf{b}$.
\end{problem}
\begin{thebibliography}{}
\bibitem{X1} Stephen Binns and Stephen G. Simpson, \emph{Embeddings into the
Medvedev and Muchnik lattices of $\Pi^0_1$ classes}, Archive for
Mathematical Logic \textbf{43} 2004, 399--414.
\bibitem{X2} Joshua A. Cole and Stephen G. Simpson, \emph{Mass problems and
hyperarithmeticity}, Journal of Mathematical Logic \textbf{7} 2008, 125--143.
\bibitem{pathak} Noopur Pathak, \emph{A computational aspect of the Lebesgue
Differentiation Theorem}, 12 pages, 2008, accepted for publication in
Journal of Logic and Analysis.
\bibitem{sosoa} Stephen G. Simpson, \emph{Subsystems of Second Order
Arithmetic}, Springer-Verlag, 1999, xiv + 445 pages.
\bibitem{sosoa2} Stephen G. Simpson, \emph{Subsystems of Second Order
Arithmetic}, 2nd edition, Association for Symbolic Logic, Cambridge
University Press, 2009, to appear.
\bibitem{X3} Stephen G. Simpson, \emph{Mass problems and randomness},
Bulletin of Symbolic Logic \textbf{11} 2005, 1--27.
\bibitem{extre} Stephen G. Simpson, \emph{An extension of the recursively
enumerable Turing degrees}, Journal of the London Mathematical Society
\textbf{75} 2007, 287--297.
\bibitem{X4} Stephen G. Simpson, \emph{Some fundamental issues concerning
degrees of unsolvability}, in: \emph{Computational Prospects of Infinity,
Part II: Presented Talks}, edited by C.-T. Chong, Q. Feng, T. Slaman, H.
Woodin, and Y. Yang, Lecture Notes Series, Number 15, Institute for
Mathematical Sciences, National University of Singapore, World Scientific,
2008, 313--332.
\bibitem{X5} Stephen G. Simpson, \emph{Mass problems and almost everywhere
domination}, Mathematical Logic Quarterly \textbf{53} 2007, 483--492.
\bibitem{X6} Stephen G. Simpson, \emph{Mass problems and intuitionism},
Notre Dame Journal of Formal Logic \textbf{49} 2008, 127--136.
\end{thebibliography}
\section{Henry Towsner}
Let $c$ be a finite coloring of the integers. Take $F$ to be the collection
of finite sets of integers all of whose finite sums are monochromatic under $%
c$, and order $F$ by reverse inclusion. (That is, $s\prec t$ iff $t\subseteq
s$.) Hindman's Theorem is essentially the statement that $F$ is not
well-ordered by $\prec$. We define the \emph{length} of $c$, $o(c)$, to be
the order type of the well-founded part of $\prec$. This is precisely the
order type of the tree of finite partial witnesses to Hindman's Theorem
which cannot be extended to full witnesses.
Recent results suggest that the order type of $c$ is related to the
difficulty of proving that Hindman's Theorem holds for $c$, and in
particular that a $c$ which has no arithmetic solution to Hindman's Theorem
is likely to require at least length $\omega ^{2}$. By contrast, the
canonical example that Hindman's Theorem implies ACA$_{0}$ over RCA$_{0}$
has order type at most $\omega +\omega $. We can ask:
\begin{problem}
What is an example of a coloring $c$ with large length?
\end{problem}
\begin{problem}
What is the supremum of the order type for recursive/arithmetic/arbitrary
colorings of the integers?
\end{problem}
The most interesting examples would have the additional property of being
homogeneously long, in the sense that the restriction of the coloring to any
infinite set is either monochromatic except on finitely many elements, or is
also long.
\section{Andreas Weiermann}
%\subsection*{Problems from the talk.}
\subsection{Maximal order types for well partial orders}
According to de Jongh and Parikh \cite{djp} there exists for any well
partial order a linear (and automatically well-ordered) extension on the
same set having a maximal possible order type. A very general problem is to
establish a sort of rule of thumb formula for calculating the maximal order
type of a concretely given well partial order. An even more general problem
is to explain the connection between concrete well orders and concrete well
partial orders in general. To this end we offer several informal principles
and it would be an interesting problem to see how far they would lead. Our
first suggestion concerns a formula (which has been developed in joint
research with M.~Rathjen) for computing maximal order types of tree
embeddability relations and the long term hope is to give an analysis of
Friedman's extended Kruskal theorem \cite{si} (of even Kr\'{\i}\v{z}'s
theorem \cite{kriz}) by it.
To explain this formula informally let us consider a given explicit operator
$W$ which maps a (countable) wpo $X$ to a (countable) wpo $W(X)$ so that the
elements of $W(X)$ can be described as generalized terms in which the
variables are replaced by constants for the elements of $X$. We assume that
the ordering between elements of $W(X)$ is induced effectively by the
ordering from $X$. (This resembles Feferman's notion of effective relative
categoricity.) In concrete situations $W$ may for example stand for an
iterated application of basic constructions like disjoint union and
Cartesian product, the set of finite sequences construction, the multiset
construction, or a tree constructor and the like. We assume that for $W$ we
have an explicit knowledge of $o(W(X))$ such that $o(W(X))=o(W(o(X)))$ and
such that this equality can be proved using an effective reification as in
\cite{RathjenWeiermann}.
Using $W$ we then build the set of $W$-constructor trees $T(W(Rec))$
(similarly as in \cite{Hasegawa}) as follows:
\begin{enumerate}
\item $\cdot\in T(W(Rec))$.
\item If $(s_i)$ is a sequence of elements in $T(W(Rec))$ and $w((x_i))$ is
a term from $W(X)$ then $\cdot(w((s_i)))\in T(W(Rec))$.
\end{enumerate}
The embeddability relation $\unlhd$ on $T(W(Rec))$ is defined recursively as
follows:
\begin{enumerate}
\item $\cdot\unlhd t$.
\item If $s\unlhd t_i$ then $s\unlhd \cdot(w((t_i)))$.
\item If $w((s_i))\leq w^{\prime}((t_j))$ mod $W(T(W(Rec)))$ is induced
recursively by $\unlhd$ then\newline
$\cdot(w((s_i)))\unlhd \cdot(w^{\prime}((t_j)))$.
\end{enumerate}
The general principle now is that
\begin{equation*}
{T(W(Rec))} \mbox{ is a wpo}
\end{equation*}
(cf. \cite{Hasegawa}) and
\begin{equation} \label{formula}
o(\langle T(W(Rec)),\unlhd\rangle)\leq \vartheta o(W(\Omega))
\end{equation}
for $o(W(\Omega))\in dom(\vartheta)$ with $o(W(\Omega))\geq\Omega^3$.
[Moreover the reverse inequality should also hold in most cases.]
To understand this formula some additional information on ordinals and in
particular about a so called \emph{collapsing function} is required (cf.,
e.g., \cite{Wilken}). Let $\Omega$ denote the first uncountable ordinal and $%
\varepsilon_{\Omega+1}$ the first epsilon number above $\Omega$. Then any
ordinal $\alpha<\varepsilon_{\Omega+1}$ can be described uniquely in terms
of its Cantor normal form:
\begin{equation*}
\alpha=\Omega^{{\alpha_1}}\cdot\beta+\cdots+\Omega^\aln\cdot{\beta_n}
\end{equation*}
where ${\alpha_1}>\ldots>{\alpha_n}$ and $0<{\beta_1},\ldots,{\beta_n}%
<\Omega $. In this situation we define the countable subterms $K\alpha$ of $%
\alpha$ recursively via
\begin{equation*}
K\alpha:=K{\alpha_1}\cup\ldots \cup K{\alpha_n}\cup\{{\beta_1},\ldots,{%
\beta_n}\}
\end{equation*}
where $K0:=0$. Let $AP=\{\omega^\delta:\delta\in ON\}$ be the class of
additive principal numbers. With $K\alpha<\beta$ we abbreviate $\forall
\xi\in K\alpha \xi<\beta$. We can then put
\begin{equation} \label{vartheta}
\vartheta\alpha:=\min\{\beta\in AP: \beta\geq\max K\alpha\wedge \forall
\gamma<\alpha(K\gamma<\beta\rightarrow \vartheta\gamma<\beta\}.
\end{equation}
One easily verifies $\vartheta\alpha<\Omega$ by induction on $\alpha$ using
a cardinality argument. It is easy to verify that then ${\varepsilon_0}%
=\vartheta\Omega$ and $\Gamma_0=\vartheta\Omega^2.$
To investigate the maximal order types of Friedman style Kruskal theorems
(which rely on a so called gap condition) one has to extend the domain of $%
\vartheta$ to intrinsically larger domains but this is rather easy (cf.,
e.g., \cite{Wilken}). In a first step one defines a function $%
\vartheta_1:\varepsilon_{\Omega_2+1}\to [\Omega,\Omega_2[$ in the same way
as $\vartheta:\varepsilon_{\Omega+1}\to \Omega$ was defined previously. Here
$\Omega_2$ denotes the second uncountable cardinal and $\varepsilon_{%
\Omega_2+1}$ the next epsilon number above $\Omega_2$. On the segment
determined by $\vartheta_1\varepsilon_{\Omega_2+1}$ on can define the
countable coefficient sets $K\alpha$ similarly as before using $%
K\vartheta_1\alpha=K\alpha$. Using this one can then define $%
\vartheta:\vartheta_1\varepsilon_{\Omega_2+1}\to \Omega$ by (\ref{vartheta}%
). This process can be iterated through the first $\omega$ number classes to
provide a function $\vartheta:\vartheta_1\ldots\vartheta_n\varepsilon_{%
\Omega_{n+1}}\to \Omega$ giving an end-extension of the previously defined
versions of $\vartheta$ \cite{Wilken}. The limiting value of $%
\vartheta\vartheta_1\ldots\vartheta_n\varepsilon_{\Omega_{n+1}}$ as $n\to
\infty$ is known to be the ordinal related to the union of Friedman's
assertions ${\mathsf{FKT}}_n$ which rely on an embeddability relation
satisfying a gap condition.
The idea is now to approximate Friedman's ${\mathsf{FKT}}_n$ via the well
partial orders
\begin{equation} \label{appr}
\underbrace{T(\ldots(T}_{\mbox{$n$-times }}(Rec^*))\ldots)
\end{equation}
for which our formula would predict a maximal order type
\begin{equation} \label{value}
\vartheta(\vartheta_1(\ldots\vartheta_{n-1}(\Omega_n^\omega)\ldots)).
\end{equation}
Here we work with an operator $W$ which is defined by iteration. Let $X^*$
be the Higman ordering on the set of finite sequences of elements from a
poset $X$. Then the partial order in (\ref{appr}) is $T(W(Rec))$ for the
operator $W(X):=\underbrace{T(\ldots(T}_{\mbox{$n-1$-times }}(X^*)).$ (We
intend to verify prediction (\ref{value}) in a joint project with M.
Rathjen.)
\begin{problem}
How far does the general formula (\ref{formula}) lead? Are there natural
situations in which it fails?
\end{problem}
\begin{problem}
Assume that $W$ as before is a natural operator mapping (countable) wpo's to
(countable) wpo's and assume that $o(W(\Omega )\geq \Omega ^{3}$. In what
generality does the following principle hold? Principle: The proof-theoretic
ordinal of ${\mathsf{RCA}}_{0}+\forall X({\mathsf{WPO}}(X)\rightarrow {%
\mathsf{WPO}}(T(W(X)))$ is equal to $\vartheta o(W(\Omega ))$?
\end{problem}
\begin{problem}
Assume that $W$ as before is a natural operator mapping (countable) wpo's to
(countable) wpo's and assume that $o(W(\Omega )\geq \Omega ^{3}$. In what
generality does the following principle hold? Principle: ${{{\mathsf{RCA}}}}%
_{0}\vdash {\mathsf{WPO}}(T(W(Rec)))\leftrightarrow {\mathsf{WO}}(\vartheta
(o(W(\Omega ))))$?
\end{problem}
From a more general perspective we believe that a general connection between
well orders and well partial orders might be as follows. Assume that $%
(X,\leq)$ is a recursive well order represented by a proof-theoretic ordinal
notation system. Assume that $\unlhd$ is a restriction of $\leq$ on $X$ such
that $x\unlhd x^{\prime}$ holds if $x\leq x^{\prime}$ holds (hereditarily)
due to a graph-theoretic reason, like a subterm or monotonicity property.
Then the rule of thumb principle would suggest that $(X,\unlhd)$ is a wpo
having maximal order type given by the order type of $\leq$.
A very interesting test case is provided by Kr\'{\i}\v{z}'s theorem.
I.~Kr\'{\i}\v{z} proved in \cite{kriz} the following wqo/wpo result
generalizing a result by H.~Friedman \cite{si}: Let $E_{\alpha }$ be the
class of all rooted trees whose edges are labelled by ordinals below a given
ordinal $\alpha $. Given $T$ in $E_{\alpha }$ and vertices $x$ and $y$ of $T$%
, agree that $x\leq y$ if and only if $x$ is on the path between $y$ and the
root. Given trees $T$ and $S$ in $E_{\alpha }$, agree that $S\leq T$ if and
only if there is an order- and inf-preserving embedding $\varphi $ of the
vertices of $S$ into the vertices of $T$ satisfying the following
\textquotedblleft gap-condition\textquotedblright : If ${x,y}$ is an edge of
$S$ and $\alpha $ is the ordinal labelling ${x,y}$, then the labels of all
edges on the path in $T$ from $\varphi (x)$ to $\varphi (y)$ are at least as
large as $\alpha $ .
\begin{theorem}[Kr\'{\i}\v{z}]
If $\langle T_{n}\rangle _{n=1}^{\infty }$ is a sequence in $E_{\alpha }$
then for some $n0$
there exists a real number $T=T(\varepsilon )$ such that $max_{|s|\leq
r}|f(s)-\zeta (s+({\textstyle\frac{3}{4}}+iT))|<\varepsilon $.
This theorem has proven useful in joint work with A.~Bovykin on independence
results for arithmetic \cite{bovykinb} and the intuition is that Voronin's
result carries reasonable strength.
\subsection{How strong is the Erd\"os Moser principle in reverse mathematics?%
}
A tournament is a complete directed simple graph. Let ${{\mathsf{CAC}}}$ be
the statement that every infinite partial order has an infinite subchain and
let $\mathop{{\EM}}\nolimits$ be the statement that every infinite
tournament contains an infinite transitive subtournament.(A finitary
analogue of ${\mathsf{EM}}$ has been investigated by Erd\"{o}s and Moser.)
Then ${{\mathsf{RT}}}_{2}^{2}$ proves ${{\mathsf{CAC}}}$ and ${\mathsf{EM}}$%
. But we also have a reversal: ${{\mathsf{RCA}}}_{0}+{\mathsf{EM}}+{\mathsf{%
CAC}}\vdash {{\mathsf{RT}}}_{2}^{2}$. The problem (which emerges from joint
work with A.~Bovykin \cite{bovykina}) is:
\begin{problem}
How strong is ${\mathsf{EM}}$ in the context of reverse mathematics? Is ${{%
\mathsf{RCA}}}_{0}+{{{\mathsf{EM}}}}$ strictly weaker than ${{\mathsf{RCA}}}%
_{0}+{{\mathsf{RT}}}_{2}^{2}$?
\end{problem}
(There exists a recursive tournament without an infinite recursive
transitive subtournament and so ${{\mathsf{EM}}}$ is not provable in ${{%
\mathsf{RCA}}}_{0}$ alone.)
\begin{thebibliography}{}
\bibitem{bovykina} A.~Bovykin and A.~Weiermann, \emph{The strength of
infinitary Ramseyan principles can be accessed by their densities}, preprint
2005.
\bibitem{bovykinb} A.~Bovykin and A.~Weiermann, \emph{Unprovable statements
based on diophantine approximation and distribution of values of
zeta-functions}, preprint 2007.
\bibitem{djp} D.J.H.~De Jongh and R.~Parikh, \emph{Well-partial orderings
and hierarchies}, Nederl. Akad. Wetensch. Proc. Ser. A 80 Indag. Math.
\textbf{39} 1977, 195--207.
\bibitem{gordeev} L.~Gordeev, \emph{Strong well-quasi-ordering tree theorem}%
, preprint (1993), talk at Fourteenth British Combinatorial Conference
(Keele, 1993)\newline
\texttt{http://www-ls.informatik.uni-tuebingen.de/gordeew/publikationen/}
\newline
\texttt{QuasiOrdering.pdf}
\bibitem{Hasegawa} R.~Hasegawa,\emph{\ Two applications of analytic
functors. Theories of types and proofs} (Tokyo, 1997). Theoret. Comput. Sci.
\textbf{272}, 2002 113--175.
\bibitem{karatsuba} A.~A.~Karatsuba and S.~M.~Voronin, \emph{The Riemann
zeta-function}, translated from the Russian by Neal Koblitz. de Gruyter
\emph{Expositions in Mathematics} \textbf{5}. Walter de Gruyter and Co.,
Berlin, 1992. xii+396 pp.
\bibitem{kriz} I.~Kr{\'{\i}}\v{z},\emph{\ Well-quasiordering finite trees
with gap-condition. Proof of Harvey Friedman's conjecture}, Ann. of Math.
(2) \textbf{130} 1989, 215--226.
\bibitem{RathjenWeiermann} M.~Rathjen and A.~Weiermann,\emph{\
Proof-theoretic investigations on Kruskal's theorem}, {Annals of Pure and
Applied Logic} \textbf{60} 1993, 49--88.
\bibitem{schm} D.~Schmidt,\emph{\ Well-Partial Orderings and Their Maximal
Order Types}{,} Habilitationsschrift, Heidelberg, 1979.
\bibitem{schutte} K.~Sch\"{u}tte, \emph{Proof Theory},. Translated from the
revised German edition by J. N. Crossley, \emph{Grundlehren der
Mathematischen Wissenschaften} \textbf{225}. Springer-Verlag, Berlin-New
York, 1977. xii+299.
\bibitem{si} S.~G.~Simpson,\emph{\ Nonprovability of certain combinatorial
properties of finite trees}{,} in\emph{\ Harvey Friedman's research on the
foundations of mathematics}, L. A. Harrington, M. D. Morley, A. \v{S}\v{c}%
edrov and S. G. Simpson eds., ,\emph{Studies in Logic and the Foundations of
Mathematics} \textbf{117}, Amsterdam, North-Holland, 1985, 87-117.
\bibitem{Voronin} S.~M.~Voronin,\textbf{\ }\emph{A theorem on the
\textquotedblleft universality\textquotedblright\ of the Riemann
zeta-function}, Izv. Akad. Nauk SSSR Ser. Mat. \textbf{39} 1975, 475--486,
703.
%\bibitem{weiermann} A.~Weiermann: {Well partial orderings and their strength
%measured in terms of their maximal order types}. Summary of a talk given at
%the BIRS-workshop on Computability, Reverse Mathematics and Combinatorics
%2008 in Banff.
\bibitem{Wilken} G.~Wilken, \emph{Ordinal arithmetic based on Skolem hulling}%
, Annals of Pure and Applied Logic \textbf{145} 2007, 130-161
\end{thebibliography}
\section{Keita Yokoyama}
ns-WKL$_{0}$ is a system of non-standard second order arithmetic which
consists of the following axioms:
\begin{enumerate}
\item The standard universe $V=(M,S)$ satisfies WKL$_{0}$.
\item There exist a non-standard universe $V^{\ast}=(M^{\ast},S^{\ast})$ and
an embedding $\pi :V\rightarrow V^{\ast}$. Moreover, $\pi $ is elementary
with respect to $\Sigma _{0}^{0}$ formulas and $\pi (M)$ is an initial
segment of $M^{\ast}$.
\item $V$ and $V^{\ast}$ are elementary equivalent with respect to $\Sigma
_{2}^{1}$ sentences.
\item For any $X\in S^{\ast}$, $X\cap M$ is an element of $S$, i.e., the
standard part of $X$ exists.
\end{enumerate}
Note that ns-WKL$_{0}$ is a conservative extension of WKL$_{0}$. (For
systems of non-standard second order arithmetic, see [1,2].)
Within ns-WKL$_{0}$, we can develop a part of non-standard analysis (see
[2]). In particular, we can define the standard part map $\mathrm{st}:%
\mathbb{R}^{\ast}\rightarrow \mathbb{R}\cup \{\pm \infty\}$. We next
consider an axiom for the transfer principle.
\begin{itemize}
\item ($\Sigma _{1}^{0}$-TP) $\pi $ is elementary with respect to $%
\Sigma_{1}^{0}$ formulas.
\end{itemize}
ns-WKL$_{0}$ + ($\Sigma _{1}^{0}$-TP) proves ACA$_{0}$, and it is a
conservative extension of ACA$_{0}$.
Within ns-WKL$_{0}$ + ($\Sigma _{1}^{0}$-TP), we can prove the following
non-standard version of the Bolzano/Weierstrass theorem:
\begin{theorem}
(nsBWT) : Let $f:\mathbb{N}\rightarrow \mathbb{R}$ be a bounded real
sequence. Then, for any $w\in \mathbb{N}^{\ast}\setminus \mathbb{N}$, $%
st(\pi (f)(w))$ is an accumulation value of $f$.
\end{theorem}
What about the reversal of this theorem?
\begin{problem}
Is (nsBWT) equivalent to ($\Sigma _{1}^{0}$-TP) over ns-WKL$_{0}$?
\end{problem}
Another problem was raised at the meeting:
\begin{problem}
\emph{(Now solved) }Let $(M,S)$ be a countable model of WWKL$_{0}$. Can we
then find $\bar{S}\supseteq S$ such that $(M,\bar{S})$ is a countable model
of WKL$_{0}$ and every closed set of positive measure which is coded in $%
\bar{S}$ contains points in $S$?
\end{problem}
This result was needed to prove that the formal system for nonstandard
analysis with Loeb measures, ns-BASIC + LMP, is conservative over WWKL$_{0}$%
. The problem was solved (positively) at the meeting by Stephen Simpson.
Yokoyama and Simpson are writing a joint paper which will include this
result.
\bigskip
\begin{thebibliography}{}
\bibitem{KY} Keita Yokoyama, \emph{Formalizing non-standard arguments in
second order arithmetic}, preprint.
\bibitem{KY2} Keita Yokoyama, \emph{Reverse Mathematics for non-standard
analysis}, in preparation.
\end{thebibliography}
\end{document}