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


7h
comment Is there any way I can get a moderator removed for misconduct?
Right. The migration protocol is designed to work under the assumption that one community ships a post to a different community, which is violated in the case of migrations to meta.
8h
comment Equivalence of Graphical model selection algorithms
Please do not simultaneously cross-post at multiple SE sites, as you did here cstheory.stackexchange.com/questions/31208 . It fragments the discussion and leads to duplication of effort.
11h
comment Is there any way I can get a moderator removed for misconduct?
And now the question was closed on meta, causing the migration to be rejected. (* facepalm *)
19h
comment FPTAS for approximating the permanent of a matrix
Because you can pad the input matrix with diagonal entries to dimension, say, $m=n/\epsilon$ while preserving the permanent, and then $m^{-2}<\epsilon$.
2d
comment Notation for $\log \log \cdots \log n$?
@DavidZhang That was 5 1/2 years ago. The standards and expectations evolve.
Apr
14
revised Is every positive integer a sum of at most 4 distinct quarter-squares?
fix link
Apr
14
comment Is every positive integer a sum of at most 4 distinct quarter-squares?
That’s not a serious obstackle: math.stackexchange.com/questions/852567
Apr
14
comment Does the Brouwer fixed point theorem admit a constructive proof?
Concerning the last paragraph: the finitized version of the problem is PPAD-complete, hence one shouldn’t expect any algorithm significantly faster than brute-force search.
Apr
13
comment Does the Brouwer fixed point theorem admit a constructive proof?
@AsafKaragila: I was just joking or not Can you prove this constructively?
Apr
12
comment Can there be a non-trivial epimorphism (of rings) from a field?
I convinced myself that it should work without choice. One can construct $A\otimes_KA$ as the quotient of the space with basis $\{u\otimes v:u,v\in A\}$ over a subspace generated by $uk\otimes v-u\otimes kv$ and friends. If this subspace contained $i_1(a)-i_2(a)$, this would be witnessed by a finite linear combination involving only finitely many elements of $A$, hence it would already show up for a finite-dimensional subspace of $A$, where we can do the algebra as usual.
Apr
12
comment Can there be a non-trivial epimorphism (of rings) from a field?
Is it clear that without a basis of $A$ that the map $V\otimes_KV\to A\otimes_KA$ is injective, which you are implicitly using in the argument?
Apr
12
comment Rediscovery of lost mathematics
See also arxiv.org/abs/1504.01402 for a follow-up.
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
If you extend RR to classes, it only makes $\neg RR$ weaker. It says that there exists a class $A$ such that for every relation $R$, $(A,R)$ is not rigid. This does not in any way contradict the fact that there is a different class, namely $V$, which does carry a rigid relation. Yair’s answer says what it says: if it is consistent with NBG that there is a nontrivial elementary embedding $V\to V$, then the existence of such an elementary embedding is also consistent with there being a set that does not carry a rigid relation.
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
In particular, in the various comments above you keep claiming “Such a model would, by definition of $¬RR$, seemingly have to realize either (ii) or (iv)”, “such a model would seemingly have to satisfy (ii) or (iv)”, and “...which means that either (ii) or (iv) holds”. All these are non sequitur.
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
I don’t see what any of what you are saying has any bearing on the question you asked here. I read your other question about RR, and the answers, and no automorphisms of $V$ are mentioned anywhere. RR says that for every set $a$, there exists a relation $r$ such that $(a,r)$ is rigid. The impossibility of (ii) and (iv) says that $(V,\in)$ is rigid. There is no connection between the two. You seem to be confused about something basic.
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
Note that ZF proves that there are plenty of rigid binary relations on various sets, such as $(\alpha,<)$ for ordinals $\alpha$, or indeed $(t,\in)$ for any transitive set $t$. What it doesn’t prove that there are such relations on arbitrary base sets.
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
Oh, I found the definition. I fail to see the connection of RR to automorphisms of the universe, which is a proper class. In any case, the fact that (assuming foundation) the universe has no automorphisms is completely trivial: $j(x)=\{j(y):y\in x\}=\{y:y\in x\}=x$, where the first equality comes from $j$ being an automorphism, and the second equality is the $\in$-induction hypothesis.
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
What is RR, what is Joel and Palumbo’s model, and what is Theorem 5?
Apr
12
comment The patterns of possibility for nontrivial automorphisms and nontrivial elementary embeddings of the universe
Did you intentionally drop the superscript, so that you are requiring foundation? Then (ii) and (iv) are impossible, the straightforward proof by $\in$-induction that every automorphism is the identity does not need any choice. (i) is easy (e.g., take a symmetric extension violating choice of a model of V=L with no inaccessible cardinals), and (iii) is a restatement of the open problem whether the existence of Reinhardt cardinals is consistent.
Apr
11
comment convergence radius of Pochhammer symbol series
@IgorRivin: No, $2^{-z}$ is correct (for $\operatorname{Re}z<1$, where the series converges). This is immediate from Alexey Ustinov’s answer.