example of a universal structure
Let be the first order language with the binary relation . Consider the following sentences
:
- •
- •
Any -structure satisfying these is called a linear order.We define the relation
so that iff . Now consider these sentences:
- 1.
- 2.
A linear order that satisfies 1. is called dense (http://planetmath.org/DenseTotalOrder).We say that a linear order that satisfies 2. is without endpoints.Let be the theory of dense linear orders without endpoints. This is a complete theory.
We can see that is a model of . It is actually a rather special model.
Theorem 1
Let be any finite linear order. Then embeds in .
Proof: By induction on , it is trivial for .
Suppose that the statement holds for all linear orders with cardinality less than or equal to .Let , then pick some , let be the structure induced by on .Then there is some embedding of into .
- •
Now suppose is less than every member of , then as is without endpoints, there is some element less than every element in the image of .Thus we can extend to map to which is an embedding of into .
- •
We work similarly if is greater than every element in .
- •
If neither of the above hold then we can pick some maximum so that .Similarly we can pick some minimum so that . Now there is some with . Then extending by mapping to is the required embedding.
It is easy to extend the above result to countable structures.One views a countable structure as a the union of an increasing chain of finite substructures.The necessary embedding is the union of the embeddings of the substructures. Thus is universal
countable linear order.
Theorem 2
is homogeneous.
Proof: The following type of proof is known as a back and forth argument.Let and be two finite substructures of .Let be an isomorphism.It is easier to think of two disjoint copies and of with a substructure of and a substructure of .
Let be an enumeration of .Let be an enumeration of . We iterate the following two step process:
The th forth step If is already in the domain of then do nothing. If is not in the domain of .Then as in proposition 1, either is less than every element in the domain of or greater than or it has an immediate successor
and predecessor in the range of .Either way there is an element in relative to the range of .Thus we can extend the isomorphism to include .
The th back step If is already in the range of then do nothing. If is not in the domain of .Then exactly as above we can find some and extend so that .
After stages, we have an isomorphism whose range includes every and whose domain includes every . Thus we have an isomorphism from to extending .
A similar back and forth argument shows that any countable dense linear order without endpoints is isomorphic to so is -categorical.
Title | example of a universal structure |
Canonical name | ExampleOfAUniversalStructure |
Date of creation | 2013-03-22 13:23:16 |
Last modified on | 2013-03-22 13:23:16 |
Owner | uzeromay (4983) |
Last modified by | uzeromay (4983) |
Numerical id | 15 |
Author | uzeromay (4983) |
Entry type | Example |
Classification | msc 03C50 |
Classification | msc 03C52 |
Related topic | Homogeneous4 |
Related topic | KappaCategorical |
Related topic | DifferentialEquation |
Related topic | ExampleOfDefinableType |
Related topic | RandomGraph |
Defines | back and forth |