From: Mike Oliver Subject: Re: Addition on Infinities Date: Thu, 11 Feb 1999 19:05:19 -0800 Newsgroups: sci.math To: kbellul@golden.net Keywords: Is X+X=X independent of Axiom of Choice? Keith Ellul wrote: > > On Thu, 11 Feb 1999, Hal Daume III wrote: > > > The question then arises, for all infinite sets X, does |X| + |X| = |X| > > for all X? The answer, basically, is yes and no, depending on whether > > or not you accept the axiom of choice. > > Do you need the axiom of choice for this? I thought that this was true > independent of AC. Well, it is *true*, because AC is true, but you need AC to *prove* it. Actually, I'm not sure you need full AC for the additive version; some fragment might suffice. For the multiplicative version (i.e. |X^2| = |X| for all infinite X) you *do* need full AC, and the proof is very pretty. Suppose |X cross X| = |X| for all infinite X. For definiteness, we'll show that you can wellorder R, the set of all reals; you can substitute any other set for R. Let Theta be the Hartog number of R; that is, Theta is the least ordinal such that there is no surjection from R to Theta. This must exist by Burali-Forti. Now we're going to let X be the disjoint union of R and Theta; that is, we assume we're coding reals and ordinals in such a way that no real is an ordinal, and then we just take X = (R union Theta). Now there must be a bijection f : X cross X --> X (actually all we need is that f is injective). We're only going to consider f restricted to R cross Theta; that is, we're only concerned with values f() such that x is a real and alpha is an ordinal less than Theta. For every such x and alpha, f() will be either a real or an ordinal less than Theta (and not both). Suppose that for every real x, there is some alpha < Theta such that f() is an ordinal rather than a real. Then for any x, let g(x) = f() for the least alpha such that this value is an ordinal. g is now an injection from the reals into the ordinals; this easily gives you a wellordering of the reals. The only other possibility is that there is some real x such that for *every* alpha < Theta, f() is a real. But then let h(alpha) = f() for this x. h is now an injection from Theta into R, which by turning it around gives you a surjection from R to Theta, contradicting the definition of Theta. Therefore this can't happen, so we're in the situation of the previous paragraph and the reals can be wellordered. You can apply this argument to any other infinite set (though you'll sometimes have to take care of the technical matter of the disjoint union, which was automatic for the reals). Therefore all sets can be wellordered, so AC holds. ============================================================================== From: ikastan@sol.uucp (ilias kastanas 08-14-90) Subject: Re: Addition on Infinities Date: 12 Feb 1999 09:36:15 GMT Newsgroups: sci.math In article , Keith Ellul wrote: @On Thu, 11 Feb 1999, Hal Daume III wrote: @ @> The question then arises, for all infinite sets X, does |X| + |X| = |X| @> for all X? The answer, basically, is yes and no, depending on whether @> or not you accept the axiom of choice. @ @Do you need the axiom of choice for this? I thought that this was true @independent of AC. You do. Without AC, a Dedekind cardinal d might exist (i.e. there are such models of ZF). Let k = d + aleph_0; then k + k > k. But you don't need full AC; the statement "for all k, k + k = k" holds in some models of ZF + ~AC, and is thus weaker than AC. Ilias ============================================================================== From: Fred Galvin Subject: Re: Infinite cardinals question Date: Fri, 17 Dec 1999 20:02:50 -0600 Newsgroups: sci.math On 17 Dec 1999, Allan Adler wrote: > nmanes@hotmail.com (Nathan Manes) writes: > > > If x is an infinate cardinal number, does x+x=x ? > > Please respond to nmanes@hotmail.com. > > I vaguely recall from reading Rubin and Rubin's book Equivalents of > the Axiom of Choice a long time ago that this law of infinite cardinal > arithmetic is equivalent to the axiom of choice. The law x*x = x (for infinite cardinals) is equivalent to the axiom of choice (Tarski). The law x+x = x is a consequence of AC. Whether it is equivalent to AC or not was a long-standing unsolved problem. I think it was finally settled some years ago, in the negative, with a very complicated model. Or maybe it wasn't, I'm not sure. ============================================================================== From: Richard Carr Subject: Re: Infinite cardinals question Date: Sat, 18 Dec 1999 14:08:45 -0500 Newsgroups: sci.math Keywords: Does Axiom of choice follow from x+x=x ? (no) On Sat, 18 Dec 1999, Fred Galvin wrote: :Date: Sat, 18 Dec 1999 02:24:18 -0600 :From: Fred Galvin :Newsgroups: sci.math :Subject: Re: Infinite cardinals question : :On Sat, 18 Dec 1999, Richard Carr wrote: : :> On Sat, 18 Dec 1999, Fred Galvin wrote: :> :> :Really? x+x = x for all infinite cardinals implies AC? I can't say :> :you're wrong, but I personally, being way behind the times, would :> :consider this exciting news. Please try to find the reference. : :> :What I seem to recall is that 20 or 30 years ago somebody (Sageev?) :> :proved that x+x = x does *not* imply AC, but I could easily be wrong. :> :Maybe someone claimed that result, but there was something wrong with :> :the proof; maybe it was a different result and I'm just confused. : :> I'll see if I can dig up my text from where ever it is- probably my :> memory of it is not correct? : :This must be the reference for the result I have in mind: Gershon Sageev, :An independence result concerning the axiom of choice, Ann. Math. Logic 8 :(1975), 1-184. All I have is the citation; I can't access the text or the :review right now. Maybe Sageev's independence result was something :different from that x+x thing we were talking about; maybe that was the :result but it has since been refuted. : : My memory of it is not correct. There are several things which look similar but are not really the same. e.g. m+n=m or m+n=n (CN21 from Rubin and Rubin)- obviously m+m=m is just a specialization of this. Also mn=m+n (this combined with m+m=m would give m=m^2 and hence AC but it gives AC anyway). ============================================================================== From: Allan Adler Subject: Re: Infinite cardinals question Date: 18 Dec 1999 16:32:10 -0500 Newsgroups: sci.math Fred Galvin writes: > This must be the reference for the result I have in mind: Gershon Sageev, > An independence result concerning the axiom of choice, Ann. Math. Logic 8 > (1975), 1-184. All I have is the citation; I can't access the text or the > review right now. Maybe Sageev's independence result was something > different from that x+x thing we were talking about; maybe that was the > result but it has since been refuted. I just read the review on Math-Sci and it does construct a model in which 2x = x for infinite x but AC is false. In this model, every set can be linearly rdered. While looking over the list of Sageev's publications, I noticed a paper published in 1981 in which he shows, assuming an inaccessible, that one can have a model in which the Dedekind finite sets form a model of Peano arithmetic. I had heard about this result in the 1970's at a conference in Providence where Sageev was supposed to speak on it, but I think the talk was cancelled because of some difficulties with the model. I never heard anything more about it until now. It is most gratifying to learn that this striking and beautiful result is really true. I would like to ask Sageev for copies of some of his papers so I can study them, but I don't have his address and can't find it at the ams website. If someone can tell me how to contact him, I would appreciate it. Allan Adler ara@altdorf.ai.mit.edu **************************************************************************** * * * Disclaimer: I am a guest and *not* a member of the MIT Artificial * * Intelligence Lab. My actions and comments do not reflect * * in any way on MIT. Morever, I am nowhere near the Boston * * metropolitan area. * * * **************************************************************************** ============================================================================== From: Fred Galvin Subject: Re: Infinite cardinals question Date: Mon, 20 Dec 1999 23:55:47 -0600 Newsgroups: sci.math On 18 Dec 1999, Allan Adler wrote: > Allan Adler writes: > > > While looking over the list of Sageev's publications, I noticed a paper > > published in 1981 in which he shows, assuming an inaccessible, that > > one can have a model in which the Dedekind finite sets form a model > > of Peano arithmetic. > > I should have said, "a nonstandard model of Peano arithmetic". You mean, of course, the Dedekind-finite *cardinals* form a nonstandard model of arithmetic (just the Peano axioms, or true arithmetic?). This seems kind of weird, seeing as the Dedekind-finite cardinals are not (unless they are all finite) closed under exponentiation. I guess this means that exponentiation in the model (defined in terms of addition and multiplication) is not the same as cardinal exponentiation.