Timeline for Two questions regarding the reverse mathematics of Siegel's lemma
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 28, 2022 at 1:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 29, 2022 at 6:12 | comment | added | Thomas Benjamin | @FrançoisG.Dorais: is it possible that Siegel's Lemma is $\Delta_1$ rather than $\Pi_1$? | |
| Apr 27, 2022 at 22:14 | answer | added | Thomas Benjamin | timeline score: 1 | |
| Apr 12, 2022 at 20:58 | history | edited | Thomas Benjamin | CC BY-SA 4.0 |
added seigel's lemma at suggestion of comment
|
| Apr 12, 2022 at 20:44 | history | edited | Thomas Benjamin | CC BY-SA 4.0 |
added seigel's lemma at suggestion of comment
|
| Apr 10, 2022 at 10:18 | comment | added | Thomas Benjamin | @FrançoisG.Dorais: since you mentioned that Siegel's Lemma was probably provable in $EFA$, what factors would possibly keep it from being provable in $EFA$? | |
| Apr 10, 2022 at 8:58 | comment | added | Thomas Benjamin | Thanks. This is very helpful. | |
| Apr 10, 2022 at 7:51 | comment | added | François G. Dorais | To see that it is provable in EFA, I would just go through the proof carefully. It only uses the finite pigeonhole principle, so this has nothing to do with second-order arithmetic, this is about first-order arithmetic. So the context you set out is incorrect. To draw the right attention, you need to recast in terms of subsystems of first-order arithmetic. | |
| Apr 10, 2022 at 7:25 | comment | added | Thomas Benjamin | @FrançoisG.Dorais: it is provability in $EFA$ that interests me (and yes, that's the theorem I am referring to). I have been led to believe that the two systems of second-order arithmetic I have mentioned in my question have the same consistency strength as $EFA$ and are conservative over it for $\Pi_2$ sentences (via the Wikipedia entry for $EFA$). How would you go about proving that Seigel's Lemma is provable in $EFA$ (or could give me a reference where that has been already done)? | |
| Apr 10, 2022 at 5:03 | comment | added | François G. Dorais | That paper is very interesting but it has nothing to do with Siegel's Lemma. It would be useful to include a statement of Siegel's Lemma with the question. Assuming this is the lemma I think about, this is about bounds for nontrivial solutions of systems of linear homogeneous equations with rational coefficients. If I'm correct, this looks like a $\Pi_1$ statement at best. Second-order arithmetic is the wrong target. It's certainly provable in PRA and probably provable in EFA. | |
| Apr 10, 2022 at 1:03 | history | edited | Thomas Benjamin | CC BY-SA 4.0 |
Added period
|
| Apr 10, 2022 at 0:03 | history | edited | Gerry Myerson | CC BY-SA 4.0 |
typos
|
| Apr 9, 2022 at 20:32 | history | asked | Thomas Benjamin | CC BY-SA 4.0 |