PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very low Entry average rating: No information on entry rating
[parent] example of a universal structure (Example)

Let $ L$ be the first order language with the binary relation $ \leq$. Consider the following sentences:

  • $ \forall x,y ((x\leq y \lor y\leq x) \land ((x \leq y \land y\leq x )\leftrightarrow x=y))$
  • $ \forall x,y,z (x \leq y \land y \leq z \rightarrow x \leq z)$
Any $ L$-structure satisfying these is called a linear order. We define the relation $ <$ so that $ x<y$ iff $ x \leq y \land x \neq y$. Now consider these sentences:
  1. $ \forall x,y ((x < y \rightarrow \exists z(x<z<y))$
  2. $ \forall x \exists y,z(y<x <z)$
A linear order that satisfies 1. is called dense. 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 $ (\mathbb{Q},\leq)$ is a model of $ T$. It is actually a rather special model.

Theorem 1   Let $ (S,\leq)$ be any finite linear order. Then $ S$ embeds in $ (\mathbb{Q},\leq)$.
Proof: By induction on $ \vert S\vert$, it is trivial for $ \vert S\vert=1$.

Suppose that the statement holds for all linear orders with cardinality less than or equal to $ n$. Let $ \vert S\vert=n+1$, then pick some $ a \in S$, let $ S^{\prime}$ be the structure induced by $ S$ on $ S\setminus {a}$. Then there is some embedding $ e$ of $ S^{\prime}$ into $ \mathbb{Q}$.

  • Now suppose $ a$ is less than every member of $ S^{\prime}$, then as $ \mathbb{Q}$ 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 $ \mathbb{Q}$.
  • We work similarly if $ a$ is greater than every element in $ S^{\prime}$.
  • If neither of the above hold then we can pick some maximum $ c_{1} \in S^{\prime}$ so that $ c_{1}<a$. Similarly we can pick some minimum $ c_{2} \in S^{\prime}$ so that $ c_{2}<a$. Now there is some $ b \in \mathbb{Q}$ with $ e(c_{1})<b<e(c_{2})$. Then extending $ e$ by mapping $ a$ to $ b$ is the required embedding. $ \square$

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 $ (\mathbb{Q},\leq)$ is universal countable linear order.

Theorem 2   $ (\mathbb{Q},\leq)$ is homogeneous.
Proof: The following type of proof is known as a back and forth argument. Let $ S_{1}$ and $ S_{2}$ be two finite substructures of $ (\mathbb{Q},\leq)$. Let $ e:S_{1} \to S_{2}$ be an isomorphism. It is easier to think of two disjoint copies $ B$ and $ C$ of $ \mathbb{Q}$ with $ S_{1}$ a substructure of $ B$ and $ S_{2}$ a substructure of $ C$.

Let $ b_{1},b_{2},\ldots$ be an enumeration of $ B \setminus S_{1}$. Let $ c_{1},c_{2},\ldots,c_{n}$ be an enumeration of $ C \setminus S_{2}$. We iterate the following two step process:

The $ i$th forth step If $ b_{i}$ is already in the domain of $ e$ then do nothing. If $ b_{i}$ is not in the domain of $ e$. Then as in proposition 1, either $ b_{i}$ is less than every element in the domain of $ e$ or greater than or it has an immediate successor and predecessor in the range of $ e$. Either way there is an element $ c$ in $ C \setminus\operatorname{range}(e)$ relative to the range of $ e$. Thus we can extend the isomorphism to include $ b_{i}$.

The $ i$th back step If $ c_{i}$ is already in the range of $ e$ then do nothing. If $ c_{i}$ is not in the domain of $ e$. Then exactly as above we can find some $ b \in B \setminus \operatorname{dom}(e)$ and extend $ e$ so that $ e(b)=c_{i}$.

After $ \omega$ stages, we have an isomorphism whose range includes every $ b_{i}$ and whose domain includes every $ c_{i}$. Thus we have an isomorphism from $ B$ to $ C$ extending $ e$. $ \square$

A similar back and forth argument shows that any countable dense linear order without endpoints is isomorphic to $ (\mathbb{Q},\leq)$ so $ T$ is $ \aleph_{0}$-categorical.



"example of a universal structure" is owned by uzeromay. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: homogeneous, $\kappa$-categorical, differential equation, example of definable type, random graph (infinite)

Also defines:  back and forth

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: isomorphic, similar, range, successor, domain, iterate, enumeration, disjoint, argument, type, homogeneous, universal, necessary, substructures, chain, increasing, union, countable, map, image, embedding, induced, structure, cardinality, induction, finite, complete theory, dense linear orders, theory, endpoints, iff, relation, linear order, sentences, binary relation, first order language
There is 1 reference to this entry.

This is version 12 of example of a universal structure, born on 2003-01-24, modified 2007-02-08.
Object id is 3925, canonical name is ExampleOfUniversalStructure.
Accessed 5658 times total.

Classification:
AMS MSC: 03C50 (Mathematical logic and foundations :: Model theory :: Models with special properties )
 03C52 (Mathematical logic and foundations :: Model theory :: Properties of classes of models)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)