Timeline for Existence of well-ordering of epsilon_0 in weak theories
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7, 2017 at 10:00 | comment | added | Emil Jeřábek | Yes, there may be a computable descending chain. | |
| Mar 7, 2017 at 1:18 | comment | added | Noah Schweber | @JoelDavidHamkins I don't think that's the case. I suspect that via the equivalence WF($\epsilon_0$) iff Con(PA), any model in which $\epsilon_0$ is illfounded will have a computable (with standard index, even!) descending chain, corresonding to a putative proof of inconsistency in PA (although that proof will be nonstandard, a standard index can say "look for the lex. least proof of $0=1$," and I think that will be the only parameter needed). But I'm not sure. | |
| Mar 7, 2017 at 0:03 | comment | added | Joel David Hamkins | Emil, while the weak theories and even PA do not prove that the $\epsilon_0$ order on representations is a well order, could you tell me whether they nevertheless prove of every particular computable sequence (or other complexity-limited sequence), that it is a not a descending sequence in the order? In other words, in the models where $\epsilon_0$ is not well-ordered, what is the complexity of the simplest counterexample to well-foundedness? I guess this is closely related to the failure of induction that you mention in your final remark. | |
| Mar 6, 2017 at 22:51 | comment | added | David Roberts♦ | @NoahSchweber thanks, that extra detail helps. | |
| Mar 6, 2017 at 19:18 | vote | accept | David Roberts♦ | ||
| Mar 6, 2017 at 16:41 | comment | added | Noah Schweber | +1. And for the OP, although (an order of type) $\epsilon_0$ is definable as a class in PA in an appropriate sense, we can improve this - working in ACA$_0$, a conservative extension of PA, there actually is an object which is a linear order of type $\epsilon_0$ (again, in an appropriate sense). The "appropriate sense" is that the class/object needs to be interpreted in the standard model. | |
| Mar 6, 2017 at 16:17 | history | answered | Emil Jeřábek | CC BY-SA 3.0 |