Age (model theory)
It has been suggested that this article be merged with Fraïssé's theorem. (Discuss) Proposed since December 2019. |
In model theory, the age of a structure (or model) A is the class of all finitely generated structures that are embeddable in A (i.e. isomorphic to substructures of A). This concept is central in the construction of a Fraïssé limit.
The main point of Fraïssé's construction is to show how one can approximate a structure by its finitely generated substructures. Thus for example the age of any dense linear order without endpoints (DLO), is precisely the class of all finite linear orderings, which are distinguished up to isomorphism only by their size. Thus the age of any DLO is essentially countable (that is, it contains only countably many isomorphism classes). This shows in a way that a DLO is a kind of limit of finite linear orderings.
One can easily see that any class K that is an age of some structure satisfies the following two conditions:
- Hereditary property
- If A ∈ K and B is a finitely generated substructure of A, then B is isomorphic to a structure in K
- Joint embedding property
- If A and B are in K then there is C in K such that both A and B are embeddable in C.
Fraïssé proved the converse result: when K is any non-empty countable set of finitely generated σ-structures (with σ a signature) that has the above two properties, then it is an age of a countable structure.
Furthermore, suppose that K happens to satisfy the following additional properties.
- Amalgamation property
- For any structures A, B and C in K such that A is embeddable in both B and C, there exists D in K to which B and C are both embeddable by embeddings that coincide on the image of A in both structures.
- Essential countability
- up to isomorphism, there are countably many structures in K.
In that case, we say that K is a Fraïssé class, and there is a unique up to isomorphism countable structure which is homogeneous and whose age is exactly K. This structure is called the Fraïssé limit of K . In this context, 'homogeneous' means that any isomorphism between two finitely generated substructures can be extended to an automorphism of the whole structure. Again, an example of this situation is the ordered set of rational numbers . It is the unique (up to isomorphism) homogeneous countable structure whose age is the set of all finite linear orderings. Note that the ordered set of natural numbers has the same age as a DLO, but it is not homogeneous since if we map {1, 3} to {5, 6}, it would not extend to any automorphism f since there should be an element between and . The same applies to integers.
Furthermore, K may satisfy the additional property of being uniformly locally finite, which means that for every n, there is a uniform bound on the size of an n-generated substructure. This condition is equivalent to the Fraïssé limit of K being ω-categorical. For example, the class of finite dimensional vector spaces over a fixed field is always a Fraïssé class, but it is uniformly locally finite only if the field is finite.
References
- Hodges, Wilfrid (1997). A shorter model theory. Cambridge University Press. ISBN 0-521-58713-1.