Tarski sentences

Recall the logical predicates that were formed in Section 3.1. They will be used again here, but now they are defined with a little more flexibility. For any $f \in {\mathbb{Q}}[x_1,\ldots, x_n]$, an atom is an expression of the form $f \bowtie 0$, in which $\bowtie$ may be any relation in the set $\{=, \not =, <, >, \leq, \geq\}$. In Section 3.1, such expressions were used to define logical predicates. Here, we assume that relations other than $\leq$ can be used and that the vector of polynomial variables lies in ${\mathbb{R}}^n$.

A quantifier-free formula, $\phi(x_1,\ldots, x_n)$, is a logical predicate composed of atoms and logical connectives, ``and,'' ``or,'' and ``not,'' which are denoted by $\wedge$, $\vee$, and $\neg$, respectively. Each atom itself is considered as a logical predicate that yields TRUE if and only if the relation is satisfied when the polynomial is evaluated at the point $(x_1,\ldots, x_n) \in {\mathbb{R}}^n$.

Example 6..2 (An Example Predicate)   Let $\phi$ be a predicate over ${\mathbb{R}}^3$, defined as

$$\phi (x_1,x_2,x_3) = (x_1^2 x_3 - x_2^4 < 0) \vee \big( \neg (3 x^2 x^3 \not = 0) \wedge (2 x_3^2 - x_1 x_2 x_3 + 2 \geq 0) \big) .$$ (6.8)

The precedence order of the connectives follows the laws of Boolean algebra. $\blacksquare$

Let a quantifier ${\cal Q}$ be either of the symbols, $\forall$, which means ``for all,'' or $\exists$, which means ``there exists.'' A Tarski sentence $\Phi$ is a logical predicate that may additionally involve quantifiers on some or all of the variables. In general, a Tarski sentence takes the form

$$\Phi (x_1,\ldots,x_{n-k}) = ({\cal Q}z_1) ({\cal Q}z_2) \ldots ({\cal Q} z_k) \;\phi (z_1,\ldots, z_k,x_1,\ldots,x_{n-k}) ,$$ (6.9)

in which the $z_i$ are the quantified variables, the $x_i$ are the free variables, and $\phi$ is a quantifier-free formula. The quantifiers do not necessarily have to appear at the left to be a valid Tarski sentence; however, any expression can be manipulated into an equivalent expression that has all quantifiers in front, as shown in (6.9). The procedure for moving quantifiers to the front is as follows [705]: 1) Eliminate any redundant quantifiers; 2) rename some of the variables to ensure that the same variable does not appear both free and bound; 3) move negation symbols as far inward as possible; and 4) push the quantifiers to the left.

Example 6..3 (Several Tarski Sentences)   Tarski sentences that have no free variables are either TRUE or FALSE in general because there are no arguments on which the results depend. The sentence

$$\Phi = \forall x \exists y \; (x^2 - y < 0) ,$$ (6.10)

is TRUE because for any $x \in {\mathbb{R}}$, some $y \in {\mathbb{R}}$ can always be chosen so that $y > x^2$. In the general notation of (6.9), this example becomes ${\cal Q}z_1 = \forall x$, ${\cal Q}z_2 = \exists y$, and $\phi (z_1,z_2) = (x^2 - y < 0)$.

Swapping the order of the quantifiers yields the Tarski sentence

$$\Phi = \exists y \forall x \; (x^2 - y < 0) ,$$ (6.11)

which is FALSE because for any $y$, there is always an $x$ such that $x^2 > y$.

Now consider a Tarski sentence that has a free variable:

$$\Phi (z) = \exists y \forall x \; (x^2 - z x^2 - y < 0) .$$ (6.12)

This yields a function $\Phi : {\mathbb{R}}\rightarrow \{$TRUE$,\;$FALSE$\}$, in which

$$\Phi (z) = \left\{ \begin{array}{ll} \mbox{\sc{true}}& \mbox{ if $z \geq 1$\ } \\ \mbox{\sc{false}}& \mbox{ if $z < 1$. } \\ \end{array}\right.$$ (6.13)

An equivalent quantifier-free formula $\phi$ can be defined as $\phi(z) = (z > 1)$, which takes on the same truth values as the Tarski sentence in (6.12). This might make you wonder whether it is always possible to make a simplification that eliminates the quantifiers. This is called the quantifier-elimination problem, which will be explained shortly. $\blacksquare$