Proving properties of C(B) (proving properties of inductive sets)
When we want to prove that every element of an inductive set has a certain property we use a proof by induction, which is based on the Induction principle.
Induction Principle:
Let α = <U, fiI be a structure, and let BU.
If S is a B-inductive subset of C(B) that is, BS and is S closed in α, then S = C(B).
Proof of the induction principle:
To prove the induction principle, we need to show that SC(B) and C(B)S, therefore (C(B) = S).
1) Show that SC(B):
It is given in the induction principle that S is a B-inductive subset of C(B), therefore, SC(B).
2) Show that C(B)S:
According to the definition of C(B), C(B) is the intersection of all S that are B-inductive in α (C(B) = {S: S is B-inductive in α}), therefore, C(B)S, based on the definition of intersection. In addition, we already proved that C(B) is the smallest B-inductive set in α, therefore, it must be a subset of S.
Let P be a property.
To prove that P(x) holds for every element x in C(B) (or that every element x in C(B) has property P), we use the Induction Principle and perform a proof by induction.
Theorem: For every xC(B), P(x) holds.
This is the kind of statements we want to prove using induction
Let Sp = {x: xC(B) and P(x) holds}.
Sp is the set consisting of all the elements x that are elements of C(B) and have a property P.
To show that Sp = C(B), we need to show that SpC(B) and C(B) Sp.
Sp consists of elements that are in C(B), therefore Sp is a subset of C(B) ( SpC(B)).
We already proved that C(B) is the smallest B-inductive set, therefore it must be a subset of any other B-inductive set. If we can prove that Sp is B-inductive, then we also proved that Sp is a subset of C(B) (C(B) Sp)
So, following the Induction Principle, if we can prove that Sp is B-inductive and knowing that SpC(B), then we can conclude that Sp and C(B) are the same set (Sp = C(B)).
Proof:
Let us prove that Sp is B-inductive. To do so, we perform the following steps, which we call the schema of a proof by induction:
Schema of Proof by induction:
a) Base Case: Show that B is a subset of Sp (BSp), in other words, show that for every element x in B, P(x) holds. Remember here, that the elements in B are defined by the base rule of the inductive definition.
b) Inductive Step: Show that Sp is closed in α, i.e., for all iI, if x1, …, xnSp, then f(x1, …, xn)Sp. In other words, show that if x1, …, xn have property P, then f(x1, …, xn) has property P as well.
To do so, we assume that x1, …, xnSp (induction hypothesis), in other words that x1, …, xn have property P, and then we show that f(x1, …, xn)Sp, in other words that f(x1, …, xn) has property P as well.
Let iI be arbitrary and let x1, …, xnC(B).
Induction Hypothesis: x1, …, xnSp (x1, …, xn have property P).
Show that f(x1, …, xn)Sp (f(x1, …, xn) has property P).
Conclude that for all iI, if x1, …, xn have property P, then f(x1, …, xn) has property P.
Example 1
Prove that every formula F has the following property P: F has an even number of parentheses.
=> the proof is in your manuscript. Note that there is an error in that proof. In the proof in your manuscript, on the Induction Step, you have:
The number of parentheses in F = the number of parentheses in G + the number of parentheses in H.
=> The correct one is:
The number of parentheses in F = the number of parentheses in G + the number of parentheses in H + 2.
Example 2
We define my-formulas as follows:
1) Base Clause: Every propositional sentence Ai (i=1,2,…) is a my-formula.
2) Inductive Clause:
(a) For every my-formula G, (G} is also a my-formula.
(b) For every my-formulas G and H, {{GH) is also a my-formula.
3) Final Rule: No expression in U* is a my-formula, unless it has to be one by 1., or 2. above.
Prove that for every my-formula F the following property P(F) holds: the number of “(” in F plus the number of “{” in F, equals the number of “}” in F plus the number of “)” in F plus the number of “” in F (i.e., n((F) + n{(F) = n)(F) + n}(F) + n(F))
Proof by Induction:
Let F be an arbitrary my-formula.
(a) Base case:
Assume F is a propositional letter, i.e. F = Ai for some iÎ{1,2,.....}. Then F has 0 (, and 0 {, 0 }, 0 ), and 0, so the number of ( plus the number if { is equal to the number of ) plus the number of }, plus the number of , i.e., n((F) + n{(F) = n)(F) + n}(F) + n(F).
Induction Step:
(b) Suppose F = (G} and G is a my-formula.
Induction hypotheses: For my-formula G the property P(G) holds, i.e., the number of ( in G plus the number of { in G, is equal to the number of } in G plus the number of ) in G plus the number of in G, i.e., n((G) + n{(G) = n)(G) + n}(G) + n(G).
n((F) = n((G) + 1
n{(F) = n{(G)
n)(F) = n)(G)
n}(F) = n}(G) + 1
n(F) = n(G).
Then, n((F) + n{(F) = n((G) + n{(G) + 1 =(by induction hypothesis) n)(G) + n}(G) n(G) + 1= n)(F) + n}(F) + n(F)
Therefore P(F) holds (i.e., n((F) + n{(F) = n)(F) + n}(F) + n(F) ).
(c) Suppose F = {{GH), where G and H are my-formulas.
Induction hypotheses: For my-formula G the property P(G) holds, i.e., the number of ( in G plus the number of { in G, is equal to the number of } in G plus the number of ) in G plus the number of in G, i.e., n((G) + n{(G) = n)(G) + n}(G) + n(G).
For my-formula H the property P(H) holds, i.e., the number of ( in H plus the number of { in H, is equal to the number of } in H plus the number of ) in H plus the number of in H, i.e., n((H) + n{(H) = n)(H) + n}(H) + n(H).
n((F) = n((G) + n((H)
n{(F) = n{(G) + n{(H) +2
n)(F) = n)(G) + n)(H) + 1
n}(F) = n}(G) + n}(H)
n(F) = n(G) + n(H) + 1.
Then, n((F) + n{(F) = n((G) + n((H) + n{(G) + n{(G) + 2 =(by induction hypothesis) n)(G) + n)(H) + n}(G) + n}(H) + n(G) + n(H) + 2= n)(F) + n}(F) + n(F)
Therefore P(F) holds (i.e., n((F) + n{(F) = n)(F) + n}(F) + n(F) ).
Since F was an arbitrary my-formula and we covered all the possibilities for the structure of F, we proved the proposition.