Stratifiable Formulae are not Context-Free

arXiv2304.10291MaRDI QIDQ6433749FDOQ6433749

Authors: Calliope Ryan-Smith 

Publication date: 20 April 2023

Abstract: Using the usual syntax for first-order formulae, the set of stratifiable formulae of set theory forms a formal language. We show that this language, and its complement, are not context-free. However, in a slightly enriched syntactic system we may consider a subset of the stratifiable formulae that is full under $alpha$-equivalence, and demonstrate that this set is context-free.

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Nonclassical and second-order set theories (03E70)

This page was built for publication: Stratifiable Formulae are not Context-Free

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433749)