(adsbygoogle = window.adsbygoogle || []).push({}); Definitions:

Briefly, for the formal, object language L, there are two mutually exclusive categories ofprimitive symbols: (i) an infinite set ofpropositional symbolsand (ii) two distinctconnectives, ~ (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 astringoflengthl. The empty string has length 0.

Formulasare strings constructed as follows:

(1) A string consisting of a single occurence 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 occuring in B is called aprime componentof B.

Thedegree of complexityof B, deg B, is the total number of occurences of connectives in B.

Assign to each primitve symbol s aweightw(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, ...}:

[tex]\frac{\forall n [\forall m < n (Pm) \Rightarrow Pn]}{\forall n (Pn)}[/tex]

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:

[tex]P\beta \Leftrightarrow_{df} w(\beta) = -1[/tex]

and a property Q of natural numbers:

[tex]Qn \Leftrightarrow_{df} \forall \beta\ deg \beta = n (P\beta)[/tex]

so that [tex]\forall \beta (P\beta) \Leftrightarrow \forall n (Qn)[/tex].

And I need to deduce Qn from [tex]\forall m < n (Qm)[/tex], knowing that PB holds for Q0.

Is that correct so far?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proofs about weights of wffs

**Physics Forums | Science Articles, Homework Help, Discussion**