Is the "ancestor" relationship impossible to define in first-order logic?

Yes, this is a standard application of the compactness theorem.

Here's a rough idea. Consider a theory which says (and adopt a mild abuse of notation):

  • $aR^*b$,

  • There is no $c_1$ with $aRc_1Rb$,

  • There are no $c_1,c_2$ with $aRc_1Rc_2Rb$,

  • There are no $c_1,c_2,c_3$ with $aRc_1Rc_2Rc_3Rb$,

  • etc.

This is obviously finitely consistent (just consider a "chain of length $n$" for $n$ large enough), but equally obviously unsatisfiable. So by compactness some clause must not actually be first-order expressible - and the only option is the first one.

EDIT: Re: the prolog definition you describe (caution: I'm not familiar with prolog); at a quick glance "negation-as-failure" is a bit nuanced. I would start by observing that first-order logic does not allow recursive, or least-fixed-point, definitions; in particular, the transitive closure of a definable relation in a structure need not be definable in that same structure.

  • Wait, but isn't Godel coding all about recursive definitions? Well, sort of - but there's some subtleties there. Godel shows that in certain structures/theories we can handle certain recursive constructions in a "reasonably decent" way. That's a far cry from what's wanted here.

As I said above, at a glance "negation-as-failure" has some subtlety to it (specifically, nonmonotonicity). However I do think that the above is really the heart of the issue, and will wind up being relevant to however one tries to link prolog and first-order logic.


The main reason is that First-Order Logic uses Tarskian semantics and logic programming uses Herbrand semantics. This has various consequences when it comes to expressiveness and other properties like compactness and completeness. For more details, see for example The Herbrand Manifesto or Herbrand Semantics, where your example (transitive closure) is discussed.

Tags:

Logic

Predicate Logic

First Order Logic

Related

Is a group isomorphic to the internal product of its Sylow p-subgroups? Hartshorne's Exercise II.4.5(c). A third time. Are all multivariate functions on finite fields equivalent to a unique polynomial of smallest degree? Is there a simple, but tight lower bound for the error made when $\sum_{n=1}^{k}\frac{1}{n^2}$ is used to approximate $\frac{\pi^2}{6}$? Proving $\underset{n\to \infty }{\text{lim}}\frac{n!}{n^{n+\frac{1}{2}} \ e^{-n}}=\sqrt{2 \pi }$ Graphing $f(2-x)$ If $\int {yy''dx} = 3xy$ is it possible to find y'? Is there an object such that its unique existence follows from choice axiom, while its existence cannot be proven without choice axiom? Evaluating $\lim_{x\to0} \frac{\sin(\pi\sqrt{\cos x})} x$ Prove or disprove that the set S is countable Normal generation of the kernel of a surjection of free groups Why does separation of variable gives the general solution to a PDE

Recent Posts