From: "Brian M. Scott" Newsgroups: sci.math Subject: Re: Power set of finite set Date: Fri, 11 Sep 1998 12:53:46 -0400 Jeremy Boden wrote: > In article <6t8l2c\$od4@b.stat.purdue.edu>, Herman Rubin > writes [snip] > >However, if one defines finite by other means, such as not having > >a 1-1 mapping properly into the set, there are models in which such > >sets exist and are not well orderable. If X is such a set, > >P(P(P(X))) is not, and there must be a counterexample. > I would be most interested to see an example of this! > According to my understanding of ZFC, > ALL sets can be well-ordered, regardless of whether they are finite or > not. True. The models in question are of ZF + ~AC, Zermelo-Fraenkel set theory with the negation of the axiom of choice, not of ZFC. > In addition the power set always exists. True but irrelevant. (Herman's last comment is perhaps phrased a trifle opaquely.) Call a set X Dedekind infinite if there is a 1-1 map from X onto a proper subset of X; a set that is not Dedekind infinite is said to be Dedekind finite. Say that a set is finite if there's a bijection between it and a finite ordinal; otherwise it's infinite. It's easy to show that every finite set is Dedekind finite; the question is whether every infinite set is Dedekind infinite. If the answer were 'yes', finite and Dedekind finite would coincide; in order for them to be distinct concepts, there must be an infinite, Dedekind finite set. It's also easy to show that every infinite, well-ordered set is Dedekind infinite: well-order it as {x(i) : i < k} for some infinite cardinal k, and let f(x(i)) = x(i+1). Thus, if there's an infinite, Dedekind finite set, it cannot be well-orderable. Herman's assertion is that there are models of ZF in which there is an infinite, Dedekind finite set (which must of necessity not be well-orderable). However, if X is an infinite, Dedekind finite set, P(P(P(P(X)))) is not. (I don't at the moment see how to prove Herman's claim that P(P(P(X))) is not.) It's infinite, but it's also Dedekind infinite. To see this, note that each ordered pair in X x X is an element of P(P(X)), so each binary relation on X is an element of P(P(P(X))). In particular, each well-order of a subset of X is a member of P(P(P(X))). For any ordinal k let W(k) be the set of these well-orders of type k; W(k) is an element of P(P(P(P(X)))). Because X is infinite, it's easy to show that W(k) is non-empty for each finite k. Define f on P(P(P(P(X)))) so that f(W(k)) = W(k+1) if k is a finite ordinal, and make f the identity everywhere else. Then f is 1-1, and W(0) isn't in the range of f, so f witnesses the fact that P(P(P(P(X)))) is Dedekind infinite. Brian M. Scott