boumol
Reputation
744
Top tag
Next privilege 1,000 Rep.
Create tags
 Mar28 comment How to explain the power of PA to non-logicians This essentially means that all $\Sigma_1$-setences that are true in the standard model are provable in PA. This result can be find in most of logic books dealing with PA (and Robinson's Q). In particular, you can take a look at the notes by Peter Smith logicmatters.net/igt/godel-without-tears (in the current version is Theorem 17 in Episode 5, page 40) Mar28 comment How to explain the power of PA to non-logicians Do you consider the fact that "PA (indeed Robinson Q is enough) is $\Sigma_1$-complete" strong enough? Mar27 comment Mathematical intro to Turing machines One example is the following "classic" written by Martin Davis amazon.com/Computability-Unsolvability-Prof-Martin-Davis/dp/… Mar19 comment Show that a recursively inseparable pair of recursively enumerable sets exists Yes, there is a standard proof (for two sets whose definiton only involves Turing machines). One place where you can find this is in Theorem 3.3.5 of the wonderful notes "Syllabus Computability Theory" written by Sebastiaan A. Terwijn math.ru.nl/~terwijn/teaching.html After you know these two sets are inseparable you can easily prove the inseparability of sets with a "logic" flavour (like in Biderman answer) Mar18 comment Books (and supporting material) that are useful in deconstructing one's intuition? @Sabysachi: torus solution? Mar15 comment Book on the first-order modal logic @user132181: The standard translation only works for propositional modal logic (and it translates these formulas into first-order, non-modal, formulas). Thus, right now I am afraid that your question does not make sense: could you clarify your question? Mar13 comment When is a Decidable Set Decidable? I suspect Russell is confusing two different uses of the term "undecidable". We have "undecidability in a formal theory" which applies to a sentence and refers to its unprovability. And then we also have "undecidability in a computability setting" which applies to a family (set) of finite objects and refers to the fact that this set cannot be computed by a Turing machine. For this second use there are some people which have advocated for using the word "uncomputable" instead of "undecidable", in order to avoid these misunderstandings. Feb15 comment Complexity of Recursively Inseparable Sets @Easterly: What do you mean here with the word "Complexity"? Jan31 answered Famous Math Texts in Spanish? Jan20 answered List naturals in ascending product order Jan10 awarded Yearling Jan10 comment Why are mathematical proofs that rely on computers controversial? @DumpsterDoofus (and the upvoters): What is the statement you talk about? Jan5 comment Determining if a theory in first-order logic is decidable @Sid: Use the "informal proof" given by André. In the proof it is crucial that you know that your theory is complete. Indeed, for complete theories (but not in general) it is known that "decidable" coincides with "recursively axiomatizable". Dec22 comment Good textbook on geometries And the recent "trilogy" by Borceux. I think up to now only the first two volumes have been published: amazon.com/An-Axiomatic-Approach-Geometry-Geometric/dp/… amazon.com/An-Algebraic-Approach-Geometry-Geometric/dp/… Nov10 answered Books about Turing machines and undecidability Oct28 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 ) Aug27 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. Jul22 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)$? Jul22 comment Illustrative examples of a phenomenon in the logic of mathematical induction This 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 Jul22 answered Illustrative examples of a phenomenon in the logic of mathematical induction