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 $()$.

  • $\begingroup$ Thank you @Brian! I didn't understand the definition of "set of parentheses" in this case. I now see that given n pairs (aka left / right pairs) of parentheses, the order in which they occur matters in order to constitute "the same set." So (()) can have 2 different meanings, although it won't if it's a proper pairing, as you noted and the lemma proves. So proper pairs, (()) and ()(), are "different sets" as you said, so do not apply to the hypothesis of the lemma. $\endgroup$ – Axel Jul 23 '20 at 1:52
  • 1
    $\begingroup$ @Axel: You’re welcome! Yes, I thought that that was where the confusion had probably arisen. $\endgroup$ – Brian M. Scott Jul 23 '20 at 2:00

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.