![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
The link target for 'identity' in the first sentence under 'Axioms' points to Identity (mathematics) that doesn't really cover identity in the sense of 'first order logic with identity' (versus without identity). I think we either need to add a section to that article, or retarget this link to a more relevant location (possibly a new as-yet unwritten article?) Does anyone more familiar than I know of a more appropriate place? Zero sharp ( talk) 05:37, 4 April 2008 (UTC)
The article states that Q with any of the axioms removed is not essentially undecidable (any extension in the same language is also undecidable), this is quite true, but then goes on to state that some of its subtheories obtained by removing some of the states axioms are decidable - in particular, that one such subtheory is equivalent to Presburger arithmetic and so is decidable. This is simply incorrect, since any finitely axiomatizable, essentially undecidable theory is also hereditarily undecidable (any subtheory in the same language is also undecidable). The languages of Q and Presburger arithmetic are different (Presburger arithmetic doesn't have multiplication), so I don't think it makes sense to talk about them in this way. Should this be removed? (This is my first time doing this sort of thing, so I feel a little uneasy about altering things myself.) Jimbobbibliobus ( talk) 21:13, 31 August 2008 (UTC)
There is an issue in the given interpretation of +. Specifically, since * is not associative in some models of Q, the parentheses should be included, or there it should be verified that they are irrelevant in this case. Thank you. Hitorikii ( talk) 05:13, 2 December 2008 (UTC)
I changed a sentence saying something like "Q, like the Peano axioms, has non-standard models of all infinite cardinalities" to say Peano arithmetic instead of Peano axioms. I usually think of "Peano axioms" as meaning the 19th century version which has a single induction axiom in full second-order logic, and which has no nonstandard models, while "Peano arithmetic" is the first-order axiomitization an infinite schema of induction axioms. I hope this change was appropriate -- please feel free to comment, I'm not any kind of expert. 66.127.55.192 ( talk) 20:30, 18 January 2010 (UTC)
I noticed that Robinson arithmetic was the subject of some edits on the article. I was interested in that subject earlier this year, and when I looked into it this is what I found:
Regarding this edit [1], I have a slight quibble. The usual statement of the second incompleteness theorem includes as a hypothesis that the theory is able to prove the Hilbert–Bernays conditions (so "contains enough arithmetic" in the statement of the 2nd theorem is a stronger assumption than "contains enough arithmetic" in the statement of the 1st theorem). Therefore, as it is usually stated, the second incompleteness theorem does not apply to Q, because Q doesn't meet the hypotheses of the theorem. In my opinion the paragraph in the article beginning "Gödel's theorems only apply to axiomatic systems defining sufficient arithmetic to carry out the coding constructions " doesn't clearly distinguish between the hypotheses of the first and second theorems. I will try to edit the article to take this into account. — Carl ( CBM · talk) 15:10, 2 December 2010 (UTC)
I am concerned about this subsection. Ignoring the fact that the link to
Skolem arithmetic seems to go to an unintended target, I do not see how it is relevant to Robinson's arithmetic. The given definition of + in terms of S and · relies on basic properties like commutativity and associativity of + and ·, distributivity, and most importantly, cancelativity of + and ·. None of these are provable in Robinson's arithmetic. I'm fairly certain that + is not definable in terms of S and · in Q.—
Emil
J.
17:48, 2 December 2010 (UTC)
In the clause "even if we additionally restrict Gödel numbers of proofs to a definable cut" what does "definable cut" mean? — Preceding unsigned comment added by 213.122.49.134 ( talk) 21:52, 7 June 2012 (UTC)
The author wrote: "... when any one of the seven axioms above is dropped. These fragments of Q ... have ... uninteresting models (i.e., models which do not extend the standard natural numbers)".
How can it be true? Let us drop the axiom (3). However, every term in form of "1+ ... +1" represents a natural number, and it's provable, that different such terms are not equal. That is, all standard natural numbers are contained in any given model of the theory, aren't they?
Eugepros ( talk) 09:13, 6 July 2012 (UTC)
Thank you, Emil, I understand. And one more: Could you say something about what the axiom (3) is necessary for? If I understand it right, the axiom (3) is a "weaker" replacement of induction scheme. But it doesn't make possible inductive inference. It excludes such models as nonnegative reals, but in my opinion such models are not worse than models with nonstandard numbers. Perhaps, not all computable functions are representable in the theory without the axiom (3), unlike Q? Is there an example of computable function, which is not representable in such theory?
Eugepros ( talk) 06:24, 9 July 2012 (UTC)
Emil, maybe I'm going beyond the scope of the article, but it's interesting subject to be noted somewhere: If I'm not mistaken, the existence of decidable extention of the theory means inapplicability of the 1st Goedel's incompleteness theorem to the theory, doesn't it? And it's interesting where exactly Goedel's proof fails: To implement Goedel's numbering and formula of provability we should express factorization by formula of arithmetic. And it's very strange why this expression doesn't work without the axiom (3).
Eugepros ( talk) 09:26, 10 July 2012 (UTC)
I understand! Without the axiom (3) we cannot prove, that prime numbers exist: So, the number 3 has dividers other than 1 and 3 - for example, 2 and 1.5 (in the model of nonnegative reals). Am I right?
Eugepros ( talk) 09:46, 10 July 2012 (UTC)
There is an ambiguity concerning the notion of weakness at the beginning of the article. An opening sentence reads, "Since Q is weaker than PA, it is incomplete." However, the article on Presberger arithmetic states, "Presburger arithmetic is much weaker than Peano arithmetic, which includes both addition and multiplication operations. Unlike Peano arithmetic, Presburger arithmetic is a decidable theory." That article goes on to state that Presberger arithmetic is "... complete: For each statement in Presburger arithmetic, either it is possible to deduce it from the axioms or it is possible to deduce its negation." It is true that the languages of these theories differ. My point is that the precise sense of 'weaker' intended here should be stated at the beginning of this article. FLengye| ( ta|k) 23:48, 6 February 2013 (UTC)
I see that the question of weakness is the subject of edit reversions. The opening sentences of this article may not provide sufficient context for the statement in question, as the notion of a fragment of first-order arithmetic is not defined within Wikipedia. Buss defines a fragment of first-order arithmetic as an axiomatizable subtheory of first-order arithmetic in his chapter of the Proof Theory of Arithmetic. This definition might exclude the possibility that the subtheory contains no formula in which the multiplication symbol occurs. Some authors define a fragment of a theory to be a "syntactically restricted subset of formulae of the theory." In this sense, both Robinson's arithmetic and Presberger's arithmetic are fragments of Peano Arithmetic. This may not be what experts in the proof theory of arithmetic intend; nevertheless, there are references in the literature to both decidable and undecidable fragments of undecidable theories. The Wikipedia article on First-Order Logic contains examples of fragments in which the language is restricted: "For instance, first-order logic is undecidable, meaning a sound, complete and terminating decision algorithm is impossible. This has led to the study of interesting decidable fragments such as C2, first-order logic with two variables and the counting quantifiers and (these quantifiers are, respectively, "there exists at least n" and "there exists at most n") (Horrocks 2010)." FLengye| ( ta|k) 00:56, 7 February 2013 (UTC) FLeℵgyel ( ta|k) 20:57, 4 June 2013 (UTC)
There is more than one reference to Mendelson's textbook, but that deals with a theory stronger than Q (though still weaker than PA). 86.132.221.167 ( talk) 15:59, 21 November 2017 (UTC)
But with this statement it is proveble, two symbols are not one symbol just as x is not on the position of y....... Jonaw2024 ( talk) 19:02, 5 June 2023 (UTC)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
The link target for 'identity' in the first sentence under 'Axioms' points to Identity (mathematics) that doesn't really cover identity in the sense of 'first order logic with identity' (versus without identity). I think we either need to add a section to that article, or retarget this link to a more relevant location (possibly a new as-yet unwritten article?) Does anyone more familiar than I know of a more appropriate place? Zero sharp ( talk) 05:37, 4 April 2008 (UTC)
The article states that Q with any of the axioms removed is not essentially undecidable (any extension in the same language is also undecidable), this is quite true, but then goes on to state that some of its subtheories obtained by removing some of the states axioms are decidable - in particular, that one such subtheory is equivalent to Presburger arithmetic and so is decidable. This is simply incorrect, since any finitely axiomatizable, essentially undecidable theory is also hereditarily undecidable (any subtheory in the same language is also undecidable). The languages of Q and Presburger arithmetic are different (Presburger arithmetic doesn't have multiplication), so I don't think it makes sense to talk about them in this way. Should this be removed? (This is my first time doing this sort of thing, so I feel a little uneasy about altering things myself.) Jimbobbibliobus ( talk) 21:13, 31 August 2008 (UTC)
There is an issue in the given interpretation of +. Specifically, since * is not associative in some models of Q, the parentheses should be included, or there it should be verified that they are irrelevant in this case. Thank you. Hitorikii ( talk) 05:13, 2 December 2008 (UTC)
I changed a sentence saying something like "Q, like the Peano axioms, has non-standard models of all infinite cardinalities" to say Peano arithmetic instead of Peano axioms. I usually think of "Peano axioms" as meaning the 19th century version which has a single induction axiom in full second-order logic, and which has no nonstandard models, while "Peano arithmetic" is the first-order axiomitization an infinite schema of induction axioms. I hope this change was appropriate -- please feel free to comment, I'm not any kind of expert. 66.127.55.192 ( talk) 20:30, 18 January 2010 (UTC)
I noticed that Robinson arithmetic was the subject of some edits on the article. I was interested in that subject earlier this year, and when I looked into it this is what I found:
Regarding this edit [1], I have a slight quibble. The usual statement of the second incompleteness theorem includes as a hypothesis that the theory is able to prove the Hilbert–Bernays conditions (so "contains enough arithmetic" in the statement of the 2nd theorem is a stronger assumption than "contains enough arithmetic" in the statement of the 1st theorem). Therefore, as it is usually stated, the second incompleteness theorem does not apply to Q, because Q doesn't meet the hypotheses of the theorem. In my opinion the paragraph in the article beginning "Gödel's theorems only apply to axiomatic systems defining sufficient arithmetic to carry out the coding constructions " doesn't clearly distinguish between the hypotheses of the first and second theorems. I will try to edit the article to take this into account. — Carl ( CBM · talk) 15:10, 2 December 2010 (UTC)
I am concerned about this subsection. Ignoring the fact that the link to
Skolem arithmetic seems to go to an unintended target, I do not see how it is relevant to Robinson's arithmetic. The given definition of + in terms of S and · relies on basic properties like commutativity and associativity of + and ·, distributivity, and most importantly, cancelativity of + and ·. None of these are provable in Robinson's arithmetic. I'm fairly certain that + is not definable in terms of S and · in Q.—
Emil
J.
17:48, 2 December 2010 (UTC)
In the clause "even if we additionally restrict Gödel numbers of proofs to a definable cut" what does "definable cut" mean? — Preceding unsigned comment added by 213.122.49.134 ( talk) 21:52, 7 June 2012 (UTC)
The author wrote: "... when any one of the seven axioms above is dropped. These fragments of Q ... have ... uninteresting models (i.e., models which do not extend the standard natural numbers)".
How can it be true? Let us drop the axiom (3). However, every term in form of "1+ ... +1" represents a natural number, and it's provable, that different such terms are not equal. That is, all standard natural numbers are contained in any given model of the theory, aren't they?
Eugepros ( talk) 09:13, 6 July 2012 (UTC)
Thank you, Emil, I understand. And one more: Could you say something about what the axiom (3) is necessary for? If I understand it right, the axiom (3) is a "weaker" replacement of induction scheme. But it doesn't make possible inductive inference. It excludes such models as nonnegative reals, but in my opinion such models are not worse than models with nonstandard numbers. Perhaps, not all computable functions are representable in the theory without the axiom (3), unlike Q? Is there an example of computable function, which is not representable in such theory?
Eugepros ( talk) 06:24, 9 July 2012 (UTC)
Emil, maybe I'm going beyond the scope of the article, but it's interesting subject to be noted somewhere: If I'm not mistaken, the existence of decidable extention of the theory means inapplicability of the 1st Goedel's incompleteness theorem to the theory, doesn't it? And it's interesting where exactly Goedel's proof fails: To implement Goedel's numbering and formula of provability we should express factorization by formula of arithmetic. And it's very strange why this expression doesn't work without the axiom (3).
Eugepros ( talk) 09:26, 10 July 2012 (UTC)
I understand! Without the axiom (3) we cannot prove, that prime numbers exist: So, the number 3 has dividers other than 1 and 3 - for example, 2 and 1.5 (in the model of nonnegative reals). Am I right?
Eugepros ( talk) 09:46, 10 July 2012 (UTC)
There is an ambiguity concerning the notion of weakness at the beginning of the article. An opening sentence reads, "Since Q is weaker than PA, it is incomplete." However, the article on Presberger arithmetic states, "Presburger arithmetic is much weaker than Peano arithmetic, which includes both addition and multiplication operations. Unlike Peano arithmetic, Presburger arithmetic is a decidable theory." That article goes on to state that Presberger arithmetic is "... complete: For each statement in Presburger arithmetic, either it is possible to deduce it from the axioms or it is possible to deduce its negation." It is true that the languages of these theories differ. My point is that the precise sense of 'weaker' intended here should be stated at the beginning of this article. FLengye| ( ta|k) 23:48, 6 February 2013 (UTC)
I see that the question of weakness is the subject of edit reversions. The opening sentences of this article may not provide sufficient context for the statement in question, as the notion of a fragment of first-order arithmetic is not defined within Wikipedia. Buss defines a fragment of first-order arithmetic as an axiomatizable subtheory of first-order arithmetic in his chapter of the Proof Theory of Arithmetic. This definition might exclude the possibility that the subtheory contains no formula in which the multiplication symbol occurs. Some authors define a fragment of a theory to be a "syntactically restricted subset of formulae of the theory." In this sense, both Robinson's arithmetic and Presberger's arithmetic are fragments of Peano Arithmetic. This may not be what experts in the proof theory of arithmetic intend; nevertheless, there are references in the literature to both decidable and undecidable fragments of undecidable theories. The Wikipedia article on First-Order Logic contains examples of fragments in which the language is restricted: "For instance, first-order logic is undecidable, meaning a sound, complete and terminating decision algorithm is impossible. This has led to the study of interesting decidable fragments such as C2, first-order logic with two variables and the counting quantifiers and (these quantifiers are, respectively, "there exists at least n" and "there exists at most n") (Horrocks 2010)." FLengye| ( ta|k) 00:56, 7 February 2013 (UTC) FLeℵgyel ( ta|k) 20:57, 4 June 2013 (UTC)
There is more than one reference to Mendelson's textbook, but that deals with a theory stronger than Q (though still weaker than PA). 86.132.221.167 ( talk) 15:59, 21 November 2017 (UTC)
But with this statement it is proveble, two symbols are not one symbol just as x is not on the position of y....... Jonaw2024 ( talk) 19:02, 5 June 2023 (UTC)