{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:57:35Z","timestamp":1772521055558,"version":"3.50.1"},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3479,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,9]]},"abstract":"<jats:p>In reverse mathematics, one formalizes theorems of ordinary mathematics in second order arithmetic and attempts to discover which set theoretic axioms are required to prove these theorems. Often, this project involves making choices between classically equivalent definitions for the relevant mathematical concepts. In this paper, we consider a number of equivalent definitions for the notions of well quasi-order and better quasi-order and examine how difficult it is to prove the equivalences of these definitions.<\/jats:p><jats:p>As usual in reverse mathematics, we work in the context of subsystems of second order arithmetic and take RCA<jats:sub>0<\/jats:sub> as our base system. RCA<jats:sub>0<\/jats:sub> is the subsystem formed by restricting the comprehension scheme in second order arithmetic to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007581_inline1\"\/> formulas and adding a formula induction scheme for <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007581_inline2\"\/> formulas. For the purposes of this paper, we will be concerned with fairly weak extensions of RCA<jats:sub>0<\/jats:sub> (indeed strictly weaker than the subsystem ACA<jats:sub>0<\/jats:sub> which is formed by extending the comprehension scheme in RCA<jats:sub>0<\/jats:sub> to cover all arithmetic formulas) obtained by adjoining certain combinatorial principles to RCA<jats:sub>0<\/jats:sub>. Among these, the most widely used in reverse mathematics is Weak K\u00f6nig's Lemma; the resulting theory WKL<jats:sub>0<\/jats:sub> is extensively documented in [11] and elsewhere.<\/jats:p><jats:p>We give three other combinatorial principles which we use in this paper. In these principles, we use <jats:italic>k<\/jats:italic> to denote not only a natural number but also the finite set {0, \u2026, <jats:italic>k<\/jats:italic> \u2212 1}.<\/jats:p>","DOI":"10.2178\/jsl\/1096901762","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:41:33Z","timestamp":1109799693000},"page":"683-712","source":"Crossref","is-referenced-by-count":26,"title":["Reverse mathematics and the equivalence of definitions for well and better quasi-orders"],"prefix":"10.1017","volume":"69","author":[{"given":"Peter","family":"Cholak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marcone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reed","family":"Solomon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007581_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-5315-4_14"},{"key":"S0022481200007581_ref006","volume-title":"Reverse mathematics 2001","author":"Marcone"},{"key":"S0022481200007581_ref001","first-page":"1","volume":"66","author":"Cholak","year":"2001","journal-title":"The strength of Ramsey's theorem for pairs"},{"key":"S0022481200007581_ref004","first-page":"923","volume":"66","author":"Herrmann","year":"2001","journal-title":"Infinite chains and antichains in computable partial orderings"},{"key":"S0022481200007581_ref009","first-page":"124","volume-title":"Recursive aspects of descriptive set theory","author":"Simpson","year":"1985"},{"key":"S0022481200007581_ref005","unstructured":"Hirschfeldt Denis R. and Shore Richard A. , Some facts about linear orderings provable in , to appear."},{"key":"S0022481200007581_ref011","volume-title":"Subsystems of second order arithmetic","author":"Simpson","year":"1998"},{"key":"S0022481200007581_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1994-1219735-8"},{"key":"S0022481200007581_ref010","first-page":"961","volume":"53","author":"Simpson","year":"1988","journal-title":"Ordinal numbers and the Hilbert basis theorem"},{"key":"S0022481200007581_ref003","article-title":"Computability-theoretic and proof-theoretic aspects of partial and linear orderings","author":"Downey","journal-title":"Israel Journal of Mathematics"},{"key":"S0022481200007581_ref002","first-page":"823","volume-title":"Handbook of recursive mathematics","volume":"2","author":"Downey","year":"1998"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T20:26:53Z","timestamp":1557174413000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007581\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["S0022481200007581"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1096901762","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]}}}