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

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

4. 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, there is an element $c$ such that $a.

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

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.

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

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