{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T15:22:00Z","timestamp":1648999320430},"reference-count":7,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":14711,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1973,12]]},"abstract":"<jats:p>In this paper a converse of Barwise's completeness theorem is proved by cut-elimination considerations applied to inductive definitions. We show that among the transitive sets <jats:italic>T<\/jats:italic> satisfying some weak closure conditions (closure under primitive-recursive set-functions is more than enough), only the unions of admissible sets satisfy Barwise's completeness theorem in the form stating that if <jats:italic>\u03c6<\/jats:italic> \u220a <jats:italic>T<\/jats:italic> is a sentence which has a derivation (in the universe) then <jats:italic>\u03c6<\/jats:italic> has a derivation in <jats:italic>T<\/jats:italic>. See \u00a71 for the origin of the problem in Barwise's paper [Ba].<\/jats:p><jats:p>Stated quite briefly the proof is as follows (a step-by-step account including relevant definitions is given in the body of the paper):<\/jats:p><jats:p>Let <jats:italic>T<\/jats:italic> be a transitive prim.-rec. closed set, and let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200055353_inline1\" \/> is nonempty, transitive and closed under pairs}. For each <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200055353_inline2\" \/> let <jats:italic>\u03ba<\/jats:italic>(<jats:italic>A<\/jats:italic>) be the supremum of closure ordinals of first-order positive operators on subsets of <jats:italic>A<\/jats:italic> (first-order with respect to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200055353_inline06\" \/> By Theorem 1 of [BGM], it is enough to prove that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200055353_inline3\" \/><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200055353_inline4\" \/> rank(<jats:italic>T<\/jats:italic>) in order to obtain that <jats:italic>T<\/jats:italic> is a union of admissible sets. (The rank of a set is defined by rank(<jats:italic>x<\/jats:italic>) = sup<jats:sub><jats:italic>y \u220a x<\/jats:italic><\/jats:sub> (rank(<jats:italic>y<\/jats:italic>) + 1); since <jats:italic>T<\/jats:italic> is prim.-rec. closed, rank(<jats:italic>T<\/jats:italic>) = smallest ordinal not in <jats:italic>T<\/jats:italic>.)<\/jats:p><jats:p>Let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200055353_inline5\" \/> We show how to find in <jats:italic>T<\/jats:italic> (in fact, in <jats:italic>L<\/jats:italic><jats:sub><jats:italic>\u03c9<\/jats:italic><\/jats:sub>(<jats:italic>A<\/jats:italic>)) a derivable sentence <jats:italic>\u03c4<\/jats:italic> that has no derivation <jats:italic>D<\/jats:italic> such that rank(<jats:italic>D<\/jats:italic>) \u2264 <jats:italic>\u03b1<\/jats:italic>. Thus, if <jats:italic>\u03c4<\/jats:italic> is to have a derivation in <jats:italic>T<\/jats:italic>, rank(<jats:italic>T<\/jats:italic>) &gt; <jats:italic>\u03b1<\/jats:italic>. <jats:italic>\u03b1<\/jats:italic> is arbitrary (&lt; <jats:italic>\u03ba<\/jats:italic>(<jats:italic>A<\/jats:italic>)), so rank(<jats:italic>T<\/jats:italic>) \u2265 <jats:italic>\u03ba<\/jats:italic>(<jats:italic>A<\/jats:italic>). Q.E.D.<\/jats:p>","DOI":"10.2307\/2271985","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:26:19Z","timestamp":1146950779000},"page":"594-612","source":"Crossref","is-referenced-by-count":1,"title":["A converse of the Barwise completeness theorem"],"prefix":"10.1017","volume":"38","author":[{"given":"Jonathan","family":"Stavi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200055353_ref003","first-page":"143","volume-title":"Proceedings of Symposia in Pure Mathematics","volume":"13","author":"Jensen","year":"1971"},{"key":"S0022481200055353_ref002","first-page":"108","volume":"36","author":"Barwise","year":"1971","journal-title":"The next admissible set"},{"key":"S0022481200055353_ref001","first-page":"226","volume":"34","author":"Barwise","year":"1969","journal-title":"Infinitary logic and admissible sets"},{"key":"S0022481200055353_ref006","volume-title":"Memoirs of the American Mathematical Society","author":"L\u00e9vy","year":"1965"},{"key":"S0022481200055353_ref004","first-page":"80","volume-title":"Lecture Notes in Mathematics","volume":"72","author":"Karp","year":"1968"},{"key":"S0022481200055353_ref005","volume-title":"Model theory for infinitary logic","author":"Keisler","year":"1971"},{"key":"S0022481200055353_ref007","first-page":"204","volume-title":"Lecture Notes in Mathematics","volume":"72","author":"Tait","year":"1968"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200055353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:22:42Z","timestamp":1559244162000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200055353\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1973,12]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1973,12]]}},"alternative-id":["S0022481200055353"],"URL":"https:\/\/doi.org\/10.2307\/2271985","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1973,12]]}}}