bio  website  math.cas.cz/~jerabek 

location  Prague  
age  37  
visits  member for  4 years, 1 month 
seen  3 hours ago  
stats  profile views  6,750 
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 semirings
And for more keywords, the specific kind of SLPs that you consider here are known as additionmultiplication chains. 
1d

comment 
Geometry of rings and semirings
Up to minor details, your algorithms are straightline 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, Sumofsquares Proofs and Their Applications”
Crossposted 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 modeltheoretic 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 firstorder 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 