imaginariesImaginaries2003-02-07 08:37:222005-03-18 22:08:09Definitionimaginarieselimination of imaginariesdefinable structureinterpretable structurecodeinterpretinterpretableimaginariesequivalence relationequivalence class% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
% Packages
\usepackage{amssymb}
\usepackage{eufrak}
\usepackage[dvips]{epsfig,graphics}
\usepackage{graphicx,psfrag}
% Theorems
\newtheorem{df}{Definition}[section]
\newtheorem{tm}[df]{Theorem}
\newtheorem{lm}[df]{Lemma}
\newtheorem{crl}[df]{Corollary}
\newtheorem{pp}[df]{Proposition}
% Spelling issues
\def\centre{\center}
% Textrm commands
% \def\bugger{{\rm bugger}}
\def\Int{{\rm Int}_{k,C}}
\def\Intn{{\rm Int}_{k,C}^{n}}
\def\acl{{\rm acl}}
\def\ch{{\rm char}}
\def\dcl{{\rm dcl}}
\def\dom{{\rm dom}}
\def\elt{{\rm elt}}
\def\eut{{\rm eut}}
\def\fiber{{\rm fib}}
\def\germ{{\rm germ}}
\def\graph{{\rm graph}}
\def\gr{{\rm grd}}
\def\ilt{{\rm ilt}}
\def\lit{{\rm ilt}}
\def\iut{{\rm iut}}
\def\lex{{\rm lex}}
\def\mo{{\rm m.o.}}
\def\rad{{\rm rad}}
\def\red{{\rm red}}
\def\rex{{\rm rex}}
\def\rcl{{\rm rcl}}
\def\tp{{\rm tp}}
\def\Aff{{\rm Aff}}
\def\Hom{{\rm Hom}}
\def\Res{{\rm Res}}
\def\Gl{{\rm Gl}}
% Math frac commands
\newcommand{\ma}{\mathfrak{A}}
\newcommand{\mb}{\mathfrak{B}}
\newcommand{\mc}{\mathfrak{C}}
\newcommand{\md}{\mathfrak{D}}
% Other commands
\newcommand{\acf}{ACF_{val}}
\newcommand{\bm}{\begin{displaymath}}
\newcommand{\cl}{\bf{d}}
\newcommand{\fp}{f^{\prime}}
\newcommand{\gda}{G_{D}^{A}}
\newcommand{\gind}{\downarrow^{g}}
\newcommand{\op}{\bf{o}}
\newcommand{\half}{{\tiny \begin{array}{l}1 \\ \overline{2}\end{array}}}
\def\isom{\simeq}
\newcommand{\mgb}{\mathbf{M}}
\newcommand{\nin}{\not\in}
\def\nom{\vartriangleleft}
\newcommand{\ra}{\rightarrow}
\newcommand{\rcf}{RCVF_{G}}
\newcommand{\real}{\textrm{real}}
\newcommand{\rk}{{\bf Remark:}}
\newcommand{\sequ}{\left< x_{n}:x<\omega \right>}
\newcommand{\sq}{ $\square$}
\newcommand{\xb}{\overline{x}}
\newcommand{\Aut}{\textrm{Aut}}
\newcommand{\PR}{^{\prime}}
\newcommand{\RS}{\mathbf{R}^{\star}}
\newcommand{\LG}{L_{4}}
\newcommand{\RR}{\mathbf{R}}
\newcommand{\RA}{\rightarrow}
\newcommand{\cla}[1]{\lceil #1 \rceil}Given an algebraic structure $S$ to investigate, mathematicians consider substructures, restrictions of the structure, quotient structures and the like. A natural question for a mathematician to ask if he is to understand $S$ is ``What structures naturally live in $S$?'' We can formalise this question in the following manner: Given some logic appropriate to the structure $S$, we say another structure $T$ is {\em definable} in $S$ iff there is some definable subset $T\PR$ of $S^{n}$, a bijection $\sigma: T\PR \ra T$ and a definable function (respectively relation) on $T\PR$ for each function (resp. relation) on $T$ so that $\sigma$ is an isomorphism (of the relevant type for $T$).
For an example take some infinite group $(G,.)$. Consider the centre of $G$, $Z:=\{x \in G: \forall y \in G (xy=yx)\}$. Then $Z$ is a first order definable subset of $G$, which forms a group with the restriction of the multiplication, so $(Z,.)$ is a first order definable structure in $(G,.)$.
As another example consider the structure $(\mathbf{R},+,.,0,1)$ as a field. Then the structure $(\mathbf{R},<)$ is first order definable in the structure $(\mathbf{R},+,.,0,1)$ as for all $x,y \in \mathbf{R}^{2}$ we have $x\leq y$ iff $\exists z (z^{2}=y-x)$. Thus we know that $(\mathbf{R},+,.,0,1)$ is unstable as it has a definable order on an infinite subset.
Returning to the first example, $Z$ is normal in $G$, so the set of (left) cosets of $Z$ form a factor group. The domain of the factor group is the quotient of $G$ under the equivalence relation $x \equiv y$ iff $\exists z \in Z (xz=y)$. Therefore the factor group $G/Z$ will not (in general) be a definable structure, but would seem to be a ``natural" structure. We therefore weaken our formalisation of ``natural" from definable to interpretable. Here we require that a structure is isomorphic to some definable structure on equivalence classes of definable equivalence relations. The equivalence classes of a $\emptyset$-definable equivalence relation are called {\em imaginaries}.
In \cite{P2} Poizat defined the property of {\em Elimination of Imaginaries}. This is equivalent to the following definition:
\begin{df} \label{I wanna b} A structure $\ma$ with at least two distinct $\emptyset$-definable elements admits {\em elimination of imaginaries} iff for every $n \in \mathbf{N}$ and $\emptyset$-definable equivalence relation $\sim$ on $\ma^{n}$ there is a $\emptyset$-definable function $f:\ma^{n} \ra \ma^{p}$ (for some $p$) such that for all $x$ and $y$ from $\ma^{n}$ we have
\bm x \sim y \textrm{ iff } f(x)=f(y). \end{displaymath} \end{df}
Given this property, we think of the function $f$ as coding the equivalence classes of $\sim$, and we call $f(x)$ a code for $x/\sim$. If a structure has elimination of imaginaries then every interpretable structure is definable.
In \cite{Sh} Shelah defined, for any structure $\ma$ a multi-sorted structure $\ma^{eq}$. This is done by adding a sort for every $\emptyset$-definable equivalence relation, so that the equivalence classes are elements (and code themselves). This is a closure operator i.e. $\ma^{eq}$ has elimination of imaginaries. See \cite{HOD} chapter 4 for a good presentation of imaginaries and $\ma^{eq}$.
The idea of passing to $\ma^{eq}$ is very useful for many purposes. Unfortunately $\ma^{eq}$ has an unwieldy language and theory. Also this approach does not answer the question above. We would like to show that our structure has elimination of imaginaries with just a small selection of sorts added, and perhaps in a simple language. This would allow us to describe the definable structures more easily, and as we have elimination of imaginaries this would also describe the interpretable structures.
\begin{thebibliography}{9}
\bibitem{HOD} Wilfrid Hodges, {\em A shorter model theory} Cambridge University Press, 1997.
\bibitem{P2} Bruno Poizat, {\em Une th\'eorie de Galois imaginaire}, Journal of Symbolic Logic, {\bf 48} (1983), pp. 1151-1170.
\bibitem{Sh} Saharon Shelah, {\em Classification Theory and the Number of Non-isomorphic Models}, North Hollans, Amsterdam, 1978.
\end{thebibliography}