Orchid XP v8 wrote:
> But there are surely *more* rational numbers than natural numbers?
> 
> Actually, let's try something easier: Common sense tells you that the 
> number of 2D coordinates is obviously [vastly] greater than the number 
> of 1D points. Yet set theory asserts that both sets are exactly the same 
> size. How can this be?


First, we need a clear definition of `size' which will work for infinite 
sets:

Given two sets, A, and B, we'll say that B is at least as large as A (B 
 >= A) if there is a function which maps every element in A into a 
unique element in B.

If no such function is possible, then we say that A is larger than B (A 
 > B).

If A >= B and B >= A. Then A and B are of the same size (A <=> B).

(Note my ASCII isn't standard here, but I think it works intuitively 
enough).


Let's start even simpler, and show that the set of natural numbers, N, 
is the same size as the set of integers, I.  Clearly I >= N, since it's 
trivial to map easy natural number into a unique integer.

To show that N >= I, consider the function

function f(i) {
	if i < 0 {
		return -2*i - 1
	} else {
		return 2*i
	}
}

You can check that (assuming I didn't make a mistake) this function maps 
each integer into a unique natural number.  This N >= I

Since we have I >= N and N >= In so I <=> N.


Also note that there's a trick that works for proving that N >= S for 
many different sets S -- just show that you can represent every element 
in S exactly in a computer program.  Since the program can be compiled 
to binary, the compiler does the work of defining the function from 
element in S to a unique element in N for you.

Post a reply to this message

Orchid XP v8 wrote:
> But even given infinite time and memory, a computer *still* can't solve 
> the Halting Problem though. Even theoretically. Don't ask me why...


Here's the idea.  Assume we have a function halts(P,i), which takes a 
function P and returns true of P(i) halts and false otherwise.  Then 
write the following function, D:

function D(i) {
	if halts(i,i) {
		while true
	} else {
		return 0
	}
}

Note that since, mathematically, be consider all programs as integers 
(for example their compiled binary form), the line halts(i,i) is ok 
since we can interchange programs and integers to our heart's desire.

Now, when happens if we try to compute halts(D,D)?

(I'll leave this to work out for yourself, as it's a good exercise)


Once you groked this, note that although the halts function is perfectly 
well defined mathematically, we've just showed that it's impossible to 
ever program, and therefore it is not a computable function.  You can of 
course, program a halts function that works perfectly well on a subset 
of all inputs, but you can't write to to determine the answer for all 
possible programs.

Post a reply to this message

As a quick additional note, you may observe that if we order the 
possible inputs the halts function (both considered as integers) in a 
big matrix, then the the call halts(i,i) is taking elements along the 
*diagonal* of this matrix, and the function D is modifying the output of 
the halts function along this diagonal.  Hey, diagonals! It's another 
diagonalization proof! The wikipedia article has a bit more thorough 
explanation of this:

http://en.wikipedia.org/wiki/Halting_problem, bottom of the `Sketch of 
proof' section.

Post a reply to this message

Jim Henderson wrote:
>
> *ding* - light bulb just went on here.  I was trying to figure this one 
> out, and it just intuitively appeared to me.
> 

It's that sort of moment of epiphany that I love about learning this 
sort of stuff.  One moment it seems totally false and the next moment it 
somehow makes sense, a bit it seems obvious!

 > The weird thing is that I can't even explain it, but I understand it.

As for the proof, this site explains it reasonably well i think: 
http://www.math.hmc.edu/funfacts/ffiles/30001.3-4.shtml

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Kevin Wampler wrote:

> > I suggest you start by proving that there's the same number of rationals 
> > as natural numbers.

> But there are surely *more* rational numbers than natural numbers?

  There's an infinite amount of rational numbers. There's an infinite
amount of natural numbers. Which set of numbers is larger?

  The answer is that the sets have the same size. That's because a unique
mapping from each rational number to a distinct natural number can be
constructed. This means that for each rational number there exists a
distinct natural number. Hence the amount of both is the same.

  Now, why this is even relevant? It's relevant because real numbers,
quite surprisingly, do *not* have such a mapping to natural numbers.
It's impossible to construct a unique mapping from each real number to
a distinct natural number. There are "too many" reals for this. For this
reason the set of real numbers is "larger" than the set of natural numbers
(and consequently the set of rational numbers).

  Where this gets unintuitive is when you think about the relation between
rational numbers and real numbers: Take any two rational numbers, and
between them there will be an infinite amount of real numbers. Take any
two real numbers, and between them there will be an infinite amount of
rational numbers. No matter which pair of numbers you choose, there will
always be numbers from the other set between them. Yet the set of real
numbers is larger than the set of rational numbers.

> Actually, let's try something easier: Common sense tells you that the 
> number of 2D coordinates is obviously [vastly] greater than the number 
> of 1D points. Yet set theory asserts that both sets are exactly the same 
> size. How can this be?

  You may be confusing the density of the numbers with their total amount.
Even though more rational numbers can appear in a smaller place than
natural numbers doesn't mean their total amount is larger.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 wrote:
>> Map each real number to a positive integer.
> 
> Um... like, how? There's more of them...

	What he meant to say was that no matter how you map integers to real 
numbers, one can construct a real number that has no integer mapped to it.

Me: There's no way to make a 1-1 correspondence between reals and integers.

You: Yes there is.

Me: I defy you to provide me with such a mapping.***

You: OK. How about this one?

Me: (Using Darren's recipe) - here's a real number that isn't mapped to 
an integer.

*** Not a mathematically sound argument. In mathematics, you can prove 
the existence of certain sets, and you can also prove that you can never 
   explicitly exhibit those sets (i.e. you can *only* show they exist - 
it is mathematically impossible to demonstrate them, though). So an 
argument that shows one cannot exhibit/construct a certain set does not 
imply that they don't exist.

Some day I have to formally learn how that is.

-- 
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."


                     /\  /\               /\  /
                    /  \/  \ u e e n     /  \/  a w a z
                        >>>>>>mue### [at] nawazorg<<<<<<
                                    anl

Post a reply to this message

Warp wrote:
>   It kind of "makes sense" that there are "more" reals than integers.
> What is more unintuitive is that the amount of rational numbers is the
> same as the amount of integers.

	That, and the fact that R^n has as many points as R (for positive 
integers n).

>   (Curiously, to a mathematician it's the other way around: The latter
> fact is quite intuitive, but the former is puzzling. Some even go as
> far as half-jokingly saying that "there just can't be more reals than
> integers, it doesn't make sense; there would be too many".)

	That's not been my experience with mathematicians - they find both to 
be fairly interesting.

	Of course, a lot of this "weirdness" is merely due to the definition of 
equality of the size of two sets. It was a convenient one to deal with 
infinite sets.

-- 
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."


                     /\  /\               /\  /
                    /  \/  \ u e e n     /  \/  a w a z
                        >>>>>>mue### [at] nawazorg<<<<<<
                                    anl

Post a reply to this message

Darren New wrote:
> What is unintuitive to me is that if you draw a numberline on the wall 
> and toss a dart at it (figuratively speaking), your probability of 
> hitting a rational number is zero. That is, there are so many more reals 
> than rationals that the chance of picking a real that's rational at 
> random is literally zero. It would seem there's *some* epsilon chance, 
> but apparently not. :-)

	Well, your probability of hitting a given real number is also 0. Same 
amount of weirdness.

	I was always somewhat uncomfortable with that aspect of probability on 
continuous distributions. Because "in real life" it isn't impossible for 
me to hit right at the center when thrown at random.

	And then there's the whole issue of interpretation of probability and 
especially statistics - I recently got more interested in the basics 
(saw too many funny stats, and wanted to learn it well enough to 
recognize the kooky ones).

	Advanced probability theory involves measure theory - which I have yet 
to study properly. My guess is what you're saying holds true because the 
set of rationals is a set of measure 0 w.r.t. to the measure they use in 
probability.

-- 
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."


                     /\  /\               /\  /
                    /  \/  \ u e e n     /  \/  a w a z
                        >>>>>>mue### [at] nawazorg<<<<<<
                                    anl

Post a reply to this message

Warp wrote:
>> Map each real number to a positive integer. Now for each number, take 
>> the real number whose first digit differs from the first digit of the 
>> first real, whose second digit differs from the second digit of the 
>> second real, etc. You've just constructed a real which is, by 
>> construction, not on your list that maps all real numbers to integers.
> 
>   I think that the concept you are trying to explain could become clearer
> if you also prove why the amount of rational numbers between 0 and 1 is
> the *same* as the amount of integers. (In other words, each rational
> number can be uniquely mapped to an integer, and there are no rational
> numbers that can't be.)

	Yes. And to be formally correct, he has to deal with the fact that 
0.3459999999.... is also 0.346 and adjust a few minor details to account 
for it.

	

-- 
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."


                     /\  /\               /\  /
                    /  \/  \ u e e n     /  \/  a w a z
                        >>>>>>mue### [at] nawazorg<<<<<<
                                    anl

Post a reply to this message

Orchid XP v8 wrote:
> What is Ackermann's function, why does it grow so fast, and why does 
> anybody care anyway?

	Not sure if this will answer your question, but it's a fun read:

http://www.scottaaronson.com/writings/bignumbers.html

	


-- 
"Auntie Em: Hate Kansas. Hate You. Took Dog. -Dorothy."


                     /\  /\               /\  /
                    /  \/  \ u e e n     /  \/  a w a z
                        >>>>>>mue### [at] nawazorg<<<<<<
                                    anl

Post a reply to this message