Ph.D. thesis of Jared Corduan
We study two themes from Reverse Mathematics.
The first theme involves a generalization of the infinite version of
Ramsey's theorem to arbitrary partial orderings.
We say that a partial ordering P has the (n,k)-Ramsey property, and write RT^n_k(P),
if for every k-coloring of the n-element chains of P there is a homogeneous copy of P.
When P is either a linear ordering or a tree, and n≥3, the statement
(∀k≥1)RT^n_k(P) is well understood
from the point of view of Reverse Mathematics (Jennifer Chubb, Jeffry L. Hirst, and Timothy H. McNicholl, Reverse mathematics, computability, and partitions of trees, J. Symbolic Logic 74 (2009), no. 1, 201–215.).
We investigate RT^n_k(P) for some partial orderings which are not trees.
We show that if P is either the binary tree with multiplicities
or an amenable partial ordering, and if n≥3,
then the statement (∀k≥1)RT^n_k(P)
is equivalent to ACA0 over RCA0.
We also classify which suborderings of
the binary tree with multiplicities have the Ramsey property.
Finally, we study the (1,k)-Ramsey property for the finite (ordinal) powers of ω.
For these orderings it makes sense to consider a first-order definition
of "an isomorphic copy of ωⁿ" and the corresponding version of
∀k RT^1_k(ωⁿ)
which we denote by EIndecn.
We place a lower bound on the complexity of EIndecn+1 by showing that it
is provable in RCA0+B∏^0_n.
Jointly with Dorais, we show that RCA0+I∑^0_{n+1} proves EIndecn
and also that RT^1_2(ω³) is equivalent to ACA0 over RCA0.
The second theme of our study involves set theoretic forcing over models of RCA0 and ACA0. Our primary focus is on notions of forcing whose conditions are subtrees of ω<ω which are ordered by inclusion and have a simple property that we call "persistence". In his paper "A variant of Mathias forcing that preserves ACA0", Dorais guides the reader through an interesting forcing construction (François Dorais, A variant of Mathias forcing which preserves ACA0, Archive for Mathematical Logic 51 (2012), 751–780). We use Dorais' framework and show that persistent notions of forcing over models of ACA0 which satisfy a particular coloring property give rise to generic extensions which also model ACA0. We also show that a slightly less restrictive property than persistence suffices to guarantee that generic extensions of models of RCA0 are themselves models of RCA0. Lastly, we work through several examples: Harrington, random, Sacks, Silver, and Miller forcing.
TeX Live must be installed:
sudo apt-get install texlive-fullThen run:
pdflatex thesis.tex
bibtex thesis.aux
makeindex thesis.idx
pdflatex thesis.tex
pdflatex thesis.texFrom the repository base directory, create the container:
docker build -f docker/Dockerfile -t coloring_posets .Then run the container:
docker run --rm -v $PWD:/artifacts -t coloring_posets