Results 1 to 3 of 3

Math Help - Set theory: Show these are equivalent.

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Set theory: Show these are equivalent.

    Show that the following are equivalent:

    a). A is finite
    b). A admits a well order <whose inverse> is also a well-order.
    c). The structure (\mathcal{P}(A), \subset_{\mathcal{P}(A)}) is well-founded: that is every S \subset \mathcal{P}(A) has a \subset-minimal element.
    I decided to go for a) \Rightarrow b) \Rightarrow c) \Rightarrow a).

    For a) \Rightarrow b):

    Assign each element of A an ordinal number. Since A is finite, and there are an infinite number of ordinals, we will always be able to do this. We can then order the ordinals (and the elements of A they represent) in the following way:

    ie. \phi, \{ \phi \}, \{\phi, \{ \phi \} \} \  \ldots

    or: \phi, \ \mathcal{P}(\phi), \ \mathcal{P}\mathcal{P} (\phi ), \ \ldots

    This is a partial order and since every element contains \phi, every non-empty subset contains a least element.

    For b) \Rightarrow c)

    If we take any S \subset \mathcal{P}(A), S contains sets of elements of A.
    Since A is well-ordered, each of the subsets of S has a least element.
    We can take all these least elements and make a new set.
    We can repeat this argument until we get a singleton set (the number of steps required to do this is equal to |S|).
    This singleton set is the \subset-minimal element.

    For c) \Rightarrow a) I run into some trouble.

    I figured the best way was to use a proof by contradiction. So suppose A is infinite.
    Let S be any subset of \mathcal{P}(A) and let B \subset \mathcal{P}(A) be the \subset-minimal element of S.

    I think I need to show that \mathcal{P}(A) is finite which is equivalent to a finite number of B \subset \mathcal{P}(A). Are there any tips for this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    The problem depends on what your previous definition of 'finite' is.

    And it would help to know what previous theorems have been established.

    What book are you working from? Suppes maybe? What exercise number?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    The second way you are claiming to order the ordinals is incorrect. for example, the power set of 2 is not 3 - it is a set with 4 elements.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Show that two C*-algebras are morita equivalent
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 8th 2010, 08:00 AM
  2. Replies: 2
    Last Post: October 4th 2010, 04:53 PM
  3. How to grasp the equivalent proposals of real number theory?
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 21st 2010, 02:26 AM
  4. Replies: 2
    Last Post: November 7th 2009, 01:13 PM
  5. Replies: 4
    Last Post: April 6th 2009, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum