Files in this item



application/pdf9411658.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Effective Versions of Ramsey's Theorem
Author(s):Hummel, Tamara Lakins
Doctoral Committee Chair(s):Jockusch, Carl G., Jr.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Abstract:Ramsey's Theorem states that if $P = \{C\sb1,\...,C\sb{n}\}$ is a partition of ($\omega\rbrack\sp{k}$ (the set of all unordered k-tuples of natural numbers) into finitely many classes, then there exists an infinite set A which is homogeneous for P; i.e., there exists $j, 1 \le j \le n,$ such that all k-tuples from A are in $C\sb{j}.$ Let H(P) denote the set of all infinite homogeneous sets for a partition P. We consider the degrees of unsolvability and arithmetical definability properties of sets in H(P) for recursive and recursively enumerable partitions P.
We use the notion of effective $\Delta\sbsp{1}{0}$-immunity to show that there exists a recursive partition $P = \{C\sb1, C\sb2\}$ of ($\omega\rbrack\sp2$ such that for every $A \in H(P), A$ is effectively $\emptyset\sp\prime$-immune, and hence every $\Pi\sbsp{2}{0}$ set $A \in H(P)$ is such that $\emptyset\sp\prime\sp\prime \le\sb{T} A \oplus \emptyset\sp\prime.$ From this it follows that every $\Pi\sbsp{2}{0}$ 2-cohesive set is of degree 0$\sp\prime\sp\prime,$ where an infinite set A is 2-cohesive if for each r.e. partition $P = \{C\sb1, C\sb2\}$ of ($\omega\rbrack\sp2,$ there exists a finite set F such that $A - F \in H(P).$
We begin a study of r.e. partitions and show that for every r.e. partition $P = \{C\sb1, C\sb2\}$ of ($\omega\rbrack\sp2,$ there exists $A \in H(P)$ such that $A\sp\prime \le\sb{T} \emptyset\sp\prime\sp\prime.$ In addition, we show that every r.e. stable partition $P = \{C\sb1, C\sb2\}$ of ($\omega\rbrack\sp3$ has a $\Delta\sbsp{4}{0}$ set $A \in H(P),$ while there exists a recursive stable partition $P = \{C\sb1, C\sb2\}$ of ($\omega\rbrack\sp3$ with no $\Delta\sbsp{3}{0}$ set $A \in H(P).$ (A partition $P = \{C\sb1,\...,C\sb{n}\}$ of ($\omega\rbrack\sp{k+1}$ is stable if for all $D \in \lbrack \omega\rbrack\sp{k},$ there exists $i, 1 \le i \le n,$ such that $D \ \cup \{a\} \in C\sb{i}$ for sufficiently large a.)
We give Jockusch's proof of Seetapun's recent result that for every recursive partition $P = \{C\sb1, C\sb2\}$ of ($\omega\rbrack\sp2,$ there exists $A \in H(P)$ such that $\emptyset\sp\prime \not\leq\sb{T} A.$ We extend Seetapun's result by establishing arithmetic bounds for such a set A. We discuss applications of these results to Reverse Mathematics and to introreducible sets.
Issue Date:1993
Description:100 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
Other Identifier(s):(UMI)AAI9411658
Date Available in IDEALS:2014-12-17
Date Deposited:1993

This item appears in the following Collection(s)

Item Statistics