Re: deductive databases

On Wed, 18 May 2005 09:23:32 -0700, alex goldman <hello_at_spamm.er> said:
> ...
> [VC]wrote: "FOL can get rid of function symbols and be as expressive as
> with them"

That's right, so long as you mean (as I imagine you do) FOL with identity. If you have identity, then the expressive work of n-place function symbols in a language L1 can be done in a language L2 in which the function symbols of L1 are replaced by n+1-place predicates that are axiomatized to express functional relations. So, e.g., the work of a 1-place function symbol f in L1 can be done by its corresponding 2-place predicate F in L2 by axiomatizing F such that (x)(y)(z)[(F(x,y) & F(x,z)) -> y=z] and translating the sentences of L1 into L2 accordingly. Thus, the sentence (x)(y)(f(x) = f(y) -> x=y) could be translated into (x)(y)(z)(F(x,z) & F(y,z) -> x=y). (This sounds a bit seat of the pants, but there are general, systematic ways of defining such translation schemes.)

> Abiteboul & Vianu write: "[FOL without function symbols] has limited
> expressive power. For instance, it cannot compute the transitive
> closure of a graph"

I'm confused by the talk of computation here, but, in the model theoretic sense of "expressive power", the TC of a graph is not expressible in first-order logic with or without function symbols.

Chris Menzel Received on Wed May 18 2005 - 20:42:26 CEST