1
$\begingroup$

In the paper linked below by Knuth and Bendix, theorem 1:

The set of all pure words is well-ordered by the relation '$>$'

has a proof that I can't seem to follow despite staring at it all day. I can't even decipher what the notation is trying to represent.

So, we have four fixed sequences:

  • An infinite sequence of variables $v_1, v_2, v_3, ...$ etc. (not relevant for Theorem 1)
  • A finite sequence of operators $f_1, f_2, f_3, ..., f_n$
  • A finite sequence of degrees $d_1, d_2, d_3, .., d_n$
    • (i.e. degree of $f_4 = d_4$)
  • and a finite sequence of weights $w_1, w_2, w_3, ..., w_n$
    • (i.e. weight of $f_4 = w_4$)

A word is then defined inductively as either a variable alone or an operator followed by an appropriate number of other words depending on the degree of said operator.

A 'pure word' is a word with no variables and the weight of a pure word, $\alpha$ is defined as follows:

  • $w(\alpha) = \sum_j w_jn(f_j , \alpha)$ where $n(f_j, \alpha)$ is the number of occurrences of $f_j$ in the word $\alpha$

Finally the relation $>$ that orders all pure words that is proved to be well-ordered is defined as:

$ \alpha > \beta $ if and only if:

    1. $w(\alpha) > w(\beta) $
    • (I'm assuming the '$>$' here is strict integer inequality and not the same '$>$' that is being defined.)
    1. $w(\alpha) = w(\beta)$ and $\alpha = f_j\alpha_1 ... \alpha_{dj}$, $\beta = f_k\beta_1 ... \beta_{dk}$, and either:
    • 2a) $ j > k$; or
    • 2b) $j = k$ and $\alpha_1 = \beta_1,..., \alpha_{t-1} = \beta_{t-1}, \alpha_t > \beta_t$, for some $t, 1 \leq t \leq d_j$

Finally on page 266, for the proof that $>$ is well-ordered the exposition states:

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:

$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$

i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I don't know whether it really is 'easy' to prove the above because I don't really know what the above is.

I'm fairly sure symbols are just operators in this context of pure words but if $n_0, n_1,$ etc. are symbols then how are they being summed? Does $n_0$ in the above actually represent $w(n_0)$. That doesn't seem to provide any clarity as to what is going on with the proof.

I've reread the first four pages of the paper multiple times and nothing seems to be getting any clearer:

https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf

Any insight would be appreciated.

$\endgroup$
1
$\begingroup$

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:

$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$

i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I think there is a small mistake here, since $n_j$ should be considered as the number of symbols of degree $j$ and not of degree $d_j$ in $\alpha$.

$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$

In this formula, the left side can be interpreted as "the total number of symbols", and the right side can be interpreted as "the first operator symbol plus the total number of arguments". Intuitively, those quantities are indeed equals.

If we correct the mistake, then it is somewhat easy to prove by induction:

  • if $\alpha$ does not contain any operator of degree $\geq 1$, then we have $\alpha = f()$, where $f$ is an operator of degree $0$ (that could be considered as a constant). We have then $n_0 = 1$, and $n_i = 0$ for any $i \geq 1$. The property $n_0 = 1 + n_2 + 2n_3 + ...$ holds;

  • if $\alpha = f(\alpha_1, …, \alpha_d)$ where $f$ is an operator of degree $d \geq 1$ and the $\alpha_i$ are pure words that verify the property we want to prove, then we get:

    • $n_k(\alpha) = \sum\limits_{i=1}^d n_k(\alpha_i)$ if $k \neq d$;
    • $n_d(\alpha) = 1 + \sum\limits_{i=1}^d n_d(\alpha_i)$.

    Therefore we get:

    $\begin{array}{rcl} n_0(\alpha)& = &\sum\limits_{i=1}^d n_0(\alpha_i) \\ & =& \sum\limits_{i=1}^d\left(1+\sum\limits_{k=2}^{\infty}(k-1)n_k(\alpha_i)\right)\\ & = & d + \sum\limits_{k=2}^{\infty}(k-1)\sum\limits_{i=1}^dn_k(\alpha_i) \\ & = &d + (d-1)(n_d(\alpha) - 1) + \sum\limits_{k = 2,k\neq d}^{\infty}(k-1)n_k(\alpha)\\ & = & 1 + \sum\limits_{k = 2}^{\infty}(k-1)n_k(\alpha)\end{array}$

    And that proves the formula by structural induction on pure words. Please note that the previous sums can be interverted because the infinite sum is, in fact, finite (since $n_k(\alpha_i) = 0$ for $k$ big enough).

The fact that $n_j$ is the number of symbols of degree $j$ and not of degree $d_j$ is somewhat confirmed after the statement: "since each nullary operator has positive weight, we have $w \geq n_0$". Why? Because $\alpha$ contains $n_0$ occurrences of nullary operators, which are supposed to be of positive weights. The statement would make no sense if $n_0$ was the number of symbols of degree $d_j$ (since $w_j$ could be zero).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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