Timeline for How tightly are decidability and "induction-completeness" linked?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2023 at 17:36 | comment | added | Fedor Pakhomov | This method, of course, doesn't help for Question 2, since if $A$ would be strongly representable over finite set of axioms, $B$ would be definable in MSO. | |
| Aug 8, 2023 at 17:34 | comment | added | Fedor Pakhomov | Then we pick $A=\{2^n\mid n\in B\}$ and observe that $\mathsf{Th}(\mathbb{N};+,A)$ isn't finitely axiomatizable over induction (here we using interpretation of (\mathbb{N};+) in $(\mathbb{N},\mathcal{P}(\mathbb{N};S)$, where naturals are interpreted by finite sets of naturals representing their binary expansions). | |
| Aug 8, 2023 at 17:34 | comment | added | Fedor Pakhomov | Using the characterization above pick a set $B$ of naturals such that it is not definable by a monadic formula (i.e. is no finally periodic), but the set of monadic $\varphi(X)$ that are true on $B$ is decidable (note that we could go back and forth between monadic formulas and $\omega$-regular expressions). I think that it should be relatively easy to show that for $B=\{n^2\mid n\in\mathbb{N}\}$ we could effectively check if it as an $\omega$-word of $0$ and $1$'s lies in a particular language $L_1L_2^\omega$. | |
| Aug 8, 2023 at 17:34 | comment | added | Fedor Pakhomov | It would be fairly easy to show that the answer to Question 1 is negative via the reduction to $\mathsf{MSO}(\mathbb{N};0,S)$. There we have the property that definable classes of sets of naturals are if treated as languages of infinite $\{0,1\}$-words are precisely $\omega$-regular languages (i.e. languages of the form $L_1L_2^\omega=\{\alpha\beta_0\beta_1\ldots\beta_n\ldots\mid \alpha\in L_1,\beta_i\in L_2\}$ where $L_1$ and $L_2$ are regular). | |
| Aug 8, 2023 at 3:10 | history | edited | Noah Schweber | CC BY-SA 4.0 |
added 456 characters in body
|
| Aug 8, 2023 at 2:55 | history | asked | Noah Schweber | CC BY-SA 4.0 |