Full and hat inductive definitions are equivalent in NBG

Archive for Mathematical Logic 54 (1-2):75-112 (2015)
  Copy   BIBTEX

Abstract

A new research project has, quite recently, been launched to clarify how different, from systems in second order number theory extending ACA0, those in second order set theory extending NBG are. In this article, we establish the equivalence between Δ01-LFP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^1_0\mbox{\bf-LFP}}$$\end{document} and Δ01-FP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^1_0\mbox{\bf-FP}}$$\end{document}, which assert the existence of a least and of a fixed point, respectively, for positive elementary operators. Our proof also shows the equivalence between ID1 and ID^1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\widehat{\it ID}_1}$$\end{document}, both of which are defined in the standard way but with the starting theory PA replaced by ZFC.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A note on theories for quasi-inductive definitions.Riccardo Bruni - 2009 - Review of Symbolic Logic 2 (4):684-699.
Quantifiers, games and inductive definitions.Peter Aczel - 1975 - Journal of Symbolic Logic 82 (2):1--14.
Non-deterministic inductive definitions.Benno van den Berg - 2013 - Archive for Mathematical Logic 52 (1-2):113-135.
Functional interpretation and inductive definitions.Jeremy Avigad & Henry Towsner - 2009 - Journal of Symbolic Logic 74 (4):1100-1120.
Global inductive definability.Jon Barwise & Yiannis N. Moschovakis - 1978 - Journal of Symbolic Logic 43 (3):521-534.
Monotone inductive definitions in explicit mathematics.Michael Rathjen - 1996 - Journal of Symbolic Logic 61 (1):125-146.
What Is Classical Mereology?Paul Hovda - 2009 - Journal of Philosophical Logic 38 (1):55 - 82.

Analytics

Added to PP
2014-11-07

Downloads
15 (#809,217)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?