# understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof:

If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are compatible, then $u_i$ is $u_i'$ for $i=1,2,\dots,n$.

Proof: We use induction on the length of $u_1\dots u_n$. We write $u_1$ as $vv_1\dots v_k$. $u_1'$ begins with $v$ and has the form $vv_1'\dots v_k'$. $u_1$ is compatible with $u_1'$, so $v_1\dots v_k$ is compatible with $v_1'\dots v_k'$. By induction hypothesis, $v_i$ is $v_i'$ for $i=1,2,\dots,k$. So $u_1$ is $u_1'$. From this it follows that $u_2\dots u_n$ is compatible with $u_2'\dots u_n'$; so by the induction hypothesis, $u_i$ is $u_i'$ for $i=2,\dots,n$.

I include his definitions below. I have trouble understanding this proof because

1) I'm not sure what the inductive hypothesis is (can somebody make it explicit and how it's being applied?) and

2) I'm not sure what is meant by "induction on the length of $u_1\dots u_n$". He makes me think that the induction hypothesis is a statement along the lines of "something is true for all symbols up to a certain positive integer $m$". But in the proof we only speak of the designators... which are recursive and we don't refer to the symbols which make up $v_1,\dots,v_k$.

I would just appreciate it if somebody can expand (make explicit) this proof since I don't see its structure. This is the first proof of the textbook, lol.

DEFINITIONS AND CONVENTIONS:

The symbol of the first-order language are $\neg,\lor,\exists$, symbols for variables, and symbols for functions and predicates. Shoenfield reserves the following letters (and their subscripted and "primed" counterparts) as syntactic variables. $u, v$ are variables for expressions, $f$ is a variable for functions, $p$ is a variable for predicates, $a$ is a variable for terms, $x$ is a variable for variables of the language.

He defines the terms of the first-order language as being 1) variables, or 2) $fa_1a_2\dots a_n$ where $f$ is an $n$-ary function and $a_1,a_2,\dots,a_n$ are terms ($n$ can be 0, and when it is, this is a constant). He defines the formulas as 1) $pa_1\dots a_n$ where $p$ is an $n$-ary predicate and $a_1,\dots,a_n$ are terms, 2) $\neg u$ where $u$ is a formula, 3) $\lor uv$ where $u,v$ are formulas, or 4) $\exists xu$ where $u$ is a formula.

He defines two expressions as being compatible if you can obtain one by adding an expression to the right of the other (one is a substring of the other). He defines a designator as being a term or a formula (since all terms and formulas in this language have the generic form $uv_1\dots v_n$ where $u$ is a symbol and $v_1, \dots, v_n$ are designators and $n$ can be 0).

Think of the theorem as being rewritten as follows:

If $m$ is a natural number, $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators, the string $u_1\dots u_n$ has exactly $m$ symbols, and $u_1\dots u_n$ and $u_1'\dots u_n'$ are compatible, then $u_i$ is $u_i'$ for $i=1, 2,\dots,n$.

The proof is by induction on $m$.

In the proof, the induction hypothesis is: if $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators, the string $u_1\dots u_n$ has fewer than $m$ symbols, and $u_1\dots u_n$ and $u_1'\dots u_n'$ are compatible, then $u_i$ is $u_i'$ for $i=1, 2,\dots,n$.

• How do we know that $v_1\dots v_k$ has $\leq m$ symbols when he applies the inductive hypothesis the first time? How do we know $u_2\dots u_n$ has $\leq m$ symbols when he applies the hypothesis the second time? – isthisreallife Jun 27 '16 at 17:35
• $v_1\dots v_k$ is shorter than $vv_1\dots v_k$, which is the same as $u_1$. But the number of symbols in $u_1$ is less than or equal to $m$, the number of symbols in $u_1\dots u_n$. Similarly, $u_2\dots u_n$ is shorter than $u_1\dots u_n$, which has length $m$. In both cases, the string is shorter because you're omitting one or more symbols at the beginning. – Mitchell Spector Jun 27 '16 at 17:57
• Oh. $m$ is both a variable that we're inducting on (as part of the hypothesis) and also an upper bound on the length of $u_1\dots u_n$. Maybe that's what I thought was confusing. – isthisreallife Jun 27 '16 at 18:03
• Is $m$ an upper bound of the length, or exactly equal to the length of $u_1\dots u_n$? If the latter, then you should change your post. – isthisreallife Jun 27 '16 at 18:10
• You're right. I wrote my previous comment too quickly; $m$ is an upper bound on the length of $u_1\dots u_n$. So that comment should read: ... But the number of symbols in $u_1$ is less than or equal to the number of symbols in $u_1\dots u_n$, which is less than or equal to $m$. Similary, $u_2\dots u_n$ is shorter than $u_1\dots u_n$, which has length less than or equal to $m$.... – Mitchell Spector Jun 27 '16 at 18:10