Skip to main content
Bounty Ended with 250 reputation awarded by Mikhail Katz
Added more detail to the definition of the extended induction scheme.
Source Link
Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105

In the classical setting, the result of the type that is asked in the question was established by Harvey Friedman, answering a question of Abraham Robinson, andRobinson; Friedman's results is reported in the following paper of Kreisel:

Axiomatizations of nonstandard analysis that are conservative extensions of formal systems for classical standard analysis, by G. Kreisel, in Applications of Model theory to Algebra, Analysis, and Probability (W. A. J. Luxemburg, editor), Holt, Rinehart and Winston, New York, 1969, pp. 93-106.

Friedman's result says that a particular theory $^*\mathsf{PA}$ of nonstandard numbers, together with the so-called $^*\Pi_{\infty}\mathsf{-Induction}$ is conservative over $\mathsf{PA}$. $^*\mathsf{PA}$ is formulated in an extension of $PA$$\mathsf{PA}$ with a new unary predicate $N(x)$, its axioms asserts the existence of an element outside of $N(x)$ [i.e., an "infinite" element], the transfer principle [that asserts through infinitely many axioms that the submodel determined by $N(x)$ is an elementary submodel of the whole model], and an axioms that says that the model determined by $N(x)$ is an initial segment of the whole model.

Friedman'sModels of $^*\mathsf{PA}$ are of the form $(M,+,*,N)$, where $(M,+,*,<)\models \mathsf{PA}$, $N$ is a proper initial segment of $M$ that is closed under $+$ and $*$, and $(N,+,*,<)$ is an elementary submodel of $(M,+,*,<)$. In this context, $(M,+,*,N)$ satisfies $^{*}\Pi_{\infty}\mathsf{-Induction}$, if for every parametrically definable subset $D$ of $(M,+,*,N)$, $(N,+,*,<,D\cap M)$ satisfies $\mathsf{PA}$ in the extended language that includes an extra predicate interpreted by $D\cap M$.

Friedman gave a direct proof of his conservatity resultsresult, but his proof can be easily established as a corollary ofmade shorter by using Phillips' refinement of the MacdowellMacDowell-Specker Theorem that says; the refinement states that every model of $\mathcal{M}$ of $\mathsf{PA}$ has a conservativeconservative elementary end extension $\mathcal{N}$ [i.e., $\mathcal{N}$ is an elementary end extension of $\mathcal{M}$ with the property that if $D$ is a parametrically definable subset of the universe of $\mathcal{N}$, then the intersection of $D$ with the universe of $\mathcal{M}$ is parametrically definable in $\mathcal{M}$].

Friedman's result is stated as a starting point of the process of gauging the strength of saturation principles in nonstandard theories of arithmetic in the following paper (see Proposition 2.3 for the statement of Friedman's result).

The Stengthstrength of nonstandard methods in arithmetic, by C.W. Henson, M. Kaufmann, and H.J. Keisler, Journal of Symbolic Logic, Dec. 1984.

A more recent result that generalizes Friedman's theorem pertains to a nonstandard variant of $\mathsf{ACA_0}$, here $\mathsf{ACA_0}$ is a well-known subsystem of the first order formulation of second order number theory that is conservative over $\mathsf{PA}$. This result is reported as Theorem 7.10 of the following paper (and is an immediate corollary of a result of mine, as mentioned by Keisler).

Nonstandard Arithmetic and reverse mathematics, by H.J. Keisler, The Bulletin of Symbolic Logic, March 2006.

In the classical setting, the result of the type that is asked in the question was established by Harvey Friedman, answering a question of Abraham Robinson, and reported in the following paper of Kreisel:

Axiomatizations of nonstandard analysis that are conservative extensions of formal systems for classical standard analysis, by G. Kreisel, in Applications of Model theory to Algebra, Analysis, and Probability (W. A. J. Luxemburg, editor), Holt, Rinehart and Winston, New York, 1969, pp. 93-106.

Friedman's result says that a particular theory $^*\mathsf{PA}$ of nonstandard numbers, together with the so-called $^*\Pi_{\infty}\mathsf{-Induction}$ is conservative over $\mathsf{PA}$. $^*\mathsf{PA}$ is formulated in an extension of $PA$ with a new unary predicate $N(x)$, its axioms asserts the existence of an element outside of $N(x)$ [i.e., an "infinite" element], the transfer principle [that asserts through infinitely many axioms that the submodel determined by $N(x)$ is an elementary submodel of the whole model], and an axioms that says that the model determined by $N(x)$ is an initial segment of the whole model.

Friedman's conservatity results can be easily established as a corollary of Phillips' refinement of the Macdowell-Specker Theorem that says that every model of $\mathcal{M}$ of $\mathsf{PA}$ has a conservative elementary end extension $\mathcal{N}$ [i.e., $\mathcal{N}$ is an elementary end extension of $\mathcal{M}$ with the property that if $D$ is a parametrically definable subset of the universe of $\mathcal{N}$, then the intersection of $D$ with the universe of $\mathcal{M}$ is parametrically definable in $\mathcal{M}$].

Friedman's result is stated as a starting point of gauging the strength of saturation principles in nonstandard theories of arithmetic in the following paper (see Proposition 2.3 for the statement of Friedman's result).

The Stength of nonstandard methods in arithmetic, by C.W. Henson, M. Kaufmann, and H.J. Keisler, Journal of Symbolic Logic, Dec. 1984.

A more recent result that generalizes Friedman's theorem pertains to a nonstandard variant of $\mathsf{ACA_0}$, here $\mathsf{ACA_0}$ is a well-known subsystem of the first order formulation of second order number theory that is conservative over $\mathsf{PA}$. This result is reported as Theorem 7.10 of the following paper (and is an immediate corollary of a result of mine, as mentioned by Keisler).

Nonstandard Arithmetic and reverse mathematics, by H.J. Keisler, The Bulletin of Symbolic Logic, March 2006.

In the classical setting, the result of the type that is asked in the question was established by Harvey Friedman, answering a question of Abraham Robinson; Friedman's results is reported in the following paper of Kreisel:

Axiomatizations of nonstandard analysis that are conservative extensions of formal systems for classical standard analysis, by G. Kreisel, in Applications of Model theory to Algebra, Analysis, and Probability (W. A. J. Luxemburg, editor), Holt, Rinehart and Winston, New York, 1969, pp. 93-106.

Friedman's result says that a particular theory $^*\mathsf{PA}$ of nonstandard numbers, together with the so-called $^*\Pi_{\infty}\mathsf{-Induction}$ is conservative over $\mathsf{PA}$. $^*\mathsf{PA}$ is formulated in an extension of $\mathsf{PA}$ with a new unary predicate $N(x)$, its axioms asserts the existence of an element outside of $N(x)$ [i.e., an "infinite" element], the transfer principle [that asserts through infinitely many axioms that the submodel determined by $N(x)$ is an elementary submodel of the whole model], and an axioms that says that the model determined by $N(x)$ is an initial segment of the whole model.

Models of $^*\mathsf{PA}$ are of the form $(M,+,*,N)$, where $(M,+,*,<)\models \mathsf{PA}$, $N$ is a proper initial segment of $M$ that is closed under $+$ and $*$, and $(N,+,*,<)$ is an elementary submodel of $(M,+,*,<)$. In this context, $(M,+,*,N)$ satisfies $^{*}\Pi_{\infty}\mathsf{-Induction}$, if for every parametrically definable subset $D$ of $(M,+,*,N)$, $(N,+,*,<,D\cap M)$ satisfies $\mathsf{PA}$ in the extended language that includes an extra predicate interpreted by $D\cap M$.

Friedman gave a direct proof of his conservatity result, but his proof can be made shorter by using Phillips' refinement of the MacDowell-Specker Theorem; the refinement states that every model of $\mathcal{M}$ of $\mathsf{PA}$ has a conservative elementary end extension $\mathcal{N}$ [i.e., $\mathcal{N}$ is an elementary end extension of $\mathcal{M}$ with the property that if $D$ is a parametrically definable subset of the universe of $\mathcal{N}$, then the intersection of $D$ with the universe of $\mathcal{M}$ is parametrically definable in $\mathcal{M}$].

Friedman's result is stated as a starting point of the process of gauging the strength of saturation principles in nonstandard theories of arithmetic in the following paper (see Proposition 2.3 for the statement of Friedman's result).

The strength of nonstandard methods in arithmetic, by C.W. Henson, M. Kaufmann, and H.J. Keisler, Journal of Symbolic Logic, Dec. 1984.

A more recent result that generalizes Friedman's theorem pertains to a nonstandard variant of $\mathsf{ACA_0}$, here $\mathsf{ACA_0}$ is a well-known subsystem of the first order formulation of second order number theory that is conservative over $\mathsf{PA}$. This result is reported as Theorem 7.10 of the following paper (and is an immediate corollary of a result of mine, as mentioned by Keisler).

Nonstandard Arithmetic and reverse mathematics, by H.J. Keisler, The Bulletin of Symbolic Logic, March 2006.

Source Link
Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105

In the classical setting, the result of the type that is asked in the question was established by Harvey Friedman, answering a question of Abraham Robinson, and reported in the following paper of Kreisel:

Axiomatizations of nonstandard analysis that are conservative extensions of formal systems for classical standard analysis, by G. Kreisel, in Applications of Model theory to Algebra, Analysis, and Probability (W. A. J. Luxemburg, editor), Holt, Rinehart and Winston, New York, 1969, pp. 93-106.

Friedman's result says that a particular theory $^*\mathsf{PA}$ of nonstandard numbers, together with the so-called $^*\Pi_{\infty}\mathsf{-Induction}$ is conservative over $\mathsf{PA}$. $^*\mathsf{PA}$ is formulated in an extension of $PA$ with a new unary predicate $N(x)$, its axioms asserts the existence of an element outside of $N(x)$ [i.e., an "infinite" element], the transfer principle [that asserts through infinitely many axioms that the submodel determined by $N(x)$ is an elementary submodel of the whole model], and an axioms that says that the model determined by $N(x)$ is an initial segment of the whole model.

Friedman's conservatity results can be easily established as a corollary of Phillips' refinement of the Macdowell-Specker Theorem that says that every model of $\mathcal{M}$ of $\mathsf{PA}$ has a conservative elementary end extension $\mathcal{N}$ [i.e., $\mathcal{N}$ is an elementary end extension of $\mathcal{M}$ with the property that if $D$ is a parametrically definable subset of the universe of $\mathcal{N}$, then the intersection of $D$ with the universe of $\mathcal{M}$ is parametrically definable in $\mathcal{M}$].

Friedman's result is stated as a starting point of gauging the strength of saturation principles in nonstandard theories of arithmetic in the following paper (see Proposition 2.3 for the statement of Friedman's result).

The Stength of nonstandard methods in arithmetic, by C.W. Henson, M. Kaufmann, and H.J. Keisler, Journal of Symbolic Logic, Dec. 1984.

A more recent result that generalizes Friedman's theorem pertains to a nonstandard variant of $\mathsf{ACA_0}$, here $\mathsf{ACA_0}$ is a well-known subsystem of the first order formulation of second order number theory that is conservative over $\mathsf{PA}$. This result is reported as Theorem 7.10 of the following paper (and is an immediate corollary of a result of mine, as mentioned by Keisler).

Nonstandard Arithmetic and reverse mathematics, by H.J. Keisler, The Bulletin of Symbolic Logic, March 2006.