boumol
Reputation
749
Top tag
Next privilege 1,000 Rep.
Create tags
 Jun15 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. Jun14 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). Jun14 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). Jun14 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? Jun8 comment New mathematical results in fiction work What new ideas were firstly introduced in the book "Gödel, Escher, Bach"? Jun7 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. Jun7 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. Jun7 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. May27 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. May21 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"). May21 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). Apr29 comment Is there a sentence in the language of $\mathrm{PA}$ asserting that $\mathrm{PA}$ is sound? Can you tell us what is the sentence "Sou(PA)"? I can see how to write down a sentence which expresses "there is no (finite) proof ...", i.e., expresses "PA is consistent". On the other hand I do not see how to write down a sentence (in the Peano language) that expresses "there is a (infinite) first-order structure ...". This trouble would not appear if one wants to write a sentence in the ZFC language saying that "PA is sound", this can be clearly done. Apr22 comment mathematical logic and valid ways of reasoning @Lays: Godel's theorem says what it says, so if you cannot follow wikipedia link I am afraid you need to improve your background. I suggest you take a deep look at plato.stanford.edu/entries/logic-classical to digest what completeness is. This entry is addressed to philosophers, so I suspect it will be easier to understand. Apr22 comment mathematical logic and valid ways of reasoning @Lays: Have you read the section "Statement of the theorem" in the wikipedia link? Apr22 comment mathematical logic and valid ways of reasoning Take a look at en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem I suspect this is what you are interested on. It is worth saying that the completeness theorem fails in second-order logic. Apr16 comment What is the formal definition of a translation between theories? Take a look at Caicedo's answer in math.stackexchange.com/questions/315399/… Apr14 comment First Order Logic: Formula for $y$ is the sum of non-negative powers of $2$ @Food4Thought: I think you are not getting the point of Carl's remark. When you say "$\exists n (2^n = x)$", how do you pretend to write this formula (and so with a fixed number of symbols) just using the vocabulary $+,\cdot,0,s$ ? Is this a formula? Apr14 comment First Order Logic: Formula for $y$ is the sum of non-negative powers of $2$ It is well known that the exponential formula is first order definable in the (standard) natural numbers (with the language you have stated in the question), you can find this on any book about Peano arithmetic or Gödel incompletenes theorem. However, for your particular question you do not need this (at least if you are thinking in the standard model), because all natural numbers are the sum of non-negative powers of 2. Apr8 comment Decidability of a Turing machine always halting in at most ten steps @Alex: Using which input? [One has to realize that there are infinite inputs] Apr8 comment Decidability of a Turing machine always halting in at most ten steps @Fischer: You are completely right about my misinterpretation of Rice's Theorem. However, I still do not see how you want to deal with all inputs: cannot be the case that a particular Turing machine halts in 10 steps for all inputs of length smaller or equal than 10, while it does not halt in 10 steps for an input of larger length?