Size of equivalence class of Cauchy sequences
Michael Press
converge to r?
--
Michael Press
Narcoleptic Insomniac
If one such sequence exists, then an infinite number do?
Suppose lim_{n -> oo} a_n = r and that {a_n} is Cauchy.
By definition then, for every e > 0 there exists N such
that |a_n - a_m| < e whenever n, m > N.
Now construct the sequence {b_n} with b_n = a_{n + 1}.
Clearly {b_n} is Cauchy and lim_{n -> oo} b_n = r, but
the choices for the first element of {b_n} are unlimited.
Maybe I'm not understanding the question properly?
Regards,
Kyle Czarnecki
William Hughes
I assume that the question is not only "is the cardinality
infinite?", but also "what is the cardinality?"
Note that there are aleph_1 sequences of rational numbers.
That gives an upper bound.
Let a_n be a Cauchy sequence. Let b_n be any
sequence of 0 and 1. Then c_n = a_n+ b_n/n
is a Cauchy sequence which converges to the same
limit as a_n. There are aleph_1 sequences of 0 and 1.
This gives a lower bound.
The answer is aleph_1.
- William Hughes
Peter L. Montgomery
or Cauchy sequences of rational numbers?
For r = 0, we can let a_n be any rational in
the interval(-1/n, 1/n), There are countably
many choices for each a_n, so there are
at least countable^countable Cauchy sequences
of rational numbers converting to 0.
Given any sequence of real numbers,
each term has countably many decimal digits,
so the sequence has countable*countable
digits in all of its terms combined.
There are at most 10^countable such sequences of digits.
So 10^countable >= (desired cardinality) >= countable^countable ,
whether the sequences have rational numbers or real numbers.
--
44 months after Japan attacked Pearl Harbor, Japan surrendered.
45 months after US attacked Iraq, it's time for the US to surrender.
pmon...@cwi.nl Microsoft Research and CWI Home: Bellevue, WA
Stephen J. Herschkorn
>Given a rational number, r, how many Cauchy sequences
>converge to r?
>
>
c, the cardinality of the reals.
Call the desired cardinality k.
If you are mean Cauchy sequences of reals, then c <= k since
(r,q,q,...) converges to q for any real r. and k <= |R^N| =
|(2^N)^N| = |2^(w x w)| = |2^w| = c, where w = omega.
If you mean Cauchy sequences of rationals, then k <= |Q^N| = c. Also,
for any sequence s of positive natural numbers which diverges to
infinity, the sequence (q + 1/s_i) converges to q. And there are at
least as many such sequences as there are sequences of natural
numbers, since given such a latter sequence t, (i + t_i) diverges to
infinity.
--
Stephen J. Herschkorn sjher...@netscape.net
Math Tutor on the Internet and in Central New Jersey and Manhattan
Stephen J. Herschkorn
>>>Given a rational number, r, how many Cauchy sequences
>>>
>>>converge to r?
>>>
>>>
>
>Note that there are aleph_1 sequences of rational numbers.
>That gives an upper bound.
>
>Let a_n be a Cauchy sequence. Let b_n be any
>sequence of 0 and 1. Then c_n = a_n+ b_n/n
>is a Cauchy sequence which converges to the same
>limit as a_n. There are aleph_1 sequences of 0 and 1.
>This gives a lower bound.
>
>The answer is aleph_1.
>
No! aleph-1 is not (necessarily) the same thing as the cardinality of
the reals, unless you assume the continuum hypothesis.
Michael Press
<1168495714....@p59g2000hsd.googlegroups.com>,
"William Hughes" <wpih...@hotmail.com> wrote:
Thanks.
--
Michael Press
MoeBlee
> Michael Press wrote:
>
> >Given a rational number, r, how many Cauchy sequences
> >converge to r?
> >
> >
>
> c, the cardinality of the reals.
So, let me see if I understand correctly: If we use the equivalence
classes of Cauchy sequences method to define real numbers, then each
real number is itself a set with cardinality that of the set of real
numbers. If we use the Dedekind cut method to define real numbers, then
each real number is a denumerable set. (?)
Thanks,
Moeblee
Dave L. Renfro
> Given a rational number, r, how many Cauchy sequences
> converge to r?
This reminds me of a question I thought of back in
1984 or 1985: What is the cardinality of the Lebesgue
spaces L^p? The thing is, I knew there were 2^c
p-integrable *functions*, but how many almost-everywhere
*equivalence classes* of functions do we have? [The usual
interpretation is L^p as a metric space whose elements
are these equivalence classes, although you can also
stick with the functions themselves and view L^p as
a pseudo-metric space.] Now if there were fewer than
2^c many functions in each of the equivalence classes,
then it would follow that the cardinality of L^p was 2^c.
However, each equivalence class has 2^c functions,
since you can add the characteristic function of any
subset of the Cantor middle thirds set to a function
and not leave the equivalence class it belongs to.
Thus, since there are 2^c functions and the equivalence
classes each have cardinality 2^c, it's not automatic
how many equivalence classes there will be. The cardinality
of the collection of equivalence classes of functions
(modulo almost everywhere equality) could, a prior, be
any cardinal number b <= 2^c, since b*2^c = 2^c for each
cardinal number b such that b <= 2^c.
After thinking about it some, I realized that since the
L^p spaces are separable, the cardinality can't be more
than (aleph_0)^(alpeh_0) = c, and of course it was at
least c (distinct constant functions obviously belong
to different almost-everywhere equal equivalence classes),
so the cardinality was exactly c.
I didn't think this was all that well known (I asked
a few professors where I was at and no one off-hand
seemed to know the answer), so I sent it in to be an
American Mathematical Monthly problem. It was rejected
as being perhaps too easy (which I agree, especially
now), and I think the letter I got outlined two additional
methods that were different from the one I submitted.
I think I later came up with still another method
a year or two later, but I don't remember what any
of the other ways are right now (besides separability).
Hummm...Just before sending this I realized L^oo isn't
covered by the separability argument. I'm sure L^oo has
cardinality c, and probably using one of the other ways
of showing L^p for 1 < p < oo has cardinality c will
do it, but I can't think of anything now.
Dave L. Renfro
Stephen J. Herschkorn
Yes, I think that is correct.
Arturo Magidin
Stephen J. Herschkorn <sjher...@netscape.net> wrote:
>MoeBlee wrote:
>
>>Stephen J. Herschkorn wrote:
>>
>>
>>>Michael Press wrote:
>>>
>>>
>>>
>>>>Given a rational number, r, how many Cauchy sequences
>>>>converge to r?
>>>>
>>>>
>>>>
>>>>
>>>c, the cardinality of the reals.
>>>
>>>
>>
>>So, let me see if I understand correctly: If we use the equivalence
>>classes of Cauchy sequences method to define real numbers, then each
>>real number is itself a set with cardinality that of the set of real
>>numbers. If we use the Dedekind cut method to define real numbers, then
>>each real number is a denumerable set. (?)
>>
>
>Yes, I think that is correct.
Or, if you define Dedekind cuts as pairs of sets of rationals, then
each real number would be a set with two elements, each element being
itself a countable set (or rationals).
(And, of course, if you define rationals as equivalence classes of
pairs of integers, then...)
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
MoeBlee
> Yes, I think that is correct.
Good. Thanks.
MoeBlee
Dave L. Renfro
> Or, if you define Dedekind cuts as pairs of sets of
> rationals, then each real number would be a set with
> two elements, each element being itself a countable
> set (or rationals).
>
> (And, of course, if you define rationals as equivalence
> classes of pairs of integers, then...)
It can really get confusing when you realize something
as simple as '2' can be so many different things: '2'
as a natural number (a two element set whose elements
are 'empty set' and '{empty set}'), an integer, a rational
number, a real number, a complex number, and then there
are several ways to define each of these sets from
the previous set. There's probably a category theoretic
way of defining '2' also, which I'd bet is in Linderholm's
"Mathematics Made Difficult" book.
Dave L. Renfro
MoeBlee
> Or, if you define Dedekind cuts as pairs of sets of rationals, then
> each real number would be a set with two elements, each element being
> itself a countable set (or rationals).
Okay, that makes sense.
By the way, from a while ago I asked about graphs. You mentioned the
notion of representing things - such as {{x} {x y}} represents the
ordered pair of x and y - and that we need to accept the arbitrariness
of this (or something to that effect). I just want to let you know that
I've pretty much always (at least since first learning about set
theory) understood that point have no problem with it; my question
about the graphs was not as to any arbitrariness but rather as to just
figuring out a way to make a representation, which you did show me too.
> (And, of course, if you define rationals as equivalence classes of
> pairs of integers, then...)
... each rational is a denumerable set.
And each integer (as an equivalence class of ordered pairs of natural
numbers) is a denumerable set.
And each complex number is an ordered pair, so it has two members.
MoeBlee
William Hughes
Stephen J. Herschkorn wrote:
> William Hughes wrote:
>
> >>>Given a rational number, r, how many Cauchy sequences
> >>>
> >>>converge to r?
> >>>
> >>>
> >
> >Note that there are aleph_1 sequences of rational numbers.
> >That gives an upper bound.
> >
> >Let a_n be a Cauchy sequence. Let b_n be any
> >sequence of 0 and 1. Then c_n = a_n+ b_n/n
> >is a Cauchy sequence which converges to the same
> >limit as a_n. There are aleph_1 sequences of 0 and 1.
> >This gives a lower bound.
> >
> >The answer is aleph_1.
> >
>
> No! aleph-1 is not (necessarily) the same thing as the cardinality of
> the reals, unless you assume the continuum hypothesis.
>
Yes and if the question were about the cardinality of the reals
the comment would be relevant. Since the question is about the
cardinality of sets of sequences, the comment is not relevant. One
does
not need the continuum hypothesis to show that there are
aleph-1 sequences of 0 and 1 (and hence aleph-1
sequences of rationals and reals)
- William Hughes
Stephen J. Herschkorn
>Stephen J. Herschkorn wrote:
>
>
>>William Hughes wrote:
>>
>>
>>
>>>>>Given a rational number, r, how many Cauchy sequences
>>>>>
>>>>>converge to r?
>>>>>
>>>>>
>>>>>
>>>>>
>>>Note that there are aleph_1 sequences of rational numbers.
>>>That gives an upper bound.
>>>
>>>Let a_n be a Cauchy sequence. Let b_n be any
>>>sequence of 0 and 1. Then c_n = a_n+ b_n/n
>>>is a Cauchy sequence which converges to the same
>>>limit as a_n. There are aleph_1 sequences of 0 and 1.
>>>
>>>
This is the mistake. There are not c such sequences, not aleph-1.
>>>This gives a lower bound.
>>>
>>>The answer is aleph_1.
>>>
>>>
>>>
>>No! aleph-1 is not (necessarily) the same thing as the cardinality of
>>the reals, unless you assume the continuum hypothesis.
>>
>>
>>
>
>
>Yes and if the question were about the cardinality of the reals
>the comment would be relevant. Since the question is about the
>cardinality of sets of sequences, the comment is not relevant. One
>does
>not need the continuum hypothesis to show that there are
>aleph-1 sequences of 0 and 1 (and hence aleph-1
>sequences of rationals and reals).
>
That claim is false. If it were, you would have a proof of the
continuum hypothesis.
c is the cardinality of the reals. Aleph-1 is the least uncountable
ordinal. It is quite standard to show that |{0,1}^N| = c. Show us
your proof that |{0,1}^N| = aleph-1.
William Hughes
Stephen J. Herschkorn wrote:
> William Hughes wrote:
>
> >Stephen J. Herschkorn wrote:
> >
> >
> >>William Hughes wrote:
> >>
> >>
> >>
> >>>>>Given a rational number, r, how many Cauchy sequences
> >>>>>
> >>>>>converge to r?
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>Note that there are aleph_1 sequences of rational numbers.
> >>>That gives an upper bound.
> >>>
> >>>Let a_n be a Cauchy sequence. Let b_n be any
> >>>sequence of 0 and 1. Then c_n = a_n+ b_n/n
> >>>is a Cauchy sequence which converges to the same
> >>>limit as a_n. There are aleph_1 sequences of 0 and 1.
> >>>
> >>>
> This is the mistake. There are not c such sequences, not aleph-1.
>
Correct. I had the inequality between c and aleph-1 reversed.
- William Hughes
Stephen J. Herschkorn
> William Hughes wrote:
>
>>>> Note that there are aleph_1 sequences of rational numbers.
>>>> That gives an upper bound.
>>>>
>>>> Let a_n be a Cauchy sequence. Let b_n be any
>>>> sequence of 0 and 1. Then c_n = a_n+ b_n/n
>>>> is a Cauchy sequence which converges to the same
>>>> limit as a_n. There are aleph_1 sequences of 0 and 1.
>>>>
>>>
> This is the mistake. There are not c such sequences, not aleph-1.
D'oh! Typo. I meant to type, "There are c such sequences, not aleph-1."
Michael Press
<1168552119....@o58g2000hsb.googlegroups.com>,
There exists a universally repelling pointed function
+
{0} hookrightarrow N_0 --> N_0
The subsequent discussion of 2 + 2 = 4
is pertinant to another running thread.
--
Michael Press
MoeBlee
On Jan 11, 1:29 pm, "Stephen J. Herschkorn" <sjhersc...@netscape.net>
wrote:
> MoeBlee wrote:
> >So, let me see if I understand correctly: If we use the equivalence
> >classes of Cauchy sequences method to define real numbers, then each
> >real number is itself a set with cardinality that of the set of real
> >numbers. (?)
> Yes, I think that is correct.
I know you mentioned something toward a proof, but would spell out for
me in more detail (hopefully with mainly basic set theory and not too
much real analysis, though I know that such a limitation can't be
insisted on) that each real number (equivalence class of Cauchy
sequences of rationals) has cardinality at least as great as the
cardinality of the set of real numbers?
Thanks,
MoeBlee
Arturo Magidin
I hope you don't mind if I give the idea I had:
It would be enough to show that there are uncountably many
Cauchy sequences of nonzero rationals that converge to 0; for given
such a null sequence, {z_n}, and given any Cauchy sequence {a_n}, then
the sequence {a_n+z_n} is also a Cauchy sequence and is equivalent to
{a_n}.
Consider the harmonic sequence H={1/n}_{n>0}
which is a Cauchy sequence of rationals that converges to 0. Any
subsequence of this is also a Cauchy sequence of rationals that
converges to 0. Given any infinite subset S of N, the set S determines
a subsequence of H by taking only those terms whose index lies in
S. Call this sequence H_S, and the terms h_{S,n}. Then H_S is a Cauchy
sequence of nonzero rationals that converges to 0, and therefore if
{a_n} is any Cauchy sequence of rationals, so is {a_n + h_{S,n} } .
If S is different from T, both infinite subsets of N, then there is a
least positive integer k such that h_{S,k} is different from h_{T,k};
then a_k+h_{S,k} is different from a_k+h_{T,k}, so the sequences
{a_n + h_{S,n}} and {a_n + h_{T,n}} are distinct (though equivalent).
Thus, we have an injection from the collection of all infinite subsets
of N to the set of Cauchy sequences of rationals that are equivalent
to {a_n}, and so the equivalence class of {a_n} contains at least
2^{aleph_0} elements.
Since the set of all sequences of rationals has cardinality
2^{aleph_0}, we already have that the cardinality of the equivalence
class is at most 2^{aleph_0}, so we are done.
Dave L. Renfro
> I know you mentioned something toward a proof, but would
> spell out for me in more detail (hopefully with mainly
> basic set theory and not too much real analysis, though
> I know that such a limitation can't be insisted on)
> that each real number (equivalence class of Cauchy
> sequences of rationals) has cardinality at least
> as great as the cardinality of the set of real numbers?
It suffices to show that the real number 0, viewed as
a collection of Cauchy sequences of rational numbers
(each of which converges to 0), has cardinality c.
This is because if (x_1, x_2, ...) converges to x
and (y_1, y_2, ...) converges to 0, then (x_1 + y_1, ...)
converges to x. This is true even if we don't restrict
the terms of the sequences to be rational numbers.
Note also that any convergent sequence is automatically
a Cauchy sequence, so all three sequences in this
discussion are Cauchy sequences. (This last part
is a fact proved, or assigned as an exercise,
early in most elementary real analysis courses.)
Thus, it suffices to show there are c many sequences
of rational numbers that converge to 0. In fact,
we can do better than that. We can show there are c
many subsequences of 1, 1/2, 1/3, 1/4, ...
How? There are c many infinite subsets of the positive
integers (there are c many subsets of the positive
integers, and only countably many finite subsets of
the positive integers) and, for each infinite subset E
of the positive integers, we can get a distinct sequence
of positive integers by simply listing the numbers in E
in increasing order.
Dave L. Renfro
Virgil
Given an arbitrary real number r \in R, and a positive rational epsilon
\in Q and less than one, then for each natural number n \in N, the set
of rationals in the open interval I_r(n) = ( r - epsilon^n, r +
epsilon^n) is countably infinite.
Every function from N to Q such that f(n) \in I_r(n) is a Cauchy
sequence converging to r, so they form a proper subset of the
equivalence class of all Cauchy sequences for that r.
And there are at least as "many" such sequences as in the set of binary
sequences f:N --> {0,1}, which is already known to be uncountable and
have cardinality at least as great as that of the reals.
Wile this is not a formal proof, its gaps can be filled in to make it
one.
Herman Rubin
>On Jan 11, 1:29 pm, "Stephen J. Herschkorn" <sjhersc...@netscape.net>
>wrote:
>> MoeBlee wrote:
>> >So, let me see if I understand correctly: If we use the equivalence
>> >classes of Cauchy sequences method to define real numbers, then each
>> >real number is itself a set with cardinality that of the set of real
>> >numbers. (?)
>> Yes, I think that is correct.
But you do not have to know anything about cardinality
to carry out the construction.
>I know you mentioned something toward a proof, but would spell out for
>me in more detail (hopefully with mainly basic set theory and not too
>much real analysis, though I know that such a limitation can't be
>insisted on) that each real number (equivalence class of Cauchy
>sequences of rationals) has cardinality at least as great as the
>cardinality of the set of real numbers?
This argument is totally irrelevant. The size of a class of
objects is not at all related to the size of the members of
that class.
--
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, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
MoeBlee
> In article <1170102825.017538.158...@a34g2000cwb.googlegroups.com>,
>
> MoeBlee <jazzm...@hotmail.com> wrote:
> >On Jan 11, 1:29 pm, "Stephen J. Herschkorn" <sjhersc...@netscape.net>
> >wrote:
> >> MoeBlee wrote:
> >> >So, let me see if I understand correctly: If we use the equivalence
> >> >classes of Cauchy sequences method to define real numbers, then each
> >> >real number is itself a set with cardinality that of the set of real
> >> >numbers. (?)
> >> Yes, I think that is correct.
>
> But you do not have to know anything about cardinality
> to carry out the construction.
Okay. Who said we do?
> >I know you mentioned something toward a proof, but would spell out for
> >me in more detail (hopefully with mainly basic set theory and not too
> >much real analysis, though I know that such a limitation can't be
> >insisted on) that each real number (equivalence class of Cauchy
> >sequences of rationals) has cardinality at least as great as the
> >cardinality of the set of real numbers?
>
> This argument is totally irrelevant.
What argument? I just asking for a proof that for each real number x,
there is a bijection between x and the set of real numbers.
> The size of a class of
> objects is not at all related to the size of the members of
> that class.
Okay. Who said otherwise in this thread?
MoeBlee
MoeBlee
> I hope you don't mind if I give the idea I had:
Of course I don't mind. Your proofs have always been helpful to me. I
thank you for them.
> It would be enough to show that there are uncountably many
> Cauchy sequences of nonzero rationals that converge to 0; for given
> such a null sequence, {z_n}, and given any Cauchy sequence {a_n}, then
> the sequence {a_n+z_n} is also a Cauchy sequence and is equivalent to
> {a_n}.
>
> Consider the harmonic sequence H={1/n}_{n>0}
>
> which is a Cauchy sequence of rationals that converges to 0. Any
> subsequence of this is also a Cauchy sequence of rationals that
> converges to 0. Given any infinite subset S of N, the set S determines
> a subsequence of H by taking only those terms whose index lies in
> S. Call this sequence H_S, and the terms h_{S,n}. Then H_S is a Cauchy
> sequence of nonzero rationals that converges to 0, and therefore if
> {a_n} is any Cauchy sequence of rationals, so is {a_n + h_{S,n} } .
>
> If S is different from T, both infinite subsets of N, then there is a
> least positive integer k such that h_{S,k} is different from h_{T,k};
> then a_k+h_{S,k} is different from a_k+h_{T,k}, so the sequences
> {a_n + h_{S,n}} and {a_n + h_{T,n}} are distinct (though equivalent).
>
> Thus, we have an injection from the collection of all infinite subsets
> of N to the set of Cauchy sequences of rationals that are equivalent
> to {a_n}, and so the equivalence class of {a_n} contains at least
> 2^{aleph_0} elements.
>
> Since the set of all sequences of rationals has cardinality
> 2^{aleph_0}, we already have that the cardinality of the equivalence
> class is at most 2^{aleph_0}, so we are done.
That's a very nice explanation; I understand it, except for a couple
of questions.
First let me sharpen my statement of the problem:
Prove that every equivalence class of Cauchy sequences of rational
numbers is equinumerous with R. (And it seems you've done that, except
I have a couple of questions.) Also, prove that the set of Cauchy
sequences of rational numbers is equinumerous with R.
My questions about your proof:
1. Without the axiom of choice, how do we know that the set of
infinite subsets of N is equinumerous with R?
Okay, I agree that the set of finite subsets of N is denumerable; and
the power set of N is equinumerous with R; and the union of two
denumerable sets is denumerable; and the set of finite subsets of N
union the the set of infinite subsets of N is equinumerous with R; so
the set of infinite subsets of N is uncountable. And, by the axiom of
choice, the sum of two infinite cardinals is the greatest of the two,
so the set of infinite subsets of N is equinumerous with R. But
without the axiom of choice? How can we prove not just that the set of
infinite subsets of N is uncountable (which is proven, I agree) but
moreover, and without the axiom of choice or continuum hypothesis,
that the set of infinite subsets of N is equinumerous with R?
2. You say that the set of all sequences of rationals is equinumerous
with R. But I'm wondering whether there's an easy way to show that.
The set of sequences of rationals is equnimumerous with the set of
functions from N into N. And I know there are proofs that the set of
functions from N into N is equinumerous with R, but those seem to be
pretty advanced proofs. Is there a simple proof I might understand?
However, since the set of Cauchy sequences of rationals is a proper
subset of the set of sequences of rationals, rather than worrying
about the size of the set of sequences of rataionals, maybe there's an
even simpler proof that the set of Cauchy sequences of rationals is
equinumerous with R?
Thanks again,
MoeBlee
MoeBlee
> It suffices to show that the real number 0, viewed as
> a collection of Cauchy sequences of rational numbers
> (each of which converges to 0), has cardinality c.
> This is because if (x_1, x_2, ...) converges to x
> and (y_1, y_2, ...) converges to 0, then (x_1 + y_1, ...)
> converges to x. This is true even if we don't restrict
> the terms of the sequences to be rational numbers.
> Note also that any convergent sequence is automatically
> a Cauchy sequence, so all three sequences in this
> discussion are Cauchy sequences. (This last part
> is a fact proved, or assigned as an exercise,
> early in most elementary real analysis courses.)
>
> Thus, it suffices to show there are c many sequences
> of rational numbers that converge to 0. In fact,
> we can do better than that. We can show there are c
> many subsequences of 1, 1/2, 1/3, 1/4, ...
> How? There are c many infinite subsets of the positive
> integers (there are c many subsets of the positive
> integers, and only countably many finite subsets of
> the positive integers) and, for each infinite subset E
> of the positive integers, we can get a distinct sequence
> of positive integers by simply listing the numbers in E
> in increasing order.
I see that you and Arturo have pretty much the same idea. I understand
the proof, but I have a couple of questions. If you like, take a look
at my post this morning to Arturo.
Thanks,
MoeBlee
Arturo Magidin
MoeBlee <jazz...@hotmail.com> wrote:
[...]
>First let me sharpen my statement of the problem:
>
>Prove that every equivalence class of Cauchy sequences of rational
>numbers is equinumerous with R. (And it seems you've done that, except
>I have a couple of questions.) Also, prove that the set of Cauchy
>sequences of rational numbers is equinumerous with R.
>
>My questions about your proof:
>
>1. Without the axiom of choice, how do we know that the set of
>infinite subsets of N is equinumerous with R?
>
>Okay, I agree that the set of finite subsets of N is denumerable; and
>the power set of N is equinumerous with R; and the union of two
>denumerable sets is denumerable; and the set of finite subsets of N
>union the the set of infinite subsets of N is equinumerous with R; so
>the set of infinite subsets of N is uncountable. And, by the axiom of
>choice, the sum of two infinite cardinals is the greatest of the two,
>so the set of infinite subsets of N is equinumerous with R. But
>without the axiom of choice? How can we prove not just that the set of
>infinite subsets of N is uncountable (which is proven, I agree) but
>moreover, and without the axiom of choice or continuum hypothesis,
>that the set of infinite subsets of N is equinumerous with R?
I don't think we need the Axiom of Choice for this one. It is easy to
get injections going both ways.
For each infinite subset S of N, take the real number that has a decimal
expansion with a 5 in position i if i is in S, and a 6 if i is not in
S. This shows that the cardinality of the infinite subsets of N is at
most that of R.
To go the other way, take the real numbers in (0,1), expressed in
binary expansion, with the terminating expansion if there is a choice
of expansion.
Now, for each such real number r, we define the infinite subset S_r of
N as follows: n is in S_r if and only if
(i) n is odd; or
(ii) n is even, and the (n/2)-th digit of the binary expansion of r
is equal to 1.
(In other words, we take the characteristic function of the decimal
expansion of r, then map it into the even integers, and then take
subsets that contain all odd natural numbers and those corresponding
to the characteristic function; this ensures we have an infinite
subset). All such S_r are infinite, and distinct real numbers have
distinct expansions, and thus distinct S_r.
So we have embeddings going each way, and we can use Cantor-Bernstein
to establish a bijection; I do not think we need AC for any of the
above constructions.
(And, of course, we can get bijections from (0,1) to all of R without
too much trouble either.
>2. You say that the set of all sequences of rationals is equinumerous
>with R. But I'm wondering whether there's an easy way to show that.
>
>The set of sequences of rationals is equnimumerous with the set of
>functions from N into N. And I know there are proofs that the set of
>functions from N into N is equinumerous with R, but those seem to be
>pretty advanced proofs. Is there a simple proof I might understand?
There is an obvious injection from 2^N to N^N, induced by the
embedding 2-->N.
Now, pick your favorite embedding from N to 2^N. This induces an
embedding from N^N to (2^N)^N. There is a natural bijection from
(2^N)^N to 2^(N x N), namely, given f in (2^N)^N, we define the
function g:N x N --> 2 by g(a,b) = f(b)(a) (note that f(b) is an
element of 2^N). Now pick your favorite bijection from N to N xN.
This induces a bijection from 2^(NxN) to 2^N by "precomposition". So
we have:
emb. bij. bij.
N^N ------> (2^N)^N -----> 2^(NxN) ----> 2^N
which gives an embedding from N^N to 2^N. Now we have embeddings going
both ways, so as above we can obtain a bijection through
Cantor-Bernstein.
MoeBlee
> Given an arbitrary real number r \in R, and a positive rational epsilon
> \in Q and less than one, then for each natural number n \in N, the set
> of rationals in the open interval I_r(n) = ( r - epsilon^n, r +
> epsilon^n) is countably infinite.
>
> Every function from N to Q such that f(n) \in I_r(n) is a Cauchy
> sequence converging to r, so they form a proper subset of the
> equivalence class of all Cauchy sequences for that r.
>
> And there are at least as "many" such sequences as in the set of binary
> sequences f:N --> {0,1}, which is already known to be uncountable and
> have cardinality at least as great as that of the reals.
>
> Wile this is not a formal proof, its gaps can be filled in to make it
Thanks, Virgil. I'll print it out and study it later.
MoeBlee
MoeBlee
> For each infinite subset S of N, take the real number that has a decimal
> expansion with a 5 in position i if i is in S, and a 6 if i is not in
> S. This shows that the cardinality of the infinite subsets of N is at
> most that of R.
>
> To go the other way, take the real numbers in (0,1), expressed in
> binary expansion, with the terminating expansion if there is a choice
> of expansion.
>
> Now, for each such real number r, we define the infinite subset S_r of
> N as follows: n is in S_r if and only if
>
> (i) n is odd; or
> (ii) n is even, and the (n/2)-th digit of the binary expansion of r
> is equal to 1.
>
> (In other words, we take the characteristic function of the decimal
> expansion of r, then map it into the even integers, and then take
> subsets that contain all odd natural numbers and those corresponding
> to the characteristic function; this ensures we have an infinite
> subset). All such S_r are infinite, and distinct real numbers have
> distinct expansions, and thus distinct S_r.
>
> So we have embeddings going each way, and we can use Cantor-Bernstein
> to establish a bijection; I do not think we need AC for any of the
> above constructions.
>
> (And, of course, we can get bijections from (0,1) to all of R without
> too much trouble either.
Got it. Nice. Thanks.
> >The set of sequences of rationals is equnimumerous with the set of
> >functions from N into N. And I know there are proofs that the set of
> >functions from N into N is equinumerous with R, but those seem to be
> >pretty advanced proofs. Is there a simple proof I might understand?
>
> There is an obvious injection from 2^N to N^N, induced by the
> embedding 2-->N.
>
> Now, pick your favorite embedding from N to 2^N. This induces an
> embedding from N^N to (2^N)^N. There is a natural bijection from
> (2^N)^N to 2^(N x N), namely, given f in (2^N)^N, we define the
> function g:N x N --> 2 by g(a,b) = f(b)(a) (note that f(b) is an
> element of 2^N). Now pick your favorite bijection from N to N xN.
> This induces a bijection from 2^(NxN) to 2^N by "precomposition". So
> we have:
>
> emb. bij. bij.
> N^N ------> (2^N)^N -----> 2^(NxN) ----> 2^N
>
> which gives an embedding from N^N to 2^N. Now we have embeddings going
> both ways, so as above we can obtain a bijection through
> Cantor-Bernstein.
I see what you did there, but I want to mull over a couple of things
on this one. It hadn't occurred to me that this one would be so
simple.
As usual, thanks for your help,
MoeBlee