On page 73 of Model Theory by Marker, he proves DLO has quantifier elimination. In it he writes:

For $\sigma: \{(i,j) : 1 \le i < j \le n\} \rightarrow 3$, let $\chi_{\sigma}(x_1,\ldots,x_n)$ be the formula

$$\bigwedge_{\sigma(i,j)=0} x_i = x_j \wedge \bigwedge_{\sigma(i,j)=1} x_i < x_j \wedge \bigwedge_{\sigma(i,j)=2} x_i > x_j$$

I have no idea what any of the termninology above means, except the set notation :$\{(i,j) : 1 \le i < j \le n\}$, and $\bigwedge$.

In particular:

  1. what does it mean to say: $\sigma :\{\ldots\} \rightarrow 3$?
  2. what is $\sigma(i,j) = k$ for k = $0,1,2$ under each of the $\bigwedge$?
  • $\begingroup$ Natural numbers can be seen as sets: $0 = \emptyset, 1 = \{0\}, 2 = \{0,1\}, 3 = \{0,1,2\}$, that is, $\varsigma: \{\} \to 3$ is a map definition. So, $\varsigma(i,j)=0$ means all $i$ and $j$ for which this map is true, $\endgroup$ – Moritz Feb 24 '15 at 21:23
  • $\begingroup$ @Moritz so which question does the statement above answer? $\endgroup$ – chibro2 Feb 24 '15 at 21:24

For your first question: $\sigma$ is simply a function that assigns $0,1$, or $2$ to each ordered pair $(i,j)$ of integers satisfying $1\le i<j\le n$. $\{(i,j):1\le i<j\le n\}$ is the set of such ordered pairs, $3$ is the set $\{0,1,2\}$, and $\sigma$ is a function from the former set to the latter.

The notation $\displaystyle\bigwedge_{\text{stuff}}\varphi(\text{stuff})$ is analogous to summation notation $\displaystyle\sum_{\text{stuff}}x(\text{stuff})$: it’s the conjunction of the formulae whose general form is $\varphi(\text{stuff})$.

In general if $\Phi=\{\varphi_0,\ldots,\varphi_n\}$ is a (finite) set of formulae, $\bigwedge\Phi$ is simply the conjunction of these formulae:


Here, for instance,

$$\bigwedge_{\sigma(i,j)=0}(x_i=x_j)=\bigwedge\{x_i=x_j:1\le i<j\le n\text{ and }\sigma(i,j)=0\}$$ is the conjunction of all $x_i=x_j$ such that $\sigma(i,j)=0$.

The formula

$$\bigwedge_{\sigma(i,j)=0} (x_i = x_j) \wedge \bigwedge_{\sigma(i,j)=1} (x_i < x_j) \wedge \bigwedge_{\sigma(i,j)=2} (x_i > x_j)$$

‘says’ that if $1\le i<j\le n$, $x_i=x_j$ whenever $\sigma(i,j)=0$, $x_i<x_j$ whenever $\sigma(i,j)=1$, and $x_i>x_j$ whenever $\sigma(i,j)=2$. In other words, the function $\sigma$ completely encodes the order relationships amongst $x_1,\ldots,x_n$.

  • $\begingroup$ So I'm still not perfectly clear, I can see $\bigwedge\{x_i=x_j:1\le i<j\le n\text{ and }\sigma(i,j)=0\} = (x_1 = x_2) \wedge \ldots \wedge (x_1 = x_n) \wedge (x_2 = x_3) \ldots$, but what purpose does $\sigma(i,j) = 0$ serve there? $\endgroup$ – chibro2 Feb 24 '15 at 22:01
  • 2
    $\begingroup$ @chibro2: It tells you which of the formulae $x_i=x_j$ with $1\le i<j\le n$ are included in the conjunction. If $(2,5)$ and $(3,4)$ are the only pairs $(i,j)$ such that $\sigma(i,j)=0$, then the conjunction is only $(x_2=x_5)\land(x_3=x_4)$. It is not, as you wrote, the conjunction of all $x_i=x_j$ with $1\le i<j\le n$, unless $\sigma$ is the constant function $\sigma(i,j)\equiv 0$. $\endgroup$ – Brian M. Scott Feb 24 '15 at 22:05
  • $\begingroup$ what if (2,5) and (3,4) are the only pairs such that $\sigma(i,j) = 1$ or $2$? then what does the formula look like? $\endgroup$ – chibro2 Feb 24 '15 at 22:25
  • 1
    $\begingroup$ @chibro2: The function $\sigma$ assigns one of the values $0,1$, and $2$ to each pair, so each pair appears in exactly one of the big conjunctions. Example: $n=6$, $\sigma(1,2)=\sigma(1,3)=\sigma(1,4)=0$, $\sigma(2,3)=\sigma(2,4)=1$, and $\sigma(3,4)=2$. Then the formula is $$\underbrace{(x_1=x_2)\land(x_1=x_3)\land(x_1=x_4)}_{\sigma(i,j)=0}\land \underbrace{(x_2<x_3)\land(x_2<x_4)}_{\sigma(i,j)=1}\land \underbrace{(x_3>x_4)}_{\sigma(i,j)=2}\;.$$ $\endgroup$ – Brian M. Scott Feb 24 '15 at 22:28
  • 1
    $\begingroup$ Ohh! wow what a complicated way to say something so simple $\endgroup$ – chibro2 Feb 24 '15 at 22:29

Well, $\sigma$ is a function, assigning pairs of distinct natural numbers between $1$ and $n$ either $0,1$ or $2$ (recall that $3=\{0,1,2\}$).

Then you define the conjunction over the pairs given the value $0$, the pairs given the value $1$ and the pairs given the value $2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.