Decidable fragments of the simple theory of types with infinity and NF

Abstract

We identify complete fragments of the simple theory of types with infinity (TSTI) and Quine's new foundations (NF) set theory. We show that TSTI decides every sentence φ in the language of type theory that is in one of the following forms: (A) φ = ∀x r11 ⋯ ∀xrkk ∃ys11 ⋯ ∃ys11 θ where the superscripts denote the types of the variables, s1 > ⋯ > s1, and θ is quantifier-free, (B) φ = ∀x r11 ⋯ ∀xrkk ∃ys11 ⋯ ∃ys11 θ where the superscripts denote the types of the variables and θ is quantifier-free. This shows that NF decides every stratified sentence φ in the language of set theory that is in one of the following forms: (A′) φ = ∀x1 ⋯ ∀xk ∃y1 ⋯ ∃yl θ where θ is quantifier-free and φ admits a stratification that assigns distinct values to all of the variables y1,⋯, yl, (B′) φ = ∀x1 ⋯ ∀xk ∃y1 ⋯ ∃yl θ where θ is quantifier-free and <p admits a stratification that assigns the same value to all of the variables y1,⋯, yl.