Table of the consistency strength about NF-style theory
editBeth number | NF-style set theory | ZF-style set theory | Typed-style theory | Higher-order arithmetic |
---|---|---|---|---|
[2] | [3] |
| ||
[5][6][A],
|
[3] | |||
[7] | ||||
[B] | ||||
[8] | [9]p. 869 | |||
[10]
|
[11], | [10]
|
||
[2][4] | [3] | , | ||
, [15] Universal set |
[3]
(a tangled web of cardinals)[17] |
|
||
is linearly ordered | ||||
[18]
the NF set are the real external ones |
||||
[10]
|
||||
[19] | ||||
[10] |
|
|||
[10]
|
(there is a weakly compact cardinal) |
|||
[10] |
|
Key
editThis is a list of symbols used in this table:
- represents .
- represents .
- in this table only denotes "exist a Dedekind infinite set".
All theories that do not have sufficient information to infer their consistency strength ordering, but whose consistency proofs are explicit, are colored yellow. All theories without consistency proofs are colored orange.
This is a list of the abbreviations used in this table:
- NF-style set theory
- is a subsystem of both and , axiomatized as extensionality, pair set, power set, sumset, and stratified separation.
- is a subsystem of , axiomatized as untyped .
- is a subsystem of like , axiomatized as untyped .
- is a subsystem of , in which only comprehension is restricted to those formulae which can be stratified using no more than three types. It is not clear whether it is appropriate to put on this row.
- see NF with urelements.^A It is not recommended to read references that are too old and can be read instead [11]
- is with urelements.
- the system of set theory that has the same nonlogical axioms as but is embedded in an intuitionistic logic. , , , and are the same theory.^B It is not clear whether it is appropriate to put on this row, because we just have and don't have a proof for and . That is, there might be a largest finite cardinal , which would contain a finite set U that is "unenlargeable", that not exist set .[20]
- see New Foundations#Definition.
- is the theory obtained by adding class notion to . [21]Its equiconsistency with implies that we cannot prove anything about classes that are not sets.
- is linearly ordered, There is currently no proof of its consistency.
- is + comprehension for stratified formules of the language using only finitely many types. Its model are exactly the models for which the NF set are the real external ones.
- axiomatized as .
- axiomatized as .
- axiomatized as .
- axiomatized as .
- axiomatized as .
- axiomatized as .
- axiomatized as is finite.
- axiomatized as .
- axiomatized as .
The axioms listed below are higher infinite axioms specific to NF-style set theory, and they also apply to NF-style type theory. When used individually, they are not necessarily very strong in the traditional sense (such as ), but when used in combination, they are indeed very strong.
- NF-style higher infinite
- or is Rosser's Axiom of Counting, which asserts that the set of natural numbers is a strongly Cantorian set.
- is Axiom of strongly Cantorian separation, which asserts that for any strongly Cantorian set A and any formula (not necessarily stratified) the set exists.
- is Axiom of Cantorian Sets, which asserts that Every Cantorian set is strongly Cantorian.
- is Axiom of Large Ordinals, which asserts that for each non-Cantorian ordinal , there is a natural number n such that .
- is Axiom of Small Ordinals, which asserts that for any formula (not necessarily stratified), there is a set A such that the elements of A which are strongly Cantorian ordinals are exactly the strongly Cantorian ordinals such that .
- ZF-style set theory
- see Mac Lane set theory.
- as with foundation weakened to allow Quine atoms and an axiom scheme asserting the existence of an n-tree of cardinals for each concrete natural number n.
- A tangled web of cardinals is a tangled web of cardinals of order . For any infinite ordinal , a tangled web of cardinals of order is a function from the set of nonempty sets of ordinals with as maximum to cardinals such that
- If .
- If , the first order theory of a natural model of with base type is completely determined by , the n smallest elements of .
- see Zermelo set theory.
- see Zermelo–Fraenkel set theory.
- see Von Neumann–Bernays–Gödel set theory.
- see Morse–Kelley set theory.
- axiomatized as "there is a -complete nonprincipal ultrafilter on the proper class ordinal ".
- Higher infinite
- is a schema asserting the existence of an n-Mahlo cardinal for each concrete natural number n, and doesn't prove that n-Mahlo cardinals exist forall n, thus allowing for nonstandard counterexamples.
- asserts that there are n-Mahlo cardinals for every n.
- see weakly compact cardinal.
- see measurable cardinal.
- Type-style theory
- see New Foundations#Ordered pairs, is Axiom of type-level ordered pair, which can also be called flat ordered pair. In models without the Axiom of Choice , the existence of a type-level ordered pair implies but is not equivalent to the existence of an infinite set, but NFU with the axiom "there is an infinite set" interprets NFU with a type-level pair in a straightforward manner. It's well-known that proofs concerning like -strong cardinals run into problems if one doesn't use the flat ordered pair, and this is no different from ZF-style set theory.
- is typical ambiguity axiom, which asserts that validity for closed predicates is invariant under shifts of type levels.
- or is a subsystem of , axiomatized as unrestricted extensionality and those instances of comprehension in which no variable is assigned a type higher than that of the set asserted to exist.
- or is a subsystem of like , in which only free variables are allowed to have the type of the set asserted to exist by an instance of comprehension.
- axiomatized as Principia Mathematica ramified type theory without the axiom of reducibility.
- is with urelements, and is untyped .
- is with urelements, and is untyped .
- is Simple theory of types with all integer types, it has a realizability model and computational interpretation and is therefore consistent, and is untyped .
- see New Foundations#Tangled Type Theory. is untyped .
- or see New Foundations#Typed Set Theory. is untyped .
- is restricted to levels 0 to k − 1, forall k > 2.
- is "level 0 contains ≥ n things for every concrete n."
- is restricted to k = 3.
- Higher-order arithmetic
- is arithmetic with induction restricted to Δ0-predicates without any axiom asserting that exponentiation is total.
- see elementary function arithmetic.
- see Peano arithmetic.
- see Second-order arithmetic.
Notes
edit- ^ Forster, Thomas; Kaye, Richard (March 1991). "End-extensions preserving power set". The Journal of Symbolic Logic. 56 (1). doi:10.2307/2274922. ISSN 0022-4812.
- ^ a b Crabbé, Marcel (1982). "On the Consistency of an Impredicative Subsystem of Quine's NF". The Journal of Symbolic Logic. 47 (1). doi:10.2307/2273386. ISSN 0022-4812.
- ^ a b c d Holmes, M. Randall (1995). "The Equivalence of NF-Style Set Theories with "Tangled" Theories; The Construction of ω-Models of Predicative NF (and more)" (PDF). The Journal of Symbolic Logic. 60 (1). doi:10.2307/2275515. ISSN 0022-4812. Retrieved 2025-07-17.
- ^ a b Holmes, M. Randall (1999-04-01). "Subsystems of Quine's ``New Foundations with Predicativity Restrictions" (PDF). Notre Dame Journal of Formal Logic. 40 (2). doi:10.1305/ndjfl/1038949535. ISSN 0029-4527. Retrieved 2025-07-15.
- ^ Jensen, Ronald Björn (1968). "On the Consistency of a Slight (?) Modification of Quine's "New Foundations"". Synthese. 19 (1/2). ISSN 0039-7857.
- ^ Boffa, Maurice (1988). "ZFJ and the consistency problem for NF". Jahrbuch der Kurt Gödel Gesellschaft. 1 (102–106): 75--79.
- ^ Grishin, Vyacheslav Nikolaevich (1969). "Consistency of a fragment of Quine's NF system". Doklady Akademii Nauk SSSR (in Russian). 189 (2): 241--243 – via Russian Academy of Sciences.
- ^ a b Enayat, Ali and Kalantari, Iraj and Moniri, Mojtaba (2006). "From bounded arithmetic to second order arithmetic via automorphisms". Logic in Tehran. 26. Association for Symbolic Logic: 87--113.
{{cite journal}}
: CS1 maint: multiple names: authors list (link) - ^ G. Jäger, "The Strength of Admissibility Without Foundation". Journal of Symbolic Logic vol. 49, no. 3 (1984).
- ^ a b c d e f Holmes, M. Randall (2001). "Strong Axioms of Infinity in NFU" (PDF). The Journal of Symbolic Logic. 66 (1). doi:10.2307/2694912. ISSN 0022-4812. Retrieved 2025-07-15.
- ^ a b Adlešić, Tin; Čačić, Vedran (2024-12-13). "Boffa's construction and models for NFU". Studia Logica. doi:10.1007/s11225-024-10155-9. ISSN 1572-8730.
- ^ a b Pabion, J. F. (1980). "TT₃ + AxInf est équivalent à l'arithmétique du second ordre" (PDF). Comptes Rendus hebdomadaires des séances de l'Académie des Sciences de Paris (série A) (in French). 290: 1117--1118.
- ^ Blot, Valentin (2022-08-02). "A direct computational interpretation of second-order arithmetic via update recursion". Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. ACM: 1–11. doi:10.1145/3531130.3532458. ISBN 978-1-4503-9351-5.
- ^ Holmes, M. Randall; Wilshaw, Sky. "NF is Consistent" (version last ed.). arXiv:1503.01406. doi:10.48550/arXiv.1503.01406.
- ^ Wang, Hao (March 1950). "A formal system of logic". The Journal of Symbolic Logic. 15 (1). doi:10.2307/2268438. ISSN 0022-4812. Retrieved 2025-07-17.
- ^ Grishin, Vyacheslav Nikolaevich (1972). "The method of stratification in set theory". Russian, Ph. D. thesis, Moscow University (in Russian). 3 – via Russian Academy of Sciences.
- ^ Holmes, M. Randall; Wilshaw, Sky. "NF is Consistent" (version 22 ed.). arXiv:1503.01406v22.
{{cite web}}
: CS1 maint: url-status (link) - ^ Esser, Olivier and Forster, Thomas (2007). "Relaxing stratification" (PDF). Bulletin of the Belgian Mathematical Society-Simon Stevin. 14 (2). The Belgian Mathematical Society: 247--258. Archived from the original (PDF) on 2025-08-13. Retrieved 2025-08-13.
{{cite journal}}
: CS1 maint: multiple names: authors list (link) - ^ Solovay, Robert (2025-07-23). "The consistency strength of NFU_star". Archived from the original on 2025-07-23. Retrieved 2025-07-23.
- ^ Forster, Thomas E (2009). "A tutorial on constructive NF" (PDF). Proceedings of the 70th anniversary NF meeting in Cambridge. 16. Archived from the original (PDF) on 2025-07-18. Retrieved 2025-07-18.
- ^ Quine, Willard Van Orman (1976). Mathematical logic (Rev. ed., 8th print ed.). Cambridge [Mass.]: Harvard university press. ISBN 978-0-674-55450-4.