Please unpack this notation from book Model Theory by Marker

Question

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

Answer 1

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

Answer 2

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