{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72544"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72544","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Effective Versions of Ramsey's Theorem","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.","abstract_html":"Ramsey&#x27;s Theorem states that if $P = \\{C\\sb1,\\...,C\\sb{n}\\}$ is a partition of (<span class=\"etd-inline-math\">&omega;\\rbrack\\sp{k}</span> (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.","abstract_has_math":true,"creators":["Hummel, Tamara Lakins"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Jockusch, Carl G., Jr."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T23:17:48Z","date_published":"2014-12-17T23:17:48Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9411658"],"render_values":[{"text":"(UMI)AAI9411658","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72544","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jockusch, Carl G., Jr."]},{"key":"dc:creator","label":"Author","values":["Hummel, Tamara Lakins"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T23:17:48Z","10000-01-01","1993"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72544","(UMI)AAI9411658"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Effective Versions of Ramsey's Theorem"]}]}],"canonical_facts":{"dc:contributor":["Jockusch, Carl G., Jr."],"dc:creator":["Hummel, Tamara Lakins"],"dc:date":["2014-12-17T23:17:48Z","10000-01-01","1993"],"dc:description":["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."],"dc:identifier":["http://hdl.handle.net/2142/72544","(UMI)AAI9411658"],"dc:subject":["Mathematics"],"dc:title":["Effective Versions of Ramsey's Theorem"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}