Proof of One Threshold for Finitely Many Monotone Conditions and for Tails

Each result cited is universally quantified over the data in its own statement.

Clause threshold. Assume that for every $p\in I$ there is $N\in\mathbb{N}$ with $P(p,N)$. Let $\psi(p,N)$ be a predicative formula expressing $P$, as in Conditions Expressed by a Predicative Formula, and Guards §expressed, and let $C$ and $u$ be fresh set variables: distinct from each other, occurring in $\psi$ nowhere, and distinct from $p$, $N$, $I$, $\mathbb{N}$ and the parameters of $\psi$. Let $\varphi(C)$ be the formula

$$\forall u\,(u\in C\Rightarrow u\in I)\Rightarrow\exists N\,\bigl(N\in\mathbb{N}\wedge\forall p\,(p\in C\Rightarrow\psi(p,N))\bigr),$$

with parameters $I$, $\mathbb{N}$ and those of $\psi$. It is built from $\psi$ and atomic formulas by connectives and quantifiers over the set variables $u$, $N$ and $p$ only, the abbreviations $\Rightarrow$ and $\forall$ being as in Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations §formula, so it is predicative by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations §predicative. By Subclasses and Subsets §subclass and as $\psi$ expresses $P$, for every set $C$, $\varphi(C)$ says: if $C\subseteq I$, then there is $N\in\mathbb{N}$ with $P(p,N)$ for every $p\in C$. We show that $\varphi(C)$ holds for every finite set $C$, by Induction over Finite Sets, and Predicative Formulas for the Segments [n] and for Finiteness §induction.

Base. $1\in\mathbb{N}$ by Natural Numbers as Indices: ℕ ⊆ ℕ₀, 1 ∈ ℕ₀, and the Two Readings of an Operation from 1 to n §one, and $\emptyset$ has no element, so $N=1$ witnesses $\varphi(\emptyset)$.

Step. Let $C$ be a finite set with $\varphi(C)$, let $x$ be a set with $x\notin C$, and let $C\cup\{x\}\subseteq I$. Then $C\subseteq I$, so by $\varphi(C)$ there is $N_{1}\in\mathbb{N}$ with $P(p,N_{1})$ for every $p\in C$; and $x\in I$, so by the assumption there is $N_{2}\in\mathbb{N}$ with $P(x,N_{2})$. By Arithmetic and Order of the Natural Numbers §trichotomy, exactly one of $N_{1}<N_{2}$, $N_{1}=N_{2}$ and $N_{2}<N_{1}$ holds; let $N=N_{2}$ in the first two cases and $N=N_{1}$ in the third. In each case $N\in\mathbb{N}$, $N_{1}\le N$ and $N_{2}\le N$, by Arithmetic and Order of the Natural Numbers §partial-order ($a\le a$, and $a\le b$ if $a<b$ or $a=b$). Every $p\in C$ lies in $I$, so $P(p,N)$ by monotonicity from $P(p,N_{1})$; and $P(x,N)$ by monotonicity from $P(x,N_{2})$. Every element of $C\cup\{x\}$ lies in $C$ or equals $x$, so $P(p,N)$ for every $p\in C\cup\{x\}$, and $\varphi(C\cup\{x\})$ holds.

By Induction over Finite Sets, and Predicative Formulas for the Segments [n] and for Finiteness §induction, $\varphi(C)$ holds for every finite set $C$, in particular for $C=I$. As $I\subseteq I$, there is $N\in\mathbb{N}$ with $P(p,N)$ for every $p\in I$. Each step picks a witness of one existential statement at a time, and no choice principle is used.

Clause tails. Let $\chi(p,n)$ be a predicative formula expressing $Q$, and let $R$ be a fresh variable, distinct from $p$, $N$, $n$, $I$, $\mathbb{N}$ and the parameters of $\chi$, whose value is the order $\le$ of $\mathbb{N}$ (that of Arithmetic and Order of the Natural Numbers); so for $N,n\in\mathbb{N}$, $(N,n)\in R$ if and only if $N\le n$. Let $P(p,N)$ be the formula

$$\forall n\,\bigl((n\in\mathbb{N}\wedge(N,n)\in R)\Rightarrow\chi(p,n)\bigr),$$

with $n$ bound. It is predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols §closure, as no quantifier in it is applied to a class variable, so it expresses itself; and, as $\chi$ expresses $Q$, for $N\in\mathbb{N}$ it holds if and only if $Q(p,n)$ holds for every $n\in\mathbb{N}$ with $N\le n$. $P$ is monotone: if $p\in I$, $N,N'\in\mathbb{N}$, $N\le N'$ and $P(p,N)$, then for every $n\in\mathbb{N}$ with $N'\le n$ we have $N\le n$ by Arithmetic and Order of the Natural Numbers §partial-order, hence $Q(p,n)$; so $P(p,N')$. The hypothesis of the clause tails says that for every $p\in I$ there is $N\in\mathbb{N}$ with $P(p,N)$. The clause threshold gives one $N\in\mathbb{N}$ with $P(p,N)$ for every $p\in I$, that is, with $Q(p,n)$ for every $p\in I$ and every $n\in\mathbb{N}$ with $N\le n$.