20,369 reputation
25789
bio website math.cas.cz/~jerabek
location Prague
age 37
visits member for 4 years, 1 month
seen 3 hours ago

I am a researcher at the Institute of Mathematics of the Czech Academy of Sciences. I work in the field of mathematical logic, specifically proof complexity (mainly subsystems of bounded arithmetic, but also propositional proof complexity) and nonclassical logics (admissible rules of modal, superintuitionistic, and other propositional logics).


14h
comment Proof theory and the generalized Riemann hypothesis
@Joel: Some huge values can be described by fewer than $\log T$ symbols, yes. But then the OP needs to clarify what special values of $T$ is he talking about, and how they are represented in the statement.
1d
comment Geometry of rings and semi-rings
And for more keywords, the specific kind of SLPs that you consider here are known as addition-multiplication chains.
1d
comment Geometry of rings and semi-rings
Up to minor details, your algorithms are straight-line programs, and $\delta(n)$ is the arithmetic circuit complexity of $n$ (over $\mathbb N$ as a semiring).
1d
comment Proof theory and the generalized Riemann hypothesis
A ZF proof of a statement is at least as long as the statement itself. In this case, the statement involves $T$. How do you intend to write it down using less than $\log T$ symbols?
1d
comment Some questions about the paper, “Hypercontractivity, Sum-of-squares Proofs and Their Applications”
Cross-posted from cstheory.stackexchange.com/q/30930
Mar
25
comment Rigid fields containing $\mathbb{C}$
Rigid as a field (and therefore rigid as a $\mathbb C$-algebra, though that’s not a big feat: $\mathbb C$ itself is also a rigid $\mathbb C$-algebra).
Mar
25
comment What is wrong with the argument that zero permanent is polynomial?
Btw, your previous question is here: mathoverflow.net/q/172909 . (The question is not the same, but the underlying confusion is.)
Mar
25
comment What is wrong with the argument that zero permanent is polynomial?
You cannot test whether perm(B) is nonzero modulo Q. You can only test whether it is nonzero, and that does not tell you anything about A.
Mar
25
comment What is wrong with the argument that zero permanent is polynomial?
I have a deja vu. Didn't you ask this already some time ago? The answer is still the same: $\mathrm{perm}(A)=0$ doesn't imply $\mathrm{perm}(B)=0$. In fact, the way the reduction works, the permanent of $B$ is always positive (and fairly large).
Mar
24
comment Formal definition of arithmetic transfinite recursion
Though if you want a simple formula, the Wikipedia article mentions that it is equivalent to $\mathrm{ACA}_0 + \Sigma^1_1$-separation.
Mar
24
comment Formal definition of arithmetic transfinite recursion
Simpson’s book.
Mar
24
comment What is the size of the smallest rigid extension field of the complex numbers?
In the Dugas–Göbel 1997 paper, they prove exactly what the MR review states, with no further assumptions on the field. In particular, $\mathbb C$ does have a rigid extension of cadinality $2^\omega$. I have no idea where the claim that this is impossible comes from, but chances are it is based on a confusion with the fact that an extension of $\mathbb C$ with trivial endomorphism monoid has to have strictly larger cardinality, which is both easy to see and mentioned in Prőhle’s paper.
Mar
24
comment Rigid fields containing $\mathbb{C}$
I finally managed to get a copy of Dugas&Göbel (1997), Automorphism groups of fields II. They prove exactly what is stated in the MR review: for every group $G$ and field $F$, there is an extension $K$ of $F$ whose automorphism group is $G$, such that $|K|=\aleph_0\lvert G\rvert\lvert F\rvert$, with no further assumptions. So, $\mathbb C$ has a rigid extension of cardinality $2^\omega$.
Mar
24
comment Normal subgroup of a totally ordered group
You mean, a nontrivial totally ordered group?
Mar
24
comment Dissolution of Tensors
It’s not quite clear to me what the question is, but anyway, a sequent $\Gamma,A,B\Longrightarrow\Delta$ is interderivable with $\Gamma,A\otimes B\Longrightarrow\Delta$.
Mar
24
comment Generalizing a result of Kreisel on $\omega$-consistency
Kreisel’s result can be improved in yet another way. The argument is that if $T$ is $\omega$-consistent, then $T+\phi$ is $\omega$-consistent whenever $T\vdash_1\phi$. Now, Smoryński proved that for $T$ r.e., $T\vdash_1\phi$ iff $\mathrm{Th}_{\Sigma_3}(\mathbb N)+\mathrm{RFN}_T\vdash\phi$. In particular, for finite $T$, $\mathrm{RFN}_T\equiv T+\mathit{PA}$. Therefore: if $T\supseteq Q$ is $\omega$-consistent, then $T+I\Sigma_n$ is $\omega$-consistent for every $n$. (Which also means that the $I\Delta_0+\mathit{EXP}$ assumptions are not needed.)
Mar
24
comment About the proof of the proposition “there exists irrational numbers a, b such that a^b is rational”
@jmc: $a\mapsto\log_ac$.
Mar
23
comment Mal'cev “rational equivalence” and model theory
Well, I’m not in that much of a touch with universal algebra, but I’m in touch with model theory. The definition of rational equivalence given in the question is even stricter than definitional equivalence (the strictest of the three model-theoretic notions mentioned). The only difference between the two is that for rational equivalence, functions of one structure are required to be defined by terms in the other structure, whereas definitional equivalence allows functions (and relations) defined by arbitrary first-order formulas.
Mar
23
comment Mal'cev “rational equivalence” and model theory
This is a special case of definitional equivalence (up to isomorphism).
Mar
23
revised Generalizing a result of Kreisel on $\omega$-consistency
added 649 characters in body