example of a universal structure
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.
Let be any finite linear order. Then embeds in .
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.
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 .
|Title||example of a universal structure|
|Date of creation||2013-03-22 13:23:16|
|Last modified on||2013-03-22 13:23:16|
|Last modified by||uzeromay (4983)|
|Defines||back and forth|