Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm hoping that there exists a prepared errata list for Elliott Mendelson's Introduction to Mathematical Logic (5th ed). If so, how does one locate it? (It does not seem to be available from the publisher (CRC Press). If no such errata resource exists, here's a question about what I think is an omission in a particular formula:

In the working up to a proof of Gödel's incompleteness theorem, Section 3.4 (p. 194) produces a long list of correlations between wfs and their Gödel numbers. Well into this process there is defined – by means of "course of values recursion" – this special relation (which I will try to parse below): $$ \textrm{Ff}(u,v,w) := \textrm{Trm}(u) \wedge \textrm{EVbl}(2^v) \wedge \textrm{Fml}(w) \wedge $$ $$ \{ \textrm{Atfml}(w) \wedge [?] $$ $$ (\exists y)_{y<w}(w=2^3\ast2^9\ast y \ast 2^5 \wedge \textrm{Ff}(u,v,y)) \vee $$ $$ (\exists y)_{y<w}(\exists z)_{z<w}(w=2^3\ast y \ast 2^{11} \ast z \ast 2^5 \wedge \textrm{Ff}(u,v,y)\wedge \textrm{Ff}(u,v,z)) \vee $$ $$ (\exists y)_{y<w}(\exists z)_{z<w}[w=2^3\ast 2^3 \ast 2^{13} \ast 2^z \ast 2^5 \ast y \ast 2^5 \wedge \textrm{EVbl}(2^z) \wedge ( z\ne v \Rightarrow \textrm{Ff}(u,v,y)) \wedge (\textrm{Fr}(u,z) \Rightarrow \neg \textrm{Fr}(y,v))]\;\} $$

The definition is intended to provide a relation which holds precisely when $u$ is the Gödel number of a term that is free for the variable with Gödel number $v$ in the wf with Gödel number $w$. Thus, in the top line above, $\textrm{Trm}(u)$ ensures that the first input is indeed the Gödel number of some term, $\textrm{EVbl}(2^v)$ ensures that the second input is the Gödel number of a variable symbol, and $\textrm{Fml}(w)$ ensures that $w$ is the Gödel number of a wf. The remaining lines (within the braces) are meant to encode the condition that the term referenced by $u$ (which I will label $U$) is free for the variable referenced by $v$ (which I label $V$) within the wf referenced by $w$ (labeled $W$), but here is where there seems to be a problem with the printed text, noted above by my insertion of the question mark.

It appears that setting up the condition is broken into four cases: the second line above captures the case that $W$ is atomic; the third line deals with the case in which $W$ has the form $\neg(Y)$ for some lower-ordered wf $Y$, with Gödel number $y$; the fourth line the case in which $W$ has the form $(Y \Rightarrow Z)$ (where $Z$ has Gödel number $z$); and the bottom two lines the final case in which $W$ has the form $((\exists Z)Y)$, where here, $Z$ is a variable symbol differing from $V$.

All but the second line in the definition makes sense. Since the presence of the conjunction symbol is contradictory, there appears to be an omission at the position of the question mark where some other wf should appear; this formula would express the statement that $U$ is free for $V$ in the atomic formula $W$. For instance, the missing expression might be something like $$ (\exists y)_{y<w}(\exists \alpha)_{\alpha<w}(\exists \beta)_{\beta<w}[\textrm{Gd}(\alpha)\wedge \textrm{Trm}(y)\wedge \textrm{Gd}(\beta)\wedge w=\alpha\ast y \ast \beta \wedge \textrm{Fr}(y,v)] $$ followed by a disjunction that ties this condition to the remaining cases that follow.

Does this sound right?

share|improve this question
By the way, +1 for quoting author and title and edition of the book you're asking about. –  Henning Makholm Aug 10 '12 at 20:27
add comment

1 Answer

I think what you quote as "$\land [?]$" should simply have been a $\lor$.

Then the second line simply says that every term is free for every variable in an atomic formula (which is intuitively true because an atomic formula contains no variable binders).

By the way, the same misprint (except for the "$[?]$", which I suspect is something you inserted?) appears in the fourth edition, p. 195.

It's not as if very many readers are going to be checking the details at this point. I believe most readers who has gotten through the preceding just think "yeah, yeah, I've convinced myself that things with intuitive interpretations of this general shape are primitive recursive already" and skip over the actual formulas.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.