wu :: forums
« wu :: forums - Denumerability Dilemma »

Welcome, Guest. Please Login or Register.
May 16th, 2024, 8:00pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   general problem-solving / chatting / whatever
(Moderators: william wu, Grimbal, SMQ, Eigenray, towr, Icarus, ThudnBlunder)
   Denumerability Dilemma
« Previous topic | Next topic »
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Denumerability Dilemma  (Read 2999 times)
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Denumerability Dilemma  
« Reply #25 on: Sep 10th, 2003, 1:22pm »
Quote Quote Modify Modify

My intuition says you can make a one to one mapping from the natural numbers..
Of course that make sense since I think it only contains rational numbers.. (Not that I've given it a tremendous amount of thought)
 
[e]::Of course I'm occasionally (all too often) wrong in cases I haven't thought through, luckily mathworld can allways get me back on track. Once I finally bother to check.::[/e]
« Last Edit: Sep 10th, 2003, 1:26pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Denumerability Dilemma  
« Reply #26 on: Sep 10th, 2003, 2:23pm »
Quote Quote Modify Modify

An answer to Countability of the Cantor set:
 

Every point in the Cantor set corresponds to an infinite length binary string. Note that when we iterate the Cantor set we remove middle thirds, which always leaves left thirds and right thirds; from the perspective of the nth iterate, a point in the Cantor set must lie in either the left third or right third of the interval in which it lied in the (n-1)th iterate. So starting from the 0th iterate we can trace a path of binary left/right decisions which will map to a Cantor point in the limit.  
 
Using the diagonalization argument, we can show that the set of infinite length binary strings is uncountable. Thus the Cantor set is uncountably infinite, although it has Lebesgue measure zero!
« Last Edit: Sep 10th, 2003, 2:24pm by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #27 on: Sep 10th, 2003, 3:25pm »
Quote Quote Modify Modify

In fact, the Cantor-Lesbegue function is an increasing continuous function whose derivative = 0 almost everywhere (i.e. everywhere but on a set (the cantor set) of measure zero), yet still carries 0 to 0, and 1 to 1.
 
The restriction of the function to the cantor set is a one-to-one-unto mapping between the cantor set and the entire interval [0,1].
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Denumerability Dilemma  
« Reply #28 on: Sep 11th, 2003, 6:05am »
Quote Quote Modify Modify

Actually, the Cantor set doesn't include just rational numbers. For instance, it includes the number 0.202002000200002... in base 3.
IP Logged

Doc, I'm addicted to advice! What should I do?
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Denumerability Dilemma  
« Reply #29 on: Oct 6th, 2003, 12:55pm »
Quote Quote Modify Modify

on Sep 8th, 2003, 8:33am, Sir Col wrote:
I would argue that any number that we attempt to produce by the infinite nature of the diagonal method remains undefined, therefore it is not possible to claim to have found a new number not in the list ... the new number does not exist and cannot ever be fully defined by the process.

 
At first when I read this, I thought you might be troubled by the idea of making an infinite number of decisions in our proof. If so, I admit I find this a bit troubling too. It makes me ask, why is it OK? Making infinite numbers of decisions comes up in many mathematical proofs, such as the Bolzano-Weierstrauss Theorem proof, in which one chooses elements ad infinitum from increasingly smaller subintervals of a bounded interval to produce a sequence that ultimately converges. It turns out that if you believe the Axiom of Choice, then you are green-lighted to make infinitely many decisions in your proofs! And apparently almost all mathematicians believe the Axiom of Choice. I don't much more about the Axiom of Choice (only heard its definition and name quickly dropped a few times when professors wanted to explain away some troubling things), but I intend to read about it in the near future.
« Last Edit: Oct 6th, 2003, 12:56pm by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #30 on: Oct 6th, 2003, 7:57pm »
Quote Quote Modify Modify

As I have said elsewhere, sometimes people want to argue about the Axiom of Choice, but if you do not have it, it usually does not mean that odd results go away - only that you are able to prove less, including a number of things that are very intuitive, but turn out to be equivalent to the axiom of choice.
 
But Cantor's diagonalization argument does not require the Axiom of Choice. You only need the axiom of choice when there are infinitely many arbitrary choices to be made. But there is no reason to be arbitrary here. Instead of saying "pick any digit other than di, 0, or 9", you can say instead "take the smallest digit other than di and 0". This completely specifies the resultant constructed number without requiring the Axiom of Choice. But the result is still all you need to derive the contradiction.
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Denumerability Dilemma  
« Reply #31 on: Oct 6th, 2003, 10:37pm »
Quote Quote Modify Modify

Ah. OK, thanks; good to know.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Denumerability Dilemma  
« Reply #32 on: Oct 7th, 2003, 9:39am »
Quote Quote Modify Modify

on Oct 6th, 2003, 12:55pm, william wu wrote:
I intend to read about it in the near future.

I recommended a book in another thread: The Mystery of the Aleph, by Amir D. Aczel. It is a book about the search for infinity, in a historical context. Starting with the early Greek ideas, culminating in the life and works of Georg Cantor, and going beyond to discuss modern notions of set theory. It explains that, in 1937, Kurt Gödel proved that the Continuum Hypothesis and the Axiom of Choice were consistent with the set of axioms forming the foundation of mathematics. In 1963, Paul Cohen proved the converse, and thus completed the demonstration that the Continuum Hypothesis and the Axiom of Choice are entirely independent of the axiomatic foundations of mathematics. In other words, the axiomatic rules of mathematics will never tell us anything about the Continuum Hypothesis and, as a result, will never be known to be true or false in our current system. Similarly, the truth (validity) of the Axiom of Choice cannot be, or ever will be, verified within our current system.
 
Because of this independence, mathematicians disagree over the use of the Axiom of Choice. They argue that, saying you can pick from an infinite set is one thing, but being able to do it is something else. As a result, mathematicians will always look for a different way to prove something, and as Cohen and Gödel proved, the Axiom of Choice is not necessary in our current system. But as has already been pointed out here, and elsewhere, it often makes the job of a mathematician much easier. Its consistency with expected results, gives it more and more support for its use.
IP Logged

mathschallenge.net / projecteuler.net
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #33 on: Oct 7th, 2003, 5:26pm »
Quote Quote Modify Modify

I cannot quite agree with the interpretations you are putting on the results of Gödel and Cohen. They have shown that these two statements are independent of the remaining axioms of a common set theory (probably ZF, but I don't remember).  
 
This does not mean that we cannot determine whether or not they are true. It means we are free to decide whether or not we want to take them as true! The independence means that if we choose to take them as axioms, we can freely do so, without fearing the discovery of a paradox (at least no more than we have to fear it in the set theory anyway). If we choose to take their negations as axioms, the same is true.
 
The reason mathematicans prefer when possible to prove theorems without these axioms is simply because anything so proved is a theorem in every theory extending the simpler axioms. So you know it holds if you are assuming the Axiom of Choice to be false, as well as when you assume it to be true.
 
The same thing happens in geometry: All the axioms of Euclidean geometry except the parallel postulate compose what is called "Absolute Geometry". Any theorem of absolute geometry holds in both Euclidean geometry and in Hyperbolic geometry.
« Last Edit: Oct 7th, 2003, 5:27pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Denumerability Dilemma  
« Reply #34 on: Oct 8th, 2003, 12:49am »
Quote Quote Modify Modify

I bow to your great knowledge on this, Icarus; and yes, it was Zermelo-Fränkel set theory axioms.
 
I found an interesting entry in Mathworld (especially the latest finding, in 2000):
http://mathworld.wolfram.com/ContinuumHypothesis.html
IP Logged

mathschallenge.net / projecteuler.net
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Denumerability Dilemma  
« Reply #35 on: Oct 8th, 2003, 3:02am »
Quote Quote Modify Modify

Morris Kline in his book "Mathematics: The Loss of Certainty" (highly recommended, by the way), writes the following:
 
"... two assertions [axiom of choise (AC) and continuum hypothesis (CH)] cannot be proved on the basis of the other ZF axioms.  
 
"Moreover, even if AC is retained in the ZF system, the CH (and certainly then the generalized CH) could not be proved.
 
"(However, the ZF axioms without AC but with GCH do imply AC)".
 
I somehow overlooked this last statement when I read this book many years ago...
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #36 on: Oct 8th, 2003, 8:03pm »
Quote Quote Modify Modify

Yes, I've heard that as well. I've tried to figure out how in the past, but never could come up with a proof. I would guess it comes from somehow showing that if A can be well-ordered, then so can P(A). But I've not seen how to do that.
 
The title of your book brings up another sore point for me in this whole business (though I don't know that the book actually takes this view, just that its title suggests it).
 
With the discovery that other sets of axioms, in disagreement with those already familiar, give rise to completely logical alternative theories, a view arose that all truth is relative. Since what is true in a theory is dependent on its axioms, well then, there is not such thing as "absolute truth". What is true and what is not is dependent on your assumptions.
 
This idea spread out of mathematics, through philosophy, and spilled into society at large, but now completely divorced from any understanding of what was going on in the first place. Now we have pseudo-intellectuals ranting that evidence may be ignored because "that's your truth, not mine".
 
The fact is, the discovery of alternative theories did not abolish the idea of absolute truth in mathematics at all. What it did was show us that the absolute truth was of a different form than we originally thought: We used to believe that it was absolutely true that "the sum of the angles of a triangle is 180o". Now we know that the absolute truth is "Under the logical structure and axioms of Euclidean geometry, the sum of the angles of a triangle is 180o". This is absolutely true, following entirely from the definitions of the concepts included in the sentence.
 
So I would argue that there was no "loss of certainty", just a shift of our certainties to a firmer foundation.
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Denumerability Dilemma  
« Reply #37 on: Oct 9th, 2003, 1:31am »
Quote Quote Modify Modify

In mathematics, 1+1=2, but in the real world, 1[le]1+1[le]3 (depending on interpretation).
 
Suppose I measure two pieces of wood. One measures 1.4 m and the other measures 1.3 m. They're each about 1 m long, but combined they are about 3 m long. Obviously I've made a gross exaggeration of my measure, but if we magnify this potential for error: 100 lots of 1.01 cm (about 1 cm each), amount to 101 cm.
 
So which is absolute truth: the axiom that 1+1=2 (if 0.75[le]1<1.25), 1+1=3 (if 1.25[le]1<1.5), or 1+1=1 (if 0.5[le]1<0.75)?
 
I am not disputing the certainty of our mathematical world, where 1+1=2. But in reality, if we can never be sure of measure, can we ever be sure of our arithmetic? Or are we saying that absolute truth exists in the imaginary, and relative truth exists in reality?
IP Logged

mathschallenge.net / projecteuler.net
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Denumerability Dilemma  
« Reply #38 on: Oct 9th, 2003, 2:40am »
Quote Quote Modify Modify

on Oct 9th, 2003, 1:31am, Sir Col wrote:
In mathematics, 1+1=2, but in the real world, 1[le]1+1[le]3 (depending on interpretation).
That's still true in mathematics, 1<2<3 => 1[le]2[le]3 <=> 1[le]1+1[le]3
Though sometimes in mathematics 1+1=0 , really depends on what system you work in Tongue
 
Quote:
Suppose I measure two pieces of wood. One measures 1.4 m and the other measures 1.3 m. They're each about 1 m long, but combined they are about 3 m long. Obviously I've made a gross exaggeration of my measure, but if we magnify this potential for error: 100 lots of 1.01 cm (about 1 cm each), amount to 101 cm.
If you have to explicitly state 1.4 and 1.3 rather than simply say 1, you imply that they aren't 1. So you then shouldn't use them as 1.
In any case mathematics has no problem whatsoever with errors in measurement.
Let's say ai = 1 + [epsilon]i ( |[epsilon]i| << 1), then  
[sum]i=1nai = n + [sum]i=1n[epsilon]i, where  [sum]i=1n[epsilon]i may be much greater than 1.
You can use statistical methods to make estimates of  the influence of errors, and proper science uses them to convey how reliable their results are.
For instance you can say what the mean error is, [mu] = [sum]i=1n[epsilon]i / n, and the standard deviation.
 
Quote:
So which is absolute truth: the axiom that 1+1=2 (if 0.75[le]1<1.25), 1+1=3 (if 1.25[le]1<1.5), or 1+1=1 (if 0.5[le]1<0.75)?
Neither. Axioms aren't true, nor false. But (axiom => theorem) is absolutely true or false.
 
Quote:
I am not disputing the certainty of our mathematical world, where 1+1=2. But in reality, if we can never be sure of measure, can we ever be sure of our arithmetic? Or are we saying that absolute truth exists in the imaginary, and relative truth exists in reality?
Depends on who 'we' is Tongue  
One might suppose absolute truth exists but is forever out of our reach. But one might also say that we can find a lot of truths from measuring, yet keeping in mind there are errors. Which may make our absolute truths in reality look like  
(measurements [wedge] [lnot]error => theory) and  
(measurement => [lnot] alternative_theory)
« Last Edit: Oct 9th, 2003, 2:51am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Denumerability Dilemma  
« Reply #39 on: Oct 9th, 2003, 4:08am »
Quote Quote Modify Modify

on Oct 9th, 2003, 1:31am, Sir Col wrote:

I am not disputing the certainty of our mathematical world, where 1+1=2. But in reality, if we can never be sure of measure, can we ever be sure of our arithmetic?

I think I have a different concept of arithmetic if this is really a question for you. As towr pointed out, error intervals should be included when doing scientific calculations involving measured quantities, for example.
IP Logged

"You're a jerk, <your surname>!"
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #40 on: Oct 9th, 2003, 7:01pm »
Quote Quote Modify Modify

Of course I agree with Towr & Wowbagger.
 
Another way of looking at the same answer to your mathematical worries is that when used in measurement, numeric symbols have a different definition than they do in mathematics. In mathematics they refer to a single number. In measurement, they refer to a range of numbers. Addition, multiplication, etc also undergo a change in definition when moved from one arena to another.
 
The result? Yes, you get different answers in measurement than in mathematics, but that is alright, because you are talking about different things! Both are logically concise, and both represent absolute truth when the complete truth is stated rather than the short version. They appear to sometimes contradict each other, but only because out of convenience, we are using the same names for our differing concepts.
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Denumerability Dilemma  
« Reply #41 on: Oct 10th, 2003, 3:27am »
Quote Quote Modify Modify

Hey, we're all agreeing – if you read what I actually said! But...
 
My point was that we can never be certain of mathematics when applied to the real world. I concluded by highlighting the irony: in imaginary worlds, where things don't really matter to us, we have absolute truth; whereas in reality, where we are affected, we have relative truth. For example, in mathematics, 1=1, in the real world, 1[approx]1. Every measurable entity is a random variable, in which the only thing we can be certain about is that we will always be uncertain about its size.
 
An interesting question would be, if we don't have absolute truth, do we have any kind of truth at all? The implication of 1[approx]1 is that 1[ne]1.
IP Logged

mathschallenge.net / projecteuler.net
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Denumerability Dilemma  
« Reply #42 on: Oct 10th, 2003, 4:18am »
Quote Quote Modify Modify

on Oct 10th, 2003, 3:27am, Sir Col wrote:
Hey, we're all agreeing – if you read what I actually said! But...
I don't think I agree with that..
 
Quote:
My point was that we can never be certain of mathematics when applied to the real world.
Sure we can, just not those fields of mathematics that works with exact values. But we can for instance use ones that works with ranges and/or uncertainy.
It's just a matter of using the model that actually applies, not one that only approximately fits. But even if you do use the approximative model, there's a subrange of problems for which you can prove, absolutely, that it's within a certain tolerance of the real model.
 
Quote:
I concluded by highlighting the irony: in imaginary worlds, where things don't really matter to us, we have absolute truth; whereas in reality, where we are affected, we have relative truth.
We have both in both. At worst we have 'weaker' truths in reality, but they're still absolute truths.
 
Quote:
For example, in mathematics, 1=1, in the real world, 1[approx]1. Every measurable entity is a random variable, in which the only thing we can be certain about is that we will always be uncertain about its size.
Not so, there is a lot certainty than that.
There are f.i. many cases where we can put bounds on our random variable [rho], where [rho] [approx]1, but certainly 0 < [rho] < 2. Moreso, as we collect more and more measurements of an entity we get a distribution which can tell us heaps in statistical math terms.  
And really, truth and certainty don't have that much to do with eachother. Absolute truth can't change, but the certainty we have about a statement changes, and can be manipulated easily.
 
Quote:
An interesting question would be, if we don't have absolute truth, do we have any kind of truth at all?
All truth is absolute, but generally limited to its scope.
It might be intersting to look up modal logic, since it deals with multiple-world models, where a statement may be true in only one world, only a model, only a frame, or allways.
 
Quote:
The implication of 1[approx]1 is that 1[ne]1.
Only in the linguistic sense, not the logical sense.
1[approx]1 => 1+[epsilon]1  = 1+[epsilon]2 with 0 [le] |[epsilon]1,2| << 1
[epsilon]1,2 can be zero.
« Last Edit: Oct 10th, 2003, 4:19am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Denumerability Dilemma  
« Reply #43 on: Oct 10th, 2003, 5:49am »
Quote Quote Modify Modify

I'm not sure how else I can phrase this; I'm not being understood at all.
 
If M is a random variable representing some attempt at unit measure, P(M=1)=0. As I said,
Quote:
Every measurable entity is a random variable, in which the only thing we can be certain about is that we will always be uncertain about its size.

Everything I've said in my previous posts supports this idea, I can only apologise for not making it clearer.
 
Regardless of whatever probability model you select, it will always remain that: a probability model. Sure, you can say that P(0.5[le]M<1.5)=1, but you can't actually state the absolute value of M. The absolute truth is that M=m, where m is the actual value. In the real world, that kind of absolute truth does not exist. Hence my question, what kind of truth are we dealing with?
IP Logged

mathschallenge.net / projecteuler.net
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Denumerability Dilemma  
« Reply #44 on: Oct 10th, 2003, 7:39am »
Quote Quote Modify Modify

on Oct 10th, 2003, 5:49am, Sir Col wrote:
Regardless of whatever probability model you select, it will always remain that: a probability model. Sure, you can say that P(0.5[le]M<1.5)=1, but you can't actually state the absolute value of M. The absolute truth is that M=m, where m is the actual value. In the real world, that kind of absolute truth does not exist. Hence my question, what kind of truth are we dealing with?

Why should P(0.5[le]M<1.5)=1 (plus all premises) not be an absolute truth? Sure, you don't know the exact value of the quantity you measured, but that's not the only "truth" there is.
IP Logged

"You're a jerk, <your surname>!"
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Denumerability Dilemma  
« Reply #45 on: Oct 10th, 2003, 12:04pm »
Quote Quote Modify Modify

on Oct 10th, 2003, 5:49am, Sir Col wrote:
The absolute truth is that M=m, where m is the actual value. In the real world, that kind of absolute truth does not exist. Hence my question, what kind of truth are we dealing with?
Even if you can't find a truth, that doesn't mean it doesn't exists. The simple truth is things are as they are. Even when we don't know how they are.
If there is another planet, outside of our solar system, somewhere in our universe with intelligent life on it, then the statement 'there is intelligent life outside of our solar system' is true, even if we can't know it is true.
Likewise whatever we measure has some actual value in that measure, even if we can't find it. And you can justifiably say M=m and P(0.5 < m < 1.5) = p, which is absolutely true for some p.
 
And of course some things you can simply count. If you have a basket of apples, you can measure the amount, by simply counting them. No uncertainty there.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #46 on: Nov 4th, 2003, 6:42pm »
Quote Quote Modify Modify

I came across a different means of counting the rationals and thought perhaps Sir Col might prefer it. It is an interesting build in its own right. It was proposed by an American logician named Charles Sanders Peirce.
 
Start with the fractions 0/1 and 1/0. Of course the second is not a real number, but it serves as a computational aid and is dropped in the actual counting. The procedure is to create a series of finite sequences by interposing between each adjacent pair in the previous sequence a fraction created by summing the numerators and the denominators of the fractions to each side:
 
0/1   1/0
0/1   1/1   1/0
0/1   1/2   1/1   2/1   1/0
0/1   1/3   1/2   2/3   1/1   3/2   2/1   3/1   1/0
0/1   1/4   1/3   2/5   1/2   3/5   2/3   3/4   1/1   4/3   3/2   5/3   2/1   5/2   3/1   4/1   1/0
.   .   .

 
The claim is that every fraction in these sequences is reduced, and every non-negative rational number occurs in them.
 
After this is shown, an enumeration of the nonnegative rationals is obtained by counting
 
1 [mapsto] 0/1 = 0
2 [mapsto] 1/1 = 1
3 [mapsto] 1/2
4 [mapsto] 2/1 = 1
5 [mapsto] 1/3
6 [mapsto] 2/3
...
That is, you count each fraction with its first appearance, starting at the left of each row. Later appearances of the same fraction are skipped.
 
Unlike with the "snake back and forth" method, this one picks up each rational number exactly once (since each fraction is reduced). And it does not have a misleading analogy to a finite situation to fool the reader into believing that some fractions are missed, or occur only after an already infinite number of previous ones.
« Last Edit: Nov 4th, 2003, 6:47pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Denumerability Dilemma  
« Reply #47 on: Jan 13th, 2004, 10:31pm »
Quote Quote Modify Modify

Icarus,
 
Interesting. May I ask where you read about Peirce's construction?
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Denumerability Dilemma  
« Reply #48 on: Jan 13th, 2004, 11:05pm »
Quote Quote Modify Modify

I remember reading about it in Graham, Knuth, and Patashnik's Concrete Mathematics; they called it the Stern-Brocot Tree.
IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Denumerability Dilemma  
« Reply #49 on: Jan 14th, 2004, 7:38pm »
Quote Quote Modify Modify

I found it in a collection of Martin Gardner's articles, called "The Colossal Book of Mathematics".
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board