20,670 reputation
25790
bio website math.cas.cz/~jerabek
location Prague
age 37
visits member for 4 years, 3 months
seen 22 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).


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 non-r.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 constant-size 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 Thue-Morse sequence, extended to $\Z$ by putting $-n-1\in A$ iff $n\in A$. So, ...
May
9
comment Is the lowenheim-skolem number of nth order logic larger than the corresponding number for 2nd order logic
Second-order 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 Paris-Harrington 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 constant-size 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?