Skip to content

Satisfaction

Consider the following three formulas:

  1. \((\bar{S}\bar{S}(\bar{0})\mathop{\bar{\times}} x) \mathop{\bar{+}} \bar{S}(\bar{0}) = \bar{S}\bar{S}\bar{S}(\bar{0})\)
  2. \(x\mathop{\bar{+}} x = \bar{0}\)
  3. \(x\mathop{\bar{\times}} y = \bar{0}\)

For each of the above formulas, there is a set of natural numbers or pairs of natuaral numbers that satisfy the above formulas.

Let \(y_1, \ldots, y_n\) be distinct variables. If we introduce a formula \(\varphi\) as \(\varphi(y_1,\ldots, y_n)\), this means that when we apply an \(n\)-tuple \((a_1,\ldots, a_n)\) of elements to \(\varphi\) we attach \(a_1\) to \(y_1\), \(a_2\) to \(y_2\) and so on. (The listed variables should include all the variables free in \(\varphi\), though sometimes it is useful to include some other variables as well.)

Witness

Let \(\sigma\) be a signature. A witness is a new constant symbol that is added to \(\sigma\). We use the notation \(\bar{a}_A\) for a witness added to name the element \(a\) in a \(\sigma\)-structure \(A\); so \(\bar{a}_A = a\).

Satisfies

Suppose \(\varphi(y_1,\ldots, y_n)\) is a qf formula of \(LR(\sigma)\), \(A\) is a \(\sigma\)-structure and \((a_1,\ldots, a_n)\) are elements in the domain of \(A\). We define the relation "\((a_1,\ldots, a_n)\) satisfies \(\varphi\)" by the following recursion on the complexity of φ:

  1. If \(\varphi\) is atomic then \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if
\[\models_A\varphi[t_1/y_1, \ldots, t_n/y_n]\]

where \(t_1,\ldots, t_n\) are closed terms (possibly witnesses) such that for each \(i\), \((t_i)_A=a_i\).

  1. If \(\varphi\) is \((\neg\psi)\), then \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if \((a_1,\ldots, a_n)\) does not satisfy \(\psi(y_1,\ldots, y_n)\)

  2. If \(\varphi\) is \((\psi\wedge\chi)\), then \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if \((a_1,\ldots, a_n)\) satisfies both satisfies both \(\psi(y_1,\ldots, y_n)\) and \(\chi(y_1,\ldots, y_n)\)

  3. If \(\varphi\) is \((\psi\vee\chi)\), then \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if either \((a_1,\ldots, a_n)\) satisfies \(\psi(y_1,\ldots, y_n)\) or \((a_1,\ldots, a_n)\) satisfies \(\chi(y_1,\ldots, y_n)\)

  4. If \(\varphi\) is \((\psi\rightarrow\chi)\), then \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if either \((a_1,\ldots, a_n)\) does not satisfy \(\psi(y_1,\ldots, y_n)\) or \((a_1,\ldots, a_n)\) satisfies \(\chi(y_1,\ldots, y_n)\)

  5. If \(\varphi\) is \((\psi\leftrightarrow\chi)\), then \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if either \((a_1,\ldots, a_n)\) either satisfies both \(\psi(y_1,\ldots, y_n)\) and \(\chi(y_1,\ldots, y_n)\), or \((a_1,\ldots, a_n)\) satisfies neither.

Warning

For part 1 to make sense, we have to know that whether \(\models_A\varphi[t_1/y_1, \ldots, t_n/y_n]\) depends only on \(a_1,\ldots, a_n\) and not on the choice of terms used to name them. This is guaranteed by Lemma 5.6.8(b).

Equivalent Formulas

Let \(\varphi(y_1,\ldots, y_n)\) and \(\psi(y_1,\ldots, y_n)\) be qf formulas of \(LR(\sigma)\) and \(A\) a \(\sigma\)-structure. We say that \(\varphi\) and \(\psi\) are equivalent in \(A\) if for all elements \(a_1,\ldots, a_n\) in the domain of \(A\), \((a_1,\ldots, a_n)\) satisfies \(\varphi\) in \(A\) if and only if it satisfies \(\psi\) in \(A\). We say that \(\varphi\) and \(\psi\) are logically equivalent if they are equivalent in every \(\sigma\)-structure.

Diophantine Equation

Let \(n\) be a positive integer and \(X\) a set of \(n\)-tuples of natural numbers. We say that \(X\) is diophantine if there is an equation \(\varphi(x_1,\ldots, x_n)\) of \(LR(\sigma_{arith})\) such that for every \(n\)-tuple \((k_1,\ldots, k_n)\) of natural numbers, \((k_1,\ldots, k_n)\in X\) if and only if for some numbers \(l_1,\ldots, l_m\),

\[\models_{\mathbb{N}} \varphi(\bar{k}_1,\ldots, \bar{k}_n,\bar{l}_1,\ldots, \bar{l}_m)\]

Computably Enumerable/Computable

Let \(n\) be a positive integer and let \(X\) be a set of \(n\)-tuples of natural numbers.

We say that \(X\) is computably enumerable, or c.e. for short, if a digital computer with infinitely extendable memory and unlimited time can be programmed so that it lists (not necessarily in any reasonable order) all and only the \(n\)-tuples that are in \(X\).

We say that \(X\) is computable if a digital computer with infinitely extendable memory and unlimited time can be programmed so that if you type in an \(n\)-tuple in \(X\), the computer prints YES, and if you type in an \(n\)-tuple not in X then it prints NO.

Lemma

Let \(n\) be a positive integer and \(X\) a set of \(n\)-tuples of natural numbers. Then the following are equivalent:

  1. \(X\) is computable.
  2. Both \(X\) and \(\mathbb{N}\setminus X\) are c.e.

Matiyasevich's Theorem

Let \(n\) be a positive integer and \(X\) a set of \(n\)-tuples of natural numbers. Then the following are equivalent:

  1. \(X\) is computably enumerable.
  2. \(X\) is Diophantine.