|
|
|
|
|
Let be a poset ordered by . A subset of is called a chain in if any two elements of are comparable. In other words, if , then either or , that is, is a total order on , or that is a linearly ordered subset of . When , we also write . When and , we write . When and , then we
write . 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:
-
is a chain under the usual order ( iff is non-negative). This is an example of a finite chain: a chain whose cardinality is finite. Any finite set can be made into a chain, since there is a bijection from
onto , and the total order on is induced by the order on
. A chain that is not finite is called an infinite chain.
-
, 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
of positive rationals and
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.
-
, the set of integers, is a chain under the usual order.
-
, 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 such that .
-
, 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.
One easy way to produce a new chain from an existing one is to form the dual of the existing chain: if is a chain, form
so that in
iff in .
Another way to produce new chains from existing ones is to form a join of chains. Given two chains , we can form a new chain
. The basic idea is to form the disjoint union of and , and order this newly constructed set so that the order among elements of is preserved, and similarly for . Furthermore, any element of is always less than any element of (See here for detail).
With these two methods, one can construct many more examples of chains:
- Take
, and form
. Then is a chain with a top element. If we take
, we get a chain with both a top and a bottom element. In fact, 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.
- We can form
which is a set with as the top element. We can also form
, which has neither top nor bottom, or
, which has both a top and a bottom element, but is not complete, as
, considered as a subset, has no top. Likewise,
is bottomless.
The idea of joining two chains can be generalized. Let
be a family of chains indexed by , itself a chain. We form
as follows: take the disjoint union of , which we also write as
. Then
iff either and , or .
For example, let
and
, with . Then
is a chain, whose total order is the lexicographic order on
. If we well-order
, then
is another chain called the long line.
Let be chains. A function from to is said to be a chain homomorphism if it is a poset homomorphism (it preserves order). is the
homomorphic image of in . 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 embeds in , we write
. A strict embedding is an embedding that is not onto. If strictly embeds in , we write
. An onto embedding is also called an isomorphism. If is isomorphic to , we write .
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
is a chain isomorphism and if is the top (bottom) element, then is the top (bottom) element in .
- In addition, the properties of being well-ordered, dense, Dedekind complete, and complete are all preserved under a chain isomorphism.
-
. More generally
.
-
.
- If
is the bottom element of , and has a top element , then there is a chain homomorphism
given by if and if .
- Dually, if
is the top of and has a bottom , then there is a chain homomorphism
given by if and if .
- If
has both a bottom and a top , then we may define
by if , if and if .
Some examples:
-
.
-
iff for any non-negative integers and .
-
for any non-negative integer .
-
.
- Let
be the chain over
under the usual order, and the chain over
under a well-ordering. Then
.
|
"chain" is owned by CWoo. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
| Also defines: |
finite chain, infinite chain, dense chain, complete chain, join of chains, chain homomorphism |
|
|
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
|
|
|
|
|
|
|
|
|
|
|