chain

Introduction

Let $A$ be a poset ordered by $\leq$ . 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\leq b$ or $b\leq a$ , that is, $\leq$ is a total order on $B$ , or that $B$ is a linearly ordered subset of $A$ . When $a\leq b$ , we also write $b\geq a$ . When $a\leq b$ and $a\neq b$ , we write $a<b$ . When $a\geq b$ and $a\neq 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,\ldots,n\}$ is a chain under the usual order ( $a\leq b$ iff $b-a$ is non-negative). 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 well-ordered set: a chain such that every non-empty subset has a minimal element (as in a poset). Other well-ordered sets are the set $\mathbb{Q}^{+}$ of positive rationals and $\mathbb{R}^{+}$ of positive reals. The well-ordering principle states that every set can be well-ordered. It can be shown that the axiom of choice is equivalent to the well-ordering 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 $a<b$ , there is an element $c$ such that $a<c<b$ .
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 non-empty 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\leq b$ in $A^{\partial}$ iff $b\leq 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)\leq(b,j)$ iff either $i=j$ and $a\leq b$ , or $i<j$ .

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 well-order $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 one-to-one. 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 well-ordered, 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 $i<k$ .
•

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 $i<k$ and $f(a,i)=y$ if $k<i$ .

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 non-negative integers $m, n$ and $p$ .
•

$\mathbf{n}\coprod\mathbb{N}\cong\mathbb{N}$ for any non-negative 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 well-ordering. Then $\coprod_{i\in I}\mathbb{R}\ncong\coprod_{j\in J}\mathbb{R}$ .

Title	chain
Canonical name	Chain
Date of creation	2013-03-22 12:09:12
Last modified on	2013-03-22 12:09:12
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	11
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03-00
Defines	finite chain
Defines	infinite chain
Defines	dense chain
Defines	complete chain
Defines	join of chains
Defines	chain homomorphism