2023/04/20 by Calliope Ryan‐Smith, Ryan-Smith, Calliope
Computer Science · Mathematics · #03D05 #03E70 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #F.4.1 #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO) #Logic, Reasoning, and Knowledge
paper · doi:10.48550/arxiv.2304.10291
openalex publication_date 2023/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Stratified formulae were introduced by Quine as an alternative way to attack Russell's Paradox. Instead of limiting comprehension by size (as in ZF set theory, using its axiom scheme of separation), unlimited comprehension is given to formulae that are in some sense descended from formulae of typed set theory. By keeping variables in a stratified structure, the most common candidates for inconsistency such as \x| x∉ x\ are eliminated. Under the usual syntax of set theory, the set of stratified formulae form a formal language. We show that, unlike the full class of well-formed formulae of set theory, this language is not context-free, and extend the result to its complement. Therefore, much like the axioms of PA and ZF (under their usual axiomatizations), the theory NF as a formal language is not context-free. We then introduce a non-standard syntax of set theory and show that with this syntax there is a restricted class of formulae, the exo-stratified formulae, that is context-free and full (up to relabelling of variables).