Emil Jeřábek
Reputation
22,903
Top tag
Next privilege 25,000 Rep.
 30m comment What is the known weakest axiom system has Löb's derivability conditions? $I\Delta_0+EXP$ is an overkill. Lob's provability conditions are provable in PV, or even in TC^0 theories like Johanssen&Pollett's $\Delta^b_1$-CR. Apr 26 comment How to calculate $\langle v,w\rangle$ based only on $\langle v,x_i\rangle$ and $\langle w,x_i\rangle$? An $n$-tuple of random vectors is a basis, with probability $1$ (assuming they are independent and their distribution is continuous). Apr 26 awarded Nice Answer Apr 26 revised Decidability of diophantine equation in a theory reference for Q Apr 25 comment Mathematicians with Aphantasia (Inability to Visualize Things in One's Mind) Please, do not include metadiscussion about the fate of the question in the question itself. If you want to discuss the closure, the appropriate place is meta.mathoverflow.net (specifically, meta.mathoverflow.net/questions/223/…). FWIW, there are already two votes to reopen the question. Apr 25 comment origin of analogy “primes as the atoms of number theory/ arithmetic” For completeness: prime and incomposite are called πρῶτον and ἀσύνθετον in the original. Apr 25 revised origin of analogy “primes as the atoms of number theory/ arithmetic” typo Apr 24 comment an algebraic variety for a boolean circuit (3) As for the update: satisfiability can be determined by itself in poly(n) space, and then you can just output a fixed solvable or unsolvable polynomial system according to the result. Apr 24 comment an algebraic variety for a boolean circuit (2) When you write "irreducible", do you mean irreducible over $\mathbb F_2$, or absolutely irreducible? Apr 24 comment an algebraic variety for a boolean circuit (1) The property you wrote down is much stronger than just NP-completeness of the problem. It happens to be true for 3-CNF, but for general circuits, it only works under a generous representation of the polynomials $f_i$ (say, as arithmetic circuits). NP-completeness only says there is a poly-time transformation of circuits $g(x_1,\dots,x_n)$ to systems of polynomials $f_i(y_1,\dots,y_m)$ so that $g$ is satisfiable iff the polynomial system is solvable, without any implied connection between the two solution sets. Do you allow this or not? Apr 22 comment Can one satisfaction class code another? All right, thanks. Apr 22 comment Can one satisfaction class code another? What is a satisfaction class? Apr 21 comment Non-Archimedean non-standard models for R @GeraldEdgar While I agree with the general sentiment, the compactness theorem for countable theories does not need the axiom of choice. Apr 21 comment What is the precise relationship between o-minimal theory and Grothendieck's “Esquisse d'un programme”? Thanks, yes, I noticed. Apr 20 revised Is injectivity of $2^{(\ldots)}$ weaker than $\mathsf{GCH}$? fix link Apr 20 comment What is the precise relationship between o-minimal theory and Grothendieck's “Esquisse d'un programme”? Definable functions needn’t be piecewise $C^\infty$. They are piecewise $C^k$ for every finite $k$, but you may need finer and finer pieces as $k$ gets larger. See the comments at mathoverflow.net/questions/234337 . Apr 20 comment Is there any digraph data set that gives all directed graphs satisfying certain requirements? Cross-posted at cstheory.stackexchange.com/questions/34425/… . Apr 17 comment Does the consistency strength hierarchy coincide with the “arithmetic consequence” hierarchy at ZF + Reinhardt? Well, I meant to set up the argument a bit differently, but this works just the same. Apr 17 comment Does the consistency strength hierarchy coincide with the “arithmetic consequence” hierarchy at ZF + Reinhardt? That $(\Pi^0_1)_S\subseteq(\Pi^0_1)_T$ iff $S\le^*_{\mathrm{Con}}T$ iff $S$ is interpretable in $T$ is the Orey-Hájek characterization of interpretability in reflexive theories. Apr 17 comment Does the consistency strength hierarchy coincide with the “arithmetic consequence” hierarchy at ZF + Reinhardt? So, in the situation in the answer: if T proves uniform $\Sigma_1$-reflection for ZFC (any large cardinal axiom does), then this arithmetic consequence of T is not provable in ZFC + Con(T).