Reputation
22,903
Top tag
Next privilege 25,000 Rep.
Access to site analytics
Badges
2 61 103
Newest
 Nice Answer
Impact
~241k people reached

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).