Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

what does two words F , G are initial mean ? with some examples .

also there is a lemma says , for any formula f in F and any word w in W(A) , if w is initial segment of F , then o[w] >= c[w]

where o[w] is the number of opening parenthess , c[w] = the closing parenthess

i didn't understand the proof of this lemma from the text , can any one give a nice proof after explaning what does initial mean with examples ?!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

If $\sigma=s_1s_2\dots s_n$ is any string of symbols, the initial segments of $\sigma$ are the empty string and the strings $s_1$, $s_1s_2$, $s_1s_2s_3$, and so on up to $\sigma$ itself. For instance, the $\sigma$ is the string segment, the initial segments of $\sigma$ are the empty string and the strings s,se,seg,segm,segme,segmen, and segment.

A formula $f\in F$ is a string of symbols satisfying certain additional conditions. Exactly what these conditions are depends on just how you’ve defined formulas, and unfotunately you didn’t tell us that. Possibly one of your formation rules was that if $f$ and $g$ are formulas, so is $(f\lor g)$. If your definition allows proposition constants $p,q$, and $r$, for instance, your rules for constructing formulas might let you construct the formula $((p\lor q)\land r)$. The non-empty initial segments of this formula are $($, $(($, $((p$, $((p\lor$, $((p\lor q$, $((p\lor q)$, $((p\lor q)\land$, $((p\lor q)\land r$, and $((p\lor q)\land r)$. Here’s a table of $o[w]$ and $c[w]$ for each initial segment $w$ of the formula $((p\lor q)\land r)$.

$$\begin{array}{l|c|c} w&o[w]&c[w]\\ \hline &0&0\\ (&1&0\\ ((&2&0\\ ((p&2&0\\ ((p\lor&2&0\\ ((p\lor q&2&0\\ ((p\lor q)&2&1\\ ((p\lor q)\land&2&1\\ ((p\lor q)\land r&2&1\\ ((p\lor q)\land r)&2&2 \end{array}$$

As you can see, we always have $o[w]\ge c[w]$ in this example.

Without having seen the proof in your text I can’t be certain, but it’s very likely that it was a proof by induction on the complexity of the formula.

Suppose, for instance, that I know that formulas $f$ and $g$ have the desired property: each of their initial segments contains at least as many opening as closing parentheses. Suppose also that the definition of formula tells me that $(f\lor g)$ is a formula. Then any non-empty initial segment of $(f\lor g)$ is either $($ followed by an initial segment (possibly empty) of $f$, or $(f\lor$ followed by an initial segment (possibly empty) of $g$. If $w=(u$, where $u$ is an initial segment of $f$, then $$o[w]=1+o[u]\ge 1+c[u]>c[u]=c[w]\;:$$ $w$ has one more opening parenthesis than $u$, $o[u]\ge c[u]$ by the induction hypothesis that $f$ has the desired property, and $w$ and $u$ have the same number of closing parentheses. If $w=(f\lor u$, where $u$ is an initial segment of $g$, then

$$o[w]=1+o[f]+o[u]\ge 1+c[f]+c[u]>c[f]+c[u]=c[w]\;:$$

$w$ has one more opening parenthesis than $f$ and $u$ combined and has exactly as many closing parentheses as $f$ and $u$ combined, while $o[f]\ge c[f]$ and $o[u]\ge c[u]$ by the induction hypothesis. Thus, $o[w]\ge c[w]$ for every initial segment of $(f\lor g)$.

As I said, I can’t be sure without seeing the actual proof, but I think it likely that it consisted of several arguments of this type, one for each of the construction rules that you have for building formulas.

share|improve this answer
thank you very much , you made it so clear for me , I read the proof again with your notes and I understood it very well specially after understanding what does initial mean . the text proves this lemma as the same way you did . but it coverd all cases . thank you very much :) :))) –  Maths Lover Jan 21 '13 at 1:43
@MathsLover: Excellent! You’re very welcome. –  Brian M. Scott Jan 21 '13 at 1:44
my text is mathematical logic : a course with exercises . part 1 , by rene cori & daniel lascar . –  Maths Lover Jan 21 '13 at 1:45
thank you :) , I'm not trained with mathematical logic and it's the first time i face it ! and I'm a high schoo student ! so it's somehow difficult for me specially in first steps in the subject as happened in abstract algebra ! again thank you professor :) –  Maths Lover Jan 21 '13 at 1:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.