Timeline for Positive existential theory of $(\mathbb{Z}; +, |_n)$
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 8, 2015 at 0:29 | comment | added | Gerhard Paseman | These comments of yours (and the question) are better suited for math.stackexchange.com. It has been decades since I looked at an undergraduate text in logic. I used Enderton in a previous millenium, and I understand some other books have come out since then. You might do a web search on books that contain the phrase "positive existential" in books with the title including "logic" or "metamathematics" to find something newer. Also, there are web resources available. Gerhard "Why Choose This Particular Paper?" Paseman, 2015.09.07 | |
| Sep 7, 2015 at 22:59 | comment | added | Mary Star | And I would be thankful if you would tell me also a book about existential and positive existential formulas/theory. @GerhardPaseman | |
| Sep 7, 2015 at 19:55 | comment | added | Mary Star | Could you tell me a good book or a link where I can find the definition of a language, the terms, the formulas, etc ? @GerhardPaseman | |
| Sep 6, 2015 at 23:04 | comment | added | Gerhard Paseman | The issue is a little more complicated: we don't know if * (multiplication) can be defined from the given theory. However, even without that, if the theory containing just the degree one polynomials is not decidable, there is not hope for the full existential theory to be decidable either. I recommend reposting this with links on math.stackexchange and reviewing what terms and what formulas are for this theory. Let them know what your background is, so that a good answer can be given. Gerhard "Practice On Some Other Theories" Paseman, 2015.09.06 | |
| Sep 6, 2015 at 20:26 | comment | added | Mary Star | Since the language doen't contain the binary operation $\cdot $ the polynomial $F(x, y, z)$ cannot be of the form $x \cdot x=x^2$, right? And that's why the polynomials $F_i$ and $G_i$ are of degree one or less. Is this correct? @GerhardPaseman | |
| Sep 3, 2015 at 8:36 | comment | added | Emil Jeřábek | What is your background? If you are unfamiliar with syntactical manipulations in first-order logic, why don't you just take the given form as an ad hoc definition of the positive existential theory in this case? | |
| Sep 2, 2015 at 21:29 | comment | added | Gerhard Paseman | You need to understand what terms are and what formulas are for this language, and what axioms are present so that certain things which are not present in the language (like a symbol for the constant 1) can be definitionally equivalent. I think F(x,y,z) could be a term like (x+(y+(x+(z+x)))), which would be like a multivariable polynomial of degree 1. If you are having a challenge with this, you might try math.stackexchange.com. I could see undergraduates near the beginning of a logic course answering this. Gerhard "Unsure What Else To Say" Paseman, 2015.09.02 | |
| Sep 2, 2015 at 20:08 | comment | added | Mary Star | So, since $F_i$ and $G_i$ contain $+$ we don't have to write it in the formula, right? I haven't really understood the part with the degree... Could you explain to me further? @GerhardPaseman | |
| Sep 2, 2015 at 17:39 | comment | added | Gerhard Paseman | The F_i and G_i are likely functional terms in the language, and so may contain +. They are degree one multivariate polynomials most likely because they are easily expressed in this language. (There may be a term-equivalent definition of a multiplication relation that works for this structure, but I am not seeing it. Thus they are "adding" variables together, not "multiplying" them.) Gerhard "Try Building Some For Yourself" Paseman, 2015.09.02 | |
| Sep 2, 2015 at 17:09 | review | First posts | |||
| Sep 2, 2015 at 17:27 | |||||
| Sep 2, 2015 at 17:09 | history | asked | Mary Star | CC BY-SA 3.0 |