example of a universal structure


Let L be the first order language with the binary relationMathworldPlanetmath . Consider the following sentencesMathworldPlanetmath:

  • x,y((xyyx)((xyyx)x=y))

  • x,y,z(xyyzxz)

Any L-structureMathworldPlanetmath satisfying these is called a linear order. We define the relationMathworldPlanetmathPlanetmath < so that x<y iff xyxy. Now consider these sentences:

  1. 1.

    x,y((x<yz(x<z<y))

  2. 2.

    xy,z(y<x<z)

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 T be the theory of dense linear orders without endpoints. This is a complete theory.

We can see that (,) is a model of T. It is actually a rather special model.

Theorem 1

Let (S,) be any finite linear order. Then S embeds in (Q,).

Proof: By inductionMathworldPlanetmath on |S|, it is trivial for |S|=1.

Suppose that the statement holds for all linear orders with cardinality less than or equal to n. Let |S|=n+1, then pick some aS, let S be the structure induced by S on Sa. Then there is some embeddingPlanetmathPlanetmath e of S into .

  • Now suppose a is less than every member of S, then as is without endpoints, there is some element b less than every element in the image of e. Thus we can extend e to map a to b which is an embedding of S into .

  • We work similarly if a is greater than every element in S.

  • If neither of the above hold then we can pick some maximum c1S so that c1<a. Similarly we can pick some minimum c2S so that c2<a. Now there is some b with e(c1)<b<e(c2). Then extending e by mapping a to b is the required embedding.

It is easy to extend the above result to countableMathworldPlanetmath 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 universalPlanetmathPlanetmathPlanetmath countable linear order.

Theorem 2

(,) is homogeneousPlanetmathPlanetmath.

Proof: The following type of proof is known as a back and forth argument. Let S1 and S2 be two finite substructures of (,). Let e:S1S2 be an isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. It is easier to think of two disjoint copies B and C of with S1 a substructure of B and S2 a substructure of C.

Let b1,b2, be an enumeration of BS1. Let c1,c2,,cn be an enumeration of CS2. We iterate the following two step process:

The ith forth step If bi is already in the domain of e then do nothing. If bi is not in the domain of e. Then as in propositionPlanetmathPlanetmath 1, either bi is less than every element in the domain of e or greater than or it has an immediate successorMathworldPlanetmathPlanetmathPlanetmath and predecessor in the range of e. Either way there is an element c in Crange(e) relative to the range of e. Thus we can extend the isomorphism to include bi.

The ith back step If ci is already in the range of e then do nothing. If ci is not in the domain of e. Then exactly as above we can find some bBdom(e) and extend e so that e(b)=ci.

After ω stages, we have an isomorphism whose range includes every bi and whose domain includes every ci. Thus we have an isomorphism from B to C extending e.

A similar back and forth argument shows that any countable dense linear order without endpoints is isomorphic to (,) so T is 0-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