Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Ord well-ordered by ∈

  1. Dec 25, 2011 #1

    jgens

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Let Ord denote the class of ordinals. Prove that Ord is is transitive and well-ordered by ∈.

    2. Relevant equations

    • A set X is called transitive if x ∈ X and y ∈ x imply y ∈ X.
    • A set X is called ordinal if it is transitive and well-ordered by ∈.
    • A total order (X,<) is well-ordered if and only if there does not exist an infinite descending sequence.

    3. The attempt at a solution

    Suppose X ∈ Ord and fix x ∈ X. If y ∈ x, then y ∈ X since X is an ordinal. If z ∈ y, then z ∈ X by the previous sentence. Since z ∈ y and y ∈ x, it follows that z ∈ x since X is well-ordered by ∈. This proves x is transitive.

    If y ∈ x, we clearly have ~(y ∈ y). If y1,y2,y3 ∈ x are such that y3 ∈ y2 and y2 ∈ y1, then y3 ∈ y1 since ∈ is a well-order on X. If z1,z2 ∈ x, then since ∈ is well-order on X, one and only one of the following holds: 1) z1 ∈ z2 2) z1 = z2 3) z2 ∈ z1. Lastly, suppose there is some infinite descending sequence a0 ∋ a1 ∋ ... in x. But since x ∋ a0 ∋ a1 ∋ ... is an infinite descending sequence in X and X is well-order by ∈, this is a contradiction. This proves x is well-ordered by ∈. In particular, x ∈ Ord, proving that Ord is transitive.

    If X ∈ Ord, then we clearly have ~(X ∈ X). If X,Y,Z ∈ Ord are such that X ∈ Y and Y ∈ Z, then X ∈ Z since Z is transitive. We show that ∈ is a total order with the following argument:

    If X,Y ∈ Ord, then Z = X∩Y is transitive. Let x denote the least element of X-Z and let y denote the least element of Y-Z. Suppose w ∈ x but ~(w ∈ Z). Then w ∈ X since X is transitive. But then w is the least element of X-Z, which is a contradiction. This means w ∈ Z, so x is a subset of Z. Conversely, if w ∈ Z but ~(w ∈ x), then x ∈ w. But then x ∈ Z which is a contradiction. This means x = Z. Arguing similarly shows that x = Z = y. Since x = y, we should have x ∈ z, which is absurd. This means Z = X or Z = Y. In particular, we have that one and only one of the following holds: 1) X ⊂ Y 2) X = Y 3) Y ⊂ X. Now suppose X ⊂ Y = X and let y denote the least element of Y-X. Since the elements of y are precisely the elements of x, this means X ∈ Y. This proves that Ord is well-ordered by ∈.

    Now suppose X0 ∋ X1 ∋ ... is an infinite descending sequence in Ord. But then X1 ∋ X2 ∋ ... is an infinite descending sequence in X0 which contradicts the fact that X is well-ordered. This completes the proof.


    My primary question is whether or not my argument for why Ord is well-ordered can be simplified. If it can, I would love suggestions.
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted