# boumol

 Nov 10 answered Books about Turing machines and undecidability Oct 28 comment Why does undecidability of arithmetic not follow from that of first-order logic?Indeed, it is also well known that these two sets (arithmetic truths versus firs-order validities) have different Turing (undecidability) degrees. In particular, there is no computable reduction reducing "arithemtic truths" to "first-order validities". If you want to take a deeper look at this I suggest you start looking at the artihmetical hierarchy (for instance, at wikipedia en.wikipedia.org/wiki/Arithmetical_hierarchy ) Sep 17 awarded Supporter Sep 16 comment Can Tarski decide constructibility in elementary geometry?I think that the decidability (i.e., computability) of the elementary (i.e., first-order) theory of this field structure (constructible numbers) is still open. Take a look at michaelbeeson.com/research/talks/EdinburghSlides.pdf (e.g., page 13) Aug 27 comment Does ZFC pin down precisely which theorems PA can and cannot prove?This comment develops (just a bit) Carl's comment. It is easy to prove from the assumption that "for all sentences $\phi$ in the language of PA, it holds that either $ZFC \vdash (PA \vdash \phi)$ or $ZFC \vdash (PA \not \vdash \phi)$" (together with assuming that $ZFC$ is consistent) that there is an algorithm to compute "provability in PA". The algorithm is the trivial one you expect (use provability in ZFC until you find the proof that shows ...). Using the well-known fact that PA is non-computable one concludes that the answer to your question is NO. Aug 26 comment Countability of the rationals: a pictorial diagramThanks, it works great. Aug 26 comment Countability of the rationals: a pictorial diagramIs there any option in the "matrix" command that allows to draw circles around the nodes? Aug 1 comment Editing e-mails in your browser using (g)vimDoes it work with gmail? It does not work to me. Jul 30 comment Editing e-mails in your browser using (g)vim@Ken: I am using the old style in gmail. Jul 30 comment Editing e-mails in your browser using (g)vim@Kent: Unfortunaley it does not work with gmail. Jul 30 asked Editing e-mails in your browser using (g)vim Jul 22 comment Illustrative examples of a phenomenon in the logic of mathematical induction@Doug: Humans in general do not write the external parenthesis (although in a syntactic way they are there). So please do not be so formal: do you seriously think that mathematicians should never write $3+2$ and start writing $(3+2)$? Jul 22 comment Illustrative examples of a phenomenon in the logic of mathematical inductionThis is the old Polish style of writing logic that for obvious reasons is not considered today. In this setting $C$ refers to the material implication. To illustrate it with some examples, 1) $Cpq$ is what we nowadays write as $p \to q$, 2) $CpCqp$ is what we write as $p \to (q \to p)$, 3) $CsCrCpCqp$ is what we write as $s \to ( r \to (p \to (q \to p)))$, etc Jul 22 answered Illustrative examples of a phenomenon in the logic of mathematical induction Jun 15 comment Decidability of the consistency for complete finitely axiomatized theories?Let me note that by completeness theorem of first-order logic it is equivalent for every sentence (using conjunction this allows to consider finite sets of sentences) the statements: 1) the sentence generates a complete theory in the sense of your question (i.e., you can prove ...), 2) the sentence has at most (up to elementary equivalence) one model. Jun 14 comment Is meta-undecidability possible?@Yuval: This result of Shelah only proves that the statement I wrote in my remark is consistent with ZFC, but not that it is independent in ZFC. Indeed, it is better (to avoid problems) to read Shelah's result as "the monadic theory of order is non computable (under CH)". As far as I know it is still open whether it is independent in ZFC (i.e., undecidable in ZFC). Jun 14 awarded Supporter Jun 14 comment Is meta-undecidability possible?I suspect Trylks is using the same word with two different meanings, one about "computability" and the other about "independence in some formal system". Thus, "decidability is undecidable" can be read as "the computability of some particular decision problem is independent in ZFC (Zermelo-Fraenkel with Choice)". Trylks, is my interpretation the one you did? Jun 14 comment Is meta-undecidability possible?Let us consider the statement "the monadic (second-order) theory of all linear orders is computable". There are reasons to belive (but I am not sure that independency has been proved) that this statement is independent (i.e., undecidable) in ZFC. More details about the reasons can be found in books.google.es/books?id=y3YpdW-sbFsC&pg=PA397 Jun 14 comment Decidability of the consistency for complete finitely axiomatized theories?I am afraid that the question has the common ambiguity of the word "decidable": in some contexts it refers to "computable", and in some others it refers to "provable in some particular logical system". Peter refers here to second meaning, but it is not clear to me what is the meaning in the original question (I bet for the computability one).