[FOM] inductive definitions in first order logic

[rgheck]

Gergely Buday wrote:
> Dear FOMers,
>
> in a recent paper of Denecker I have found the following:
>
> "It is well-known that, in general, inductive definitions cannot be
> expressed in first-order logic (FO)."
>
> Could you please point me to the literature where this claim is
> argumented? And, what does "in general" means? This suggests that in
> special cases it is possible to include inductive definitions into
> predicate logic.
>
>   
Since you don't say what the paper is, I can't know for sure what 
Denecker has in mind. (You could ask him.) But here's a guess. First, 
"in general" means: Not all inductive definitions can be expressed in 
FOL. Second, by "expressing an inductive definition", I take it that 
what he has in mind is something that is semantical. Of course, in PA, 
we can get the effect of certain sorts of inductive definitions, via 
coding by finite sequences and recursion on the course of values. But, 
this will not give you the right result semantically, because of the 
existence of non-standard models. Now, back to "in general": Of course, 
some inductive definitions can be expressed in first-order PA in that 
sense, because some are completely trivial, e.g.:
f(0) = 0
f(n + 1) = 0
No problem there!

Richard Heck


-- 
-----------------------
Richard G Heck Jr
Professor of Philosophy
Brown University