Factorization of polynomials and \(\Sigma ^ 0_ 1\) induction (Q1082338): Difference between revisions

This paper is a contribution to Reverse Mathematics in the context of countable algebra. We build on the work of \textit{H. M. Friedman}, \textit{S. G. Simpson} and \textit{R. L. Smith} [Ann. Pure Appl. Logic 25, 141-181 (1983; Zbl 0575.03038); Addendum ibid. 28, 319-321 (1985; Zbl 0575.03039)]. Recall that \(RCA_ 0\) is the subsystem of second order arithmetic with \(\Delta^ 0_ 1\) comprehension and \(\Sigma^ 0_ 1\) induction. In the Friedman-Simpson-Smith paper, \(RCA_ 0\) was used as the weak base theory, and it was noted that many basic lemmas of countable algebra are provable there. In the present work, we consider a weaker theory \(RCA^*_ 0\) which consists of \(\Delta^ 0_ 1\) comprehension, \(\Sigma^ 0_ 0\) induction, and the exponential function. Thus \(RCA_ 0\) is equal to \(RCA^*_ 0\) plus \(\Sigma^ 0_ 1\) induction. We show that, over \(RCA^*_ 0\), \(\Sigma^ 0_ 1\) induction is equivalent to each of the following assertions: (1) any polynomial over a countable field can be factored into irreducible factors; (2) any polynomial over a countable field has at least one irreducible factor. In the last part of the paper, we present model- theoretic arguments showing that \(RCA^*_ 0\) is conservative over EFA (elementary function arithmetic) for \(\Pi^ 0_ 2\) sentences, and that \(WKL^*_ 0\) (consisting of \(RCA^*_ 0\) plus weak König's Lemma) is conservative over \(RCA^*_ 0\) for \(\Pi^ 1_ 1\) sentences. These results are analogous to the corresponding results for \(RCA_ 0\) due to \textit{L. Harrington} (unpublished).