You are here
Homechain
Primary tabs
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 $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 $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 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\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 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 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$.

$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 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}$.
Mathematics Subject Classification
0300 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
Chain from A to B
As far as I remember "chain from A to B" is defined as a maximal chain having A and B as min. and max. elements correspondingly. Do I remember correctly? If yes, then the entry "Chain" needs correction to say about "chain from A to B".
Also we should state how existence of chains from A to B is related with axiom of choice and Kuratowski's lemma in particular.

Victor Porton  http://www.mathematics21.org
* Algebraic General Topology and Math Synthesis
* 21 Century Math Method (post axiomatic math logic)
* Category Theory  new concepts
Re: Chain from A to B
> As far as I remember "chain from A to B" is defined
> as a maximal chain having A and B as min. and
> max. elements correspondingly. Do I remember
> correctly?
This is not correct. There is nothing that requires
that a chain from A to B be maximal.
> Also we should state how existence of chains from A
> to B is related with axiom of choice and Kuratowski's
> lemma in particular.
If $A \le B$, then there always exists a chain from A
to B, namely $\{A, B\}$. Choice is not required here.
The axiom of choice become relevant when we ask for a
maximal chain.
Re: Chain from A to B
>> As far as I remember "chain from A to B" is defined
>> as a maximal chain having A and B as min. and
>> max. elements correspondingly. Do I remember
>> correctly?
> This is not correct. There is nothing that requires
> that a chain from A to B be maximal.
Anyway we should define "a maximal chain from A to B" and just
"chain from A to B". (Should we now file a correction to "Chain"?)
Indeed my memory suggests that the word "maximal" can be omitted in this context accordingly definitions in some book. But my memory may be flaky.

Victor Porton  http://www.mathematics21.org
* Algebraic General Topology and Math Synthesis
* 21 Century Math Method (post axiomatic math logic)
* Category Theory  new concepts
Re: Chain from A to B
My experience is that most authors allow chains to be nonmaximal, and when they want maximal they say so. The same goes for flags (a synonym for chains in some contexts). A flag is not generally maximal, unless you add the prefix "maximal flag" One could certainly define chain this way, but I don't think it is standard, in particular because there are many many uses of chains, including in PM articles, which are not intended only for maximal chains.
For example, the parabolic subgroups are stabilizers of certain chains/flags of subspaces. If we only allowed maximal then all parabolics would be Borel, and that is simply not the case. In the same vein, one can define a simplicial complex from a poset by taking the faces to be all chains in the poset. If all chains were maximal you wouldn't get a simplicial complex and you would not have subfaces (that is, you would not have edges of 2simplex and vertices of 1simplex, etc.) These are just some ways that chain is used in very well established ways and were the assumption of maximal would not be feasable.
So no, I don't think this is a correction. I think the standard solution to such problems on PM is to attach an entry that defines maximal chain, and if you wish, state WITH REFERENCE (not flaky memory) that some authors assume all chains are maximal. (I say with reference because the references at my fingertips don't do this so I think it is a rare assumption and worth supporting if it is true.)