Emil Jeřábek
|
Registered User
|
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 progressions How 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) |
|
Jun 8 |
awarded | ● Necromancer |
|
Jun 5 |
comment |
Is there an RSS reader for mathematicians? I don’t care about RSS readers, but the bookmarklet is just awesome. |
|
Jun 4 |
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. |
|
Jun 4 |
revised |
Ontological status of some “sets” in ZFC fix markup |
|
Jun 4 |
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”. |
|
Jun 3 |
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. |
|
May 31 |
comment |
Deduction theorem This is the answer. I’m sorry I can only upvote it once. |
|
May 30 |
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. |
|
May 30 |
comment |
Boys and Girls Revisited I suppose you mean to wait until every family has a boy, and only then tell them to multiply forever? |
|
May 28 |
comment |
Order-independent properties arising naturally in mathematics The 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. |
|
May 28 |
revised |
Homomorphisms from powers of Z to Z fix name |
|
May 28 |
comment |
Fixed point theorems The 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$. |
|
May 28 |
awarded | ● Pundit |
|
May 26 |
awarded | ● Enlightened |
|
May 25 |
awarded | ● Nice Answer |
|
May 24 |
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. |
|
May 24 |
comment |
Are undecidable consequences of Con recursively enumerable? This shouldn’t be an answer, but a comment. |
|
May 24 |
comment |
Order type of the smallest set containing the identity function and closed under exponentiation With 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. |
|
May 23 |
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/… |
|
May 23 |
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. |
|
May 23 |
accepted | Do operations generate well-ordered sets only? |
|
May 23 |
comment |
Do operations generate well-ordered sets only? Yes, this was also pointed out by Joseph Van Name above. |
|
May 23 |
revised |
Do operations generate well-ordered sets only? comment on well order |
|
May 23 |
answered | Do operations generate well-ordered sets only? |
|
May 22 |
comment |
fixedpoint or fixed point or fixed-point Except 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). |
|
May 20 |
answered | Reference request: Minimal Axiomatizations of PA over (+,x,<=). |
|
May 17 |
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. |
|
May 17 |
comment |
Verifying the correctness of a Sudoku solution Thanks, it was fun. |
|
May 17 |
accepted | Verifying the correctness of a Sudoku solution |
|
May 17 |
revised |
Is there a contractible bounded homogeneous space? spelling |
|
May 16 |
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). |
|
May 16 |
comment |
Cyclotomic fields False statements tend to be hard to prove. |
|
May 16 |
answered | Basic results with three or more hypotheses |
|
May 13 |
revised |
Solve for $A$ and $B$ in $AXB=Y$ fix markup |
|
May 7 |
revised |
Verifying the correctness of a Sudoku solution Fix typos. Now I’m really going to stop, promise. |
|
May 7 |
comment |
Verifying the correctness of a Sudoku solution I’m sorry for the number of edits. I’m going to stop here. |
|
May 7 |
revised |
Verifying the correctness of a Sudoku solution this is the smallest axiomatization |
|
May 7 |
revised |
Verifying the correctness of a Sudoku solution clarify the material on dependent sets |
|
May 7 |
accepted | Smallest base to reach partial recursive functions as a closure of unbound search |
|
May 7 |
revised |
Verifying the correctness of a Sudoku solution expand |
|
May 7 |
comment |
Smallest base to reach partial recursive functions as a closure of unbound search Kalmá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$.) |
|
May 7 |
comment |
Zeros of polynomials in discretely ordered rings You 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$. |
|
May 6 |
revised |
Verifying the correctness of a Sudoku solution more typos |
|
May 6 |
revised |
Verifying the correctness of a Sudoku solution fix some typos |
