In mathematics, a Gödel numbering for sequences provides an effective way to represent each finite sequence of natural numbers as a single natural number. While a set theoretical embedding is surely possible, the emphasis is on the effectiveness of the functions manipulating such representations of sequences: the operations on sequences (accessing individual members, concatenation) can be "implemented" using total recursive functions, and in fact by primitive recursive functions.
It is usually used to build sequential “data types” in arithmetic-based formalizations of some fundamental notions of mathematics. It is a specific case of the more general idea of Gödel numbering. For example, recursive function theory can be regarded as a formalization of the notion of an algorithm, and can be regarded as a programming language to mimic lists by encoding a sequence of natural numbers in a single natural number.Monk 1976: 56–58Csirmaz 1994: 99–100 (se

online

** Gödel numbering **

Besides using Gödel numbering to encode unique sequences of symbols into unique natural numbers (i.e. place numbers into mutually exclusive or one-to-one correspondence with the sequences), we can use it to encode whole “architectures” of sophisticated “machines”. For example, we can encode Markov algorithms,Monk 1976: 72–74 or Turing machinesMonk 1976: 52–55 into natural numbers and thereby prove that the expressive power of recursive function theory is no less than that of the former machine-like formalizations of algorithms.

** Accessing members **

Any such representation of sequences should contain all the information as in the original sequence—most importantly, each individual member must be retrievable. However, the length does not have to match directly; even if we want to handle sequences of different length, we can store length data as a surplus member, or as the other member of an ordered pair by using a pairing function.
We expect that there is an effective way for this information retrieval process in form of an appropriate total recursive function. We want to find a totally recursive function ''f'' with the property that
for all ''n'' and for any ''n''-length sequence of natural numbers $\backslash langle\; a\_0,\backslash dots\; a\_\; \backslash rangle$, there exists an appropriate natural number ''a'', called the Gödel number of the sequence, such that for all ''i'' where $0\backslash le\; i\; \backslash le\; n-1$, $f(a,i)\; =\; a\_i$.
There are effective functions which can retrieve each member of the original sequence from a Gödel number of the sequence. Moreover, we can define some of them in a constructive way, so we can go well beyond mere proofs of existence.

** Gödel's β-function lemma **

By an ingenious use of the Chinese remainder theorem, we can constructively define such a recursive function $\backslash beta$ (using simple number-theoretical functions, all of which can be defined in a total recursive way) fulfilling the specifications given above. Gödel defined the $\backslash beta$ function using the Chinese remainder theorem in his article written in 1931. This is a primitive recursive function.
Thus, for all ''n'' and for any ''n''-length sequence of natural numbers $\backslash langle\; a\_0,\backslash dots\; a\_\; \backslash rangle$, there exists an appropriate natural number ''a'', called the Gödel number of the sequence such that $\backslash beta(a,i)\; =\; a\_i$.Monk 1976: 58 (= Thm 3.46)

** Using a pairing function **

Our specific solution will depend on a pairing function—there are several ways to implement the pairing function, so one method must be selected. Now, we can abstract from the details of the implementation of the pairing function. We need only to know its “interface”: let $\backslash pi$, ''K'', and ''L'' denote the pairing function and its two projection functions, respectively, satisying specification
:$K\backslash left(\backslash pi\backslash left(x,y\backslash right)\backslash right)\; =\; x$
:$L\backslash left(\backslash pi\backslash left(x,y\backslash right)\backslash right)\; =\; y$
We shall not discuss and formalize the axiom for excluding alien objects here, as it is not required to understand the method.

** Remainder for natural numbers **

We shall use another auxiliary function that will compute the remainder for natural numbers. Examples:
* $\backslash mathrm(5,\; 3)\; =\; 2$
* $\backslash mathrm(7,\; 2)\; =\; 1$
It can be proven that this function can be implemented as a recursive function.

** Using the Chinese remainder theorem **

= Implementation of the β function

= Using the Chinese remainder theorem, we can prove that implementing $\backslash beta$ as :$\backslash beta(s,i)\; =\; \backslash mathrm\backslash left(K\backslash left(s\backslash right),\backslash left(i+1\backslash right)\backslash cdot\; L\backslash left(s\backslash right)+1\backslash right)$ will work, according to the specification we expect $\backslash beta$ to satisfy. We can use a more concise form by an abuse of notation (constituting a sort of pattern matching): :$\backslash beta\backslash left(\backslash pi\backslash left(x\_0,m\backslash right),i\backslash right)\; =\; \backslash mathrm\backslash left(x\_0,\; \backslash left(i+1\backslash right)\backslash cdot\; m+1\backslash right)$ Let us achieve even more readability by more modularity and reuse (as these notions are used in computer scienceHughes 1989 (se

online

)): by defining $\backslash forall\; imath>\; the\; sequence$ m\_i\; =\; (i+1)\backslash cdot\; m+1$,\; we\; can\; write\; :$ \backslash beta\backslash left(\backslash pi\backslash left(x\_0,m\backslash right),i\backslash right)\; =\; \backslash mathrm\backslash left(x\_0,\; m\_i\backslash right)$.\; We\; shall\; use\; this$ m\_i$notation\; in\; the\; proof.$

= Hand-tuned assumptions

= For proving the correctness of the above definition of the $\backslash beta$ function, we shall use several lemmas. These have their own assumptions. Now we try to find out these assumptions, calibrating and tuning their strength carefully: they should not be said in an either superfluously sharp, or unsatisfactorily weak form. Let $a\_0,\backslash dots\; a\_$ be a sequence of natural numbers. Let ''m'' be chosen to satisfy :$\backslash forall\; i\; \backslash in\; \backslash overline\; n\; \backslash setminus\; \backslash left\backslash \; \backslash left(i\; \backslash mid\; m\backslash right)$ :$\backslash forall\; i\; <\; n\; \backslash left(\; a\_i\; <\; m\_i\; \backslash right)$ The first assumption is meant as :$1\; \backslash mid\; m\; \backslash land\; \backslash dots\; \backslash land\; n-1\; \backslash mid\; m$ It is needed to meet an assumption of the Chinese remainder theorem (that of being pairwise coprime). In the literature, sometimes this requirement is replaced with a stronger one, e.g. constructively built with the factorial function, but the stronger premise is not required for this proof. The second assumption does not concern the Chinese remainder theorem in any way. It will have importance in proving that the specification for $\backslash beta$ is met eventually. It ensures that an $\backslash tilde\; x$ solution of the simultaneous congruence system :$x\; \backslash equiv\; a\_i\; \backslash pmod$ for each ''i'' where $0\backslash le\; i\; \backslash le\; n-1$ also satisfies :$a\_i\; =\; \backslash mathrm(\backslash tilde\; x,\; m\_i)$.Csirmaz 1994: 100 (se

online

Burris 1998: Supplementary Text

Arithmetic I

Lemma 4 A stronger assumption for ''m'' requiring $\backslash forall\; i\; <\; n\; \backslash ;\; (a\_i\; <\; m)$ automatically satisfies the second assumption (if we define the notation $m\_i$ as above).

** Proof that (coprimality) assumption for Chinese remainder theorem is met **

In the section Hand-tuned assumptions, we required that
:$\backslash forall\; i\; \backslash in\; \backslash overline\; n\; \backslash setminus\; \backslash left\backslash \; \backslash left(i\; \backslash mid\; m\backslash right)$. What we want to prove is that we can produce a sequence of pairwise coprime numbers in a way that will turn out to correspond to the Implementation of the β function.
In detail:
:$\backslash forall\; i,j\; n\; \backslash ;\; \backslash left(\; i\; \backslash neq\; j\; \backslash rightarrow\; \backslash mathrm\backslash left(m\_i,m\_j\backslash right)\; \backslash right)\; math>\; remembering\; that$ \backslash forall\; imath>\; we\; defined$ m\_i\; =\; (i+1)\backslash cdot\; m+1$.\; The\; proof\; is\; by\; contradiction;\; assume\; the\; negation\; of\; the\; original\; statement:\; :$ \backslash exists\; i,j\; n\; \backslash ;\; \backslash left(\; i\; \backslash neq\; j\; \backslash land\; \backslash lnot\; \backslash mathrm\backslash left(m\_i,m\_j\backslash right)\; \backslash right)\; math>$,j>$$

** First steps **

We know what “coprime” relation means (in a lucky way, its negation can be formulated in a concise form); thus, let us substitute in the appropriate way:
:$\backslash exists\; i,j\; n\; \backslash ;\; \backslash left(\; i\; \backslash neq\; j\; \backslash land\; \backslash exists\; p\; \backslash in\; \backslash mathrm\; \backslash mid\; m\_i\; m\_j\; \backslash right)\; \backslash right)\; math>\; Using\; a\; \u201cmore\u201dprenex\; normal\; form(but\; note\; allowing\; a\; constraint-like\; notation\; in\; quantifiers):\; :$ \backslash exists\; i,j\; n,p\; \backslash in\; \backslash mathrm\; \backslash ;\; \backslash left(\; i\; \backslash neq\; j\; \backslash land\; p\; \backslash mid\; m\_i\; m\_j\; \backslash right)\; math>\; Because\; of\; a\; theorem\; ondivisibility,$ p\; \backslash mid\; m\_i\; \backslash land\; p\; \backslash mid\; m\_j$allows\; us\; to\; also\; say\; :$ p\; \backslash mid\; m\_i\; -\; m\_j$.\; Substituting\; thedefinitions\; of$ m\_k$-sequence\; notation,\; we\; get$ m\_i\; -\; m\_j\; =\; (i-j)\; \backslash cdot\; m$,\; thus\; (asequalityaxioms\; postulate\; identity\; to\; be\; acongruence\; relationsee\; also\; related\; notions,\; e.g.\; \u201cequals\; for\; equals\u201d\; (referential\; transparency),\; and\; another\; related\; notion\; Leibniz\text{'}s\; law\; /identity\; of\; indiscernibles)\; we\; get\; :$ p\; \backslash mid\; (i-j)\; \backslash cdot\; m$.\; Since\; \text{'}\text{'}p\text{'}\text{'}\; is\; aprime\; element(note\; that\; theirreducible\; elementproperty\; is\; used),\; we\; get\; :$ p\; \backslash mid\; i-j\; \backslash lor\; p\; \backslash mid\; m$.$,j>$

** Resorting to the first hand-tuned assumption **

Now we must resort to our assumption
:$\backslash forall\; i\; \backslash in\; \backslash overline\; n\; \backslash setminus\; \backslash left\backslash \; \backslash left(i\; \backslash mid\; m\backslash right)$.
The assumption was chosen carefully to be as weak as possible, but strong enough to enable us to use it now.
The assumed negation of the original statement contains an appropriate existential statement using indices $i\backslash land\; j\backslash land\; i\backslash neq\; j\; math>;\; this\; entails$ i-j\; \backslash in\; \backslash overline\; n\; \backslash setminus\; \backslash left\backslash $,\; thus\; the\; mentioned\; assumption\; can\; be\; applied,\; so$ i-j\; \backslash mid\; m$holds.$

** Using an (object) theorem of the propositional calculus as a lemma **

We can prove by several means known in propositional calculus that
:$\backslash left(A\; \backslash land\; \backslash left(\; A\; \backslash rightarrow\; B\backslash right)\backslash right)\; \backslash rightarrow\; B$
holds.
Since $i-j\; \backslash mid\; m$, by the transitivity property of the divisibility relation, $p\; \backslash mid\; i-j\; \backslash rightarrow\; p\; \backslash mid\; m$. Thus (as equality axioms postulate identity to be a congruence relation )
:$p\; \backslash mid\; m$
can be proven.

** Reaching the contradiction **

The negation of original statement contained
:$p\; \backslash mid\; m\_i$
and we have just proved
:$p\; \backslash mid\; m$.
Thus,
:$p\; \backslash mid\; m\_i\; -\; \backslash left(i+1\backslash right)\backslash cdot\; m$
should also hold.
But after substituting the definition of $m\_i$,
:$m\_i\; -\; \backslash left(i+1\backslash right)\backslash cdot\; m\; =\; 1$
Thus, summarizing the above three statements, by transitivity of the equality,
:$p\; \backslash mid\; 1$
should also hold.
However, in the negation of the original statement ''p'' is existentially quantified and restricted to primes $\backslash exists\; p\; \backslash in\; \backslash mathrm$. This establishes the contradiction we wanted to reach.

** End of reductio ad absurdum **

By reaching contradiction with its negation, we have just proven the original statement:
:$\backslash forall\; i,j\backslash ;\; \backslash left(\; i\; \backslash neq\; j\; \backslash rightarrow\; \backslash mathrm\backslash left(m\_i,m\_j\backslash right)\backslash right)\; math>$

** The system of simultaneous congruences **

We build a system of simultaneous congruences
:$x\; \backslash equiv\; a\_0\; \backslash pmod$
::$\backslash vdots$
:$x\; \backslash equiv\; a\_\; \backslash pmod$
We can write it in a more concise way:
:$\backslash forall\; i\; <\; n\; \backslash ;\; \backslash left(x\; \backslash equiv\; a\_i\; \backslash pmod\backslash right)$
Many statements will be said below, all beginning with "$\backslash forall\; i\; <\; n\; \backslash ;\; \backslash left(\backslash dots\backslash right)$". To achieve a more ergonomic treatment, from now on all statements should be read as being in the scope of an $\backslash forall\; i\; <\; n\; \backslash ;\; \backslash left(\backslash dots\backslash right)$ quantification. Thus, $\backslash forall\; i\; <\; n\; ($ begins here.
Let us chose a solution $x\_0$ for the system of simultaneous congruences. At least one solution must exist, because $m\_0,\backslash dots\; m\_$ are pairwise comprime as proven in the previous sections, so we can refer to the solution ensured by the Chinese remainder theorem. Thus, from now on we can regard $x\_0$ as satisfying
:$x\_0\; \backslash equiv\; a\_i\; \backslash pmod$,
which means (by definition of modular arithmetic) that
:$\backslash mathrm\backslash left(x\_0,m\_i\backslash right)\; =\; \backslash mathrm\backslash left(a\_i,m\_i\backslash right)$

** Resorting to the second hand-tuned assumption **

Recall the second assumption, “$\backslash forall\; i\; <\; n\; \backslash ;\; \backslash left(a\_i\; <\; m\_i\; \backslash right)$”, and remember that we are now in the scope of an implicit quantification for ''i'', so we don't repeat its quantification for each statement.
The second assumption $a\_i\; <\; m\_i$ implies that
:$\backslash mathrm\backslash left(a\_i,m\_i\backslash right)\; =\; a\_i$.
Now by transitivity of equality we get
:$\backslash mathrm\backslash left(x\_0,m\_i\backslash right)\; =\; a\_i$.

** QED **

Our original goal was to prove that the definition
:$\backslash beta\backslash left(\backslash pi\backslash left(x\_0,m\backslash right),i\backslash right)\; =\; \backslash mathrm\backslash left(x\_0,m\_i\backslash right)$
is good for achieving what we declared in the specification of $\backslash beta$: we want $\backslash beta\backslash left(\backslash pi\backslash left(x\_0,m\backslash right),i\backslash right)\; =\; a\_i$ to hold.
This can be seen now by transitivity of equality, looking at the above three equations.
(The large scope of ''i'' ends here.)

** Existence and uniqueness **

We have just proven the correctness of the definition of $\backslash beta$: its specification requiring
:$\backslash forall\; a\_0,\backslash dots,\; a\_\backslash ;\backslash exists\; s\backslash ;\backslash forall\; i\; <\; n\; \backslash ;\; \backslash beta(s,i)\; =\; a\_i$
is met. Although proving this was most important for establishing an encoding scheme for sequences, we have to fill in some gaps yet. These are related notions similar to existence and uniqueness (although on uniqueness, “at most one” should be meant here, and the conjunction of both is delayed as a final result).

** Uniqueness of encoding, achieved by minimalization **

Our ultimate question is: what number should stand for the encoding of sequence $\backslash left\backslash langle\; a\_0,\backslash dots,a\_\backslash right\backslash rangle$? The specification declares only an existential quantification, not yet a functional connection. We want a constructive and algorithmic connection: a (total) recursive function that performs the encoding.

** Totality, because minimalization is restricted to special functions **

This gap can be filled in in a straightforward way: we shall use minimalization, and the totality of the resulting function is ensured by everything we have proven till now (i.e. the correctness of the definition of $\backslash beta$ by meeting its specification). In fact, the specification
:$\backslash forall\; a\_0,\backslash dots,\; a\_\backslash ;\backslash exists\; s\backslash ;\backslash forall\; i\; <\; n\; \backslash ;\; \backslash beta(s,i)\; =\; a\_i$
plays a role here of a more general notion (“special function”Monk 1976: 45 (= Def 3.1.)). The importance of this notion is that it enables us to split off the (sub)class of (total) recursive functions from the (super)class of partial recursive functions. In brief, the specification says that a function ''f''
E.g. defined by
:$f\; :\; \backslash mathbb\; N^\; \backslash to\; \backslash mathbb\; N$
:$f\backslash left(a\_0,\backslash dots,\; a\_,\; s\backslash right)\; =\; \backslash begin0\; \&\; \backslash mathrm\backslash ;\backslash forall\; i\; <\; n\; \backslash ;\; \backslash left(\backslash beta(s,i)\; =\; a\_i\backslash right)\; \backslash \backslash \; 1\; \&\; \backslash mathrm\backslash ;\backslash exists\; i\; <\; n\; \backslash ;\; \backslash left(\; \backslash beta(s,i)\; \backslash neq\; a\_i\; \backslash right)\backslash end$
satisfying the specification
:$f\backslash left(a\_0,\backslash dots,\; a\_,\; s\backslash right)\; =\; 0\; \backslash leftrightarrow\; \backslash forall\; i\; <\; n\; \backslash ;\; \backslash left(\backslash beta(s,i)\; =\; a\_i\backslash right)$
is a special function; that is, for each fixed combination of all-but-last arguments, the function ''f'' has root in its last argument:
:$\backslash forall\; a\_0,\backslash dots,a\_\backslash ;\backslash exists\; s\backslash ;\; \backslash left(f\backslash left(a\_0,\backslash dots,a\_,s\backslash right)=0\backslash right)$

** The Gödel numbering function g can be chosen to be total recursive **

Thus, let us choose the minimal possible number that fits well in the specification of the $\backslash beta$ function:
:$g\; :\; \backslash mathbb\; N^n\; \backslash to\; \backslash mathbb\; N$
:$\backslash left\backslash langle\; a\_0,\backslash dots,a\_\backslash right\backslash rangle\; \backslash longmapsto\; \backslash mu\; a\; .\; \backslash left\backslash ;\_\backslash left(\backslash beta\backslash left(a,i\backslash right)\_=\_a\_i\backslash right)\backslash right.html"\; style="text-decoration:\; none;"\; class="mw-redirect"\; title="\backslash forall\; i\; n\; \backslash ;\; \backslash left(\backslash beta\backslash left(a,i\backslash right)\; =\; a\_i\backslash right)\backslash right">\backslash forall\; i\; n\; \backslash ;\; \backslash left(\backslash beta\backslash left(a,i\backslash right)\; =\; a\_i\backslash right)\backslash right$

** Access of length **

If we use the above scheme for encoding sequences only in contexts where the length of the sequences is fixed, then no problem arises. In other words, we can use them in an analogous way as arrays are used in programming.
But sometimes we need dynamically stretching sequences, or we need to deal with sequences whose length cannot be typed in a static way. In other words, we may encode sequences in an analogous way to lists in programming.
To illustrate both cases: if we form the Gödel numbering of a Turing machine, then the each row in the matrix of the “program” can be represented with tuples, sequences of fixed length (thus, without storing the length), because the number of the columns is fixed.Monk 1976: 53 (= Def 3.20, Lem 3.21) But if we want to reason about configuration-like things (of Turing-machines), and specifically if we want to encode the significant part of the tape of a running Turing machine, then we have to represent sequences together with their length. We can mimic dynamically stretching sequences by representing sequence concatenation (or at least, augmenting a sequence with one more element) with a totally recursive function.Csirmaz 1994: 101 (=Thm 10.7, Conseq 10.8), se

online

/ref> Length can be stored simply as a surplus member: :$g\; :\; \backslash mathbb\; N^*\; \backslash to\; \backslash mathbb\; N$ :$\backslash left\backslash langle\; a\_0,\backslash dots,a\_,\; a\_n\backslash right\backslash rangle\; \backslash longmapsto\; \backslash mu\; a\; .\; \backslash left\backslash ;\_\backslash left(\backslash beta\backslash left(a,i+1\backslash right)\_=\_a\_i\backslash right)\backslash right.html"\; style="text-decoration:\; none;"\; class="mw-redirect"\; title="a\_0\; =\; n\; \backslash land\; \backslash forall\; i\; n\; \backslash ;\; \backslash left(\backslash beta\backslash left(a,i+1\backslash right)\; =\; a\_i\backslash right)\backslash right">a\_0\; =\; n\; \backslash land\; \backslash forall\; i\; n\; \backslash ;\; \backslash left(\backslash beta\backslash left(a,i+1\backslash right)\; =\; a\_i\backslash right)\backslash right$

** Notes **

** References **

*
* Each chapter is downloadable verbatim o

author's page

* * * * Translation of Smullyan 1992.

** External links **

*
{{DEFAULTSORT:Godel Numbering For Sequences
Category:Computability theory
Category:Articles containing proofs

online

= Implementation of the β function

= Using the Chinese remainder theorem, we can prove that implementing $\backslash beta$ as :$\backslash beta(s,i)\; =\; \backslash mathrm\backslash left(K\backslash left(s\backslash right),\backslash left(i+1\backslash right)\backslash cdot\; L\backslash left(s\backslash right)+1\backslash right)$ will work, according to the specification we expect $\backslash beta$ to satisfy. We can use a more concise form by an abuse of notation (constituting a sort of pattern matching): :$\backslash beta\backslash left(\backslash pi\backslash left(x\_0,m\backslash right),i\backslash right)\; =\; \backslash mathrm\backslash left(x\_0,\; \backslash left(i+1\backslash right)\backslash cdot\; m+1\backslash right)$ Let us achieve even more readability by more modularity and reuse (as these notions are used in computer scienceHughes 1989 (se

online

)): by defining $\backslash forall\; imath>\; the\; sequence$ m\_i\; =\; (i+1)\backslash cdot\; m+1$,\; we\; can\; write\; :$ \backslash beta\backslash left(\backslash pi\backslash left(x\_0,m\backslash right),i\backslash right)\; =\; \backslash mathrm\backslash left(x\_0,\; m\_i\backslash right)$.\; We\; shall\; use\; this$ m\_i$notation\; in\; the\; proof.$

= Hand-tuned assumptions

= For proving the correctness of the above definition of the $\backslash beta$ function, we shall use several lemmas. These have their own assumptions. Now we try to find out these assumptions, calibrating and tuning their strength carefully: they should not be said in an either superfluously sharp, or unsatisfactorily weak form. Let $a\_0,\backslash dots\; a\_$ be a sequence of natural numbers. Let ''m'' be chosen to satisfy :$\backslash forall\; i\; \backslash in\; \backslash overline\; n\; \backslash setminus\; \backslash left\backslash \; \backslash left(i\; \backslash mid\; m\backslash right)$ :$\backslash forall\; i\; <\; n\; \backslash left(\; a\_i\; <\; m\_i\; \backslash right)$ The first assumption is meant as :$1\; \backslash mid\; m\; \backslash land\; \backslash dots\; \backslash land\; n-1\; \backslash mid\; m$ It is needed to meet an assumption of the Chinese remainder theorem (that of being pairwise coprime). In the literature, sometimes this requirement is replaced with a stronger one, e.g. constructively built with the factorial function, but the stronger premise is not required for this proof. The second assumption does not concern the Chinese remainder theorem in any way. It will have importance in proving that the specification for $\backslash beta$ is met eventually. It ensures that an $\backslash tilde\; x$ solution of the simultaneous congruence system :$x\; \backslash equiv\; a\_i\; \backslash pmod$ for each ''i'' where $0\backslash le\; i\; \backslash le\; n-1$ also satisfies :$a\_i\; =\; \backslash mathrm(\backslash tilde\; x,\; m\_i)$.Csirmaz 1994: 100 (se

online

Burris 1998: Supplementary Text

Arithmetic I

Lemma 4 A stronger assumption for ''m'' requiring $\backslash forall\; i\; <\; n\; \backslash ;\; (a\_i\; <\; m)$ automatically satisfies the second assumption (if we define the notation $m\_i$ as above).

online

/ref> Length can be stored simply as a surplus member: :$g\; :\; \backslash mathbb\; N^*\; \backslash to\; \backslash mathbb\; N$ :$\backslash left\backslash langle\; a\_0,\backslash dots,a\_,\; a\_n\backslash right\backslash rangle\; \backslash longmapsto\; \backslash mu\; a\; .\; \backslash left\backslash ;\_\backslash left(\backslash beta\backslash left(a,i+1\backslash right)\_=\_a\_i\backslash right)\backslash right.html"\; style="text-decoration:\; none;"\; class="mw-redirect"\; title="a\_0\; =\; n\; \backslash land\; \backslash forall\; i\; n\; \backslash ;\; \backslash left(\backslash beta\backslash left(a,i+1\backslash right)\; =\; a\_i\backslash right)\backslash right">a\_0\; =\; n\; \backslash land\; \backslash forall\; i\; n\; \backslash ;\; \backslash left(\backslash beta\backslash left(a,i+1\backslash right)\; =\; a\_i\backslash right)\backslash right$

author's page

* * * * Translation of Smullyan 1992.