boumol
Reputation
773
Top tag
Next privilege 1,000 Rep.
Create new tags
 Jan 10 comment Why are mathematical proofs that rely on computers controversial? @DumpsterDoofus (and the upvoters): What is the statement you talk about? Jan 5 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". Dec 22 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/… 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 ) 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. 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 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 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 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). Jun 14 comment Decidability of the consistency for complete finitely axiomatized theories? Let me say that the problem in my remark is non computable (i.e., undecidable). This can be shown translating Hilbert's tenth problem (about the existential theory of natural numbers with addition and product) into your setting, because there is a mechanical way to translate a diophantine equation into a first-order formula (in the language with order,addition and product) expressing "it is a finite initial segment of the standard natural numbers of a fixed size and where there is a solution of the initial diophantine equation". Now I cannot can develop this into a full answer (maybe later). Jun 14 comment Decidability of the consistency for complete finitely axiomatized theories? Let me rephrase the question clarifying what I understand is the input and the output of the problem you are interested. INPUT: a first-order formula $\varphi$ such that it has at most (up to elementary equivalence) one model. OUTPUT: Yes/No depending whether the input formula has one or zero models. Thomas, is this reformalization the adequate one you are interested in? Jun 8 comment New mathematical results in fiction work What new ideas were firstly introduced in the book "Gödel, Escher, Bach"? Jun 7 comment Second Order Logic: Existential could be expressed as a universal quantifier. I suggest you delete your last comments and add them at the end of your question as an addendum (just edit your question). This will help people to more easily understand your problem. Jun 7 comment Second Order Logic: Existential could be expressed as a universal quantifier. On the other hand, it is obvious that universal and existential quantifiers are interdefinable using negation. Since "negation" coincides with "implies a contradiction" I would suspect you could make sense of your ideas using instead of the variable "Y" any formula that is a contradiction formula. Jun 7 comment Second Order Logic: Existential could be expressed as a universal quantifier. What you have written makes no sense to me. You can only write in a formula something like $\forall Y$ in case that $Y$ is a (first-order or second-order) variable, but then $B \to Y$ is not a formula. In other words, the expression $\forall Y.( \forall X. B \to Y) \to Y$ is not a formula, even assuming $B$ is a formula. May 27 comment Gödel's incompleteness wrt weakend versions of ZFC Let me say that the answer to your question is a trivial "No". It is trivial because if a system is non-complete and you take a weaker system (like for example one obtained deleting axioms of the initial system) then the weaker system is also non-complete. Another issue is what happens when one replaces an axiom with alternative ones (like replacing "Infinity Axiom" with "The negation of Infinity Axiom"). This is in general non trivial, and this is what other peopople has addressed in the answers to your question. May 21 comment What do linearly ordered abelian groups look like? Mi mistake for not reading the details. I answered just using the information in the title ("linearly ordered abelian groups"). May 21 comment What do linearly ordered abelian groups look like? With the term "copy" you mean a "subgroup" or a "isomorphic copy"? In the first case the answer is yes (by Hahn's embedding theorem) and in the second case the answer is no (a trivial counterexample is the rationals).