Timeline for "Almost all" quantifier
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 8, 2011 at 13:34 | comment | added | Emil Jeřábek | @boumol: End of page 357 and the beginning of the next page. | |
| Sep 8, 2011 at 13:30 | comment | added | boumol | @Dave: Where in Mazur's paper it is stated this fact? | |
| Sep 8, 2011 at 12:00 | comment | added | Dave Marker | In Mazur, B. Questions of decidability and undecidability in number theory. J. Symbolic Logic 59 (1994), no. 2, 353–371. Mazur says that it is open whether deciding if a diophantine equation has infinitely many solutions is $\Pi_2$-complete. | |
| Sep 7, 2011 at 13:59 | comment | added | boumol | @David: Thanks for the correction, you are right. By the way, anybody knows a reference for the $\Pi_2$-completeness of the problem of determining in general whether a diophantine equation has infinitely many solutions? This is claimed by JDH at the end of the stackexchange link. | |
| Sep 7, 2011 at 13:41 | comment | added | David E Speyer | @bourmol That's not really very on topic. Marker and Slaman add an "alomst all" quantifier but they delete the "for all" and "there exists" quantifiers. This makes the logic much weaker than standard logic. We talked about this some at math.stackexchange.com/questions/50625 | |
| Sep 7, 2011 at 13:28 | comment | added | boumol | If you want to have more insight on this quantifier take a look at the paper "Decidability of the Natural Numbers with the Almost-All Quantifier" by Marker and Slaman (the link is arxiv.org/abs/math/0602415 ) | |
| Sep 7, 2011 at 12:45 | comment | added | Emil Jeřábek | The answer is the same in all cases I can think of, but what do you mean by a “model of natural numbers”? A model elementarily equivalent to $\mathbb N$, a model of Peano arithmetic, a model of Robinson arithmetic, or what? | |
| Sep 7, 2011 at 12:39 | answer | added | Emil Jeřábek | timeline score: 10 | |
| Sep 7, 2011 at 12:28 | history | asked | Piotr Pstrągowski | CC BY-SA 3.0 |