# Please unpack this notation from book Model Theory by Marker

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$?
• 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, – Moritz Feb 24 '15 at 21:23
• @Moritz so which question does the statement above answer? – 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:

$$\bigwedge\Phi=\varphi_0\land\varphi_1\land\ldots\land\varphi_n\;.$$

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$.

• 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? – chibro2 Feb 24 '15 at 22:01
• @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$. – Brian M. Scott Feb 24 '15 at 22:05
• 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? – chibro2 Feb 24 '15 at 22:25
• @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}\;.$$ – Brian M. Scott Feb 24 '15 at 22:28
• Ohh! wow what a complicated way to say something so simple – 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$.