21,375 reputation
25993
bio website math.cas.cz/~jerabek
location Prague
age 38
visits member for 4 years, 6 months
seen 14 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).


15h
comment Trivial zeroes of the Riemann Zeta function are simple
@Bazin: You should include your working definition of the zeta function in the question, as any answer will crucially depend on it.
2d
awarded  nt.number-theory
2d
awarded  Nice Answer
2d
comment Continued Fractions from Digit Streams
Well, what about it?
2d
answered Continued Fractions from Digit Streams
Aug
25
comment Undecidable set of problems
What, if any, of the two occurrences of the word “decidable” in your post refer to algorithmic decidability of a set of finite strings, and what refer to unprovability and nonrefutability of a formula in a formal system? In the latter case, what is the system?
Aug
25
awarded  Good Answer
Aug
24
comment What are key $\Sigma^0_2$ or $\Pi^0_3$ theorems?
What you are talking about are just unimportant syntactical details. What matters is that PCA can’t prove more $\Pi_2$ sentences than $I\Sigma_1$. (Specifically, one important point is that all relations in PCA are $\Sigma_1$-definable, and in particular, being $\Sigma_1$ is preserved by taking transitive closure.) PRA can be considered in the orthodox sense just an equational theory, but it is quite often also defined as an equivalent regular FO theory, and then it is exactly the $\Pi_2$ fragment of $I\Sigma_1$.
Aug
24
comment What are key $\Sigma^0_2$ or $\Pi^0_3$ theorems?
@LucasK.: The description of PCA in mathoverflow.net/q/208696 does not seem to include anything that would not formalize in $I\Sigma_1$, or for that matter in its $\Pi_2$ fragment, which is just PRA. Thus, PCA should be equivalent (or at least, included in) PRA, and much weaker than the $\Pi_2$ fragment of PA.
Aug
23
comment What are key $\Sigma^0_2$ or $\Pi^0_3$ theorems?
Even better, the $\Pi^0_2$ fragment of PA is axiomatized by the uniform $\Sigma_1$ reflection schema for finite subtheries of PA (that is, for the theories $I\Sigma_n$)
Aug
20
answered Has by well-foundedness every non-empty class an $R$-minimal element? Also if axiom REG is not assumed?
Aug
20
comment bound on the size of a circuit
These are not research-level questions. For a more appropriate site, you can try cs.stackexchange.com .
Aug
20
comment Has by well-foundedness every non-empty class an $R$-minimal element? Also if axiom REG is not assumed?
Now that I think about it, the model constructed in Theorem 11 of our paper arxiv.org/abs/1311.0814 should do the job: it satisfies ZFC^- with collection, and there is a class carrying a dense linear order (with no least element) whose every subset is well-ordered.
Aug
20
comment Has by well-foundedness every non-empty class an $R$-minimal element? Also if axiom REG is not assumed?
Let $X$ be a class. First, by a straightforward induction on $n$, prove for all $n\in\omega$ that $X$ is a finite set with $< n$ elements, or it contains an $n$-element subset. Thus, assuming $X$ is not a finite set, we have $\forall n\in\omega\,\exists x\subseteq X\,|x|=n$. Applying collection, there is a set $z$ such that $\forall n\in\omega\,\exists x\in z\,(x\subseteq X\land|x|=n)$. Then $X\cap\bigcup z$ is an infinite subset of $X$.
Aug
20
comment Has by well-foundedness every non-empty class an $R$-minimal element? Also if axiom REG is not assumed?
That every proper class has an infinite subset is implied by collection, so I take it you don't include the collection schema in the list of axioms of ZFC^-?
Aug
14
comment Deciding a quadratic diophantine equation
The criterion should read that $-ab$ is a square modulo $c$, $-ac$ a square modulo $b$, and $-bc$ a square modulo $a$. The statement with Legendre/Jacobi symbols is not in general equivalent to this unless $a,b,c$ are primes. Already in the simplest case $a=b=1$, it’s not true that a square-free $c$ is a sum of two rational squares iff it is $\equiv1\pmod4$.
Jul
17
comment A question on integers relatively prime to their Euler totien function
@JeremyRouse: I read the condition as “$Y$ be a subset of $X$ containing all prime numbers, and possibly some other numbers”.
Jul
14
comment Lattices without prime ideals
Ah, sorry: they are meet-irreducible, but not prime. However, they are most definitely proper ideals, so they need to be dealt with in the answer in one way or another.
Jul
14
comment Lattices without prime ideals
The principal ideals generated by any $\alpha\in\kappa$ are all prime.
Jul
14
comment Propositional logic without negation
Your implications are a notational variant for monotone sequents, so you might want to look into the monotone sequent calculus.