2
$\begingroup$

I am reading a paper and there is the following theorem:

Let $n$ be a fixed integer, and $n >1$.

Denote divisibility in $\mathbb{Z}[\frac{1}{n}]$ by $|_n$, thus for all $x, y \in \mathbb{Z}$ $$x |_n y \leftrightarrow \exists q, f \in \mathbb{Z}: y=xqn^{-f}$$ Then the positive existential theory of $(\mathbb{Z}; +, |_n)$ is undecidable, i.e. there is no algorithm to decide formulas of the form $$\exists x_1, \dots , x_m \in \mathbb{Z}: \land_{i=1}^s F_i (x_1, \dots , x_m) |_n G_i (x_1, \dots , x_m), $$ where $F_i$ and $G_i$ are polynomials over $\mathbb{Z}$ of degree one or less, and where $\land_{i=1}^s$ denotes a finite conjunction.

Why does the positive existential theory of $(\mathbb{Z}; +, |_n)$ contain formulas of the form $\exists x_1, \dots , x_m \in \mathbb{Z}: \land_{i=1}^s F_i (x_1, \dots , x_m) |_n G_i (x_1, \dots , x_m), $ ?

This formula does not contain $+$. Do we suppose that the polynomials $F_i$ and $G_i$ contain additions?

Also why are these polynomials of degree one or less?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Sep 2, 2015 at 17:39
  • $\begingroup$ 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 $\endgroup$
    – Mary Star
    Commented Sep 2, 2015 at 20:08
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Sep 2, 2015 at 21:29
  • $\begingroup$ 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? $\endgroup$
    – Emil Jeřábek
    Commented Sep 3, 2015 at 8:36
  • $\begingroup$ 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 $\endgroup$
    – Mary Star
    Commented Sep 6, 2015 at 20:26

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .