Lecture 6 (25.11.96)
Previous lecture:
Lecture 5 ,
Overview ,
Course home page ,
Material of this and subsequent lectures:
- [Ma3]
J.A. Makowsky,
Draft chapter of Interpretations, Translations and
Reductions (for the Handbook of Logic in CS)
Translation schemes
Detailed definition of
- $1-\tau-\sigma$- Translation scheme $\Phi$
- the induced map $\Phi^*$ from $\tau$-structures to
$\sigma$-structures.
- the induced map $\Phi^#$ from $\sigma$-formulas to
$\tau$-formulas.
- Statement of the fundamental lemma on translation schemes.
For a $\tau$-structures A and a $\sigma$-formula $\theta$
we have that
$\Phi^*({\bf A}) \models \theta$ iff $\bf A \models
\Phi^#(\theta)$.
We proved the lemma in great detail.
Exapmples of applications of the fundamental lemma.
- Hamiltonicity is not MSOL definable over ordered
graphs of the form $< V,E,R_< >$.
- The theory of the reals with addition, multiplication and
sin(x) is undecidable (using the undecidability of the theory
of the natural numbers proved by K. Goedel). Note that the theory
of the reals with addition and multiplication (and order)
is decidable by a theorem due to A. Tarski.
Exercise: Formulate the exact properties PROPERTIES
of $\Phi^*$ and/or $\PHI^#$ needed such that:
-
If $K_1$ is a class of $\tau$-structures,
$K_2$ is a class of $\sigma$-structures definable by $\theta$,
and $\Phi$ is a $\tau-\sigma$-translation scheme such that
PROPERTIES hold, then $K_1$ is definable by $\Phi^#(\theta)$.
-
If $K_1$ is a class of $\tau$-structure whose theory is decidable,
$K_2$ is a class of $\sigma$-structures,
and $\Phi$ is a $\tau-\sigma$-translation scheme such that
PROPERTIES hold, then the theory of $K_1$ is decidable.
Next lecture:
Lecture 7
Draft of chapter on translation schemes:
Chapter of Handbook