dc.contributor.author | Meyer, Albert R. | en_US |
dc.date.accessioned | 2023-03-29T14:03:37Z | |
dc.date.available | 2023-03-29T14:03:37Z | |
dc.date.issued | 1973-12 | |
dc.identifier.uri | https://hdl.handle.net/1721.1/148867 | |
dc.description.abstract | 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: | en_US |
dc.relation.ispartofseries | MIT-LCS-TM-038 | |
dc.relation.ispartofseries | MAC-TM-038 | |
dc.title | Weak Monadic Second Order Theory of Successor is not Element-recurive | en_US |
dc.identifier.oclc | 09593746 | |