Files in this item
Files  Description  Format 

application/pdf 9411658.pdf (4MB)  (no description provided) 
Description
Title:  Effective Versions of Ramsey's Theorem 
Author(s):  Hummel, Tamara Lakins 
Doctoral Committee Chair(s):  Jockusch, Carl G., Jr. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
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 ktuples 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 ktuples 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}$ 2cohesive set is of degree 0$\sp\prime\sp\prime,$ where an infinite set A is 2cohesive 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 
Type:  Text 
Description:  100 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1993. 
URI:  http://hdl.handle.net/2142/72544 
Other Identifier(s):  (UMI)AAI9411658 
Date Available in IDEALS:  20141217 
Date Deposited:  1993 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois