Weak Monadic Second Order Theory of Successor is not Element-recurive
Let L SIS be the set of formulas expressible in a week monadic second order logic using only the predicates [x =y+1] and [x E z]. Bucci and Elgot [3,4] have shown that the truth of sentences in L SIS (under the standard interpretation < N, successor > with second order variables interpreted as...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148867 |
| _version_ | 1826208583035912192 |
|---|---|
| author | Meyer, Albert R. |
| author_facet | Meyer, Albert R. |
| author_sort | Meyer, Albert R. |
| collection | MIT |
| description | Let L SIS be the set of formulas expressible in a week monadic second order logic using only the predicates [x =y+1] and [x E z]. Bucci and Elgot [3,4] have shown that the truth of sentences in L SIS (under the standard interpretation < N, successor > with second order variables interpreted as ranging over finite sets) is decidable. We refer to the true sentences in L SIS as WSIS. We shall prove that WSIS is not elementary-recursive in the sense of Kalmar. In fact, we claim a stronger result: |
| first_indexed | 2024-09-23T14:07:35Z |
| id | mit-1721.1/148867 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:07:35Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488672023-03-30T03:30:17Z Weak Monadic Second Order Theory of Successor is not Element-recurive Meyer, Albert R. Let L SIS be the set of formulas expressible in a week monadic second order logic using only the predicates [x =y+1] and [x E z]. Bucci and Elgot [3,4] have shown that the truth of sentences in L SIS (under the standard interpretation < N, successor > with second order variables interpreted as ranging over finite sets) is decidable. We refer to the true sentences in L SIS as WSIS. We shall prove that WSIS is not elementary-recursive in the sense of Kalmar. In fact, we claim a stronger result: 2023-03-29T14:03:37Z 2023-03-29T14:03:37Z 1973-12 https://hdl.handle.net/1721.1/148867 09593746 MIT-LCS-TM-038 MAC-TM-038 application/pdf |
| spellingShingle | Meyer, Albert R. Weak Monadic Second Order Theory of Successor is not Element-recurive |
| title | Weak Monadic Second Order Theory of Successor is not Element-recurive |
| title_full | Weak Monadic Second Order Theory of Successor is not Element-recurive |
| title_fullStr | Weak Monadic Second Order Theory of Successor is not Element-recurive |
| title_full_unstemmed | Weak Monadic Second Order Theory of Successor is not Element-recurive |
| title_short | Weak Monadic Second Order Theory of Successor is not Element-recurive |
| title_sort | weak monadic second order theory of successor is not element recurive |
| url | https://hdl.handle.net/1721.1/148867 |
| work_keys_str_mv | AT meyeralbertr weakmonadicsecondordertheoryofsuccessorisnotelementrecurive |