Induction: from the top down A subset of s of u is closed under f and g iff whenever elements and y belong to s, then so do f(,g) and g(a S is inductive iff b c s and s is closed under f and Let c be the intersection of all the inductive subsets of u. then C is inductive Logic in Computer Science-p.5/16
Induction: from the top down A subset of S of U is closed under f and g iff whenever elements x and y belong to S, then so do f(x, y) and g(x). S is inductive iff B ⊆ S and S is closed under f and g. Let C∗ be the intersection of all the inductive subsets of U. Then C∗ is inductive. Logic in Computer Science – p.5/16
Induction: from the bottom up Let Cx be the set of things which can be reached from b by applying f and g a finite number of times. Define a constructive sequence to be a finite sequence< o, .. In> of elements of U such that for each i< m we have at least one of c;∈B f(;, Ik)for some i<i, k< i i=g(ai) for some j < i Then Ck is the set of all points such that some construction sequence ends with Logic in Computer Science -p6/16
Induction: from the bottom up Let C∗ be the set of things which can be reached from B by applying f and g a finite number of times. Define a constructive sequence to be a finite sequence < x0, · · · , xn > of elements of U such that for each i ≤ n we have at least one of xi ∈ B xi = f(xj , xk) for some j < i, k < i xi = g(xj ) for some j < i Then C∗ is the set of all points x such that some construction sequence ends with x. Logic in Computer Science – p.6/16