How Do Weights and Degrees Influence the Structure of Logical Formulas?

[honestrosewater]

Definitions:
Briefly, for the formal, object language L, there are two mutually exclusive categories of primitive symbols: (i) an infinite set of propositional symbols and (ii) two distinct connectives, ~ (negation) and -> (implication).
If s_1, s_2, ..., s_l are (not necessarily distinct) primitive symbols and l is a natural number, s_1s_2...s_l is a string of length l. The empty string has length 0.
Formulas are strings constructed as follows:
(1) A string consisting of a single occurrence of a propositional symbol is a formula (called a prime formula).
(2) If B is a formula, ~B is a formula (called a negation formula).
(3) If B and C are formulas, ->BC is a formula (called an implication formula (B is the antecedent)).
(Formulas will be denoted by B, C, D, ...)
A propositional symbol occurring in B is called a prime component of B.
The degree of complexity of B, deg B, is the total number of occurences of connectives in B.
Assign to each primitve symbol s a weight w(s) by stipulating:
if s is a propositional symbol, w(s) = -1, w(~) = 0, w(->) = 1.
Assign to each string, where s_1, s_2, ..., s_l are primitive symbols, the weight:
w(s_1s_2...s_l) = w(s_1) + w(s_2) + ... + w(s_l).
Since every B is a string, every B has a weight, w(B).

Problems:
Show that, for any B,
(i) w(B) = -1;
(ii) if B is the string s_1s_2...s_l and k < l, w(s_1s_2...s_k) >= 0.
(iii) Show that if B is an implication formula, B = ->CD, then ->C is the shortest non-empty initial segment of B whose weight is 0.
______
I think I can handle (ii) and (iii) once I get (i). The book says to prove (i) by strong induction on deg B, but I don't know how to begin (I didn't really follow when he ran through induction at the beginning).
Strong induction, where n and m range over natural numbers {0, 1, 2, ...}:
$$\frac{\forall n [\forall m < n (Pm) \Rightarrow Pn]}{\forall n (Pn)}$$
I see that for all B, B has length >= 1, and, when B has length = 1, deg B = 0 and w(B) = -1, by definition.
I'm not yet comfortable with the notation, but I think I need to define a property P of formulas:
$$P\beta \Leftrightarrow_{df} w(\beta) = -1$$
and a property Q of natural numbers:
$$Qn \Leftrightarrow_{df} \forall \beta\ deg \beta = n (P\beta)$$
so that $$\forall \beta (P\beta) \Leftrightarrow \forall n (Qn)$$.
And I need to deduce Qn from $$\forall m < n (Qm)$$, knowing that PB holds for Q0.
Is that correct so far?

 

[AKG]

If length(B) = 1, w(B) = -1. If length(B) = 2, then B = ~C for some propositional symbol C (you can easily check that B must take this form). Then w(B) = w(~C) = w(~) + w(C) = 0 - 1 = -1. Suppose that $\forall B\, (length (B) \leq k) \Rightarrow (w(B) = -1)$. Then all statements C such that length(C) = k+1 are either of the form C = ~D, or C = ->EF, where clearly length(E) + length(F) = deg(D) = k, so length(E), length(F), length(D) < k.

If C = ~D, w(C) = w(~) + w(D) = 0 - 1 = -1 (note w(D) = -1 by the inductive hypothesis).
If C = ->EF, w(C) = w(->EF) = w(->) + w(E) + w(F) = 1 - 1 - 1 = -1 (again by the inductive hypothesis).

 

[AKG]

For (ii), you know that w(B) = -1, so if $w(s_1\dots s_k) < 0$, then $w(s_1\dots s_k) \leq -1$, therefore $w(s_{k+1}\dots s_l) \geq 0$. This is only possible if the number of "->" is greater than or equal to the number of propositional symbols in the substring $s_{k+1}\dots s_l$, but this is not possible. For k < n < l, let n be the least number such that $s_n$ is a "->". Show that $s_n\dots s_l$ is a formula, thus its weight is -1, and thus it has one less "->" than propositional symbols. So it is impossible for any k for $w(s_{k+1}\dots s_l) \geq 0$, proving that $w(s_1\dots s_k) \geq 0$.

For (iii), use the fact that w(->) = 1, w(C) = -1, so w(->C) = 0, but any "relevant" substring of that, ->C' will have weight

w(->C') = w(->) + w(C')
w(->C') = 1 + w(C')
w(->C') > 1 + 0 ... by (ii)
w(->C') > 1
w(->C') != 0.

 

[honestrosewater]

Wow, thanks. It makes much more sense to prove (i) with length. I'll post my work soon.
Just curious- how did you decide how to prove (ii)? I can usually see certain facts, that certain things will happen in such a way, but I'm not always sure what to do with them.
BTW, I like the <

 

[AKG]

For (ii), I don't know how I decided to do what I did, but I can give you reasons as to why you might think to do it that way. 1) It is a proof by contradiction, which I think tends to be my first instinct toward proving something. 2) There are two relevant substrings here, the one containing the first k symbols, and the one containg the rest. The one containing the rest is more likely to be meaningful, i.e. more likely to be a formula and/or contain one, and therefore you are more likely to be able to use what you already know (like the rules for what counts as a formula, and what you proved in (i)).

Also, (ii) says something is > 0. Where does that number come from? Well, you know how that number is found, so what makes it greater than or equal to zero? Since we're dealing only with adding 0, 1, or -1, it's pretty easy to figure that out.

 

[honestrosewater]

Ugh, I'm having problems figuring out what proving (i) by strong induction on deg(B) even means. He says eariler, "We shall often wish to prove that all formulas B have some property P- briefly, $\forall B (PB)$. This may be done by [strong] induction on deg(B), as follows. Define a property Q of natural numbers by stipulating that Q holds for a given number n iff P holds for all formulas B such that deg(B) = n.[/color] Then clearly $\forall B (PB)$ is equivalent to $\forall n (Qn)$."
I take this to mean that I need:
(1) $$Qn \Leftrightarrow \forall B\ deg(B) = n (PB)$$.
I'm trying to match his form, and, in his formulation of the "Strong Principle of Induction":
(2) $$\frac{\forall n [\forall m < n (Pm) \Rightarrow Pn]}{\forall n (Pn)}$$,
he says that $$\forall m < n (Pm)$$ means "all numbers m smaller than n have the property P" (he actually omits the parentheses around propositional functions but I prefer including them). So, in (1), $$\forall B\ deg(B) = n (PB)$$ would mean "all formulas B with deg(B) = n have the property P".[/color] Does that not have the same meaning as the indigo phrase above?
For (i), the property I want to prove B has is [w(B) = -1], so (1) becomes:
(3) $$Qn \Leftrightarrow \forall B\ deg(B) = n (w(B) = -1)$$,
but I can't figure out how to incorporate (3) into (2). I think the Qn in (3) should replace the Pm in (2), but I don't see how to do this.
Forgetting (1) and (3) and just thinking it through, I come up with:
(4) $$\frac{\forall B [\forall C deg(C) < deg(B) (w(C) = -1) \Rightarrow (w(B) = -1)]}{\forall B (w(B) = -1)}$$.
(4) seems to say what I want to prove. I'm further inclined to think that (4) is correct because he says, still speaking about the outline quoted above, "Stated in terms of P rather than Q, this is tantamount to saying: if we deduce PB (for arbitrary B) from the induction hypothesis that PC holds for all formulas B such that deg(C) < deg(B), then it follows that $\forall B (PB)$." So what am I missing?

 

[honestrosewater]

For (ii), I don't know how I decided to do what I did, but I can give you reasons as to why you might think to do it that way. 1) It is a proof by contradiction, which I think tends to be my first instinct toward proving something. 2) There are two relevant substrings here, the one containing the first k symbols, and the one containg the rest. The one containing the rest is more likely to be meaningful, i.e. more likely to be a formula and/or contain one, and therefore you are more likely to be able to use what you already know (like the rules for what counts as a formula, and what you proved in (i)).

Also, (ii) says something is > 0. Where does that number come from? Well, you know how that number is found, so what makes it greater than or equal to zero? Since we're dealing only with adding 0, 1, or -1, it's pretty easy to figure that out.

Great, thanks.