Effective Versions of Ramsey's Theorem

Ramsey's Theorem states that if $P = \{C\sb1,\...,C\sb{n}\}$ is a partition of (ω\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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Hummel, Tamara Lakins

Contributors dc:contributor

• Jockusch, Carl G., Jr.

• Mathematics

Identifier

(UMI)AAI9411658

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/72544