Timeline for A question regarding a fragment of Robinson Arithmetic
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Dec 16, 2015 at 1:08 | vote | accept | Thomas Benjamin | ||
| Dec 15, 2015 at 21:25 | comment | added | Thomas Benjamin | Also, whatever happened to rules of substitution in logic where variables can be substituted for other variables? In $\forall$x $\forall$y $\exists$z $\exists$w(x$\frown$y=z$\frown$w) is there some reason one cannot substitute 'y' for 'z' and 'x' for 'w' (since you took "$x$ for $z$ and $y$ for $w$)? In the case of ||||| (since x,y,z,and w take such strings as values), why can't x=|, y=||||, z=|||, and w=||? Certainly those values satisfy my original axiom-- would my original axiom be deemed a tautology then? | |
| Dec 15, 2015 at 19:36 | comment | added | Thomas Benjamin | (cont.) 'proper' first-order way to express this fact as an axiom. Thanks in advance. | |
| Dec 15, 2015 at 19:23 | comment | added | Thomas Benjamin | @EmilJeřábek: My interest is in models where '$+$' is interpreted as concatenation. Here is what I am attempting to do: consider an arbitrary string of |' s, say, |||||. It , through concatenation, can be expressed several different ways (e.g. |$\frown$||||, ||||$\frown$|, |||$\frown$||, etc.). If one allows for '0' to be interpreted as the empty string '$\epsilon$', it seems to me that $\epsilon$$\frown$| = |$\frown$$\epsilon$ (if one deems $\epsilon$$\frown$| to be meaningless one could always add this as an axiom--is this your point?). In any case let me know if there is a | |
| Dec 15, 2015 at 11:37 | comment | added | Emil Jeřábek | Oh, and if you meant $\forall x,y\,\exists z,w\,(x+z=w+y)$, that still doesn't imply commutativity or $0+x=x$. For instance, if $M$ is any model of (1)-(5) (e.g., violating $0+x=x$), let $M'$ be a model with domain $M\cup\{\infty\}$, where $a+\infty=\infty+a=\infty$ for all elements $a$, and $S(\infty)=\infty$. Then $M'$ is a model of (1)-(5) and of your extra axiom. The axiom also holds in the model in my linked answer. | |
| Dec 15, 2015 at 10:39 | comment | added | Emil Jeřábek | ??? That axiom is a tautology (take $x$ for $z$ and $y$ for $w$). | |
| Dec 15, 2015 at 2:04 | comment | added | Thomas Benjamin | @EmilJeřábek: If you would interpret '$+$' as '$\frown$' and add to the fragment of Robinson arithmetic under consideration the following axiom $\forall$x $\forall$y $\exists$z $\exists$w (x+y=z+w), the resulting theory would prove commutativity and $\forall$x (0+x=x). | |
| Dec 14, 2015 at 17:28 | comment | added | Emil Jeřábek | Oh, of course: the theory does not prove $\forall x\,(0+x=x)$, because full Robinson arithmetic does not. | |
| Dec 14, 2015 at 17:17 | comment | added | Emil Jeřábek | I also sense there is some confusion going on, since the question uses the word “undecidable” in two different senses, almost adjacent to each other. So let me stress that the linked question concerned the algorithmic undecidability of the Robinson arithmetic without multiplication, not its incompleteness (which should be obvious, as the theory does not include the Presburger division axioms such as the one mentioned by SJR). | |
| Dec 14, 2015 at 17:10 | comment | added | Emil Jeřábek | As I mentioned in a comment to the linked answer, $\forall x,y\,(x+y=y+x)$ works as an example. The model in my answer does not even satisfy $\forall x\,(x+1=1+x)$ (that is, $\forall x\,(S(0)+x=S(x))$.) Even simpler, I see no reason the theory should prove $\forall x\,(0+x=x)$, though this would require a different model. | |
| Dec 14, 2015 at 15:00 | answer | added | Fan Zheng | timeline score: 1 | |
| Dec 14, 2015 at 14:08 | comment | added | Joel David Hamkins | I added a link to the previous question. Also, @SJR, why not post your comment as an answer? | |
| Dec 14, 2015 at 14:07 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Added link to question
|
| Dec 14, 2015 at 13:24 | comment | added | Sidney Raffer | In your language you can say that every element is even or odd. This is true in the non-negative integers under addition but false for the set of polynomials with non-negative leading coefficients (under addition, with successor defined in the obvious way.) | |
| Dec 14, 2015 at 12:50 | review | Close votes | |||
| Dec 15, 2015 at 5:19 | |||||
| Dec 14, 2015 at 9:38 | history | asked | Thomas Benjamin | CC BY-SA 3.0 |