Results 1 to 3 of 3

Thread: Set theory: Show these are equivalent.

  1. #1
    Super Member Showcase_22's Avatar
    Sep 2006
    The raggedy edge.

    Set theory: Show these are equivalent.

    Show that the following are equivalent:

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

    For $\displaystyle a) \Rightarrow b)$:

    Assign each element of $\displaystyle A$ an ordinal number. Since $\displaystyle 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 $\displaystyle A$ they represent) in the following way:

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

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

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

    For $\displaystyle b) \Rightarrow c)$

    If we take any $\displaystyle S \subset \mathcal{P}(A)$, $\displaystyle S$ contains sets of elements of $\displaystyle A$.
    Since $\displaystyle A$ is well-ordered, each of the subsets of $\displaystyle 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 $\displaystyle |S|$).
    This singleton set is the $\displaystyle \subset$-minimal element.

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

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

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

  2. #2
    Senior Member
    Feb 2010
    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
    Nov 2010
    Staten Island, NY
    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: Oct 8th 2010, 07:00 AM
  2. Replies: 2
    Last Post: Oct 4th 2010, 03:53 PM
  3. How to grasp the equivalent proposals of real number theory?
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Mar 21st 2010, 01:26 AM
  4. Replies: 2
    Last Post: Nov 7th 2009, 12:13 PM
  5. Replies: 4
    Last Post: Apr 6th 2009, 12:29 PM

Search Tags

/mathhelpforum @mathhelpforum