 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] san rrcom> wrote:
> Stuff like proofs that the number of real numbers 0 <= N < 1 is larger
> than the number of positive integers.
> 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.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>> The class of computable functions (also known as recursive functions)
>> are something that you're familiar with.
>
> Er... no.
Well, maybe not by name, but you're certainly familiar with the concept.
For example, you can see that the Ackermann function is computable
while the Halting function is not. At the very least, since you code a
lot you're intuitively familiar with the notion of what sorts of
functions you can code (though maybe less so what sorts you *can't* code).
> I see... Thank you for the illumination. Now tell me what a
> diagonalization argument is, and how you pronounce it without sounding
> stupid. ;-)
I pronounce it diagonal (as in the diagonal of a square) ization (as in
rasterization, memorization, etc.).
I don't have a formal definition, but perhaps I can give some of the
intuition. The name derives from `Cantor's diagonal argument' for why
the set of real numbers is strictly larger than the set of rationals.
If you're not familiar with this proof you should read about it, as it's
both absolutely brilliant and extremely simple.
I've using the term more generally of course, but the basic idea is the
same. Let's say you have two set of elements, A and B, and you want to
provide a proof that there exist something in B which is not in A. One
way you can do this that ends up being useful much of the time is to
define an element, x, in B in such a way that it represents a
modification of each element in A, and by doing so we prove that x
cannot be in A since it's different that each element of A.
This may sound a bit odd, and it oversimplifies a lot too, but I think I
can explain it better with examples.
In the case of Cantor's original argument A is the set of natural
numbers and B is the set of reals. If we assume that there are the same
number of natural numbers and reals, then you could provide an
(infinite) list of all the real numbers. To form a real number that
cannot be in this list, we form a number, x, which has at each digit a
modification of a different real number in a hypothetical list. Means
that x cannot be in our list, and thus by contradiction that it's
impossible to form such a list in the first place.
The halting argument has a similar flavor. In this case we want to show
that there are functions that are not computable, so we create define a
function that, given a program, determines if it halts and then modifies
that behavior. But this program can't work on its own input and thus
cannot be computable in the first place.
There's several ways to apply this idea to show that there are total
computable functions which are not primitive recursive, but here's one.
Represent each primitive recursive program as a natural number (by
compiling it to binary if you wish). Then, define a new function from
the naturals to the naturals which, when given a number, decompiles it
into a primitive recursive function, runs the function with its own
numerical representation as input, and adds one to the result (note that
the primitive recursive function is guaranteed to always halt). The
resulting function is computable, but cannot be primitive recursive
(since then for some input it would have it give its own output plus one!).
You can use the same idea to construct a computable function that grows
faster than any primitive recursive function, or a non-computable
function which grows faster than any computable function (eg. the Busy
Beaver function). It's also the same sort of idea that Goedel used in
his proof that some theorems are unprovable. Personally, I find the
idea to be probably the most interesting discovery of 20th century
mathematics (counting 1891 when Cantor published his proof as "20th
century" of course), so needless to say I recommend you read more about
it if you're intrigued.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 20:31:04 +0100, Orchid XP v8 wrote:
>>>> The class of computable functions (also known as recursive functions)
>>>> are something that you're familiar with.
>>> Er... no.
>>
>> Do you understand the concept of recursion?
>
> Sure.
>
> I don't know much about the formal theory of computation though. I
> always assumed that "computable function" just meant "function that can
> be computed by a computer". Apparently the definition is much less
> general that than...
Ah, I see.
I also don't have a good grasp of formal computational theory. I also
wouldn't have thought that "computable functions" was limited just to
recursive functions, though, just from the name.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> always assumed that "computable function" just meant "function that can
> be computed by a computer".
Yes. But the question is, what functions *are* computable by a computer?
That's kind of the point.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> Mmm, I see. Yes, the third identity requires you to either recurse twice
> (requiring more stack), or to build a table of results to avoid the
> extra recursion (also requiring more memory).
More concrete examples: Heap sort can be implemented iteratively (the
heap sort algorithm itself only requires O(1) memory to sort an array
of values). AFAIK, quicksort cannot be implemented iteratively.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Darren New wrote:
>
>> Map each real number to a positive integer.
>
> Um... like, how? There's more of them...
Yes. That's the point. Assume you do that. Then construct a real not on
the list. Obviously, your assumption that it was possible to do that
was wrong.
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Orchid XP v8 wrote:
> > Darren New wrote:
> >
> >> Map each real number to a positive integer.
> >
> > Um... like, how? There's more of them...
> Yes. That's the point. Assume you do that. Then construct a real not on
> the list. Obviously, your assumption that it was possible to do that
> was wrong.
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.
(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".)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Darren New wrote:
>
>> Map each real number to a positive integer.
>
> Um... like, how? There's more of them...
It's a proof by contradiction, so you start by assuming that you can
build such a map and then derive from that a contradiction, thus
invalidating the premise that you the map was possible.
It's wise to learn not to trust your intuitions too much with this sort
of thing. As warp pointed out, there are the same number of rationals
as natural numbers, whereas intuitively you might think that there's
more rationals than integers and the same number of reals as rationals.
And intuition becomes even less of a guide when you start reasoning
about more complicated sets.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> The class of computable functions (also known as recursive functions)
>>> are something that you're familiar with.
>>
>> Er... no.
>
> Well, maybe not by name, but you're certainly familiar with the concept.
> For example, you can see that the Ackermann function is computable
> while the Halting function is not. At the very least, since you code a
> lot you're intuitively familiar with the notion of what sorts of
> functions you can code (though maybe less so what sorts you *can't* code).
Proving that something exists is a *comparatively* easy task: Just hold
up one of them, and the fact that you're standing there holding it kinda
proves it exists.
Proving that something does *not* exist... well that's a whole other
kettle of fish. ;-)
[BTW... Who the HELL has fish in a kettle??]
> I don't have a formal definition, but perhaps I can give some of the
> intuition. The name derives from `Cantor's diagonal argument' for why
> the set of real numbers is strictly larger than the set of rationals. If
> you're not familiar with this proof you should read about it, as it's
> both absolutely brilliant and extremely simple.
>
> I've using the term more generally of course, but the basic idea is the
> same. Let's say you have two set of elements, A and B, and you want to
> provide a proof that there exist something in B which is not in A. One
> way you can do this that ends up being useful much of the time is to
> define an element, x, in B in such a way that it represents a
> modification of each element in A, and by doing so we prove that x
> cannot be in A since it's different that each element of A.
>
> This may sound a bit odd, and it oversimplifies a lot too, but I think I
> can explain it better with examples.
>
> In the case of Cantor's original argument A is the set of natural
> numbers and B is the set of reals. If we assume that there are the same
> number of natural numbers and reals, then you could provide an
> (infinite) list of all the real numbers. To form a real number that
> cannot be in this list, we form a number, x, which has at each digit a
> modification of a different real number in a hypothetical list. Means
> that x cannot be in our list, and thus by contradiction that it's
> impossible to form such a list in the first place.
>
> The halting argument has a similar flavor. In this case we want to show
> that there are functions that are not computable, so we create define a
> function that, given a program, determines if it halts and then modifies
> that behavior. But this program can't work on its own input and thus
> cannot be computable in the first place.
>
> There's several ways to apply this idea to show that there are total
> computable functions which are not primitive recursive, but here's one.
> Represent each primitive recursive program as a natural number (by
> compiling it to binary if you wish). Then, define a new function from
> the naturals to the naturals which, when given a number, decompiles it
> into a primitive recursive function, runs the function with its own
> numerical representation as input, and adds one to the result (note that
> the primitive recursive function is guaranteed to always halt). The
> resulting function is computable, but cannot be primitive recursive
> (since then for some input it would have it give its own output plus one!).
>
> You can use the same idea to construct a computable function that grows
> faster than any primitive recursive function, or a non-computable
> function which grows faster than any computable function (eg. the Busy
> Beaver function). It's also the same sort of idea that Goedel used in
> his proof that some theorems are unprovable. Personally, I find the
> idea to be probably the most interesting discovery of 20th century
> mathematics (counting 1891 when Cantor published his proof as "20th
> century" of course), so needless to say I recommend you read more about
> it if you're intrigued.
...OK, and this is the kind of thing that I sit down and read and end up
feeling utterly perplexed.
Logic, set theory, category theory, number theory, complexity theory,
topology... they all seem to abound with utterly counter-intuitive laws
and theorums. It's really quite mind-bending.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> always assumed that "computable function" just meant "function that
>> can be computed by a computer".
>
> Yes. But the question is, what functions *are* computable by a computer?
> That's kind of the point.
The question, surely, is what functions are *not* computable by a
computer? ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>
> I don't know much about the formal theory of computation though. I
> always assumed that "computable function" just meant "function that can
> be computed by a computer". Apparently the definition is much less
> general that than...
>
Not really! Formally you tend to consider only functions which take a
single natural number as input and provide a single number as output.
This may seem restrictive, but remember that everything on your computer
can be considered as being as represented by integers (in binary)
anyway, so it's not really a restriction at all.
As for the `function' part of `computable function' you of course mean
something which only takes an input and provides an output, and thus
doesn't allow for user interaction and the such, but you can always
model user interaction as simply providing the inputs to a an
appropriately defined proper function so even this isn't really a
restriction.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> What is more unintuitive is that the amount of rational numbers is the
> same as the amount of integers.
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. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> 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. :-)
Yet between any two chosen real numbers there's an infinite amount of
rational numbers, and vice-versa. There's no range of real numbers where
there wouldn't be an infinite amount of rational numbers.
Yet there are "more" real numbers than rational numbers.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 21:00:36 +0100, Orchid XP v8 wrote:
>>> always assumed that "computable function" just meant "function that
>>> can be computed by a computer".
>>
>> Yes. But the question is, what functions *are* computable by a
>> computer? That's kind of the point.
>
> The question, surely, is what functions are *not* computable by a
> computer? ;-)
I would think any problem that was mathematically intractable. :-)
Or put another way, some computational problems where the growth function
is exponential. Some of those problems are solved on a small scale
computationally (like the traveling salesman problem), but as the scale
of the problem grows, the complexity grows as well.
At least that's what I remember from my discrete maths class in the early
90's. :-)
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 20:59:40 +0100, Orchid XP v8 wrote:
> Proving that something exists is a *comparatively* easy task: Just hold
> up one of them, and the fact that you're standing there holding it kinda
> proves it exists.
Depends on the nature of the proof. Try taking that argument to someone
with a background in philosophy. :-)
"My universe is what happens to my eyes and my ears; anything else is
surmise and hearsay."
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> ...OK, and this is the kind of thing that I sit down and read and end up
> feeling utterly perplexed.
>
> Logic, set theory, category theory, number theory, complexity theory,
> topology... they all seem to abound with utterly counter-intuitive laws
> and theorums. It's really quite mind-bending.
Don't be intimidated, I think that the diagonalization arguments are
actually rather easy to understand for someone who doesn't have a lot of
background in this sort of thing. It's a bit mind blowing at first, but
at some point it'll click and everything will make sense, something
which I haven't found to be the case with eg. set theory.
I suggest you start by proving that there's the same number of rationals
as natural numbers. Once you've done that study Cantor's diagonal
argument until you understand why there's more reals than natural
numbers, and thus more reals than rationals. Ask for help if you're
confused and I'll provide it when I read the newsgroup (or more likely,
someone else will beat me to it).
From there I'd take a look at the definition of the busy beaver
function as an example of the same sort of technique on computable
functions, and then look at the halting theorem in the same light.
Sooner or later it should all start to seem intuitive and
straightforward, even if it's a bit mind-bending at the moment.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> The question, surely, is what functions are *not* computable by a
>> computer? ;-)
>
> I would think any problem that was mathematically intractable. :-)
Well, if you don't know "how" to solve a problem then you can't write a
program that does it. That's true enough. I'm not sure it makes it not a
"computable function" though...
> Or put another way, some computational problems where the growth function
> is exponential. Some of those problems are solved on a small scale
> computationally (like the traveling salesman problem), but as the scale
> of the problem grows, the complexity grows as well.
>
> At least that's what I remember from my discrete maths class in the early
> 90's. :-)
Nope. That's not "impossible" to compute, just really damned slow. ;-)
To a mathematician, 10^1534 years is a finite amount of time. In
practical terms it's a ridiculously long time - many times longer than
the current age of the universe, and plenty long enough for any
hypothetical computer to exhaust all the available energy in the
universe without reaching the end - but still, technically, a finite
run-time.
If we're talking about what a computer can *theoretically* calculate.
It's just a matter of leaving the machine running for long enough.
But even given infinite time and memory, a computer *still* can't solve
the Halting Problem though. Even theoretically. Don't ask me why...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
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. :-)
Probability of hitting an object with a size of zero: 0%. ;-)
Probability of hitting an uncountable infinity of objects each with a
size of zero: 100%.
GO FIGURE!
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 13:09:40 -0700, Kevin Wampler wrote:
> I suggest you start by proving that there's the same number of rationals
> as natural numbers.
*ding* - light bulb just went on here. I was trying to figure this one
out, and it just intuitively appeared to me.
The weird thing is that I can't even explain it, but I understand it.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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?
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?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> 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.
Yes. But I meant my probability of hitting *any* rational number is zero.
> 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.
I think that was the technical term I saw, yes. Just seemed strange. Not
wrong, but strange. :-)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> > Well, your probability of hitting a given real number is also 0.
> > Same amount of weirdness.
> Yes. But I meant my probability of hitting *any* rational number is zero.
I think that this confuses people because they think that if the
probability for something is 0, that means that it's *impossible* for
that something to happen.
This is indeed so in the discrete case. However, in this case the
probability is 0 because the total probability of 1 has been divided
among an *infinite* amount of numbers. Thus, mathematically, the resulting
probability of hitting a given number is 0, as 1/infinite = 0.
*After* you have thrown the dart, the probability to hit the number
the dart did hit grows to 1 (or 100%).
Or if we say the same thing in another way: Even though there is an
infinite amount of numbers, that doesn't mean you can't choose one.
(I really wonder if this has any relation whatsoever to the so-called
axiom of choice.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> *After* you have thrown the dart, the probability to hit the number
> the dart did hit grows to 1 (or 100%).
But is the probability that it hit any rational number (vs any
irrational number) non-zero at that point? If you do it countably many
times, will you *ever* hit *any* rational number?
> (I really wonder if this has any relation whatsoever to the so-called
> axiom of choice.)
That's pretty much exactly what the axiom of choice is. Given an
infinite set of sets, can you create a set by picking one element from
each subset?
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Warp" <war### [at] tagpovrayorg> wrote in message
news:4877ba85@news.povray.org...
> 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.
And now the really fun part: Is there a subset of real numbers that is "more
numerous" than intergers or rationals but less so than reals?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
somebody wrote:
> And now the really fun part: Is there a subset of real numbers that is "more
> numerous" than intergers or rationals but less so than reals?
That's actually a long-standing problem, but I remember hearing that
someone had figured out the answer must be "No." I believe they were
waiting on others verifying the proof. (Which, as you can imagine, must
be pretty hairy.)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
somebody wrote:
> And now the really fun part: Is there a subset of real numbers that is "more
> numerous" than intergers or rationals but less so than reals?
I bet even Gail didn't know that Oracle has solved *that* problem.
http://laurentschneider.com/wordpress/2007/10/what-is-bigger-than-infinity.html
(Check out the comments, too.)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
somebody wrote:
> And now the really fun part: Is there a subset of real numbers that is "more
> numerous" than intergers or rationals but less so than reals?
Apparently, in most maths, it's neither true nor false, but an axiom to
be adopted.
http://en.wikipedia.org/wiki/Continuum_hypothesis
(That's the *actual* answer to the question, methinks.)
--
Darren New / San Diego, CA, USA (PST)
Helpful housekeeping hints:
Check your feather pillows for holes
before putting them in the washing machine.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
>> Well, your probability of hitting a given real number is also 0.
>> Same amount of weirdness.
>
> Yes. But I meant my probability of hitting *any* rational number is zero.
Because both are sets of measure 0 here. That's why it's the same
amount of weirdness.
--
Cut my pizza in six slices, please; I can't eat eight.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> I think that this confuses people because they think that if the
> probability for something is 0, that means that it's *impossible* for
> that something to happen.
>
> This is indeed so in the discrete case. However, in this case the
> probability is 0 because the total probability of 1 has been divided
> among an *infinite* amount of numbers. Thus, mathematically, the resulting
> probability of hitting a given number is 0, as 1/infinite = 0.
Maybe so, but it's not as compelling as a formal proof. In math, you
can't divide by infinity.
I'm not saying it's "wrong", and your message addresses the dilemma in
another way. The question ultimately is the interpretation of
probability. I know the mathematical definition, but how do I give it
meaning in the real world?
--
Cut my pizza in six slices, please; I can't eat eight.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> somebody wrote:
>> And now the really fun part: Is there a subset of real numbers that is
>> "more
>> numerous" than intergers or rationals but less so than reals?
>
> Apparently, in most maths, it's neither true nor false, but an axiom to
> be adopted.
>
> http://en.wikipedia.org/wiki/Continuum_hypothesis
Yes. Haven't studied it, but I remember that the answer was either
"No", or "Can't be decided." Your message makes me think it's the latter.
--
Cut my pizza in six slices, please; I can't eat eight.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Yes. Haven't studied it, but I remember that the answer was either
> "No", or "Can't be decided." Your message makes me think it's the latter.
You are correct. The truth of that conjecture can be proven to be
independent of the ZFC axioms of set theory.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> I bet even Gail didn't know that Oracle has solved *that* problem.
>
> http://laurentschneider.com/wordpress/2007/10/what-is-bigger-than-infinity.html
>
>
> (Check out the comments, too.)
Comments? Seems to be one comment, repeated multiple times. :-P
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Warp wrote:
>> *After* you have thrown the dart, the probability to hit the number
>> the dart did hit grows to 1 (or 100%).
>
> But is the probability that it hit any rational number (vs any
> irrational number) non-zero at that point? If you do it countably many
> times, will you *ever* hit *any* rational number?
>
>> (I really wonder if this has any relation whatsoever to the so-called
>> axiom of choice.)
>
> That's pretty much exactly what the axiom of choice is. Given an
> infinite set of sets, can you create a set by picking one element from
> each subset?
>
I don't see how it directly applies completely directly, but the notion
of choosing elements from sets without need a rule by which to make the
choice is certainly the main feature of both.
As a more mind bending thing than the probability of 0 that you'll hit a
rational number, if you assume that the axiom of choice is true then you
can show that there exists subsets of the real numbers in the unit
interval such that it it's *impossible* to define *any* probability that
the dart will hit an element of it (zero or otherwise).
Essentially the real numbers are numerous enough that with the help of
the axion of choice it's possible to define subsets of the reals that
are so bizarrely structured that the notion of length, area, volume etc.
don't even apply to them. (more specifically, they're known as
non-measurable sets since they don't have a well defined measure).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> 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.
It may seem a bit like cheating, but there's an easy way to define such
a set. Take whatever system you wish to use to construct sets of
natural numbers, so long as you only have a countable number of axioms
and rules. Now, each construction of a set will require a finite set of
derivation steps to define it. Since we have only a countable number of
choices for each derivation step and a finite number of steps in total,
there are the same number of such derivations as there are natural
numbers. Since there are uncountably many subsets of the natural
numbers, there must be some subsets for which there exists no derivation
to construct them. And there you go, a proof of the existence of a set
which by definition it's impossible to construct!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz <m.n### [at] ieeeorg> wrote:
> In math, you can't divide by infinity.
I don't think that's correct. Maybe in *some* branches of math you can't,
but that's certainly not true for *all* branches of math.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
>
>
> 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
>
>
And if you like really big numbers, The Clarkkkkson number is even bigger.
http://qntm.org/?clarkkkkson
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> Not sure if this will answer your question, but it's a fun read:
>
> http://www.scottaaronson.com/writings/bignumbers.html
Yeah, that IS pretty fun actually...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 21:12:29 +0100, Orchid XP v8 wrote:
>>> The question, surely, is what functions are *not* computable by a
>>> computer? ;-)
>>
>> I would think any problem that was mathematically intractable. :-)
>
> Well, if you don't know "how" to solve a problem then you can't write a
> program that does it. That's true enough. I'm not sure it makes it not a
> "computable function" though...
There's a difference, though, between knowing how to solve a problem and
being able to show - mathematically - that the problem grows at an
exponential rate as the size of the problem is increased in a linear
fashion.
>> Or put another way, some computational problems where the growth
>> function is exponential. Some of those problems are solved on a small
>> scale computationally (like the traveling salesman problem), but as the
>> scale of the problem grows, the complexity grows as well.
>>
>> At least that's what I remember from my discrete maths class in the
>> early 90's. :-)
>
> Nope. That's not "impossible" to compute, just really damned slow. ;-)
I don't think it's about a specific size for the problem, but rather the
growth pattern as the size of the problem is increased.
Doing something like calculating aircraft separation is an example of
such a problem - it's the calculation of the intersection of oblique
spheroids (because the separation is IIRC 5,000 feet horizontally and
3,000 feet vertically). With 2 plans that's easy. With 20 planes it
takes more time to calculate the intersections to determine if an
airspace violation has occurred.
With 200 planes, it takes even more time. With 2,000 even moreso.
And at some point, of course, you have to start over because planes
aren't stationary in space - they move.
> If we're talking about what a computer can *theoretically* calculate.
> It's just a matter of leaving the machine running for long enough.
>
> But even given infinite time and memory, a computer *still* can't solve
> the Halting Problem though. Even theoretically. Don't ask me why...
But this is an aspect I hadn't considered.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 11 Jul 2008 14:23:30 -0700, Kevin Wampler wrote:
> 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!
Yeah. That is a nice feeling, isn't it? :-)
> > 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
Cool, thanks for that.
Jim
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Map each real number to a positive integer.
>
> Um... like, how? There's more of them...
http://en.wikipedia.org/wiki/Reductio_ad_absurdum
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
