PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
imaginaries (Definition)

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 definable in $ S$ iff there is some definable subset $ T^{\prime}$ of $ S^{n}$, a bijection $ \sigma: T^{\prime}\rightarrow T$ and a definable function (respectively relation) on $ T^{\prime}$ 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 imaginaries.

In [2] Poizat defined the property of Elimination of Imaginaries. This is equivalent to the following definition:

Definition 0.1   A structure $ \mathfrak{A}$ with at least two distinct $ \emptyset$-definable elements admits elimination of imaginaries iff for every $ n \in \mathbf{N}$ and $ \emptyset$-definable equivalence relation $ \sim$ on $ \mathfrak{A}^{n}$ there is a $ \emptyset$-definable function $ f:\mathfrak{A}^{n} \rightarrow \mathfrak{A}^{p}$ (for some $ p$) such that for all $ x$ and $ y$ from $ \mathfrak{A}^{n}$ we have
$\displaystyle x \sim y \textrm{ iff } f(x)=f(y). $

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 [3] Shelah defined, for any structure $ \mathfrak{A}$ a multi-sorted structure $ \mathfrak{A}^{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. $ \mathfrak{A}^{eq}$ has elimination of imaginaries. See [1] chapter 4 for a good presentation of imaginaries and $ \mathfrak{A}^{eq}$. The idea of passing to $ \mathfrak{A}^{eq}$ is very useful for many purposes. Unfortunately $ \mathfrak{A}^{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.

Bibliography

1
Wilfrid Hodges, A shorter model theory Cambridge University Press, 1997.
2
Bruno Poizat, Une théorie de Galois imaginaire, Journal of Symbolic Logic, 48 (1983), pp. 1151-1170.
3
Saharon Shelah, Classification Theory and the Number of Non-isomorphic Models, North Hollans, Amsterdam, 1978.



"imaginaries" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: cyclic code

Also defines:  imaginaries, elimination of imaginaries, definable structure, interpretable structure, code
Keywords:  interpret, interpretable, imaginaries, equivalence relation, equivalence class
Log in to rate this entry.
(view current ratings)

Cross-references: simple, theory, language, presentation, closure operator, sort, property, equivalence classes, isomorphic, equivalence relation, quotient, domain, factor group, cosets, normal, order, unstable, field, first order, centre, group, infinite, type, isomorphism, function, relation, definable function, bijection, subset, iff, definable, logic, quotient structures, structure, restrictions, substructures, algebraic structure
There are 32 references to this entry.

This is version 4 of imaginaries, born on 2003-02-07, modified 2005-03-18.
Object id is 3990, canonical name is Imaginaries.
Accessed 9537 times total.

Classification:
AMS MSC: 03C68 (Mathematical logic and foundations :: Model theory :: Other classical first-order model theory)
 03C95 (Mathematical logic and foundations :: Model theory :: Abstract model theory)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)