# A decision problem about balanced parentheses

José Manuel Rodríguez Caballero josephcmac at gmail.com
Tue Mar 17 03:11:16 EDT 2020

```Dear FOM members,
I would like to ask for any reference concerning the following problem or
any variation of it.

Given a list of balanced parentheses L, is there a proof in first-order
Peano arithmetic that we are in either of the following cases:

A. there is a positive integer n such that L is equal to Dyck(n),

B. for any positive integer n we have that L is not equal to Dyck(n),

where Dyck(n) is given by the following algorithm:

Input: a positive integer n.
Step 1. Write the divisors of 2n in increasing order.
Step 2. Delete the divisors d such that both d and 2n divided by d are even
numbers.
Step 3. For any odd number in the list, write an open parenthesis and for
any even number, write a close parenthesis.
Output: the list of parentheses, denoted Dyck(n).

Example,
Input n = 30.

Step 1.
1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Step 2.
1, 3, 4, 5, 12, 15, 20, 60

Step 3 (output).
Dyck(30) is ( ( ) ( ) ( ) )

In the case of the list L given by  ( ( ) ( ) ( ) ), we are in case A. For
the list L given by ( ) ( ( ( ) ) ) we are in case B.

Sincerely yours,
Jose M.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200317/70228c75/attachment.html>
```