MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

# Emil Jeřábek

 10,809 Reputation 4008 views

## Registered User

 Name Emil Jeřábek Member for 2 years Seen 13 hours ago Website Location Prague Age 35
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).
 16h comment Every abelian torsion-free group is strictly totally orderable (via the compactness theorem)I have added a note on generalization to other structures. I think this also illustrates the difference between the two proofs. 16h revised Every abelian torsion-free group is strictly totally orderable (via the compactness theorem)generalization 16h accepted Every abelian torsion-free group is strictly totally orderable (via the compactness theorem) 16h comment Every abelian torsion-free group is strictly totally orderable (via the compactness theorem)Well, the argument is similar, but I would not say it’s quite the same. Your argument goes by embedding the whole group into something rich enough that it turns out to be easily orderable, whereas here we reduce the problem to subgroups that are poor enough to be easily orderable. Essentially, one looks at the group as the direct limit of its finitely generated subgroups. (This does not literally work, as the orders on the subgroups are not canonically chosen. The purpose of compactness here is to make these choices in a consistent way.) 17h comment Number of integers in ratio of arithmetic progressionsHow many integers are arbitrarily close to $a/c$? This is not a research-level question. 17h answered Every abelian torsion-free group is strictly totally orderable (via the compactness theorem) Jun8 awarded ● Necromancer Jun5 comment Is there an RSS reader for mathematicians?I don’t care about RSS readers, but the bookmarklet is just awesome. Jun4 comment The Erdős-Turán conjecture or the Erdős' conjecture?Ha. The verb is copy edit, the noun is copy editing (as in “I’ve done some copy editing today”), and the adjective is copy-editing (as in “This is a great copy-editing tool”), for much the same reasons as in mathoverflow.net/questions/131424. It seems copyedit and copyediting are also possible. Jun4 revised Ontological status of some “sets” in ZFCfix markup Jun4 comment The Erdős-Turán conjecture or the Erdős' conjecture?@Butch: The reason for insisting on an en-dash instead of a hyphen is pretty much the same as the reason you gave for connecting the two names in the first place: “the Erdős-Turán conjecture” looks like a conjecture made by one person whose double-barrelled surname is Erdős-Turán. Think Paul du Bois-Reymond. I thus can’t comprehend the double standards that avoiding a space is so important while avoiding a hyphen is “fascism” and “nitpicking”. Jun3 comment Is there a nice characterisation of topoi with nice meta-logical properties?Indeed. There is nothing higher-order about the logic of Henkin semantics, it is just multi-sorted first-order logic with a light touch of syntactic sugar, and it would save unnecessary confusion if people called it as such. May31 comment Deduction theoremThis is the answer. I’m sorry I can only upvote it once. May30 comment Deduction theorem@François: How come? A is derivable from A by a one-line proof consisting of just A, even if your system has no logical axioms or rules. More generally, every Hilbert system defines a Tarski-style consequence relation, irrespective of the presence of any particular rules. May30 comment Boys and Girls RevisitedI suppose you mean to wait until every family has a boy, and only then tell them to multiply forever? May28 comment Order-independent properties arising naturally in mathematicsThe question is quite interesting for logics between first and second order. In particular, inflationary fixed-point logic characterizes classes of structures recognizable in deterministic polynomial time in the presence of a linear order, but it is strictly weaker in general, and it is an open problem whether there exist a logic characterizing polynomial time on unordered structures at all. May28 revised Homomorphisms from powers of Z to Zfix name May28 comment Fixed point theoremsThe poset I’m applying Pataraia’s FPT to does not include $\varnothing$, so it has to produce another fixed point. And I use all the topological properties: the space needs to be compact Hausdorff so that images of closed sets are closed, and so that the poset has joins of directed subsets (which translates to: any family of closed sets with the finite intersection property has nonempty intersection). The theorem does not hold in general for locally compact spaces: consider $X=(0,1]$ and $f(x)=x/2$. May28 awarded ● Pundit May26 awarded ● Enlightened May25 awarded ● Nice Answer May24 comment Are undecidable consequences of Con recursively enumerable?Anyway, PA proves $\sigma\to\Pr_{PA}(\ulcorner\sigma\urcorner)$ for every $\Sigma^0_1$-sentence $\sigma$ by formalizing the proof of $\Sigma^0_1$-completeness of Q. May24 comment Are undecidable consequences of Con recursively enumerable?This shouldn’t be an answer, but a comment. May24 comment Order type of the smallest set containing the identity function and closed under exponentiationWith tetration, it will be a well quasi-order per mathoverflow.net/questions/131596 . I seems very plausible that the order is also linear (hence a well order), though I don’t see an immediate simple argument. As for the order type, if I understand it correctly, the results from www1.maths.leeds.ac.uk/~rathjen/KRUSKAL.neu.pdf should imply that it is bounded by $\vartheta\Omega^\omega$ (whatever that means), but that’s probably an overkill. May23 comment Do operations generate well-ordered sets only?We will get comment editing as soon as we move to SE 2.0: meta.mathoverflow.net/discussion/1416/5/… May23 comment Do operations generate well-ordered sets only?I also found the exercise nonobvious, but the point is basically that the $g_i$ functions are $n^{\Theta(n^i)}$ so that they form an increasing chain, while $h(n)=n^{\Theta(n^n)}$ grows faster than any of them, which makes $\tau(g_i,h)=2h(n)^{h(n)}-g_i(n)$ a decreasing chain. May23 accepted Do operations generate well-ordered sets only? May23 comment Do operations generate well-ordered sets only?Yes, this was also pointed out by Joseph Van Name above. May23 revised Do operations generate well-ordered sets only?comment on well order May23 answered Do operations generate well-ordered sets only? May22 comment fixedpoint or fixed point or fixed-pointExcept that you should really do as you say and use a hyphen (fixed-point, U+002D, TeX: -), not a minus sign (fixed−point, U+2212, TeX: dollar-dollar). May20 answered Reference request: Minimal Axiomatizations of PA over (+,x,<=). May17 comment Could the Jacobian conjecture be undecidable?Yes, if it is undecidable in a half-decent theory, then it is true. Yes, you cannot prove in, say, ZFC that it is undecidable in ZFC, but then again, you cannot prove in ZFC that anything is undecidable in ZFC. However, it is conceivable that the undecidability of the conjecture in ZFC is provable by assuming some stronger hypothesis, such as the consistency of ZFC. May17 comment Verifying the correctness of a Sudoku solution Thanks, it was fun. May17 accepted Verifying the correctness of a Sudoku solution May17 revised Is there a contractible bounded homogeneous space?spelling May16 comment Cyclotomic fields@Tom: My comment concerned the first version of the question, where it was impossible to guess that the OP is actually talking about ideals. It looked like a plain identity between two numbers (which were actually distinct). May16 comment Cyclotomic fieldsFalse statements tend to be hard to prove. May16 answered Basic results with three or more hypotheses May13 revised Solve for $A$ and $B$ in $AXB=Y$fix markup May7 revised Verifying the correctness of a Sudoku solution Fix typos. Now I’m really going to stop, promise. May7 comment Verifying the correctness of a Sudoku solution I’m sorry for the number of edits. I’m going to stop here. May7 revised Verifying the correctness of a Sudoku solution this is the smallest axiomatization May7 revised Verifying the correctness of a Sudoku solution clarify the material on dependent sets May7 accepted Smallest base to reach partial recursive functions as a closure of unbound search May7 revised Verifying the correctness of a Sudoku solution expand May7 comment Smallest base to reach partial recursive functions as a closure of unbound searchKalmár elementary will certainly do, and so will polynomial time, or even uniform $\mathit{AC}^0$ (by a different argument). (Not that it would matter, but the formula for addition actually gives $1+0=2\cdot1\dot-((2\cdot1\dot-1)\dot-0)=2\dot-((2\dot-1)\dot-0)=2\dot-1=1$. The point of the expression is that $x+y=z-((z-x)-y)$, and if we take $z\ge x+y$, then one can replace $-$ with limited subtraction. Now, $S(x)S(y)=xy+x+y+1\ge x+y$.) May7 comment Zeros of polynomials in discretely ordered ringsYou don’t need Pell’s equation. You can prove that for every $b\le a-2$ there exist $y\ge x\ge0$ such that $p(a,x,y)=0$ satisfying the two congruences in Lemma 2 by a straightforward induction on $b$ (keeping $a$ fixed). The induction step follows from an inverse version of Lemma 1, whose conclusion reads $2ay\ge x+y$ and $p(a,y,2ay-x)=0$. May6 revised Verifying the correctness of a Sudoku solution more typos May6 revised Verifying the correctness of a Sudoku solution fix some typos