In the classic book, Introduction to Metamathematics by Steven Kleene, Lemma 2 of Section 7 (chapter 2), seems to me to be false. I am wondering if I am missing something. Here is the context:
The following definitions are used:
Proper pairing - one-to-one pairing between n left parentheses "(" and n right parentheses ")" such that for each pair left parenthesis is on the left from the right parenthesis and if no two pairs separate each other.
Pairs of parentheses that separate each other - two pairs separate each other if they occur in the order $(_i(_j)_i)_j$ (ignoring everything else).
Then Kleene gives Lemma 1, stated below, which I agree with and find easy to prove using strong induction. Note that the lemma states "an" innermost pair, not "precisely one" innermost pair.
Lemma 1: A proper pairing of $2n$ parentheses ($n>0$ and $n$ is a natural number) contains an innermost pair, i.e. a pair which includes no other of the parentheses between them.
Then Kleene gives Lemma 2 as follows, which I disagree with.
Lemma 2: A set of $2n$ parentheses admits at most one proper pairing.
Kleene gives the following explanation: "Prove by a (simple) induction on $n$. (HINT: Under the induction step by Lemma 1 the given parentheses contain an innermost pair. Withdrawing this, the hypothesis of the induction applies to the set of the parentheses remaining."
I have a problem with this. Why? Consider $(^1_1(^2_2)^3_2)^4_1$ and $(^1_1)^2_1(^3_2)^4_2$. Each of these examples contains $2n$ parentheses, is a proper pairing, but are not the same pairing. The last sentence of Kleene's explanation does not hold because, just because the an innermost pair is removed, you can include a set of parentheses around the outside or concatenated with the current pair.
Am I missing something?
Your example does not support your objection, since $(())$ and $()()$ are not the same string of parentheses. They are different sets, and each of them does in fact admit a single proper pairing, illustrated by the colors here: $\color{red}(\color{blue}(\color{blue})\color{red})$, and $\color{red}(\color{red})\color{blue}(\color{blue})$. Moreover, for each of them it is true that if we remove an innermost pair, what is left is a single pair that has a unique proper pairing: there is only one innermost pair in $(())$, and there are two innermost pairs in $()()$, but removing any of these innermost pairs leaves the properly paired string $()$.