Abstract

Consider first order logic augmented by least fixed point operator in the following way: For any formula F in which a predicate P appears only positively, the following are added to FOL.
  - a new predicate symbol F* (intended to be the fixed point of F)
-  axiom stating that F* is a fixed point for F
-  axiom stating that F* is contained in every fixed point of F.
It is easy to see that F* might not be the least fixed point of F since it is least only with respect to fixed points definable in this system, and that this system does not have a sound and complete proof system.

The work presented here examines if this system can prove "natural" statements involving fixed points. As a motivating example of a natural statement, we considered the following:  Let A by a monotone operator on binary relations such that if the graph of a predicate P is a partial function, so is A(P), and provably so. Then, A* is a partial function. 

We showed that this is provable within the system, and defined a subclass of statements provable by the system. Future works include trying to determine the power of this system.