verify the claim that consequences of balanced identities are again balanced.

Question

verify the claim that consequences of balanced identities are again balanced. An identity is p≈q balanced if each variable occurs the same number of times in p as in q.if ∑ is balanced set of identities then using induction on the lenght of a formal deduction we can show that if ∑→p≈q then p≈q is balanced.

Answer 1

Let $\Sigma$ be a set of balanced identities and suppose $\Sigma \vdash p \approx q$. Let $$p_1 \approx q_1,\; p_2 \approx q_2,\; \ldots,\; p_n \approx q_n$$ be a formal deduction of $p \approx q$ from $\Sigma$, and let us see, by induction on $n$, that $p \approx q$ is balanced.

If $n=1$, then $p \approx q$ is $p_1 \approx q_1$ and either this identity belongs to $\Sigma$, or $p_1 = q_1$ (that is $p_1 \approx q_1$ has the form $t \approx t$). In any case, $p_1 \approx q_1$ is balanced.

Suppose, as induction hypothesis, that $$\Sigma' = \Sigma \cup \{ p_1 \approx q_1,\, \ldots,\, p_{n-1} \approx q_{n-1} \}$$ is balanced. There are five ways that $p_n \approx q_n$ can follow from $\Sigma'$:

1. By reflexivity. If $p_n = q_n$, then $p_n \approx q_n$ is balanced.
2. By simmetry. If $p_n \approx q_n$ follows from $\Sigma'$ because $q_n \approx p_n \in \Sigma'$, then clearly $p_n \approx q_n$ is balanced.
3. By transitivity. If $p_n \approx q_n$ because for some $r \in T(X)$ we have that (at least) one of $p_n \approx r$ or $r \approx p_n$ is in $\Sigma'$ and that (at least) one of $q_n \approx r$ or $r \approx q_n$ is in $\Sigma'$, then $p_n \approx r$ and $r \approx q_n$ are both balanced, and so the same happens with $p_n \approx q_n$.
4. By replacement. If $t \approx t' \in \Sigma'$, and $t$ is a subterm of $p_n$ and $q_n$ is the result of replacing the occurrence of $t$ in $p_n$ with $t'$, then $p_n \approx q_n$ is balanced.
5. By substitution. If $t \approx t' \in \Sigma'$ is an identity on the variables $x_1, \ldots, x_k$ and $r_1, \ldots, r_k \in T(X)$ are such that $p_n$ follows from replacing every occurrence of $x_i$ with $r_i$ in $t$ and $q_n$ follows from replacing every occurrence of $x_i$ with $r_i$ in $t'$, then $p_n \approx q_n$ is balanced.

The induction is complete.