Induction on fields of binary relations.
W. Russell Belding · Notre Dame Journal of Formal Logic · 1972
In [1] the following principle of induction, introduced by Montague in [2],A. If φ(x) is a formula not containing the variable y and R is a well-founded relation, thenis proved in the field of G.B. set theory.It is shown below that the restriction that R be well-founded can be removed and the induction will still hold provided a restriction is placed on the formula φ(x).The relationship between the various induction principles of [1] and the induction principle proved in this paper (Theorem 1) is discussed.The notation and definitions used in this paper are explained and defined in [1].The relations considered in this paper are always binary relations.The following theorem gives a new sufficient condition for induction of binary relations.Theorem 1. (Induction Principle E).For every R and every φ(x), if R is a binary relation, φ{x) a formula not containing the variable y and φ{x) has the property that for every sequence of sets {a n } n<ω such that a n+1 Ra n for every n ^ 0, there is at least one integer m ^ 0 such that φ{a m ) holds, thenProof: An indirect proof is used.Assume the hypothesis and suppose the induction fails.That is,Suppose a 0 is such that a o e Fldft and ~φ(a Ό ).First suppose that a 0 has no predecessor or that φ holds for every predecessor of a Q .Then clearly (3) a 0 e Fldfl A (X) (xRa 0φ(x)) By ( 3) and (1) it follows that φ(a 0 ) holds, contrary to (2).Thus,