Inductive definitions over finite structures (Q2639057): Difference between revisions

We give a simple proof of a theorem of Gurevich and Shelah that the inductive closure of an inflationary operator is equivalent, over the class of finite structures, to the inductive closure (i.e. minimal fixpoint) of a positive operator. A variant of the same proof establishes a theorem of Immerman that the class of inductive closures of positive first order operators is closed under complementation.