Scribd Logo
Upload

Welcome to Scribd!

  • 153 views

    Well Ordering Theorem

    Uploaded by

    Mike Jones
    This document defines key terms related to binary relations and partially ordered sets. It then presents the Well-Ordering Theorem, which states that every set can be well-ordered. The proof uses Zorn's Lemma, which guarantees a maximal element in a partially ordered set if every totally ordered subset has an upper bound. Specifically, it considers the set of all well-orderings on subsets of a given set X, and shows this set satisfies Zorn's Lemma and thus contains a maximal well-ordering - which must in fact be a well-ordering of all of X.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Well Ordering Theorem

    Uploaded by

    Mike Jones
    153 views2 pages
    This document defines key terms related to binary relations and partially ordered sets. It then presents the Well-Ordering Theorem, which states that every set can be well-ordered. The proof uses Zorn's Lemma, which guarantees a maximal element in a partially ordered set if every totally ordered subset has an upper bound. Specifically, it considers the set of all well-orderings on subsets of a given set X, and shows this set satisfies Zorn's Lemma and thus contains a maximal well-ordering - which must in fact be a well-ordering of all of X.

    Original Description:

    a fundamental result in General Topology email: [email protected] category: mkj mathematics

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document defines key terms related to binary relations and partially ordered sets. It then presents the Well-Ordering Theorem, which states that every set can be well-ordered. The proof uses Zorn's Lemma, which guarantees a maximal element in a partially ordered set if every totally ordered subset has an upper bound. Specifically, it considers the set of all well-orderings on subsets of a given set X, and shows this set satisfies Zorn's Lemma and thus contains a maximal well-ordering - which must in fact be a well-ordering of all of X.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    153 views2 pages

    Well Ordering Theorem

    Uploaded by

    Mike Jones
    This document defines key terms related to binary relations and partially ordered sets. It then presents the Well-Ordering Theorem, which states that every set can be well-ordered. The proof uses Zorn's Lemma, which guarantees a maximal element in a partially ordered set if every totally ordered subset has an upper bound. Specifically, it considers the set of all well-orderings on subsets of a given set X, and shows this set satisfies Zorn's Lemma and thus contains a maximal well-ordering - which must in fact be a well-ordering of all of X.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    The Well-Ordering Theorem

    page 1 of 2

    Definition 1. If each of A and B is a set, then the Cartesian product of A and B, denoted by
    A  B, is the set {(a,b) | a  A and b  B}.

    Definition 2. A binary relation on a given set is any subset of the Cartesian product of the set
    with itself.

    Definition 3. If R is a binary relation on a given set, then aRb means (a,b)  R.

    Definition 4. If R is a binary relation on a given set, then R is said to be reflexive if, and only if,
    for each x in the given set, xRx.

    Definition 5. If R is a binary relation on a given set, then R is said to be symmetric if, and only if,
    for each x in the given set and for each y in the given set, if xRy, then yRx.

    Definition 6. If R is a binary relation on a given set, then R is said to be anti-symmetric if, and
    only if, for each x in the given set and for each y in the given set, if xRy and yRx, then x = y.

    Definition 7. If R is a binary relation on a given set, then R is said to be transitive if, and only if,
    for each x in the given set and for each y in the given set and for each z in the given set,
    if xRy and yRz, then xRz.

    Definition 8. A partial order on a given set is a binary relation on the set such that the binary
    relation is reflexive, anti-symmetric, and transitive. The set, with regard to a given partial order
    on it, is called a partially ordered set.

    Definition 9. If R is a binary relation on a given set, then for each x in the set and for each y in
    the set, x and y are said to be related (with respect to R) if, and only if, xRy or yRx.

    Definition 10. A totally ordered subset of a given partially ordered set is a subset of the given
    partially ordered set such that every two members of the subset are related.

    Definition 11. If H is a subset of a given partially ordered set, then an upper bound for H is any
    member p of the given partially ordered set such that for each x in H, xRp, where R is the given
    partial order.

    In the development leading to the presentation of a specific result, it often happens that we wish
    to use certain theorems as axioms. That is, we do not wish to prove those theorems – their proof
    being readily available in the literature – nor do we wish to focus attention on them. To this end,
    we will use the term ‘synapse’ for such theorems.

    Synapse. (Zorn’s Lemma) If every totally ordered subset of a given partially ordered set has an
    upper bound, then the partially ordered set has a maximal element.

    Theorem. (Well-Ordering Theorem) Every set can be well-ordered.


    The Well-Ordering Theorem
    page 2 of 2

    Proof:
    Suppose X is a set.
    Let A be the set of well-orderings on subsets of X. (That is, an element of A is an ordered pair
    (a,b), where a is a subset of X and b is a well-ordering of a.)
    A can be partially ordered by continuation. That is, E  F if, and only if, E is an initial segment
    of F and the ordering of the members of E is the same as their ordering in F. If T is a totally
    ordered subset of A, then the union of the sets in T can be ordered in a way that makes it a
    continuation of any set in T; this ordering is a well-ordering, and therefore an upper bound of T
    in A. Therefore, by Zorn’s Lemma, A has a maximal element, say (M,R).
    Suppose that M does not equal X.
    Then there exists an element x of X such that x  M.
    Then M  {x} has a well-ordering that restricts to R on M, and for which x is larger than each
    element of M. This well-ordered set is a continuation of (M,R), contradicting maximality.
    Therefore, M = X. Therefore, R is a well-ordering for X. Therefore, X can be well-ordered. █

    (end of document)

    You might also like