| Version current |
Version 3 |
| A \emph{G\"odel numbering} is any way off assigning numbers to the formulas of a language. This is often useful in allowing sentences of a language to be self-referential. The number associated with a formula $\phi$ is called its \emph{G\"odel number} and is denoted $\ulcorner\phi\urcorner$. |
A \emph{G\"odel numbering} is any way off assigning numbers to the formulas of a language. This is often useful in allowing sentences of a language to be self-referential. The number associated with a formula $\phi$ is called its \emph{G\"odel number} and is denoted $\ulcorner\phi\urcorner$. |
|
More formally, if $\mathcal{L}$ is a language and $\mathcal{G}$ is a surjective partial function from the terms of $L$ to the formulas over $L$ then $\mathcal{G}$ is a G\"odel numbering. $\ulcorner\phi\urcorner$ may be |
|
More formally, if $\mathcal{L}$ is a language and $\mathcal{G}$ is a surjective partial function from the terms of $\mathcal{L}$ to the formulas over $\mathcal{L}$ then $\mathcal{G}$ is a G\"odel numbering. $\ulcorner\phi\urcorner$ may be any term $t$ such that $\mathcal{G}(t)=\phi$. Note that $\mathcal{G}$ is not defined within $\mathcal{L}$ (there is no formula or object of $\mathcal{L}$ representing $\mathcal{G}$), however properties of it (such as being in the domain of $\mathcal{G}$, being a subformula, and so on) are.
|
h{G\"odel number} and is denoted $\ulcorner\phi\urcorner$.
|
|
More formally, if $\mathcal{L}$ is a language and $\mathcal{G}$ is a surjective partial function from the terms of $L$ to the formulas over $L$ then $\mathcal{G}$ is a G\"odel numbering. $\ulcorner\phi\urcorner$ may be any term $t$ such that $\mathcal{G}(t)=\phi$. Note that $\mathcal{G}$ is not defined within $L$ (there is no formula or object of $L$ representing $\mathcal{G}$), however properties of it (such as being in the domain of $\mathcal{G}$, being a subformula, and so on) are. |
| Athough anything meeting the properties above is a G\"odel numbering, depending on the specific language and usage, any of the following properties may also be desired (and can often be found if more effort is put into the numbering): |
Athough anything meeting the properties above is a G\"odel numbering, depending on the specific language and usage, any of the following properties may also be desired (and can often be found if more effort is put into the numbering): |
|
|
| \begin{itemize} |
\begin{itemize} |
| \item If $\phi$ is a subformula of $\psi$ then $\ulcorner\phi\urcorner<\ulcorner\psi\urcorner$ |
\item If $\phi$ is a subformula of $\psi$ then $\ulcorner\phi\urcorner<\ulcorner\psi\urcorner$ |
|
|
| \item For every number $n$, there is some $\phi$ such that $\ulcorner\phi\urcorner=n$ |
\item For every number $n$, there is some $\phi$ such that $\ulcorner\phi\urcorner=n$ |
|
|
| \item $\mathcal{G}$ is injective |
\item $\mathcal{G}$ is injective |
| \end{itemize} |
\end{itemize} |
|
Here is an example G\"odel numbering of arithmetic. $\langle x_1,\ldots,x_n\rangle$ is a single number which represents the sequence $\vec{x}$ in a unique way so that each $x_i$ can be recovered; a typical definition is |
|
$$\langle x_1,\ldots,x_n\rangle=\sum_{i<n} p_i^{x_i}$$ |
|
where $p_i$ is the $i$-th prime. |
|
The symbols of the language of arithmetic are $=$, $\forall$, $\neg$, $\wedge$, $0$, $S$, $<$, $+$, $\cdot$, and the variables $v_i$ for any integer $i$. |
|
We can define a function $e$ by recursion as follows: |
|
\begin{itemize} |
|
\item $e(v_i)=\langle 0,v_i\rangle$ |
|
\item $e(\langle \phi=\psi\rangle)=\langle 1,e(\phi),e(\psi)\rangle$ |
|
\item $e(\forall v_i \phi)=\langle 2,e(v_i),e(\phi)\rangle$ |
|
\item $e(\neg\phi)=\langle 3,e(\phi)\rangle$ |
|
\item $e(\phi\wedge\psi)=\langle 4,e(\phi),e(\psi)\rangle$ |
|
\item $e(0)=\langle 5\rangle$ |
|
\item $e(S\phi)=\langle 6,e(\phi)\rangle$ |
|
\item $e(\phi<\psi)=\langle 7,e(\phi),e(\psi)\rangle$ |
|
\item $e(\phi+\psi)=\langle 8,e(\phi),e(\psi)\rangle$ |
|
\item $e(\phi\cdot\psi)=\langle 9,e(\phi),e(\psi)\rangle$ |
|
And $\mathcal{G}$ is just the inverse of $e$. |
