numeral

**natural deduction** metalanguage, practical foundations

**type theory** (dependent, intensional, observational type theory, homotopy type theory)

**computational trinitarianism** = **propositions as types** +**programs as proofs** +**relation type theory/category theory**

In informal mathematical speech and writing, a **numeral** refers to any notation or terms which denotes a natural number directly. Usually, in mathematics, this refers to base ten place-value notation, so that for instance $0$, $2$, $13$, and $890$ are numerals.

In the more formal world of logic and type theory, a **numeral** generally means a term whose type is a natural numbers type and which is of canonical form. The meaning of “canonical form” may vary with the formal theory, but with the usual presentation of the natural numbers as an inductive type generated by zero $0$ and the successor operation $s$, the numerals are the terms of the form

$s(s(\cdots s(s(0))\cdots )).$

Often, the numeral representing the natural number $n$ — which is to say, the term with $s$ applied $n$ times to $0$ — is denoted by $\underline{n}$. Thus, for instance, $\underline{2}$ means $s(s(0))$. It is important to note that $\underline{2}$ is not (usually) a term *inside* the formal system being considered; it is a “meta-notation” which stands for the term $s(s(0))$. (One might say that the underline converts *informal* numerals to *formal* ones.) In particular, any statement which quantifies over a natural number $n$ that occurs in a term $\underline{n}$ can only be expressed in the metatheory?.

Not every term of natural number type $\mathbb{N}$ is a numeral; consider for instance $\underline{2}+\underline{2}$. However, good formal systems have the property of canonicity, which in this context means that every term of type $\mathbb{N}$ *computes to*, or is *provably equal to*, a numeral. In our example, if $+$ is defined by recursion, there is a sequence of beta-reduction steps leading from $\underline{2}+\underline{2}$ to $\underline{4}$. (Canonicity is about terms in the empty context?; in a context with free variables of type $\mathbb{N}$, then of course there will be more terms of type $\mathbb{N}$, built out of these variables.)

If we add to such a formal system an axiom using an existential statement, then this is equivalent to adding to the language an additional term for a natural number that is not (and may not provably be equal to) any canonical numeral. For example, in $PA + \neg{Con(PA)}$ (Peano arithmetic? plus the axiom that Peano arithmetic is inconsistent?), we have the axiom

$\exists n, (n \vdash_{PA} \bot) ,$

stating the existence of a number $n$ that is the Gödel number? of a proof in $PA$ of a falsehood. If we instead extend the language of $PA$ with a new symbol $※$ and add the axiom

$※ \vdash_{PA} \bot ,$

then (assuming that $PA$ and so $PA + \neg{Con(PA)}$ is in fact consistent) one can prove

$\underline{n} \neq ※$

in this system for every natural number $n$, but one cannot prove

$\forall n,\, n \neq ※$

(which is actually trivially refutable).

Revised on November 20, 2012 01:11:43
by Toby Bartels
(64.89.57.196)