comment
comment
What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?
Where does it cut off mid-sentence?
revised
Loading…
revised
Loading…
revised
Loading…
comment
The Reverse Mathematics of writing a set as a union?
@FrancoisDorais: would "$\Sigma_{1}$-Separation implies the Union Principle" hold if the Union Principle was restricted to finite unions of finite sets?
comment
What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?
@NoahSchweber: have you any reference that shows that "the usual proof of Szemeredi actually goes through in $RCA_{0}$ alone"? that would be very helpful to me to study. Thanks in advance for your help in this matter. It would be much appreciated.
comment
What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?
If you could provide the proof that the Regularity Lemma is provable in $RCA_0$ or $I$$\Sigma_n$ in an answer I would, of course, accept it....
comment
What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?
Also, I didn't see that Prof. Friedman explicitly mentioned the Regularity Lemma in the FoM post you provided the link to though I am definitely aware of both of his Grand Conjectures.
comment
What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?
Then is the 'Union Principle' exposited in the mathoverflow question I mentioned actually provable in $I$$\Sigma_n$ when restricted to finite sets?
revised
Loading…
Loading…
comment
Maximal $l^2$ restriction of psd quadratic form on $\mathbb{R}^n$
What is the bigger research problem you are considering?
comment
The Reverse Mathematics of writing a set as a union?
Thanks. Just checking....
comment
The Reverse Mathematics of writing a set as a union?
@FrancoisDorais: Were you ever able to prove "$\Sigma^{0}_{1}$-Separation implies the Union Principle"?