|
|
|
|
properties of well-ordered sets
|
(Theorem)
|
|
|
The purpose of this entry is to collect properties of well-ordered sets. We denote all orderings uniformly by . If you are interested in history, have a look at [C].
The following properties are easy to see:
Now we define an important ingredient for understanding the structure of well-ordered sets.
Definition 1 (section) Let  be well-ordered. Then for every  we define the section of  :
A section is also known as an initial segment. We denote the set of all sections of  by
 . This set is ordered by inclusion.
Theorem 1 Let be a well-ordered set. Then the mapping
defined by
is a bijective order morphism. In particular,
is well-ordered.
Proof. Let  with  . Then
 , so
 is an order morphism. Now assume that
 . If  didn't equal  , we would have
 , leading to a contradiction. Therefore
 is injective. Now let
 , then there exists a  such that
 , so
 is surjective. 
Theorem 2 Let and be well-ordered sets and
a bijective order morphism. Then there exists a bijective order morphism
such that for all
Proof. Setting
 is well-defined by Theorem 1. The rest of the theorem follows since
 and  are bijective order morphisms. 
Theorem 3 Let be a well-ordered set and such that there is an injective order morphism
. Then
.
Proof. The image of a section of  under  has a maximal element which in turn defines a smaller section of  . We may therefore define the following two monotonically decreasing sequences of sets:
 |
 |
 |
section defined by maximal element of  |
|
 |
 |
 |
section defined by maximal element of  |
|
Now
 is well-ordered, so the set defined by the elements of the sequence  has a minimal element, that is
 and hence
 for some sufficiently large  . Applying
 times to the latter equation yields
 , that is  is the maximal element of  , and thus of  . 
Theorem 4 Let and be well-ordered sets. Then there exists at most one bijective order morphism
.
Proof. Let
 be two bijective order morphisms. Let  and set
 and
 . Then the restrictions
 and
 are bijective order morphisms, so the restriction of
 to
 is a bijective order morphism to
 . Now either
 or
 , so by Theorem 3
 , hence  and thus
 . 
Theorem 5 Let and be well-ordered sets such that for every section
there is a bijective order morphism to a section
and vice-versa, then there is a bijective order morphism
.
Proof. Let  and let
 be a section such that there is a bijective order morphism
 . By Theorem 3,
 is unique, and so is  by Theorem 4. Defining
 by setting
 gives therefore a well-defined (by Theorem ![[*] [*]](http://images.planetmath.org:8080/cache/objects/7231/l2h//usr/share/latex2html/icons/crossref.png) ) and injective order morphism. But  is also surjective, since any maps uniquely to  via
 , and back again by  . 
Theorem 6 Let and be well-ordered sets. Then there is an injective order morphism
or
. If cannot be chosen bijective, then it can at least be chosen such that its image is a section.
Proof. Let
 be the set of sections of  from which there is an injective order morphism to  . If
 is the empty set, then  must be empty, since otherwise we could map the least element of  to  . If
 is not empty, we may consider the set
 . If  , nothing remains to be shown. Otherwise the set
 is nonempty an hence has a least element  . By construction, there is no injective order morphism from
 to  , but there is an injective order morphism from
 for every element  which is strictly smaller than  . Now assume there is an element  such that there is no injective order morphism from
 . Then we can similarly construct a least element  for which there is no injective order morphism
 . Surely,  is greater than all the elements from the images of the functions  , but then there is a bijective order morphism from
 to
 by Theorem 5 which is a contradiction. Therefore, all sections of  and  itself map injectively and order-preserving to  . 
Theorem 7 Let be a well-ordered set and
a nonempty subset. Then there is a bijective order morphism from to one of the sets in
.
Proof. The set  is well-ordered with respect to the order induced by  . Assume a bijective order morphism as stated by the theorem does not exist. Then, by virtue of Theorem 6, there is an injective but not surjective order morphism
 whose image is a section
 . The element  defines a section in
 which is identical to  by Theorem 3. Thus  is surjective which is a contradiction. 
- C
- G. CANTOR, Beiträge zur Begründung der transfiniten Mengenlehre (Zweiter Artikel), Math. Ann. 49, 207-246 (1897).
|
Anyone with an account can edit this entry. Please help improve it!
"properties of well-ordered sets" is owned by GrafZahl. [ full author list (4) ]
|
|
(view preamble)
| Other names: |
initial segment |
This object's parent.
|
|
Cross-references: functions, empty set, maps, restrictions, equation, minimal element, sequences, monotonically decreasing, maximal element, image, well-defined, surjective, injective, contradiction, mapping, inclusion, structure, order morphism, bijective, poset, well-ordered, least element, strictly, subset, totally ordered set, easy to see, properties, orderings
There are 6 references to this entry.
This is version 6 of properties of well-ordered sets, born on 2005-07-16, modified 2008-04-30.
Object id is 7231, canonical name is PropertiesOfWellOrderedSets.
Accessed 3266 times total.
Classification:
| AMS MSC: | 06A05 (Order, lattices, ordered algebraic structures :: Ordered sets :: Total order) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|