{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T01:31:11Z","timestamp":1649122271336},"reference-count":3,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":14164,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1975,6]]},"abstract":"<jats:p>In this paper we investigate some of the recursion-theoretic problems which are suggested by the logical notion of independence.<\/jats:p><jats:p>A set <jats:italic>S<\/jats:italic> of natural numbers will be said to be <jats:italic>k-independent<\/jats:italic> (respectively, \u221e-<jats:italic>independent<\/jats:italic>) if, roughly speaking, in every correct system there is a <jats:italic>k<\/jats:italic>-element set (respectively, an infinite set) of independent true sentences of the form <jats:italic>x<\/jats:italic> \u2208 <jats:italic>S<\/jats:italic>. <jats:italic>S<\/jats:italic> will be said to be <jats:italic>effectively independent<\/jats:italic> (respectively, <jats:italic>absolutely independent<\/jats:italic>) if given any correct system we can generate an infinite set of independent (respectively, absolutely independent) true sentences of the form <jats:italic>x<\/jats:italic> \u2208 <jats:italic>S<\/jats:italic>.<\/jats:p><jats:p>We prove that<\/jats:p><jats:p>(a) <jats:italic>S<\/jats:italic> is absolutely independent \u21d4<jats:italic>S<\/jats:italic> is effectively independent \u21d4<jats:italic>S<\/jats:italic> is productive;<\/jats:p><jats:p>(b) for every positive integer <jats:italic>k<\/jats:italic> there is a \u03a0<jats:sub>1<\/jats:sub> set which is <jats:italic>k<\/jats:italic>-independent but not (<jats:italic>k<\/jats:italic> + 1)-independent;<\/jats:p><jats:p>(c) there is a \u03a0<jats:sub>1<\/jats:sub> set which is <jats:italic>k<\/jats:italic>-independent for all <jats:italic>k<\/jats:italic> but not \u221e-independent;<\/jats:p><jats:p>(d) there is a co-simple set which is \u221e-independent.<\/jats:p><jats:p>We also give two new proofs of the theorem of Myhill [1] on the existence of an infinite set of \u03a3<jats:sub>1<\/jats:sub> sentences which are absolutely independent relative to Peano arithmetic. The first proof uses the existence of an absolutely independent \u03a0<jats:sub>1<\/jats:sub> set of natural numbers, and the second uses a modification of the method of G\u00f6del and Rosser.<\/jats:p>","DOI":"10.2307\/2271896","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:35:13Z","timestamp":1146936913000},"page":"159-166","source":"Crossref","is-referenced-by-count":0,"title":["Independent G\u00f6del sentences and independent sets"],"prefix":"10.1017","volume":"40","author":[{"given":"A. M.","family":"Dawes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. B.","family":"Florence","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200053718_ref003","volume-title":"Degrees of unsolvability","author":"Shoenfield","year":"1971"},{"key":"S0022481200053718_ref002","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200053718_ref001","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19720180704"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200053718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T15:40:43Z","timestamp":1559144443000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200053718\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,6]]},"references-count":3,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1975,6]]}},"alternative-id":["S0022481200053718"],"URL":"https:\/\/doi.org\/10.2307\/2271896","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975,6]]}}}