bio  website  math.cas.cz/~jerabek 

location  Prague  
age  37  
visits  member for  4 years, 3 months 
seen  22 hours ago  
stats  profile views  6,932 
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).
2d

comment 
Positive rational numbers as sum of unit fractions
What is the difference between this question and mathoverflow.net/q/191966 ? 
May 18 
comment 
Godel's second incompleteness theorem for nonr.e. theories
Isn't that simply $\Sigma_2$soundness? 
May 16 
awarded  Nice Answer 
May 15 
comment 
If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?
@Asaf: You can hang the theorem at your belt and pat it in a suggestive way in case they wanted to try more tricks, but it’s no good trying to examine the body when all what’s left is a smoking crater in the ground. Meanwhile, given your professional interests, you might appreciate that sometimes you just don’t have the Choice. Can you prove the Keisler–Shelah theorem (and Łoś’s theorem) in ZF + BPIT? It works for elementary amalgamation. 
May 15 
comment 
If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?
@TimCampion: In the statement of Theorem 5.3.1, take $\bar a$ and $\bar c$ to be the empty sequences. The picture is somewhat misleading, as the two mappings depicted in the lower part are not really elementary. 
May 15 
comment 
If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?
Yes. And the argument is this: let $T'$ be a finite subset of $T_2$, and $\phi(a_1,\dots,a_n)$ its conjunction, with the $M_2$constants explicitly indicated. Since $M_1$ and $M_2$ are elementarily equivalent, the sentence $\exists x_1\dots\exists x_n\,\phi(x_1,\dots,x_n)$, which holds in $M_2$, must also hold in $M_1$, so you can choose $a'_1,\dots,a'_n\in M_1$ such that $M_1\models\phi(a'_1,\dots,a'_n)$. Then $M_1$, expanded with its own constants, and with $a'_i$ for $M_2$'s constants, is a model of $T_1\cup T'$. 
May 15 
comment 
If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?
The Keisler–Shelah theorem, which involves a delicate construction of an ultrafilter, is an overkill. The fact that any two elementarily equivalent structures are elementarily embedded in one structure can be proved by a very simple compactness argument. 
May 12 
comment 
Algebraic Closure of the field of rational functions
Over finite fields, there is a description due to Kedlaya: eudml.org/doc/249608 . 
May 11 
comment 
Ways to prove the fundamental theorem of algebra
If $\mathbb K$ is algebraically closed, then the fundamental theorem of algebra holds by definition, so appealing to the Nullstellensatz is pointless. 
May 11 
comment 
Asymptotics on number of bounded prime gaps
This is more or less a duplicate of mathoverflow.net/q/176875 . 
May 9 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
... while this doesn't help with analysis of the model with random or generic $A$, it gives a completely explicit example of a Leibnizian model with no definable elements. 
May 9 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
You're right, that was misleading. Let me restate the remark in a more useful form. First, $m$equivalence is determined by constantsize neighbourhoods iff $(\Z,<,A,S,P)$ has quantifier elimination. Now, for any set $A$, the following are equivalent: (1) $(\Z,<,A,S,P)$ has quantifier elimination, and no definable elements; (2) every finite string that occurs in $A$ occurs in all sufficintly long intervals. It's not immediately obvious that there are nonperiodic sets $A$ with this property, but one such is the ThueMorse sequence, extended to $\Z$ by putting $n1\in A$ iff $n\in A$. So, ... 
May 9 
comment 
Is the lowenheimskolem number of nth order logic larger than the corresponding number for 2nd order logic
Secondorder and $n$th order logic have the same LS number: you can emulate $n$th order logic by $n$sorted 2nd order logic, as you can state in 2nd order logic that every subset of the $i$th sort is represented in the $(i+1)$th sort. 
May 9 
comment 
PA proves that functions are total
No $\Sigma_1$sound r.e. extension of arithmetic can represent all recursive functions in a provably total way, and yes, for PA you can take the ParisHarrington function: the usual arguments that PA doesn't prove $\forall x\exists y\phi(x,y)$ actually apply to PA + the set of all true $\Pi_1$ sentences, hence to all possible definitions of the same function. 
May 8 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
Dense orbit is certainly not sufficient by itself. If $A$ is a random set of positive integers, it still has dense orbit, but one can use it to define $\min(A)$. So, at least one needs to require that every finite string appears infinitely often in both directions, but I have doubts this is sufficient either. Note that if one could guarantee $m$equivalence by examining a constantsize neighbourhood (depending on $m$), then $A$ must have the property in my first comment (take $m$ larger than the quantifier rank of the formula "such and such substring occurs somewhere between $x$ and $y$"). 
May 8 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
Sorry, the comments arrived at the same time. If you want to write it up, please go ahead. 
May 8 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
I’m kind of busy at the moment to look at it properly. You’re right that the property fails even for generic sets, so it’s not the right notion. However, I feel that there should be a property along those lines that would cover both examples. 
May 8 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
Anyway: assume for contradiction that random $\langle\mathbb Z,<,A\rangle$ has a definable element with positive probability. Then there is a formula $\phi(x)$ and $n\in\mathbb Z$ such that $\phi$ defines $n$ with probability $\epsilon>0$. However, by translation invariance, for every $m$, $\phi$ defines $m$ with probability $\epsilon$ as well. Considering $>1/\epsilon$ different $m$s gives a contradiction. 
May 8 
comment 
Is there a Leibnizian model with no definable elements, in a finite language?
I think that by a quantifier elimination argument, you only need that $A$ satisfies the following property: for every finite pattern, there exists an $n$ such that the pattern is realized in every interval of length $n$ (is this description clear enough?). However, this is actually almost surely false for a random $A$. 
May 7 
answered  Is there a Leibnizian model with no definable elements, in a finite language? 