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.