Timeline for Complexity of deciding if an incomplete first-order theory has a stable completion
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2019 at 16:49 | vote | accept | James E Hanson | ||
| Apr 1, 2019 at 2:10 | answer | added | James E Hanson | timeline score: 1 | |
| Mar 31, 2019 at 14:55 | comment | added | tomasz | Yes, this is what I was thinking about. Well, with disjoint variables for $\varphi_1,\varphi_2$, but that is no big difference. | |
| Mar 31, 2019 at 14:34 | comment | added | James E Hanson | What I mean by coding is something like Slaman and Woodin's result that the class of partial orders with a linearization with the same order type as $\mathbb{Q}$ is $\Sigma$_1^1$-complete. The proof goes by taking an arbitrary tree and constructing a partial order such that the partial order has such a linearization if and only if the original tree was not well-founded. It's an 'encoding' since the construction is relatively low complexity (I believe it's computable from the tree, even). | |
| Mar 31, 2019 at 14:31 | comment | added | James E Hanson | I assume you're talking about coding in a 'switch' with something like $\psi(\overline{x},y_1,y_2) = (y_1=y_2 \wedge \varphi_1(\overline{x})) \vee (y_1 \neq y_2 \wedge \varphi_2(\overline{x}))$? That does seem relevant but I'll have to think about it. Thank you. | |
| Mar 31, 2019 at 10:54 | comment | added | tomasz | In any event, it is not hard to show that given any two formulas $\varphi_1,\varphi_2$, you can construct a formula $\varphi$ (purely syntactically, independently of $T$) such if $\varphi_1$ is not $k$-stable or $\varphi_2$ is not $k$-stable, then $\varphi$ is not $k$-stable. Using this (for countable languages), you can recursively construct a sequence $(\varphi_n)_{n\in \mathbf N}$ such that the $\varphi_n$s are increasingly unstable, and $T$ is stable iff each $\varphi_n$ is stable. I don't fully understand the question, but this should give you a negative answer. | |
| Mar 31, 2019 at 10:47 | comment | added | tomasz | But do you mean by encoding, exactly? | |
| Mar 30, 2019 at 20:34 | history | asked | James E Hanson | CC BY-SA 4.0 |