Effective Versions of Ramsey's Theorem

Hummel, Tamara Lakins

Permalink

https://hdl.handle.net/2142/72544 Copy

Description

Title

Effective Versions of Ramsey's Theorem

Author(s)

Hummel, Tamara Lakins

Issue Date

1993

Doctoral Committee Chair(s)

Jockusch, Carl G., Jr.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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 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.

Graduation Semester

1993

Type of Resource

text

Permalink

http://hdl.handle.net/2142/72544

Owning Collections