Timeline for Are there sets which are computable in one model, but uncomputable in another?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2014 at 13:07 | vote | accept | Wojowu | ||
| Nov 6, 2014 at 18:39 | comment | added | 喻 良 | It would make induction fail. | |
| Nov 6, 2014 at 18:12 | comment | added | Wojowu | @LiangYu I don't see why this should be a contradiction. It can be the case that the subset of $\Bbb N^U$ becomes finite. | |
| Nov 6, 2014 at 18:08 | comment | added | 喻 良 | Concerning the last question. Any infinite subset of $(\mathbb{N})^U$ in $U$ does not exist in any proper extension $V$ of $U$. Otherwise, $(\mathbb{N})^U$ belongs to $V$, a contradiction. | |
| Nov 6, 2014 at 16:09 | answer | added | Joel David Hamkins | timeline score: 8 | |
| Nov 6, 2014 at 16:06 | comment | added | Andrej Bauer | A set $A \subseteq \mathbb{N}$ is computable iff $\exists n \in \omega \,.\, \forall m \in \omega \,.\, \exists k \in \omega \,.\, T(n,m,k) \land (U(k) \neq 0 \iff m \in A) $, where $T$ and $U$ are the Kleene predicate and function (primitive recursive). This is a $\Delta_0$-formula, therefore absolute for transitive classes. So at least the first part of your question has a positive answer: computability is absolute because it is expressible by a $\Delta_0$-formula. | |
| Nov 6, 2014 at 15:40 | comment | added | Asaf Karagila♦ | @Monroe: There's a slight issue with the suggested clarification, every two countable non-standard models of $\sf PA$ are order-isomorphic. | |
| Nov 6, 2014 at 15:29 | comment | added | Monroe Eskew | Please clarify what you mean by $A$ being in 2 nonstandard models. Maybe you need to say that $\mathbb N^U$ and $\mathbb N^V$ are isomorphic and you are comparing $A$ and its image under the isomorphism, which is a member of the other model. But then the same absoluteness considerations should apply as in the standard case. The condition is just that there is some $e$ coding a function $f$ into $\{0,1\}$ such that for all $n$, $f(n) = 1$ iff $n \in A$. But this statement should transfer through the isomorphism. | |
| Nov 6, 2014 at 15:19 | history | asked | Wojowu | CC BY-SA 3.0 |