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 (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
chain (Definition)

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 $ a<b$. 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}:=\lbrace 1, 2, \ldots, n\rbrace$ is a chain under the usual order ($ a\le 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\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 for detail).

With these two methods, one can construct many more examples of chains:

  1. Take $ \mathbb{R}$, and form $ A=\mathbb{R}\coprod \lbrace a\rbrace$. Then $ A$ is a chain with a top element. If we take $ B=\lbrace b\rbrace \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 $ \lbrace A_i\mid i\in I\rbrace$ 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 $ 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}$.



"chain" is owned by CWoo. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

Also defines:  finite chain, infinite chain, dense chain, complete chain, join of chains, chain homomorphism
Log in to rate this entry.
(view current ratings)

Cross-references: well-ordering, dense, properties, isomorphic, strictly, strict, one-to-one, homomorphic image, preserves, homomorphism, function, long line, lexicographic order, indexed by, NOR, complete, disjoint union, join, infimum, supremum, bounded, Dedekind complete, integers, axiom of choice, states, well-ordering principle, reals, rationals, positive, minimal element, well-ordered set, natural numbers, induced, onto, bijection, finite set, finite, iff, order, cardinality, linearly ordered, total order, comparable, subset, poset
There are 22 references to this entry.

This is version 7 of chain, born on 2002-01-05, modified 2007-07-19.
Object id is 1344, canonical name is Chain.
Accessed 5646 times total.

Classification:
AMS MSC: 03-00 (Mathematical logic and foundations :: General reference works )
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy
Chain from A to B by porton on 2007-02-13 14:34:20
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
[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)