Factorization of polynomials and \(\Sigma ^ 0_ 1\) induction
type: Item
instance of: scholarly article
title: Factorization of polynomials and \(\Sigma ^ 0_ 1\) induction
zbMATH Open document ID: 0603.03019
DOI: 10.1016/0168-0072(86)90074-6
author: Stephen G. Simpson
author: Rick L. Smith
published in: Annals of Pure and Applied Logic
publication date: 1986-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 12L15
Mathematics Subject Classification ID: 12E05
zbMATH DE Number: 3972856
zbMATH Keywords: Reverse Mathematics
zbMATH Keywords: countable algebra
zbMATH Keywords: second order arithmetic
zbMATH Keywords: comprehension
zbMATH Keywords: induction
zbMATH Keywords: exponential function
zbMATH Keywords: elementary function arithmetic
MaRDI profile type: Publication
full work available at URL: 0168-0072(86)90074-6
OpenAlex ID: W2002594958
cites work: Addendum to ``Countable algebra and set existence axioms''
cites work: Q3699664
cites work: Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?
cites work: Q3395521
cites work: Q3884109
cites work: ∏ 0 1 Classes and Degrees of Theories
cites work: Effective procedures in field theory
cites work: Q4138726
cites work: Q5600870
description: scientific article; zbMATH DE number 3972856