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 .
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 |