Proof of The Graph of Multiplication on ℕ₀ Is Given by a Predicative Formula

Write ${\cdot}=\{w:\sigma(w)\}$ for the multiplication on $\mathbb{N}_{0}$, $\sigma$ being the formula of that class abstraction; it quantifies over set variables only.

The graph on three variables. Let $q$ and $p$ be set variables and $S$ a class variable, distinct from $x_{0},x_{1},x_{2}$ and not occurring in $\sigma$. By Predicativity under Renaming of Set Variables by Variables, of Formulas with Ordered Pairs, and of Formulas for Relations, Functions, Maps, Injectivity, Surjectivity and Bijectivity (iv), with the class variable $S$ for $s$, the formula $((x_{1},x_{2}),p)\in S$ is predicative, and under an assignment of sets to $x_{1},x_{2},p$ and a class to $S$ it holds if and only if $((x_{1},x_{2}),p)$ is an element of $S$. Since the ordered pairs in it are eliminated as defined set symbols (Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (viii)), $S$ occurs in it only in atomic parts $z\in S$ with $z$ a set variable. Replacing each such part by $\sigma(z)$ (renaming bound variables of $\sigma$ where necessary) is exactly the elimination of the class term $\cdot$ from $((x_{1},x_{2}),p)\in{\cdot}$ prescribed by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (ix). The result is predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols (i), as the replacement introduces no quantifier over a class variable; and since a set $z$ lies in $\cdot$ if and only if $\sigma(z)$ holds (Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols (viii)), it holds exactly when $((x_{1},x_{2}),p)\in S$ holds with $\cdot$ assigned to $S$, that is, exactly when $((x_{1},x_{2}),p)\in{\cdot}$. Let $\psi$ be the formula

$$\exists q\,\exists p\,\bigl(q=(x_{1},x_{2})\wedge x_{0}=(q,p)\wedge((x_{1},x_{2}),p)\in{\cdot}\bigr),$$

its first two conjuncts being formulas of Predicativity under Renaming of Set Variables by Variables, of Formulas with Ordered Pairs, and of Formulas for Relations, Functions, Maps, Injectivity, Surjectivity and Bijectivity (ii). All quantifiers of $\psi$, those of its conjuncts included, bind set variables only, so $\psi$ is predicative, and its free variables are among $x_{0},x_{1},x_{2}$. By the reading in Predicativity under Renaming of Set Variables by Variables, of Formulas with Ordered Pairs, and of Formulas for Relations, Functions, Maps, Injectivity, Surjectivity and Bijectivity (ii) and the one just obtained for the third conjunct, under an assignment of sets to $x_{0},x_{1},x_{2}$, $\psi$ holds if and only if there are sets $q$ and $p$ with

$$q=(x_{1},x_{2}),\qquad x_{0}=(q,p),\qquad ((x_{1},x_{2}),p)\in{\cdot}.$$

Fix such an assignment. If $\psi$ holds, take sets $q$ and $p$ as displayed. Then $x_{0}=((x_{1},x_{2}),p)$, and by Multiplication on Omega: Products Lie in Omega, Multiplication Is a Binary Operation with Value the Product, and Membership in the Multiplication (iii) the third relation gives $x_{1}\in\mathbb{N}_{0}$, $x_{2}\in\mathbb{N}_{0}$ and $p=x_{1}\cdot x_{2}$; hence $x_{0}=((x_{1},x_{2}),x_{1}\cdot x_{2})$, and the condition of (i) holds. Conversely, suppose $x_{1},x_{2}\in\mathbb{N}_{0}$ and $x_{0}=((x_{1},x_{2}),x_{1}\cdot x_{2})$. Take $q=(x_{1},x_{2})$ and $p=x_{1}\cdot x_{2}$ (sets, as an ordered pair and an element of $\mathbb{N}_{0}$ by Multiplication on Omega: Products Lie in Omega, Multiplication Is a Binary Operation with Value the Product, and Membership in the Multiplication (i)). Then $q=(x_{1},x_{2})$ and $x_{0}=(q,p)$, and $((x_{1},x_{2}),p)\in{\cdot}$ by Multiplication on Omega: Products Lie in Omega, Multiplication Is a Binary Operation with Value the Product, and Membership in the Multiplication (iii); so $\psi$ holds. Thus $\psi$ expresses the condition of (i), in the sense of Conditions Expressed by a Predicative Formula, and Guards (ii).

The graph on one variable. Let $\chi$ be the formula $\exists x_{1}\,\exists x_{2}\,\psi$. The new quantifiers bind set variables, so $\chi$ is predicative by Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (v) (with Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (vi), as for $\psi$), and its only possible free variable is $x_{0}$. Under an assignment of a set to $x_{0}$, $\chi$ holds if and only if there are sets $m$ and $n$ such that $\psi$ holds when $m$ and $n$ are assigned to $x_{1}$ and $x_{2}$ (Formulas of the Language of Class Theory, Free Variables, Predicative Formulas and Abbreviations (iv)); by (i), as just proved, this is the case if and only if

$$m\in\mathbb{N}_{0},\qquad n\in\mathbb{N}_{0},\qquad x_{0}=((m,n),m\cdot n).$$

So $\chi$ holds exactly when the condition of (ii) holds, and it expresses that condition by Conditions Expressed by a Predicative Formula, and Guards (ii).