2026-09-22T06:29:01Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/72544 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Jockusch, Carl G., Jr. Hummel, Tamara Lakins 2014-12-17T23:17:48Z 2014-12-17T23:17:48Z 10000-01-01 1993 1993 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. Made available in DSpace on 2014-12-17T23:17:48Z (GMT). No. of bitstreams: 1 9411658.pdf: 4108010 bytes, checksum: d824e0299c99f44175b16dd54787523f (MD5) Previous issue date: 1993 Embargo set by: Seth Robbins for item 72712 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 100 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993. http://hdl.handle.net/2142/72544 (UMI)AAI9411658 Mathematics Effective Versions of Ramsey's Theorem text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.