chain
Introduction
Let $A$ be a poset ordered by $\le $. A subset $B$ of $A$ is called a chain in $A$ if any two elements of $B$ are comparable^{}. In other words, if $a,b\in B$, then either $a\le b$ or $b\le a$, that is, $\le $ is a total order^{} on $B$, or that $B$ is a linearly ordered subset of $A$. When $a\le b$, we also write $b\ge a$. When $a\le b$ and $a\ne b$, we write $$. When $a\ge b$ and $a\ne b$, then we write $a>b$. A poset is a chain if it is a chain as a subset of itself. The cardinality of a chain is the cardinality of the underlying set.
Below are some common examples of chains:

1.
$\mathbf{n}:=\{1,2,\mathrm{\dots},n\}$ is a chain under the usual order ($a\le b$ iff $ba$ is nonnegative). This is an example of a finite chain: a chain whose cardinality is finite. Any finite set^{} $A$ can be made into a chain, since there is a bijection from $\mathbf{n}$ onto $A$, and the total order on $A$ is induced by the order on $\mathbf{n}$. A chain that is not finite is called an infinite chain.

2.
$\mathbb{N}$, the set of natural numbers, is a chain under the usual order. Here we have an example of a wellordered set: a chain such that every nonempty subset has a minimal element (as in a poset). Other wellordered sets are the set ${\mathbb{Q}}^{+}$ of positive rationals and ${\mathbb{R}}^{+}$ of positive reals. The wellordering principle states that every set can be wellordered. It can be shown that the axiom of choice^{} is equivalent^{} to the wellordering principle.

3.
$\mathbb{Z}$, the set of integers, is a chain under the usual order.

4.
$\mathbb{Q}$, the set of rationals, is a chain under the usual order. This is an example of a dense chain: a chain such that for every pair of distinct elements $$, there is an element $c$ such that $$.

5.
$\mathbb{R}$, the set of reals, is a chain under the usual order. This is an example of a Dedekind complete chain: a chain such that every nonempty bounded^{} subset has a supremum^{} and an infimum^{}.
Constructing chains
One easy way to produce a new chain from an existing one is to form the dual of the existing chain: if $A$ is a chain, form ${A}^{\partial}$ so that $a\le b$ in ${A}^{\partial}$ iff $b\le a$ in $A$.
Another way to produce new chains from existing ones is to form a join of chains. Given two chains $A,B$, we can form a new chain $A\coprod B$. The basic idea is to form the disjoint union^{} of $A$ and $B$, and order this newly constructed set so that the order among elements of $A$ is preserved, and similarly for $B$. Furthermore, any element of $A$ is always less than any element of $B$ (See here (http://planetmath.org/AlternativeTreatmentOfConcatenation) for detail).
With these two methods, one can construct many more examples of chains:

1.
Take $\mathbb{R}$, and form $A=\mathbb{R}\coprod \{a\}$. Then $A$ is a chain with a top element. If we take $B=\{b\}\coprod A$, we get a chain with both a top and a bottom element. In fact, $B$ is an example of a complete chain: a chain such that every subset has a supremum and an infimum. Observe that any finite chain is complete^{}.

2.
We can form ${\mathbb{N}}^{\partial}$ which is a set with $1$ as the top element. We can also form ${\mathbb{N}}^{\partial}\coprod \mathbb{N}$, which has neither top nor bottom, or $\mathbb{N}\coprod {\mathbb{N}}^{\partial}$, which has both a top and a bottom element, but is not complete, as $\mathbb{N}$, considered as a subset, has no top. Likewise, ${\mathbb{N}}^{\partial}$ is bottomless.
The idea of joining two chains can be generalized. Let $\{{A}_{i}\mid i\in I\}$ be a family of chains indexed by $I$, itself a chain. We form ${\coprod}_{i\in I}{A}_{i}$ as follows: take the disjoint union of ${A}_{i}$, which we also write as ${\coprod}_{i\in I}{A}_{i}$. Then $(a,i)\le (b,j)$ iff either $i=j$ and $a\le b$, or $$.
For example, let $I=\mathbb{R}$ and ${A}_{i}=\mathbb{R}$, with $i\in I$. Then ${\coprod}_{i\in I}{A}_{i}$ is a chain, whose total order is the lexicographic order^{} on ${\mathbb{R}}^{2}$. If we wellorder $I=\mathbb{R}$, then ${\coprod}_{i\in I}{A}_{i}$ is another chain called the long line.
Chain homomorphisms
Let $A,B$ be chains. A function $f$ from $A$ to $B$ is said to be a chain homomorphism if it is a poset homomorphism^{} (it preserves order). $f(A)$ is the homomorphic image of $A$ in $B$. Two chains are homomorphic if there is a chain homomorphism from one to another. A chain homomorphism is an embedding^{} if it is onetoone. If $A$ embeds in $B$, we write $A\subseteq B$. A strict embedding is an embedding that is not onto. If $A$ strictly embeds in $B$, we write $A\subset B$. An onto embedding is also called an isomorphism^{}. If $A$ is isomorphic to $B$, we write $A\cong B$.
Some properties:

•
Two finite chains are isomorphic iff they have the same cardinality.

•
Top and bottom elements are preserved by chain isomorphisms. In other words, if $f:A\to B$ is a chain isomorphism and if $a\in A$ is the top (bottom) element, then $f(a)$ is the top (bottom) element in $B$.

•
In addition, the properties of being wellordered, dense, Dedekind complete, and complete are all preserved under a chain isomorphism.

•
$A\subseteq A\coprod B$. More generally ${A}_{i}\subseteq {\coprod}_{i\in I}{A}_{i}$.

•
$(A\coprod B)\coprod C\cong A\coprod (B\coprod C)$.

•
If $k$ is the bottom element of $I$, and ${A}_{k}$ has a top element $x$, then there is a chain homomorphism $f:{\coprod}_{i\in I}{A}_{i}\to {A}_{k}$ given by $f(a,i)=a$ if $i=k$ and $f(a,i)=x$ if $i>k$.

•
Dually, if $k$ is the top of $I$ and ${A}_{k}$ has a bottom $x$, then there is a chain homomorphism $f:{\coprod}_{i\in I}{A}_{i}\to {A}_{k}$ given by $f(a,i)=a$ if $i=k$ and $f(a,i)=x$ if $$.

•
If ${A}_{k}$ has both a bottom $x$ and a top $y$, then we may define $f:{\coprod}_{i\in I}{A}_{i}\to {A}_{k}$ by $f(a,i)=a$ if $i=k$, $f(a,i)=x$ if $$ and $f(a,i)=y$ if $$.
Some examples:

•
$\mathbf{n}\subset \mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q}\subset \mathbb{R}$.

•
$\mathbf{n}\coprod \mathbf{m}\cong \mathbf{p}$ iff $p=m+n$ for any nonnegative integers $m,n$ and $p$.

•
$\mathbf{n}\coprod \mathbb{N}\cong \mathbb{N}$ for any nonnegative integer $n$.

•
$\mathbb{N}\coprod {\mathbb{N}}^{\partial}\ncong {\mathbb{N}}^{\partial}\coprod \mathbb{N}$.

•
Let $I$ be the chain over $\mathbb{R}$ under the usual order, and $J$ the chain over $\mathbb{R}$ under a wellordering. Then ${\coprod}_{i\in I}\mathbb{R}\ncong {\coprod}_{j\in J}\mathbb{R}$.
Title  chain 
Canonical name  Chain 
Date of creation  20130322 12:09:12 
Last modified on  20130322 12:09:12 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 0300 
Defines  finite chain 
Defines  infinite chain 
Defines  dense chain 
Defines  complete chain 
Defines  join of chains 
Defines  chain homomorphism 