- #1
phoenixthoth
- 1,605
- 2
while reading an article regarding logic, i came across something that always used to confuse me as a student of logic back in 98 with harr1ngton. formulas are defined recursively:
1. if t1 and t2 are terms then t1=t2 is a formula.
2. too lazy to type this one
3. if f and g are formulas then so are f ^ g (the conjunction of f and g--ie f AND g), f v g, f->g, and f<->g.
4. and a couple more
5. f is a formula if and only if it can be constructed from a finite number of applications of rules 1-4.
then the kicker is that something can be proved about ALL formulas by what's called "induction on formulas" or "induction on the complexity of the formula." basically, you prove that something is true for formulas of the form t1=t2, the something i omitted in #2, and then prove that if the something you want to prove applies to f and g then it must apply to f ^ g, f v g, f->g, etc, and a couple more, and then that proves it for ALL formulas.
trivial example: you can use this to prove that all formulas have the same number of right parentheses as left parentheses. doing this was a question on the logic final. so i charged forward, using induction, and poof i was done yet i didn't understand why you could use induction.
well now i finally understand it.
there is another form of induction which is used on natural numbers. you can use it to prove facts about numbers. that was something i understood well and something i could prove. i never fully understood why they were both called induction.
what i did recently is call any set like the natural numbers and the set of formulas an "inductive playground." then i proved an induction principle for all inductive playgrounds, of which natural numbers and the set of formulas are special cases.
the basic idea is that to prove something about a set of things (eg numbers or formulas) that are defined recursively, all one must do is rather than literally prove it about all of the objects in the set, prove it by going along the recursive definition...
we can call S an inductive playground if there is a set (called the initial set) I_0 contained in S and n functions (n>0) with domain a cartesian product of S and range S such that if
I_(m+1) := I_m u f_1[I^{k_1}_m] u...u f_n[I^{k_n}_m], then S is the union of all the I_m's. (in this notation, I^{k_1}_m is the set I_m crossed with itself k_1 times and f_i is a k_i-ary function; ie, a function of k_i variables.
four examples include the following:
1. S is the set of natural numbers, n=1, and f_1, or just f, is the successor function: f(n)=n+1. then let I_0={0}. I_m={0,1,...,m} and S=N is the union of all the I_m's.
2. the set of all well formed formulas (or just formulas). here there are about seven functions, some of whom are of one variable and some of two. an example is the function that takes two formulas and maps that to the conjunction of the formulas.
3. let z be an element in [0,1] and let f(x)=4x(1-x). then the orbit of z is an inductive playground.
4. let P be an ordered list of all primes: P={p_1, p_2, ...} and f(x)=p_(x+1). then P is an inductive playground.
induction principle for inductive playgrounds
let S be an inductive playground equipped with the f_i's and initial set I_0. if T is a subset of S with the following two properties then T=S:
1. I_0 is a subset of T [this is the generalized induction step]
2. for all i (i=1,...,n) and for all s_1,...,s_(k_i) in S, if s_1,...,s_(k_i) are in T then so is f(s_1,...,s_(k_i)).
***
can anyone give more examples of inductive playgrounds where this kind of thing might be useful?
1. if t1 and t2 are terms then t1=t2 is a formula.
2. too lazy to type this one
3. if f and g are formulas then so are f ^ g (the conjunction of f and g--ie f AND g), f v g, f->g, and f<->g.
4. and a couple more
5. f is a formula if and only if it can be constructed from a finite number of applications of rules 1-4.
then the kicker is that something can be proved about ALL formulas by what's called "induction on formulas" or "induction on the complexity of the formula." basically, you prove that something is true for formulas of the form t1=t2, the something i omitted in #2, and then prove that if the something you want to prove applies to f and g then it must apply to f ^ g, f v g, f->g, etc, and a couple more, and then that proves it for ALL formulas.
trivial example: you can use this to prove that all formulas have the same number of right parentheses as left parentheses. doing this was a question on the logic final. so i charged forward, using induction, and poof i was done yet i didn't understand why you could use induction.
well now i finally understand it.
there is another form of induction which is used on natural numbers. you can use it to prove facts about numbers. that was something i understood well and something i could prove. i never fully understood why they were both called induction.
what i did recently is call any set like the natural numbers and the set of formulas an "inductive playground." then i proved an induction principle for all inductive playgrounds, of which natural numbers and the set of formulas are special cases.
the basic idea is that to prove something about a set of things (eg numbers or formulas) that are defined recursively, all one must do is rather than literally prove it about all of the objects in the set, prove it by going along the recursive definition...
we can call S an inductive playground if there is a set (called the initial set) I_0 contained in S and n functions (n>0) with domain a cartesian product of S and range S such that if
I_(m+1) := I_m u f_1[I^{k_1}_m] u...u f_n[I^{k_n}_m], then S is the union of all the I_m's. (in this notation, I^{k_1}_m is the set I_m crossed with itself k_1 times and f_i is a k_i-ary function; ie, a function of k_i variables.
four examples include the following:
1. S is the set of natural numbers, n=1, and f_1, or just f, is the successor function: f(n)=n+1. then let I_0={0}. I_m={0,1,...,m} and S=N is the union of all the I_m's.
2. the set of all well formed formulas (or just formulas). here there are about seven functions, some of whom are of one variable and some of two. an example is the function that takes two formulas and maps that to the conjunction of the formulas.
3. let z be an element in [0,1] and let f(x)=4x(1-x). then the orbit of z is an inductive playground.
4. let P be an ordered list of all primes: P={p_1, p_2, ...} and f(x)=p_(x+1). then P is an inductive playground.
induction principle for inductive playgrounds
let S be an inductive playground equipped with the f_i's and initial set I_0. if T is a subset of S with the following two properties then T=S:
1. I_0 is a subset of T [this is the generalized induction step]
2. for all i (i=1,...,n) and for all s_1,...,s_(k_i) in S, if s_1,...,s_(k_i) are in T then so is f(s_1,...,s_(k_i)).
***
can anyone give more examples of inductive playgrounds where this kind of thing might be useful?