Group Structure on any set
Faizal Ahmed
thanks
faizal
Arturo Magidin
Faizal Ahmed <fai...@iitk.ac.in> wrote:
>Given any non empty set, is it possible to define a group structure on the same??
Yes: find a (set theoretic) bijection to a group of the same
cardinality; there are groups of every cardinality.
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Michael van Opstall
> In article <76dfb0e3.0301...@posting.google.com>,
> Faizal Ahmed <fai...@iitk.ac.in> wrote:
> >Given any non empty set, is it possible to define a group structure on
> >the same??
>
> Yes: find a (set theoretic) bijection to a group of the same
> cardinality; there are groups of every cardinality.
>
I'm curious. I see this using the GCH; is it true without CH?
> ======================================================================
> "It's not denial. I'm just very selective about
> what I accept as reality."
> --- Calvin ("Calvin and Hobbes")
> ======================================================================
>
> Arturo Magidin
> mag...@math.berkeley.edu
>
>
======================================================================
Michael A. Van Opstall
Padelford C-113
ops...@math.washington.edu
http://www.math.washington.edu/~opstall/
Arturo Magidin
Michael van Opstall <ops...@math.washington.edu> wrote:
>On Thu, 30 Jan 2003, Arturo Magidin wrote:
>
>> In article <76dfb0e3.0301...@posting.google.com>,
>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>> >Given any non empty set, is it possible to define a group structure on
>> >the same??
>>
>> Yes: find a (set theoretic) bijection to a group of the same
>> cardinality; there are groups of every cardinality.
>>
>
>I'm curious. I see this using the GCH; is it true without CH?
Why would you need the continuum hypothesis? You need the Axiom of
Choice (to be able to find a bijection to some cardinal; comparability
of any two sets), but I don't see the need for CH or GCH...
Let alpha be an infinite cardinal. Then the cardinality of the direct sum
of alpha copies of the integers is alpha*aleph_0 = alpha
, so this will suffice for
infinite cardinals.
To see this, we count the elements of the direct sum as follows: every
element corresponds to a finite n-tuple of nonzero elements of Z
(countably many of them), and a finite subset of alpha of cardinality
n (there are alpha of them). So there are at most aleph_0*alpha=alpha
possible elements. Since there are at least a different elements (a 1
in exactly one entry), that gives you the equality.
(I guess you were trying to use the direct product instead of the
direct sum? That would give aleph_0^a = 2^a elements...)
David C Ullrich
(Arturo Magidin) wrote:
>In article <Pine.LNX.4.44.030130...@zeno1.math.washington.edu>,
>Michael van Opstall <ops...@math.washington.edu> wrote:
>>On Thu, 30 Jan 2003, Arturo Magidin wrote:
>>
>>> In article <76dfb0e3.0301...@posting.google.com>,
>>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>>> >Given any non empty set, is it possible to define a group structure on
>>> >the same??
>>>
>>> Yes: find a (set theoretic) bijection to a group of the same
>>> cardinality; there are groups of every cardinality.
[...]
>
>Let alpha be an infinite cardinal. Then the cardinality of the direct sum
>of alpha copies of the integers is alpha*aleph_0 = alpha
>, so this will suffice for
>infinite cardinals.
[...]
>
>(I guess you were trying to use the direct product instead of the
>direct sum? That would give aleph_0^a = 2^a elements...)
Dunno what he had in mind, but that's what _I_ was thinking
of when I first read the question and decided I didn't see why
it was obvious. Duh.
Of course we still have the finite cardinals to deal with.
>======================================================================
>"It's not denial. I'm just very selective about
> what I accept as reality."
> --- Calvin ("Calvin and Hobbes")
>======================================================================
>
>Arturo Magidin
>mag...@math.berkeley.edu
David C. Ullrich
Denis Feldmann
> On Thu, 30 Jan 2003 18:43:45 +0000 (UTC), mag...@math.berkeley.edu
> (Arturo Magidin) wrote:
>
>> 100...@zeno1.math.washington.edu>, Michael van Opstall
>> <ops...@math.washington.edu> wrote:
>>> On Thu, 30 Jan 2003, Arturo Magidin wrote:
>>>
>>>> In article <76dfb0e3.0301...@posting.google.com>,
>>>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>>>>> Given any non empty set, is it possible to define a group
>>>>> structure on the same??
>>>>
>>>> Yes: find a (set theoretic) bijection to a group of the same
>>>> cardinality; there are groups of every cardinality.
> [...]
>>
>> Let alpha be an infinite cardinal. Then the cardinality of the
>> direct sum of alpha copies of the integers is alpha*aleph_0 = alpha
>> , so this will suffice for
>> infinite cardinals.
> [...]
>>
>> (I guess you were trying to use the direct product instead of the
>> direct sum? That would give aleph_0^a = 2^a elements...)
>
> Dunno what he had in mind, but that's what _I_ was thinking
> of when I first read the question and decided I didn't see why
> it was obvious. Duh.
>
> Of course we still have the finite cardinals to deal with.
Well, if you find the direct sum obvious, I don't understand what is hard
with Z/nZ... Unless you work without choice. Could it be possible that there
exists infinite sets without any group structure? After all, is G is a
Dedekind-finite (but not finite) group, the sequence a, a^2, ...must be
periodic for all a (else we would have constructed (without choice) an
injection of IN into G), but I dont see any other strong argument against
G...
David C Ullrich
<denis.f...@wanadoo.fr> wrote:
>David C Ullrich wrote:
>> On Thu, 30 Jan 2003 18:43:45 +0000 (UTC), mag...@math.berkeley.edu
>> (Arturo Magidin) wrote:
>>
>>> In article <Pine.LNX.4.44.0301301009180.30225-
>>> 100...@zeno1.math.washington.edu>, Michael van Opstall
>>> <ops...@math.washington.edu> wrote:
>>>> On Thu, 30 Jan 2003, Arturo Magidin wrote:
>>>>
>>>>> In article <76dfb0e3.0301...@posting.google.com>,
>>>>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>>>>>> Given any non empty set, is it possible to define a group
>>>>>> structure on the same??
>>>>>
[...]
>>
>> Of course we still have the finite cardinals to deal with.
>
>Well, if you find the direct sum obvious, I don't understand what is hard
>with Z/nZ...
Um, I thought it would be clear I was joking, sorry.
>Unless you work without choice. Could it be possible that there
>exists infinite sets without any group structure? After all, is G is a
>Dedekind-finite (but not finite) group, the sequence a, a^2, ...must be
>periodic for all a (else we would have constructed (without choice) an
>injection of IN into G), but I dont see any other strong argument against
>G...
>>
>>> ======================================================================
>>> "It's not denial. I'm just very selective about
>>> what I accept as reality."
>>> --- Calvin ("Calvin and Hobbes")
>>> ======================================================================
>>>
>>> Arturo Magidin
>>> mag...@math.berkeley.edu
>>
>>
>> David C. Ullrich
>
David C. Ullrich
Denis Feldmann
> On Thu, 30 Jan 2003 22:48:14 +0100, "Denis Feldmann"
> <denis.f...@wanadoo.fr> wrote:
>
>> David C Ullrich wrote:
>>> On Thu, 30 Jan 2003 18:43:45 +0000 (UTC), mag...@math.berkeley.edu
>>> (Arturo Magidin) wrote:
>>>
>>>> In article <Pine.LNX.4.44.0301301009180.30225-
>>>> 100...@zeno1.math.washington.edu>, Michael van Opstall
>>>> <ops...@math.washington.edu> wrote:
>>>>> On Thu, 30 Jan 2003, Arturo Magidin wrote:
>>>>>
>>>>>> In article <76dfb0e3.0301...@posting.google.com>,
>>>>>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>>>>>>> Given any non empty set, is it possible to define a group
>>>>>>> structure on the same??
>>>>>>
> [...]
>>>
>>> Of course we still have the finite cardinals to deal with.
>>
>> Well, if you find the direct sum obvious, I don't understand what is
>> hard with Z/nZ...
>
> Um, I thought it would be clear I was joking, sorry.
Oh, it was clear :-) My question below should have made it clearer
>
>> Unless you work without choice. Could it be possible that there
>> exists infinite sets without any group structure? After all, is G
>> is a Dedekind-finite (but not finite) group, the sequence a, a^2,
>> ...must be periodic for all a (else we would have constructed
>> (without choice) an injection of IN into G), but I dont see any
>> other strong argument against G..
So, what do you think ? Is it really possible to construct a model of ZF
with a non-empty set without any group structure? Hard to believe, but...
David C Ullrich
<denis.f...@wanadoo.fr> wrote:
I really have no idea - don't really have a good enough feeling for
how things work without AC.
>>>>> ======================================================================
>>>>> "It's not denial. I'm just very selective about
>>>>> what I accept as reality."
>>>>> --- Calvin ("Calvin and Hobbes")
>>>>> ======================================================================
>>>>>
>>>>> Arturo Magidin
>>>>> mag...@math.berkeley.edu
>>>>
>>>>
>>>> David C. Ullrich
>>>
>>
>>
>> David C. Ullrich
>
David C. Ullrich
G. A. Edgar
<Pine.LNX.4.44.030130...@zeno1.math.washington.edu>,
Michael van Opstall <ops...@math.washington.edu> wrote:
> > Yes: find a (set theoretic) bijection to a group of the same
> > cardinality; there are groups of every cardinality.
> >
>
> I'm curious. I see this using the GCH; is it true without CH?
Without CH (but with AC)...
if n is a finite cardinal, use the cyclic group of order n.
if n is an infinite cardinal, use the direct sum of n copies of Z.
[Direct sum, meaning all but finitely many coordinates are zero.]
--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/
Arturo Magidin
Arturo Magidin <mag...@math.berkeley.edu> wrote:
>In article <Pine.LNX.4.44.030130...@zeno1.math.washington.edu>,
>Michael van Opstall <ops...@math.washington.edu> wrote:
>>On Thu, 30 Jan 2003, Arturo Magidin wrote:
>>
>>> In article <76dfb0e3.0301...@posting.google.com>,
>>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>>> >Given any non empty set, is it possible to define a group structure on
>>> >the same??
>>>
>>> Yes: find a (set theoretic) bijection to a group of the same
>>> cardinality; there are groups of every cardinality.
>>>
>>
>>I'm curious. I see this using the GCH; is it true without CH?
>
>Why would you need the continuum hypothesis? You need the Axiom of
>Choice (to be able to find a bijection to some cardinal; comparability
>of any two sets), but I don't see the need for CH or GCH...
Actually... does anybody know if the bijectability of an infinite set
with the collection of its finite subsets can be achieved without the
Axiom of Choice?
Because, silly me, if you have a set S of cardinality alpha>= aleph_0,
then the collection of all finite subsets of S form a group under
symmetric difference of cardinality alpha.
Fred Galvin
> In article <b1brp1$pu8$1...@agate.berkeley.edu>,
> Arturo Magidin <mag...@math.berkeley.edu> wrote:
>
> Actually... does anybody know if the bijectability of an infinite set
> with the collection of its finite subsets can be achieved without the
> Axiom of Choice?
No, that's equivalent to AC. Let F(A) denote the collection of all
finite subsets of A. Using the Kuratowski ordered pair (x,y) =
{{x},{x,y}}, the Cartesian product AxA is a subset of F(F(A)), and so
|A| <= |AxA| <= |F(F(A))|. If we also have |A| = |F(A)| = |F(F(A))|,
then it follows that |AxA| = |A|. Tarski proved that the principle
"every infinite cardinal is equal to its square" is equivalent to the
axiom of choice.
In fact, if A is a Dedekind-finite set (meaning that A has no
countably infinite subset), then |A| < |F(A)|.
--
It takes steel balls to play pinball.
Randall Dougherty
Denis Feldmann <denis.f...@wanadoo.fr> wrote:
>So, what do you think ? Is it really possible to construct a model of ZF
>with a non-empty set without any group structure? Hard to believe, but...
Yes, this is possible; in fact, it happens in one of the first models
one runs into when considering forcing constructions of models of ZF
without choice. This is the model obtained by forcing in countably
many Cohen reals and then taking a suitable symmetric submodel to
get a model of ZF containing an infinite Dedekind-finite set of reals.
The constructed set A in this model satisfies:
(1) A is infinite;
(2) there is no infinite sequence of distinct elements of A.
The same method used to prove (2) can also be used to prove:
(3) For any natural number n > 1, there is no partition of A
into sets of size n.
But a set A with these three properties cannot have a group structure.
If it did, then by (1) there would be a non-identity element x.
If x has infinite order, then the sequence of powers of x contradicts (2);
if x has finite order, then the partition of A into right cosets of the
subgroup generated by x contradicts (3).
Randall Dougherty rdo...@ccrwest.org
"I have yet to see any problem, however complicated, which when looked at in
the right way didn't become still more complicated." -- Poul Anderson
Arturo Magidin
Fred Galvin <gal...@math.ukans.edu> wrote:
>On Fri, 31 Jan 2003, Arturo Magidin wrote:
>
>> In article <b1brp1$pu8$1...@agate.berkeley.edu>,
>> Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>
>> Actually... does anybody know if the bijectability of an infinite set
>> with the collection of its finite subsets can be achieved without the
>> Axiom of Choice?
>
>No, that's equivalent to AC. Let F(A) denote the collection of all
>finite subsets of A. Using the Kuratowski ordered pair (x,y) =
>{{x},{x,y}}, the Cartesian product AxA is a subset of F(F(A)), and so
>|A| <= |AxA| <= |F(F(A))|. If we also have |A| = |F(A)| = |F(F(A))|,
>then it follows that |AxA| = |A|. Tarski proved that the principle
>"every infinite cardinal is equal to its square" is equivalent to the
>axiom of choice.
Ah. I thought it might be the case, but thought there was a chance it
could be done. Thanks! (Another poster has already pointed out that
there are models without AC where a set cannot be given a group
structure)...
Herman Rubin
Arturo Magidin <mag...@math.berkeley.edu> wrote:
>In article <b1brp1$pu8$1...@agate.berkeley.edu>,
>Arturo Magidin <mag...@math.berkeley.edu> wrote:
>>In article <Pine.LNX.4.44.030130...@zeno1.math.washington.edu>,
>>Michael van Opstall <ops...@math.washington.edu> wrote:
>>>On Thu, 30 Jan 2003, Arturo Magidin wrote:
>>>> In article <76dfb0e3.0301...@posting.google.com>,
>>>> Faizal Ahmed <fai...@iitk.ac.in> wrote:
>>>> >Given any non empty set, is it possible to define a group structure on
>>>> >the same??
>>>> Yes: find a (set theoretic) bijection to a group of the same
>>>> cardinality; there are groups of every cardinality.
>>>I'm curious. I see this using the GCH; is it true without CH?
>>Why would you need the continuum hypothesis? You need the Axiom of
>>Choice (to be able to find a bijection to some cardinal; comparability
>>of any two sets), but I don't see the need for CH or GCH...
>Actually... does anybody know if the bijectability of an infinite set
>with the collection of its finite subsets can be achieved without the
>Axiom of Choice?
The answer is no. In fact, even two-element subsets suffice.
For let X be an arbitrary infinite set, and let Y be the set
of all ordinal numbers which can be mapped injectively into
X. Then if the union of X and Y is bijective with X x Y,
X can be well-ordered.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Deptartment of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
David Libert
> In article <b1c858$e7i$1...@news-reader11.wanadoo.fr>,
> Denis Feldmann <denis.f...@wanadoo.fr> wrote:
>
> >So, what do you think ? Is it really possible to construct a model of ZF
> >with a non-empty set without any group structure? Hard to believe, but...
>
> Yes, this is possible; in fact, it happens in one of the first models
> one runs into when considering forcing constructions of models of ZF
> without choice. This is the model obtained by forcing in countably
> many Cohen reals and then taking a suitable symmetric submodel to
> get a model of ZF containing an infinite Dedekind-finite set of reals.
> The constructed set A in this model satisfies:
> (1) A is infinite;
> (2) there is no infinite sequence of distinct elements of A.
> The same method used to prove (2) can also be used to prove:
> (3) For any natural number n > 1, there is no partition of A
> into sets of size n.
> But a set A with these three properties cannot have a group structure.
> If it did, then by (1) there would be a non-identity element x.
> If x has infinite order, then the sequence of powers of x contradicts (2);
> if x has finite order, then the partition of A into right cosets of the
> subgroup generated by x contradicts (3).
>
>
> Randall Dougherty rdo...@ccrwest.org
So the standard construction of a Dedekind set of reals gives a set
having no group structure.
There is also a standard construction of an amorphous set, where a
set A is defined to defined to be amorphous iff A is infinite and
every subset B of A has B finite or A-B finite.
Namely this constuction is a Cohen symmetric model, where there are
labels for A's elements, and there are in turn labels for all the
elements of A's elements, and the model allows all permutations
respecting membership of those two levels of labels, and the bottom
level labels are forced to be Cohen reals, with finite support for the
symmetries.
This construction gives an amorphous set A with no group structure.
I had wondered if the conclusion of no group structure would follow
more abstractly, not resting on a particular construction, but instead
being a general ZF theorem, if A is amorphous then A has no group
structure.
Denis Feldman already pointed out any Dedekind set can't have a
group structure on it with any elements of infinite order, ie inject
omega into such a group as various powers of such a group element.
ZF |- any amorphous set is Dedekind, so we at least have over ZF
that any group structure on an amorphous set must be a torsion group,
ie all elements of finite order.
Surprisingly, I think it is possible to have amorphous sets with
group structure, ie from Con(ZF) there is a Cohen symmetric model
with an amorphous set having a group structure. This would show we
can't get the example of a set without group structure abstractly,
just over ZF from properties of amorphous or Dedekind, but must
analyse a specific construction as Randall mentioned above.
To get an amorphous set with a group structure. Let G be the direct
sum of countablly many copies of Z/2. We make a label for each
element of G, and we make the permutation group acting on those labels
be all group homomorphisms of that G. Below each of these labels for
G memebrs, put another generation of labels for their members, making
these be forced as Cohen reals. Within permutations on the G
elements, make arbitrary permutations on the labels below.
In other words, the first standard construction I mentioned above is
mimicing with a Cohen symmetric model the Fraenkel Mostowski
permutation model of complete symmetry on atoms, so this mimicing
interpreting the FM atoms as labels for sets of Cohen reals. My last
version above is similarly coding into Cohen symmetric models the FM
model with atoms being G elements and permutations being G
homomorphisms.
So G's group operation as acting on labels makes it into the
symmetric model, since it has empty support, since all permutations
being G homomorphisms respect it. So the set constructed by this, ie
the set of all denotations of labels corresponding to G elements, ie
we put also a label for that set in as usual in these construction,
this constructed set has a group operation, the one induced by G's
operation.
It remains to be seen that the A constructed this way is amorphous.
Given finitely many labels of G elements, the subgroup of G they
generate is finite, since G was a direct sum of 2 element groups.
Considering G as a Z/2 vector space, such a generated finite
subgroup of G is a subspace of the vector space. So we can find an
automorphism of the vector space (and hence a group homomorphism of G
as a group) fixing the finite subspace and carrying any designated G
member from outside the subspace to any other designated member. Ie,
for each pair of G members outside the finite subspace, there exists
such a vector space automorphism.
This is a big enough fragment of transitivity of the group action on
G to do the usual arguments that the constructed set is amorphous, ie
from the original construction.
--
David Libert ah...@FreeNet.Carleton.CA
Martin Goldstern
> I had wondered if the conclusion of no group structure would follow
> more abstractly, not resting on a particular construction, but instead
> being a general ZF theorem, if A is amorphous then A has no group
> structure.
> ...
> Surprisingly, I think it is possible to have amorphous sets with
> group structure, ie from Con(ZF) there is a Cohen symmetric model
> with an amorphous set having a group structure.
I think the right notion for "abstractly" showing that ZF does
not imply "on every set there is a group structure" is not
the notion of "amorphous", but "strongly amorphous" (perhaps
also called "superamorphous"?).
An infinite set X is called strongly amorphous if
1) every subset of X is finite or cofinite
2) every finitary relation (i.e., every R subset X^n)
is first order definable in the language of equality with
parameters from X.
(e.g., { (x,y,z): x=y or z=a=/=x }, for some fixed a in X )
(Note that (1) is a special case of (2), namely n=1)
It is easy to see that :
if
R is an equivalence relation on an infinite strongly amorphous set X
then:
on some cofinite subset Y, R induces one of the two trivial
equivalence relations.
The most straightforward Cohen and Mostowski models give in fact
not only amorphous but strongly amorphous sets, and clearly ZF implies
that an infinite strongly amorphous set cannot carry a group structure,
by an argument we have already seen. (use cosets modulo a
1-generated subgroup)
David Libert
> In article <b1f124$1op2$1...@agate.berkeley.edu>,
> Arturo Magidin <mag...@math.berkeley.edu> wrote:
[...]
> >Actually... does anybody know if the bijectability of an infinite set
> >with the collection of its finite subsets can be achieved without the
> >Axiom of Choice?
>
> The answer is no. In fact, even two-element subsets suffice.
>
> For let X be an arbitrary infinite set, and let Y be the set
> of all ordinal numbers which can be mapped injectively into
> X. Then if the union of X and Y is bijective with X x Y,
> X can be well-ordered.
I will fill in some details which were helpful to me in
understanding the above, hence maybe helpful for others.
The original question posed above was about an infinite set
bijecting to all its finite subsets.
The answer after that is that ZF proves every infinite set is
bijective with the set of all its finite subsets <-> AC. So in
particular, ZF doesn't prove every infinite subset is bijective with
its finite subsets.
This all relates to a theorem of Tarski: ZF proves every infinite
set A is bijective with AxA <-> AC.
The proof of Tarski's theorem involves steps as Herman just wrote
above. And these same steps can be used to settle the original
question, about all finite subsets.
Namely, toward proving in ZF that if every sey is bijective with
all its finite subsets, then AC, I discuss how the opening parts
reduce to the statement Herman mentioned.
So in ZF, we assume X is infinite, and that every set bijects with
all its finite subsets. We let Y be as Herman wrote above, the set
of all ordinals which inject into X, ie the Hartog's number of X.
We form the disjoint union of X and Y, ie replace one by an
isormorphic copy if necessary so the unioning operation is disjoint.
For ease of notation I will write this as just the union of the
original X and Y, and assume these are disjoint (else replace X by a
isomorphic copy of X with no ordinals as members, ie Xx{1} for
example).
We apply the assumed property to X union Y, ie X union Y is
bijective with the set of all its finite subsets.
Since X and Y are assumed disjoint, there is a canonical injection
of XxY into the set of finite subsets of X union Y,
ie <x,y> |-> {x,y} and since X,Y disjoint this is 1-1.
We assume the set of finite subsets of X union Y bijects to
X union Y, so compose that with that last from XxY, obtaining an
injection of XxY into X union Y.
In fact, as will be seen below, we could stop there in terms of what
is needed below for AC, but to relate this to the comments above, we
can also inject X union Y into XxY. Namely send x in X to
<x,0> in XxY (Y is a set of ordinals), and send y in Y to
<x_0 , 1+y> for some fixed x_0 in X.
So we have injections each way, between X union Y and XxY,
so by Cantor Bernstein (a ZF theorem needing no fragment of AC), these
are bijective, as noted above.
So that gets us from the question originally posed to the followup
above.
Now to relate this to the proof of Tarski's theorem. For Tarkski's
theorem, we assume X is infinite, and that every infinite set is
bijective with its square.
We form the same Y (Hartog's number) for X as above, and take the
same disjointified union X union Y as above.
Now we apply the premise from Tarki's theorem to X union Y,
to obtain a bijection of X union Y with (X union Y)^2.
XxY is a subset of (X union Y)^2, so from the last we get an
injection of XxY into X union Y.
The remainder of the proof of Tarski's theorem only needs this
injection XxY >-> X union Y, and from that concludes X is
well-orderable.
So this is where the proof of Tarski's theorem merges with the proof
about finite subsets, namely the the finite subsets version we
actually got a bijection XxY >->> X union Y, but as I noted
above, the rest of the proof actually only needs the injection
XxY >-> X union Y.
So how do we get from such an injection to a well-ordering of X?
This was given in a post proving Tarski's theorem:
[1] Mike Oliver Feb 11 '99 "Re: Addition on Infinities"
http://mathforum.org/discuss/sci.math/a/m/135314/135349
[1] defined Y as the least ordinal that X doesn't surject onto.
This is equivalent to Herman's definition of no injections from.
--
David Libert ah...@FreeNet.Carleton.CA
David Libert
This is really intended to be a followup to
[0] David Libert Feb 5 '03 "Re: Group Structure on any set"
http://mathforum.org/discuss/sci.math/m/478403/480104
I lost [0] off my computer, so I am attaching this to Herman's
article, the parent of [0].
In [0], I wrote:
>hru...@odds.stat.purdue.edu (Herman Rubin) writes:
>
>> In article <b1f124$1op2$1...@agate.berkeley.edu>,
>> Arturo Magidin <mag...@math.berkeley.edu> wrote:
>
> [...]
>
>> >Actually... does anybody know if the bijectability of an infinite set
>> >with the collection of its finite subsets can be achieved without the
>> >Axiom of Choice?
>>
>> The answer is no. In fact, even two-element subsets suffice.
>>
>> For let X be an arbitrary infinite set, and let Y be the set
>> of all ordinal numbers which can be mapped injectively into
>> X. Then if the union of X and Y is bijective with X x Y,
>> X can be well-ordered.
[...]
> So this is where the proof of Tarski's theorem merges with the proof
>about finite subsets, namely the the finite subsets version we
>actually got a bijection XxY >->> X union Y, but as I noted
>above, the rest of the proof actually only needs the injection
>XxY >-> X union Y.
>
> So how do we get from such an injection to a well-ordering of X?
>This was given in a post proving Tarski's theorem:
>
>[1] Mike Oliver Feb 11 '99 "Re: Addition on Infinities"
> http://mathforum.org/discuss/sci.math/a/m/135314/135349
>
>
> [1] defined Y as the least ordinal that X doesn't surject onto.
>This is equivalent to Herman's definition of no injections from.
That last point is wrong, but it has no significant effect on
Herman's article indirectly quoted above nor on Mike's [0].
So the issue about defining Hartog's number for an arbitrary set X.
This is the least ordinal which is in some sense "big" compared to X.
It is mainly useful in the context of ZF.
Herman's article gave what I think is the standard definition of
Hartog's number, namely the least ordinal which can't be injected into
X. Mike's [1] gave a variant definition: the least ordinal which X
can't surject onto.
I claimed above in [0] that these definitions were equivalent. I am
now retracting that.
So let us define injective and surjective versions of Hartog's
number, as above, so I am just stipulating names now:
define i(X) = the least ordinal alpha s.t. there is no
injection : alpha >-> X
s(X) = the least ordinal alpha s.t. there is no
surjection : X ->> alpha
I was claiming in [0] that ZF proves for every X i(X) = s(X).
In fact, ZF does prove one direction: for every X i(X) <= s(X).
To see this, suppose beta is an ordinal < i(X), so there is an
injection f : beta >-> X .
Define a surjection X -> beta, by taking f^-1 on Range(f) and
taking contantly 0 on X - Range(f).
This surjection shows beta < s(X).
So every beta < i(X) has beta < s(X), so i(X) <= s(X) as
claimed.
ZFC proves i(X) and s(X) are both the successor cardinal of #X,
so ZFC proves i and s are the same functions.
But there is a ZF model with a set X s.t. i(X) < s(X).
Namely, I have written before about Paul Cohen's second ~AC model
from _Set Theory and the Continuum Hypothesis_ , namely which
contains an omega sequence of 2 element sets which has no choice
functions.
It is on page 142. The sequence is called S_5.
I mentioned in some previous post that Cohen's proof also shows no
infinite subset of the range of the countable sequence has a choice
function.
Also, to make the discussion below easier for notation, I will
mention that the 2 element sets in the countable sequence are pairwise
disjoint.
So let X be the union of the countably many sets in the range of
S_5, is a countable union of 2 element sets.
I claim that omega does not inject into X. Else there would
infinitely many S_5 elements non-disjoint with the range of such an
injection : omega >-> X, and on these elements you could pick the
first member of the 2 element set enumerated by the injection from
omega, obtaining a choice function on an infinite part of the
sequence, contrary to the property just mentioned.
On the other hand, any finite ordinal can inject into X, by
induction on finite ordinals, this is true for any X.
So i(X) = omega exactly.
But I can define a surjection from X -> omega. Namely the 2
elements from the n'th 2 element set enumerated by S_5 should go to
n. Each n in omega gets hit exactly twice.
This shows omega < s(X).
Cohen's model didn't collapse any cardinals, and the Cohen symmteric
model is a submodel of a forcing ZFC extension of the ground model,
which didn't collapse cardinals from the ground model. This ZFC
forcing extension sees that X is countable, so it has no surjections
from X onto omega_1, so the symmetric submodel also has none.
So Cohen's model has no surjections : X -> omega_1.
From the previous surjection : X ->> omega we can compose with
various surjections from omega onto various countable ordinals.
So X surjects onto each countable ordinal individually but doesn't
surject onto omega_1.
So s(X) = omega_1 exactly.
So i(X) = omega and s(X) = omega_1.
Herman's article took Y = i(X). Mike's [1] took Y = s(X)
(actually Mike was using R in place of the current thread's X).
But this does not matter for the proofs. Mike used the property of
Y to rule out case which would inject Y >-> X (or Y >-> R in Mike's
literal terminology in [1]).
Mike noted such an injection would induce a surjection contra Mike's
definition Y = s(X).
That observation was basically the same as my proof above of
i(X) <= s(X).
So to rephrase this in terms of this present article, Mike's proof
got an injection Y >-> R, but since Y = s(R) this contra's
i(R) <= s(R), ie an injection from s(R) would induce an injection
from i(R) since that is smaller, contra def of i.
So if instead you run the [1] proof on Herman's definition Y = i(X),
then the contradiction from the injection is immediate.
So either definition Y = i(X) or Y = s(X) can make the proof
from [1] work.
So in the end, Mike's [1] can still be used to fill in the claims
from Herman's article, as I wrote in [0], but it is not by the
literal i(X) = s(X) I claimed in [0].
--
David Libert ah...@FreeNet.Carleton.CA