scott <sco### [at] scottcom> wrote:
> > Integers are allowed to have infinite digits before the decimal place.
> > Reals are allowed them after the decimal place as well. ;-)

> Genuine question then, why isn't the set of real numbers countable, 
> given that you could represent each one with two integers (one for the 
> digits before the decimal point, one for the digits after the decimal 
> point)?

The set of all strings that contain all possible combinations of two
or more digits (in other words, the set of all possible decimal
representations) is uncountable. In other words, it's not possible to
enumerate them all. This might be a bit surprising (it was to me...)

Cantor's diagonal argument is used to demonstrate this. Note, though,
that said argument only proves that there are sets that are uncountable
(ie. cannot be enumerated with integers), not that the set of reals is
uncountable.

Cantor's diagonal argument is a proof by contradiction. It goes something
like this:

Let's assume that it is possible to enumerate every single possible infinite
string of digits. Thus we have a(n infinite) list of numbered strings (its
order doesn't really matter, as long as it contains *all* of them.) For
example like:

1: 1001101110...
2: 0010110111...
3: 1100011110...
4: 0111001101...
...

If the assumption is true, that means that this list is complete, ie. it
contains every single possible string using those two digits. Which would
mean that it's impossible to construct a string that does not appear in
that list.

However, we can construct such a string: Take the first digit of the first
string and invert it, the second digit of the second string and invert it,
and so on. In other words, with the example above the string would be
0110... etc.

Said string is different from every single one in that list (because it
necessarily differs from each one by at least one of the digits.) This is
a contradiction because the list was supposed to contain *all* of them.
(It doesn't help if you just "add" this new string to the list. You can
then construct another string that's not in the list.)

Because this is a contradiction, the initial premise is necessarily false:
It's *not* possible to enumerate all of those strings. Therefore the set
of all those strings is genuinely larger than the set of integers.

(But as said, AFAIK this only proves that the set of all possible strings
of two digits is larger than the set of integers, it doesn't yet prove
that the set of real numbers is also. However, it's probably getting there,
and may only require a few steps more to prove also that.)

-- 
                                                          - Warp

Post a reply to this message

>> Genuine question then, why isn't the set of real numbers countable,
>> given that you could represent each one with two integers (one for the
>> digits before the decimal point, one for the digits after the decimal
>> point)?
>
> The set of all strings that contain all possible combinations of two
> or more digits (in other words, the set of all possible decimal
> representations) is uncountable. In other words, it's not possible to
> enumerate them all. This might be a bit surprising (it was to me...)

This is surprising to me too, I would have thought that because every 
string of digits (without a decimal place) represents an integer then it 
would be countable.

> Let's assume that it is possible to enumerate every single possible infinite
> string of digits. Thus we have a(n infinite) list of numbered strings (its
> order doesn't really matter, as long as it contains *all* of them.) For
> example like:
>
> 1: 1001101110...
> 2: 0010110111...
> 3: 1100011110...
> 4: 0111001101...
> ...
>
> If the assumption is true, that means that this list is complete, ie. it
> contains every single possible string using those two digits. Which would
> mean that it's impossible to construct a string that does not appear in
> that list.
>
> However, we can construct such a string: Take the first digit of the first
> string and invert it, the second digit of the second string and invert it,
> and so on. In other words, with the example above the string would be
> 0110... etc.

I understand that, but don't understand why that proves it is 
uncountable. Because you can do a similar thing with a list of all 
natural numbers, ie calculate the sum and then you get a new natural 
number that wasn;t in the list to start with.

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> >> Genuine question then, why isn't the set of real numbers countable,
> >> given that you could represent each one with two integers (one for the
> >> digits before the decimal point, one for the digits after the decimal
> >> point)?
> >
> > The set of all strings that contain all possible combinations of two
> > or more digits (in other words, the set of all possible decimal
> > representations) is uncountable. In other words, it's not possible to
> > enumerate them all. This might be a bit surprising (it was to me...)

> This is surprising to me too, I would have thought that because every 
> string of digits (without a decimal place) represents an integer then it 
> would be countable.

Note that an infinite string of digits does not represent an integer
(because no integer is infinite.) That's probably what causes the
confusion.

("No real number is infinite either." That's correct. But the decimal
representation of a real number can be.)

That's not to say that no set containing infinite decimal representations
is countable. For example the set of rational numbers contains infinitely
many values which decimal representation is infinite, yet this set is
countable. (It just that, obviously, the set of rationals does not
contain *all* possible infinite decimal representations.)

"Decimal representation" in itself might be a problematic thing to rely
on when dealing with infinite sets, because it's not very intuitive.

> > However, we can construct such a string: Take the first digit of the first
> > string and invert it, the second digit of the second string and invert it,
> > and so on. In other words, with the example above the string would be
> > 0110... etc.

> I understand that, but don't understand why that proves it is 
> uncountable.

Because there's no way to enumerate them. (More technically, there exists
no bijective function between the two sets.)

> Because you can do a similar thing with a list of all 
> natural numbers, ie calculate the sum and then you get a new natural 
> number that wasn;t in the list to start with.

You cannot sum all the natural numbers because there's an infinite
amount of them.

Any sum of a finite amount of natural numbers gives a number that was
already in the set.

-- 
                                                          - Warp

Post a reply to this message

> Note that an infinite string of digits does not represent an integer
> (because no integer is infinite.) That's probably what causes the
> confusion.

True.

> ("No real number is infinite either." That's correct. But the decimal
> representation of a real number can be.)

That also probably explains why you can't represent every real number 
with two integers (one for the fractional part and one for the integral 
part).

>> Because you can do a similar thing with a list of all
>> natural numbers, ie calculate the sum and then you get a new natural
>> number that wasn;t in the list to start with.
>
> You cannot sum all the natural numbers because there's an infinite
> amount of them.

I guess the bit I got confused with / didn't understand is that you can 
have a set with an infinite number of natural numbers, yet none of the 
natural numbers themselves are infinite in size.

Post a reply to this message

On 7/16/2013 12:35 AM, scott wrote:
>> Integers are allowed to have infinite digits before the decimal place.
>> Reals are allowed them after the decimal place as well. ;-)
>
> Genuine question then, why isn't the set of real numbers countable,
> given that you could represent each one with two integers (one for the
> digits before the decimal point, one for the digits after the decimal
> point)?

I didn't comment on Orchid's quip since I assume he was joking, but you 
are rightly confused because it is completely incorrect.  Real numbers 
do indeed have an "integer before the decimal place", but critically 
*not* necessarily "after the decimal place".  The reason is that there 
may be infinitely many digits after the decimal place, all integers only 
have a finite number of digits.

Post a reply to this message

> I didn't comment on Orchid's quip since I assume he was joking, but you
> are rightly confused because it is completely incorrect.  Real numbers
> do indeed have an "integer before the decimal place", but critically
> *not* necessarily "after the decimal place".  The reason is that there
> may be infinitely many digits after the decimal place, all integers only
> have a finite number of digits.

How do I better understand that all integers have a finite number of 
digits, but there are infinite number of them? That's the bit I'm 
struggling with.

The way I see it, the number of positive integers with N or fewer digits 
is 10^N, so if N is finite then 10^N has got to be finite too?

Post a reply to this message

On 7/16/2013 8:06 AM, scott wrote:
>
> How do I better understand that all integers have a finite number of
> digits, but there are infinite number of them? That's the bit I'm
> struggling with.
>
> The way I see it, the number of positive integers with N or fewer digits
> is 10^N, so if N is finite then 10^N has got to be finite too?
>

Ahh I see.  This is one of many counter intuitive things which happens 
with infinities.  Perhaps the issue here is that there are two different 
ways that we tend to think about sizes of things at play here, and it's 
not always made clear which one we're talking about:

1) finite vs. infinite
2) bounded vs. unbounded

#1 here refers the the number of elements within a set, for instance the 
set {3,7,9} has three elements, the set of integers has infinitely many 
elements, and the set of reals has "even more infinitely" many elements 
in a certain well defined sense.

#2 instead relates to some notion of the "size" of the different 
elements within a set.  This is tricky because depending on what you're 
doing you might care about a different definition of what "size" is. 
For example with positive integers you might care about the number of 
digits, but with real numbers you might care about the magnitude of the 
number with relation to the < and > relations (which is certainly *not* 
the same as the number of digits in it!).  Often you just figure it out 
from context.

So this tells you a little bit about the concepts, but I think that some 
examples are useful in getting the mathematical intuitions.  For instance:

* If you have a set of integers, where the number of digits in each 
integer is bounded, then there are only finitely many integers in that 
set (as you said, at most 10^N).

* If you have a set of integers where the number of digits in each 
integer is unbounded, then there are infinitely many integers in that 
set.  For although each particular integer has only a finite number of 
digits, for any particular number N, you can always "look further" and 
find an integer with more than N digits.

I think this last one is probably where your confusion comes from. 
There is more that you can say about the relationships between the 
concepts of finite/infinite and bounded/unbounded, but hopefully the 
small bit I've covered this helps clarify things a little.

You can, by the way, give precise mathematical definitions of these 
concepts, but I've decided not to do so since I wasn't sure it would 
actually make the issue more clear.

Post a reply to this message

> Ahh I see.  This is one of many counter intuitive things which happens
> with infinities.  Perhaps the issue here is that there are two different
> ways that we tend to think about sizes of things at play here, and it's
> not always made clear which one we're talking about:
>
> 1) finite vs. infinite
> 2) bounded vs. unbounded
>
> #1 here refers the the number of elements within a set, for instance the
> set {3,7,9} has three elements, the set of integers has infinitely many
> elements, and the set of reals has "even more infinitely" many elements
> in a certain well defined sense.
>
> #2 instead relates to some notion of the "size" of the different
> elements within a set.  This is tricky because depending on what you're
> doing you might care about a different definition of what "size" is. For
> example with positive integers you might care about the number of
> digits, but with real numbers you might care about the magnitude of the
> number with relation to the < and > relations (which is certainly *not*
> the same as the number of digits in it!).  Often you just figure it out
> from context.
>
> So this tells you a little bit about the concepts, but I think that some
> examples are useful in getting the mathematical intuitions.  For instance:
>
> * If you have a set of integers, where the number of digits in each
> integer is bounded, then there are only finitely many integers in that
> set (as you said, at most 10^N).
>
> * If you have a set of integers where the number of digits in each
> integer is unbounded, then there are infinitely many integers in that
> set.  For although each particular integer has only a finite number of
> digits, for any particular number N, you can always "look further" and
> find an integer with more than N digits.

I guess the problem is I'm thinking of each "integer" as a set of 
digits. This set has a finite yet unbounded number of elements. But then 
if you make a set of all possible "integers" you don't get a set with a 
finite yet unbounded number of elements, you get a set with an infinite 
number of elements.

Post a reply to this message

On 7/17/2013 12:44 AM, scott wrote:
>
> I guess the problem is I'm thinking of each "integer" as a set of
> digits. This set has a finite yet unbounded number of elements. But then
> if you make a set of all possible "integers" you don't get a set with a
> finite yet unbounded number of elements, you get a set with an infinite
> number of elements.

It is a strange concept, and it's not for nothing that some people 
reject it entirely.  I don't really have an explanation which will make 
it less strange, except to mention that mathematically it might be best 
to think of "infinite" as meaning "not finite".

Let me explain a bit more.  If a set S has a finite number of elements, 
then there is some integer n such that S has n elements (this is pretty 
much the definition of "finite").  Therefore, if you can show that no 
matter which number n you pick, S will always have more then n elements, 
they s is not finite, and therefore infinite.

You probably already understand this reasoning, if which case I doubt it 
did much to make it "feel" like it makes sense.  The real strange thing 
that's going on is that you're grouping all the integers into a single 
set.  This is sort of the difference between unbounded and infinite in 
this case (i.e. with positive integers).  The individual integers in 
this set increase without bound, but it's the while set of all of them 
that's infinite.  With relation to the above definition of "finite" you 
can think that for any particular integer i, there's some n such that i 
<= n (obviously), as soon as you consider *all* the integers as a single 
thing this stops being true.

I don't know if this ever starts to make sense so much as you just start 
to get used to it.

Post a reply to this message

On Sat, 13 Jul 2013 15:50:42 +0200, Warp <war### [at] tagpovrayorg> wrote:

> 1) Does a unit square contain the same amount of points as a unit line?
> (We are talking about real numbers here.)
>
> 2) If yes, that means there has to be a 1-to-1 mapping between those
> points. Give a function that expresses such a mapping.
>
> 3) If the answer to the first question is yes, then it follows that
> the amount of points inside a unit cube is also the same as the amount
> of points on a unit line. The same for a four-dimensional hypercube,
> and so on. Can you give a generic function that gives a 1-to-1 mapping
> between a unit line and an n-dimensional unit cube?
>
> 4) So the next question is: Does a countably-infinite-dimensional unit
> cube contain the same amount of points as a unit line? If yes, can you
> give a 1-to-1 mapping between them?
>
> 5) And the logical extreme: Does an uncountably-infinite-dimensional
> unit cube contain the same amount of points as a unit line? Explain why.
> (Also explain how the number of dimensions can be uncountably infinite.
> That seems to defy the definition of "dimension".)
>

I don't know.

Maybe I should start with something simpler.

Infinity + Infinity = ?

Is there any other answer than 2(Infinity)?

If so please explain.

-Unlike Warp I don't know the answer and really want to know :)

-- 
-Nekar Xenos-

Post a reply to this message