0
$\begingroup$

I was given in my homework the following question:

Suppose that for some set A, the well ordered set P(A) (under inclusion) has the property that every non-empty subset of it has a minimal element. I was asked to show that A is finite.

I'd be happy to get clues/hints in this manner

$\endgroup$
  • $\begingroup$ Saying that "$P(A)$ has the property that every non-empty subset of it has a minimal element" is the same as saying that $P(A)$ is well-ordered (as a partial order). So you could more simply say "Suppose that for some set $A$, the partially ordered set $P(A)$ (under inclusion) is well-ordered." $\endgroup$ – Alex Kruckman Nov 18 '15 at 22:44
  • $\begingroup$ @AlexKruckman In the usual terminology, a well-ordered set must be totally ordered. If every nonempty subset of $P$ has a least element then $P$ is well-ordered. A partially ordered set in which every nonempty subset has a minimal element is called well-founded not well-ordered. If $A$ has more than one element, then the power set $P(A)$ is not well-ordered. $\endgroup$ – bof Nov 18 '15 at 22:49
  • $\begingroup$ @bof Sure, that's why I wrote "well-ordered (as a partial order)". But you're right, well-founded is a better choice. In any case, the term "well-ordered" is out of place where it appears in the OP's question, which is the point I was trying to get across. $\endgroup$ – Alex Kruckman Nov 18 '15 at 22:52
  • $\begingroup$ @AlexKruckman Oops, I didn't even see "well ordered" in the original post. $\endgroup$ – bof Nov 18 '15 at 23:16
  • $\begingroup$ @AlexKruckman "well-founded" not well-ordered. $\endgroup$ – BrianO Nov 18 '15 at 23:22
2
$\begingroup$

If we assume for a contradiction that $A$ is infinite, then the set of all infinite subsets of $A$ is nonempty, and therefore has a minimal element. That is, there is an infinite set $B\subseteq A$ such that every proper subset of $B$ is finite. Can you get a contradiction from that?

$\endgroup$
  • $\begingroup$ Does the following use the axiom of choice: let b be an element of B, then B\{b} is finite and hence has the same cardinality as Nn, for some natural n, but then B has the same cardinality as N(n+1) and hence finite. $\endgroup$ – availanche Nov 18 '15 at 22:10
  • $\begingroup$ @availanche No, it doesn't use the axiom of choice. $\endgroup$ – bof Nov 18 '15 at 22:16
1
$\begingroup$

By contradiction, A is infinite.

Define B to be the set of all sets of A (or equivalently elements of P(A)) that are infinite. In this case, A is an element of B, and hence B is non-empty subset of A, and therefore it has a minial element, let it be C.

C is a minimal element of B (by inclusion), hence it does not properly include any set in B, but then it does not properly include any infinite set, i.e. C is an infinite set of A that properly includes only finite sets of A.

Let c be an element in C, then C properly includes C\{c} and hence C\{c} is finite, i.e. shares the same cardinality with Nn, for some natural n, but then C shares the same cardinality with N(n+1) and hence finite, arriving at contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.