# Set theory: Show these are equivalent.

• Mar 8th 2011, 07:34 AM
Showcase_22
Set theory: Show these are equivalent.
Quote:

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?
• Mar 9th 2011, 01:16 PM
MoeBlee
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?
• Mar 10th 2011, 08:34 AM
DrSteve
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.