Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-30T23:18:31.135Z Has data issue: false hasContentIssue false
  • English
  • Français

Foundation versus induction in Kripke-Platek set theory

Published online by Cambridge University Press:  12 March 2014

Domenico Zambella
Domenico Zambella*
Affiliation:
Department of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

We denote by KP_ the fragment of set-theory containing the axioms of extensionality, pairing, union and foundation as well as the schemas of ∆0-comprehension and ∆0-collection, that is: Kripke-Platek set-theory (KP) with the axiom of foundation in place of the ∈-induction schema. The theory KP is obtained by adding to KP_ the schema of ∈-induction

Using ∈-induction it is possible to prove the existence of the transi tive closure without appealing to the axiom of infinity (see, e.g., [1]). Vice versa, when a theory proves the existence of the transitive closure, some induction is immediately ensured (by foundation and comprehension). This is not true in general: e.g., the whole of Zermelo-Fraenkel set-theory without the axiom of infinity does not prove ∈-induction (in fact, it does not prove the existence of the transitive closure; see, e.g., [3]). Open-induction is the schema of ∈-induction restricted to open formulas. We prove the following theorem.

KP_ proves open-induction.

We reason in a fixed but arbitrary model of KP_ whom we refer to as the model. The language is extended with a name for every set in the model. We call this constants parameters. Let φ(x) be a satisfiable open-formula possibly depending on parameters and with no free variable but x. We show that φ(x) is satisfied by an ∈-minimal set, that is, a set a such that φ(a) and (∀x ∈ a) ¬φ(x). We assume that no ordinal satisfies φ(x), otherwise the existence of a ∈-minimal set follows from foundation and comprehension.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 4 , December 1998 , pp. 1399 - 1403
Copyright
Copyright © Association for Symbolic Logic 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Barwise, J., Admissible sets and structures, Springer-Verlag, 1975.CrossRefGoogle Scholar
[2] Gogol, D., The ∀n∃-completeness of Zermelo-Fraenkel set theory, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 24 (1978), pp. 289–290.CrossRefGoogle Scholar
[3] Mancini, A., A note on recursive models of set theories, forthcoming.Google Scholar
[4] Omodeo, E., Parlamento, F., and Policriti, A., Decidability of ∃*∀-sentences in membership theories, Mathematical Logic Quarterly, vol. 42 (1996), pp. 41–58.CrossRefGoogle Scholar
[5] Parlamento, F. and Policriti, A., The logically simplest form of the infinity axiom, Proceedings of the American Mathematical Society, vol. 103 (1988), pp. 274–276.CrossRefGoogle Scholar