5 Appendix: Inductive definition In our class, many definitions are defined recursively or inductively. We just introduce Definition 6. A set S is closed under a single operation f (s1, .. Sn)if and only if every S1 S,f(81,…,sn)∈S Definition 7. The closure of a set S under (all) the operations in a set T is the smallest C such that 1. SCC and 2.计f∈Tisn- ary and sI,…,sn∈C,then∫(81,…,sn)∈C. With these concepts, we have an Theorem on the property of inductive definition Theorem 8. Suppose that s is closed under the operations of T, there is a smallest closure C such that SCc Proof. Given a set D, sCD and D is closed under the operations of T. Consider the set C=nDISCDAD is closed under the operations of T) It is obvious that S CC. And C is the smallest set according to definition of C As a direct application of Theorem 8, we have the following Theorem about well-defined Definition Theorem 9. If s is a set of well defined propositions and is closed under all five connectives, then s is the set of all well defined propositions Exercises 1. Show that there are no well-defined propositions of length 2, 3, or 6, but that any other positive length is possi 2. Given an example such that(onB)=(rnd)but afr, where a and B are well-defined and r and 8 are two expressions 3. Draw formation tree of the following propositions (a)(AVB)→(-C)∧D) (b)((=A)VB)∧(AV(=B)) 4. Let a be a well-defined proposition; let c be the number of places at which binary connective symbols(A, V,7,,)occur in a; let s be the number of places at which proposition letters occur in a Show by using the induction principle that s=c+1 5. Determine the Polish notation of proposition or vice versa5 Appendix: Inductive definition In our class, many definitions are defined recursively or inductively. We just introduce Definition 6. A set S is closed under a single operation f(s1, . . . , sn) if and only if every s1, . . . , sn ∈ S, f(s1, . . . , sn) ∈ S Definition 7. The closure of a set S under (all) the operations in a set T is the smallest C such that 1. S ⊆ C and 2. if f ∈ T is n-ary and s1, . . . , sn ∈ C, then f(s1, . . . , sn) ∈ C. With these concepts, we have an Theorem on the property of inductive definition. Theorem 8. Suppose that S is closed under the operations of T, there is a smallest closure C such that S ⊆ C. Proof. Given a set D, S ⊆ D and D is closed under the operations of T. Consider the set C = ∩{D|S ⊆ D ∧ D is closed under the operations of T}. It is obvious that S ⊆ C. And C is the smallest set according to definition of C. As a direct application of Theorem 8, we have the following Theorem about well-defined Definition: Theorem 9. If S is a set of well defined propositions and is closed under all five connectives, then S is the set of all well defined propositions Exercises 1. Show that there are no well-defined propositions of length 2, 3, or 6, but that any other positive length is possible. 2. Given an example such that (α ∧ β) = (γ ∧ δ) but α ̸= γ, where α and β are well-defined and γ and δ are two expressions. 3. Draw formation tree of the following propositions: (a) ((A ∨ B) → ((¬C) ∧ D)). (b) (((¬A) ∨ B) ∧ (A ∨ (¬B))). 4. Let α be a well-defined proposition; let c be the number of places at which binary connective symbols(∧, ∨, →, ↔ ) occur in α; let s be the number of places at which proposition letters occur in α. Show by using the induction principle that s = c + 1. 5. Determine the Polish notation of proposition or vice versa. 6