A New Proof of a Theorem by Ginsburg and Spanier

Marcus Kracht

Department of Linguistics

UCLA 405 Hilgard Avenue

PO Box 951543

Los Angeles

CA 90095-1543

December 18, 2002

Abstract In [2], Ginsburg and Spanier showed that the semilinear subsets of ${\mathrm{ℕ}}^{n}$ are exactly the sets that are definable in Presburger Arithmetic. The proof relied on two results shown in [1]: (1) that linear equations define semilinear sets, and (2) that the complement of a semilinear set is and the intersection of semilinear sets is again semilinear. Here we offer a much simpler proof of this fact. Basically, using quantifier elimination for Presburger Arithmetic we avoid having to show closure under negation. Instead, this will now follow from the results. Second, closure under intersection will be shown using standard techniques from linear algebra.

# 1  Preliminaries

Let ${\mathrm{ℕ}}^{n}$ be the set of $n$–tuples of natural numbers. A tuple is denoted by an arrow, eg $\stackrel{\to }{v}$, whose coordinates are ${v}^{i}$, $i. Put $\stackrel{\to }{0}≔〈0,0,\dots ,0〉$. Define $\stackrel{\to }{v}+\stackrel{\to }{w}$ by

 $\left(\stackrel{\to }{v}+\stackrel{\to }{w}\right)\left(i\right)=\stackrel{\to }{v}\left(i\right)+\stackrel{\to }{w}\left(i\right)$ (1.1)

Denote the structure $⟨{\mathrm{ℕ}}^{n},\overline{0},+⟩$ also by ${\mathrm{ℕ}}^{n}$. The unit vector which is $0$ except at place number $i$. where it is $1$, is denoted by $\stackrel{\to }{{e}_{i}}$. We define $n\stackrel{\to }{v}$ inductively as follows. $0\stackrel{\to }{v}≔\overline{0}$, $\left(n+1\right)\stackrel{\to }{v}≔n\stackrel{\to }{v}+\stackrel{\to }{v}$. We write $\mathrm{ℕ}\stackrel{\to }{v}$ for the set $\left\{n\stackrel{\to }{v}:\phantom{\rule{mediummathspace}{0.2em}}n\in \mathrm{ℕ}\right\}$ and $V+W≔\left\{\stackrel{\to }{v}+\stackrel{\to }{w}:\stackrel{\to }{v}\in V,\phantom{\rule{mediummathspace}{0.2em}}\stackrel{\to }{w}\in W\right\}$. A nonempty subset of ${\mathrm{ℕ}}^{n}$ is called linear if it can be written as

 ${\stackrel{\to }{v}}_{0}+\mathrm{ℕ}{\stackrel{\to }{v}}_{1}+\mathrm{ℕ}{\stackrel{\to }{v}}_{2}+\cdots +\mathrm{ℕ}{\stackrel{\to }{v}}_{m}$ (1.2)

for some $m$ (which may be zero, in which case we get the singleton $\left\{{\stackrel{\to }{v}}_{0}\right\}$). Likewise, a subset of ${\mathrm{ℤ}}^{n}\left({\mathrm{ℚ}}^{n}\right)$ is called linear if it has the form

 ${\stackrel{\to }{v}}_{0}+\mathrm{ℤ}{\stackrel{\to }{v}}_{1}+\mathrm{ℤ}{\stackrel{\to }{v}}_{2}+\cdots +\mathrm{ℤ}{\stackrel{\to }{v}}_{m}$ (1.3)

for subsets of ${\mathrm{ℤ}}^{n}$ as well as

 ${\stackrel{\to }{v}}_{0}+\mathrm{ℚ}{\stackrel{\to }{v}}_{1}+\mathrm{ℚ}{\stackrel{\to }{v}}_{2}+\cdots +\mathrm{ℚ}{\stackrel{\to }{v}}_{m}$ (1.4)

for subsets of ${\mathrm{ℚ}}^{n}$. The linear subset of ${\mathrm{ℚ}}^{n}$ are nothing but the affine subspaces.

A subset of ${\mathrm{ℕ}}^{n}\left({\mathrm{ℤ}}^{n},{\mathrm{ℚ}}^{n}\right)$ is called semilinear if it is the finite union of semilinear sets. We employ the following notation.

Definition 1.1. Let $M$ and $N$ be finite subsets of ${\mathrm{ℕ}}^{n}$. Then $\mathrm{\Sigma }\left(M:N\right)$ denotes the set of vectors of the form $\stackrel{\to }{u}+{\mathrm{\Sigma }}_{i such that $\stackrel{\to }{u}\in M$, ${k}_{i}\in \mathrm{ℕ}$ and ${\stackrel{\to }{v}}_{i}\in N$ for all $i.

Presburger Arithmetic is defined as follows. The basic symbols are $0$, $1$, $+$, $<$ and ${\equiv }_{m}$, $m\in \mathrm{ℕ}-\left\{0,1\right\}$. Then Presburger Arithmetic is the first order theory of the structure $\underset{_}{\mathrm{ℤ}}≔〈\mathrm{ℤ},0,1,+,<,〈{\equiv }_{m}:1, where $a{\equiv }_{m}b\phantom{\rule{mediummathspace}{0.2em}}\phantom{\rule{mediummathspace}{0.2em}}\mathrm{iff}\phantom{\rule{mediummathspace}{0.2em}}\phantom{\rule{mediummathspace}{0.2em}}a-b$ is divisible by $m$.

Negation can be eliminated.

 $\begin{array}{ccc}\hfill ¬\left(x\doteq y\right)& ↔& x (1.5)

where $\underset{_}{n}$ is defined by $\underset{_}{0}≔0$, $\underset{_}{n+1}≔\underset{_}{n}+1$. We shall occasionally use $x\le y$ for $x. Moreover, multiplication by a given natural number also is definable: put $0t≔\overline{0}$, and $\left(n+1\right)\phantom{\rule{mediummathspace}{0.2em}}t\phantom{\rule{mediummathspace}{0.2em}}≔\phantom{\rule{mediummathspace}{0.2em}}nt+t$. Every term in the variables ${x}_{i}$, $i, is equivalent to $b+{\mathrm{\Sigma }}_{i, where $b,{a}_{i}\in \mathrm{ℕ}$, $i. A subset $S$ of ${\mathrm{ℤ}}^{n}$ is definable if there is a formula $\varphi \left({x}_{o},{x}_{1},\dots ,{x}_{n-1}\right)$ such that

 $S=\left\{〈{k}_{i}:i (1.6)

The definable subsets of ${\mathrm{ℤ}}^{n}$ are closed under union, intersection and complement and permutation of the coordinated. Moreover, if $S\subseteq {\mathrm{ℤ}}^{n+1}$ is definable, so is its projection

 ${\pi }_{n}\left[S\right]≔\left\{〈{k}_{i}:i (1.7)

The same holds for definable subsets of ${\mathrm{ℕ}}^{n}$, which are simply those definable subsets of ${\mathrm{ℤ}}^{n}$ that are included in ${\mathrm{ℕ}}^{n}$. Clearly, if $S\subseteq {\mathrm{ℤ}}^{n}$ is definable, so $S\cap {\mathrm{ℕ}}^{n}$.

# 2  Linear Equations

Lemma 2.1. Suppose that $a+{\mathrm{\Sigma }}_{i is a linear equation with rational numbers $a$, $b$, ${p}_{i}$ and ${q}_{i}\phantom{\rule{mediummathspace}{0.2em}}\left(i. Then there is an equivalent equation $g+{\mathrm{\Sigma }}_{i with positive integer coefficients such that $g·h=0$ and for every $i.

Proof First, multiply with the least common denominator to transform the equation into an equation with integer coefficients. Next, for every $i, substract ${q}_{i}{x}_{i}$ from both sides ${p}_{i}>{q}_{i}$ and ${p}_{i}{x}_{i}$ otherwise.

Call an equation reduced if it has the form

 $g+\sum _{i (2.1)

with positive integer coefficients $g$ and ${k}_{i}$, $i. Likewise for an inequation. Evidently, modulo renaming of variables we can transform every rational equation into reduced form.

Lemma 2.2. The set of solutions of reduced equation is semilinear.

Proof Let $\mu$ be the least common multiple of the ${k}_{i}$. Consider a vector of the form ${\stackrel{\to }{c}}_{i,j}=\left(\mu /{k}_{i}\right){\stackrel{\to }{e}}_{i}+\left(\mu /{k}_{j}\right){\stackrel{\to }{e}}_{j}$, where $i and $m\le j. Then if $\stackrel{\to }{v}$ is a solution, so is $\stackrel{\to }{v}+{\stackrel{\to }{c}}_{i,j}$ and conversely. Put $C≔\left\{{\stackrel{\to }{c}}_{i,j}:i and let

 $P≔\left\{\stackrel{\to }{u}:g\sum _{i (2.2)

Both $P$ and $C$ are finite. Moreover, the set of solutions is exactly $\mathrm{\Sigma }\left(P:C\right)$.

Lemma 2.3. The set of solutions of a reduced inequation is semilinear.

Proof Assume that the inequation has the form

 $g+\sum _{i (2.3)

Define $C$ and $P$ as before. Let $E≔\left\{{\stackrel{\to }{e}}_{i}:m\le i. Then the set of solutions is $\mathrm{\Sigma }\left(P:C\cup E\right)$. If the inequation has the form

 $g+\sum _{i (2.4)

the set of solutions is $\mathrm{\Sigma }\left(P:C\cup F\right)$ where $F≔\left\{{\stackrel{\to }{e}}_{i}:i.

Lemma 2.4. Let $M\subseteq {\mathrm{ℚ}}^{n}$be an affine subspace. Then $M\cap {\mathrm{ℤ}}^{n}$ is a semilinear subset of ${\mathrm{ℤ}}^{n}$.

Proof Let ${\stackrel{\to }{v}}_{i}$, $i, be vectors such that

 $M={\stackrel{\to }{v}}_{0}+\mathrm{ℚ}{\stackrel{\to }{v}}_{1}+\mathrm{ℚ}{\stackrel{\to }{v}}_{2}+\cdots +\mathrm{ℚ}{\stackrel{\to }{v}}_{m-1}$ (2.5)

We can assume that the ${\stackrel{\to }{v}}_{i}$ are lineary independent. Clearly, since $\mathrm{ℚ}\stackrel{\to }{w}=\mathrm{ℚ}\left(\lambda \phantom{\rule{mediummathspace}{0.2em}}\stackrel{\to }{w}\right)$ for any nonzero rational number $\lambda$, we can assume that ${\stackrel{\to }{v}}_{i}\in {\mathrm{ℤ}}^{n}$, $i. Now, let $V≔\left\{{\stackrel{\to }{v}}_{0}+{\sum }_{0. $V\cap {\mathrm{ℤ}}^{n}$is finite. Moreover, if ${\stackrel{\to }{v}}_{0}+{\sum }_{0 then also ${\stackrel{\to }{v}}_{0}+{\sum }_{0 if ${\kappa }_{i}-{\kappa }_{i}^{\prime }\in \mathrm{ℤ}$. Hence,

 $M=\bigcup _{\stackrel{\to }{w}\in V}\stackrel{\to }{w}+\mathrm{ℤ}{\stackrel{\to }{v}}_{1}+\cdots +\mathrm{ℤ}{\stackrel{\to }{v}}_{m}$ (2.6)

There is a semilinear set.

Lemma 2.5. Let $M\subseteq {\mathrm{ℤ}}^{n}$ be a semilinear subset of ${\mathrm{ℤ}}^{n}$. Then $M\cap {\mathrm{ℕ}}^{n}$ is semilinear.

Proof It suffices to show this for linear subsets. Let ${\stackrel{\to }{v}}_{i}$, $i, be vectors such that

 $M={\stackrel{\to }{v}}_{0}+\mathrm{ℤ}{\stackrel{\to }{v}}_{1}+\cdots +\mathrm{ℤ}{\stackrel{\to }{v}}_{m-1}$ (2.7)

Put ${\stackrel{\to }{w}}_{i}≔-{\stackrel{\to }{v}}_{i}$, $0. Then

 $M={\stackrel{\to }{v}}_{0}+\mathrm{ℕ}{\stackrel{\to }{v}}_{1}+\mathrm{ℕ}{\stackrel{\to }{v}}_{2}+\cdots +\mathrm{ℕ}{\stackrel{\to }{v}}_{m-1}+\mathrm{ℕ}{\stackrel{\to }{w}}_{1}+\cdots +\mathrm{ℕ}{\stackrel{\to }{w}}_{m-1}$ (2.8)

Thus, we may without loss of generality assume that

 $M={\stackrel{\to }{v}}_{0}+\mathrm{ℕ}{\stackrel{\to }{v}}_{1}+\mathrm{ℕ}{\stackrel{\to }{v}}_{2}+\cdots +\mathrm{ℕ}{\stackrel{\to }{v}}_{m-1}$ (2.9)

Notice, however, that these vectors are not necessarily in ${\mathrm{ℕ}}^{n}$. For $i$ starting at $1$ until $n$ we do the following.

Let ${x}_{j}^{i}≔{\stackrel{\to }{v}}_{i}\left(i\right)$. Assume that for $0, ${x}_{j}^{i}\ge 0$, and that for $p\le j, ${x}_{j}^{i}>0$. (A renaming of the variables can achieve this.) We introduce new cyclic vectors ${\stackrel{\to }{c}}_{j,k}$ for $0 and $p\le k. Let $\mu$ the least common multiple of the $|{x}_{s}^{i}|$, for all $0 where ${x}_{s}^{i}\ne 0$:

 ${\stackrel{\to }{c}}_{i,j}≔\left(\mu /{x}_{j}^{i}\right){\stackrel{\to }{v}}_{j}+\left(\mu /{x}_{k}^{i}\right){\stackrel{\to }{v}}_{k}$ (2.10)

Notice that the $s$-coordinates of these vectors are positive for $s, since this is a positive sum of positive numbers. The $i$th coordinate of these vectors is $0$. Suppose that the $i$th coordinate of

 $\stackrel{\to }{w}={\stackrel{\to }{v}}_{0}+\sum _{0 (2.11)

is $\ge 0$, where ${\gamma }_{j}\in \mathrm{ℕ}$ for all $0. Suppose further that for some $k\ge p$ we have ${\lambda }_{k}\ge {v}_{0}^{i}+\left(\mu /|{x}_{k}^{i}|\right)$. Then there must be a $j such that ${\lambda }_{j}\ge \left(\mu /{x}_{j}^{i}\right)$. Then put ${\lambda }_{r}^{\prime }≔{\lambda }_{r}$ for $r\ne j,\phantom{\rule{mediummathspace}{0.2em}}k,\phantom{\rule{mediummathspace}{0.2em}}{\lambda }_{j}^{\prime }≔{\lambda }_{j}-\left(\mu /{x}_{j}^{i}\right)$ and ${\lambda }_{k}^{\prime }≔{\lambda }_{k}+\left(\mu /{x}_{k}^{i}\right)$. Then

 $\stackrel{\to }{w}={\stackrel{\to }{c}}_{j,k}+\sum _{0 (2.12)

Moreover, ${\lambda }_{j}^{\prime }\le {\lambda }_{j}$ for all $j, and ${\lambda }_{k}^{\prime }<{\lambda }_{k}$. Thus, by adding these cyclic vectors we can see to it that the coefficients of ${\stackrel{\to }{v}}_{k}$ for $p\le k are bounded. Now define $P$ to be the set of

 $\stackrel{\to }{w}={\stackrel{\to }{v}}_{0}+\sum _{0 (2.13)

where ${\lambda }_{j}<{v}_{0}^{j}+m|\mu /{x}_{j}^{i}|$ for all $0. Then

 $M\cap {\mathrm{ℕ}}^{n}=\bigcup _{\stackrel{\to }{u}\in P}\stackrel{\to }{u}+\sum _{0 (2.14)

with all ${\lambda }_{j}$, ${\kappa }_{j,k}\ge 0$. Now we have achieved that all $j$th coordinates of vectors are positive.

The following is now immediate.

Lemma 2.6. Let $M\subseteq {\mathrm{ℚ}}^{n}$ be an affine subspace. Then $M\cap {\mathrm{ℕ}}^{n}$ is a semilinear subset of ${\mathrm{ℕ}}^{n}$.

Lemma 2.7. The intersection of two semilinear sets is again semilinear.

Proof It is enough to show the claim for linear sets. So, let ${C}_{0}=\left\{{\stackrel{\to }{u}}_{i}:i, ${C}_{1}=\left\{{\stackrel{\to }{v}}_{i}:i and ${S}_{0}≔\mathrm{\Sigma }\left(\left\{{\stackrel{\to }{v}}_{0}\right\}:{C}_{0}\right)$ and ${S}_{1}≔\mathrm{\Sigma }\left(\left\{{\stackrel{\to }{v}}_{1}\right\};{C}_{1}\right)$ be linear. We will show that ${S}_{0}\cap {S}_{1}$ is semilinear. To see this, notice that $\stackrel{\to }{w}\in {S}_{0}\cap {S}_{1}$ $\mathrm{iff}$ there are natural numbers ${\kappa }_{i}\left(i and ${\lambda }_{j}\left(j such that

 $\stackrel{\to }{w}=\stackrel{\to }{c}+\sum _{i (2.15)

So, we have to show that the set of these $\stackrel{\to }{w}$ is semilinear.

The equations are now taken as linear equations with ${\kappa }_{i}$, $i and ${\lambda }_{j}$, $i, as variables. Thus we have equations for $m+n$ variables. We solve these equations first in ${\mathrm{ℚ}}^{m+1}$. They form an affine subspace of ${\mathrm{ℚ}}^{m+n}\cong {\mathrm{ℚ}}^{m}\oplus {\mathrm{ℚ}}^{n}$. By the Lemma 2.6, the intersection of the set with ${\mathrm{ℕ}}^{m+n}$ is semilinear, and so is its projection onto ${\mathrm{ℕ}}^{m}$ (or to ${\mathrm{ℕ}}^{n}$ for that matter). Let it be ${\cup }_{i, where for each $i, ${L}_{i}\subseteq {\mathrm{ℕ}}^{m}$ is linear. Thus there is a representation of ${L}_{i}$ as

 ${L}_{i}=\stackrel{\to }{\theta }+\mathrm{ℕ}{\stackrel{\to }{\eta }}_{0}+\cdots +\mathrm{ℕ}{\stackrel{\to }{\eta }}_{\gamma -1}$ (2.16)

Now put

 ${W}_{i}≔\left\{{\stackrel{\to }{v}}_{0}+\sum _{i (2.17)

From the construction we get that

 ${S}_{0}\cap {S}_{1}=\bigcup _{i (2.18)

Define vector ${\stackrel{\to }{q}}_{i}≔{\mathrm{\Sigma }}_{i, ${\stackrel{\to }{u}}_{i}$, $i<\gamma$ and $\stackrel{\to }{r}≔\stackrel{\to }{c}+{\mathrm{\Sigma }}_{j. Then

 ${W}_{i}=\stackrel{\to }{r}+\mathrm{ℕ}{\stackrel{\to }{q}}_{0}+\cdots +\mathrm{ℕ}{\stackrel{\to }{q}}_{\gamma -1}$ (2.19)

So, ${W}_{i}$ is linear. This shows the claim.

Lemma 2.8. If $S\subseteq {\mathrm{ℕ}}^{n}$ is semilienar, so is its projection ${\pi }_{n}\left[S\right]$.

## 2.1  The Theorem

We need one more prerequisite. Say that a first-order theory $T$ has quantifier elimination if for every formula $\varphi \left(\stackrel{\to }{x}\right)$ there exists a quantifier free formula $\chi \left(\stackrel{\to }{x}\right)$ such that $T⊢\varphi \left(\stackrel{\to }{x}\right)↔\chi \left(\stackrel{\to }{x}\right)$. We follow the proof of [3].

Theorem 2.9. (Presburger) Presburger Arithmetic has quantifier elimination.

Proof It is enough to show that for every formula $\left(\exists x\right)\varphi \left(\stackrel{\to }{y},x\right)$ with $\varphi \left(\stackrel{\to }{y},x\right)$ quantifier free there exists a quantifier free formula $\chi \left(\stackrel{\to }{y}\right)$ such that

 $\mathrm{ℤ}\models \left(\forall \stackrel{\to }{y}\right)\left(\left(\exists x\right)\varphi \left(\stackrel{\to }{y},x\right)↔\chi \left(\stackrel{\to }{y}\right)\right)$ (2.20)

Now, we may further eliminate negation (see the remarks above) and disjunctions inside $\varphi \left(\stackrel{\to }{y},x\right)$ (since $\left(\exists x\right)\left(\alpha \vee \beta \right)↔\left(\exists x\right)\alpha \vee \left(\exists x\right)\beta$ ). Finally, we may assume that all conjuncts contain $x$. For if $\alpha$ does not contain $x$ fee, $\left(\exists x\right)\left(\alpha \wedge \beta \right)$ is equivalent to $\alpha \wedge \left(\exists x\right)\beta$. So, $\varphi$ can be assumed to be a conjunction of atomic formulae of the following form:

 $\left(\exists x\right)\left(\underset{i{t}_{i}^{″}\wedge \underset{i (2.21)

Now, $s\equiv t$ is equivalent with $ns\equiv nt$, so after suitable multiplication we may see to it that all the ${n}_{i}$, ${n}_{i}^{\prime }$, ${n}_{i}^{\prime \prime \prime }$ are the same number $\nu$.

 $\left(\exists x\right)\left(\underset{i{\tau }_{i}^{″}\wedge \underset{i (2.22)

We may rewrite the formula in the following way (replacing $\nu x$ b< $x$ and the condition that $x$ is divisible by $\nu$).

 $\left(\exists x\right)\left(x{\equiv }_{\nu }0\wedge \underset{i{\tau }_{i}^{″}\wedge \underset{i (2.23)

Assume that $p>0$. Then the first set of conjunctions is equivalent with the conjunction of ${\bigwedge }_{i (which does not contain $x$) and $x\doteq {\tau }_{0}$. We may therefore eliminate all occurances of $x$ by ${\tau }_{0}$ in the formula (2.23).

Thus, from now on we may assume that $p=0$. Also, notice that $x<\sigma \wedge x<\tau$ is equivalent to $\left(x<\sigma \wedge \sigma \le \tau \right)\vee \left(x<\tau \wedge \tau <\sigma \right)$. This means that we can assume $q\le 1$, and likewise that $r\le 1$. Next we show that we can actually have $s\le 1$. To see this, notice the following.

Let $u$, $v$, $w$, $x$ be integeres, $w$, $x>1$, and let $p$ be the least common multiple of $w$ and $x$. Then qed $\left(p/w,\phantom{\rule{mediummathspace}{0.2em}}p/x\right)=1$, and so there exist integers $m$, $n$ such that $1=m·p/w+n·p/x$. It follows that the following are equivalent.

$y\equiv u$ $\left(\mathrm{mod}\phantom{\rule{mediummathspace}{0.2em}}w\right)$ and $y\equiv v$ $\left(\mathrm{mod}\phantom{\rule{mediummathspace}{0.2em}}x\right)$

$u\equiv v$ $\left(\mathrm{mod}\phantom{\rule{mediummathspace}{0.2em}}\mathrm{ged}\phantom{\rule{mediummathspace}{0.2em}}\left(w,x\right)\right)$ and $y\equiv m\left(p/w\right)u+n\left(p/x\right)v\phantom{\rule{mediummathspace}{0.2em}}\phantom{\rule{mediummathspace}{0.2em}}\left(\mathrm{mod}\phantom{\rule{mediummathspace}{0.2em}}p\right)$.

Proof Using this equivalence we can reduce the congruence statements to a conjunction of congruences where only involves $x.$

This leaves us with 8 possibilities. If $r=0$ or $s=0$ the formula is actually trivially true. That is to say, $\left(\exists x\right)\left(x<\tau \right)$, $\left(\exists x\right)\left(v, $\left(\exists x\right)\left(x{\equiv }_{m}\xi \right)$, $\left(\exists x\right)\left(x<\tau \wedge x{\equiv }_{m}\xi \right)$ and $\left(\exists x\right)\left(v are equivalent to $\top$. Finally, it is verified that

 $\left(\exists x\right)\left(x<\tau \wedge v (2.24)
 $\left(\exists x\right)\left(x<\tau \wedge v (2.25)

Theorem 2.10. (Ginsburg & Spanier) A subset of ${\mathrm{ℕ}}^{n}$ is semilinear iff it is definable in Presburger Arithmetic.

Proof  $\left(⇒\right)$ Every semilinear set is definable in Presburger Arithmetic. To see this it is enough to show that linear sets are definable. For if $M$ is a union of ${N}_{i}$, $i, and each ${N}_{i}$ is linear and hence definable by a formula ${\varphi }_{i}\left(\stackrel{\to }{x}\right)$, then $M$ is definable by ${\bigvee }_{i. Now let $M=\stackrel{\to }{v}+\mathrm{ℕ}{\stackrel{\to }{v}}_{0}+\cdots +\mathrm{ℕ}{\stackrel{\to }{v}}_{m-1}$ be linear. Then put

 $\varphi \left(\stackrel{\to }{x}\right)≔\left(\exists {y}_{0}\right)\left(\exists {y}_{1}\right)\dots \left(\exists {y}_{m-1}\right)\left(\underset{i (2.26)

$\varphi \left(\stackrel{\to }{x}\right)$ defines $M$. $\left(⇒\right)$ Let $\varphi \left(\stackrel{\to }{x}\right)$ be a formula defining $S$. By Theorem 2.9, there exists a quantifier free formula $\chi \left(\stackrel{\to }{x}\right)$ defining $S$. Moreover, as we have remarked above, $\chi$ can be assumed to be negation free. Thus, $\chi$ is a disjunction of conjunctions of atomic formulae. By Lemma 2.7, the set of semilinear subsets of ${\mathrm{ℕ}}^{n}$ is closed under intersection of members, and it is also closed under union. Thus, all we need to show is that atomic formulae define semilinear sets. Now, observe that ${x}_{0}{\equiv }_{m}{x}_{1}$ is equivalent to $\left(\exists {x}_{2}\right)\left({x}_{0}\doteq {x}_{1}+m{x}_{2}\right)$, which is semilinear, as it is the projection of ${x}_{0}\doteq {x}_{1}+m{x}_{2}$ onto the first two components.

Corollary 2.11. The complement of a semilinear set is again semilinear.

# References

[1] Seymour Ginsburg and Edwin H. Spanier.
Bounded ALGOL–Like Languages.
Transactions of the American Mathematical Society, 113:333 – 368, 1964.

[2] Seymour Ginsburg and Edwin H. Spanier.
Semigroups, Presburger Formulas, and Languages.
Pacific Journal of Mathematics, 16:285 – 296, 1966.

[3] J. Donald Monk. Mathematical Logic. Springer, Berlin, Heidelberg, 1976.