|
||||||||||||
|
Title: Denumerability Dilemma Post by Sir Col on Sep 7th, 2003, 11:59am It will probably not surprise some members here to know that I have issues with transfinite set theory, in particular, the notion of denumerability. In case this is unfamiliar, here's a brief introduction to the black art... A transfinite theorist says that a set of numbers is denumerable if there exists a one-to-one mapping with the set of natural numbers; they would even go as far as saying that the set is countable. The typical example cited is the set of even numbers. 1[to]2, 2[to]4, 3[to]6, ... , n[to]2n Hence there are infinitely many even numbers as there are natural numbers. We can use a two-dimensional array to form a grid of ordered pairs: (1,1) (2,1) (3,1) (4,1) ... (1,2) (2,2) (3,2) (4,2) ... (1,3) (2,3) (3,3) (4,3) ... (1,4) (2,4) (3,4) (4,4) ... and so on. By taking the ratio of any pair (p,q), we can form a rational number, p/q. As the array extends to infinity, every rational number is contained and can be expressed from the grid. By taking pairs off in a diagonal snaking pattern, we obtain the following sequence: (1,1) (2,1) (1,2) (1,3) (2,2) (3,1) (4,1) (3,2) (2,3) (1,4) ... Converting these to rational numbers and removing repeats, we get the following one-to-one mapping: 1[to]1, 2[to]2, 3[to]1/2, 4[to]1/3, 5[to]3, 6[to]4, 7[to]3/2, ... Hence the rational numbers are denumerable. The final assault in an introductory course to the transfinite is the demonstration that the set of real numbers are NOT denumerable. This is usually demonstrated in the following way... Without loss of generaility, we shall consider the real numbers on the continuum over the interval 0 and 1. Imagine we have a complete list of the decimal numbers in this interval and suppose that this is the top of the unordered infinite set we have obtained: 0.32150136... 0.54314772... 0.75325180... et cetera We will now write-down a number in the following way. The 1st digit will be different from the 1st digit of the 1st number, therefore, even if the other digits match, it will be a different number from the 1st number. Similarly we shall ensure that the 2nd digit of our number is different from the 2nd digit of the 2nd number, and so on. As this number will be different from every number in the list, which was supposed to be the entire list of real numbers over the interval 0 to 1, we demonstrate that the set of real numbers is not denumerable. Now we've endured the preamble. Here's part of my objection... Imagine writing every number from 1 to 999, except we consider the number to be a string and we shall reverse it. By placing this after "0.", we shall form every decimal fraction from 0.001 to 0.999; in other words, every decimal fraction containing 3 decimal places. If we extend this to infinity, each natural number corresponds, on a one-to-one mapping, with the complete set of decimal fractions, that is, the real numbers: 1[to]0.1, 2[to]0.2, ... , 9[to]0.9, 10[to]0.01, 11[to]0.11, 12[to]0.21, ... , 19[to]0.91, 20[to]0.02, 21[to]0.12, ... , 1432[to]0.2341, ... Hence the set of real numbers is denumerable. I've deliberately not said any more at this stage – I've got bucket loads more ;) – as I'd be very interested to hear thoughts on this first. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by SWF on Sep 7th, 2003, 12:49pm You are asking for trouble from Icarus. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Sep 7th, 2003, 12:53pm even 1/9, a rational number, will never be in that set.. in the natural -> even and natural -> rational case for every even, resp. rational number you can prove there's a natural number (inherently finite) that maps to it. But you can't find any (finite) number that maps to 1/9 in this supposed natural -> real mapping. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 7th, 2003, 1:13pm on 09/07/03 at 12:49:02, SWF wrote:
As I post this, I just noticed from the "who's on-line" that he's prowling, and upon reading this, no doubt, growling! ::) My argument, Towr, would be that 1/9=0.111... would not exist in any finite set, but as I said, "If we extend this to infinity..." Iwe were to argue that 1/9 does not exist in my mapped set, then I would argue that the attempt to denumerate the rationals by spiralling fails too, as you cannot return along a spiral from a position at infinity. In fact, from any position, n, along either axis on an n by n grid, there will remain at least n(n–1)/2 numbers in the grid not accounted for; that is, (n-1)/2n of the grid. As it happens, I do not accept my previous paragraph anymore than I accept that 1/9 is not in my denumerated list. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Sep 7th, 2003, 1:26pm I don't quite know what you mean with 'extend to infinity', unless you actually reach infinity (which isn't a natural number and thus can't be used to map from) you can never get 1/9. You can however reach any rational number by spiraling. every rational number is mapped to by a finite natural number (which all all finite so it really needn't be specified). But with reals, in your way you'llonly get an infinite number of digits, as in 1/9, when you reach infinity, but never before not at any finite number. btw here's a finite set with 1/9 in it. {1/9} :P |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 7th, 2003, 1:35pm on 09/07/03 at 13:26:50, towr wrote:
Fair point; I meant in my mapped set. 1. How far would you have to go in your spiralling matrix before you got EVERY rational number? 2. Are you suggesting that the other (n–1)/2n of the grid has already been done? You only get just over half of an n by n grid using the spiralling method. The method does not permit you to access the remaining part. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Sep 7th, 2003, 1:50pm on 09/07/03 at 13:35:37, Sir Col wrote:
But you can get _any_ in finite time. That's the point. Quote:
(1,1) (1,1) (2,1) (1,2) (1,1)(2,1)(3,1) (1,2)(2,2) (1,3) etc As a result you're not missing out on any part. Any rational number p/q corresponds with point (p,q) which you reach at the step with natural number (p+q-2)(p+q-1)/2+q |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Sep 7th, 2003, 2:02pm on 09/07/03 at 13:13:27, Sir Col wrote:
GRRrrRRRrrrRRR! >:( Quote:
And your argument would be wrong! Every time a puzzle touches on the infinite, this same misconception comes up! EVERY NATURAL NUMBER is FINITE! There are an infinite number of them, yes. But they themselves do not include ANY infinite values! Now look back at your sequence definition. You will see that the only way to get infinite decimals out of it is if the index itself has an infinite number of decimals before the decimal point. While you can define such numbers, they are NOT Natural numbers. (They are called 10-adics, and are not actually infinite - the concept of finite vs infinite value is not defined for them.) With natural numbers you only get a finite number of digits, so the corresponding numbers under your scheme are all terminating decimals. I.e., you are getting a subset of the rationals, just as Towr said, not the entire reals. Quote:
But since n is finite, you are not stopping at n. You are being fooled by trying to apply intuition obtained from finite cases to an infinite situation. Here is the formula for the index of a pair (p, q) under a different variant of this diagonalization process (It uses the Whole numbers - starting at 0, not 1 - and instead of snaking back and forth, it takes each diagonal in the same direction) (p, q) [mapsto] ((p+q)(p+q+1)/2) + p As you can see, every pair has a finite index. A little work shows that any two pairs have different indices, and a bit more work shows that every whole number occurs as an index. (To get the rationals from this version, you have to throw out not only the pairs that are not relatively prime, but also those with 0 denominators.) Quote:
I'm glad you don't accept it, but it sounds like the basis of your not accepting it is flawed intuition, just as your argument that 1/9 is in your denumerated list is flawed. All joking aside, I do not mind people questioning me or the "black arts" upon which I pontificate. As I have said before, honest intellectual debate based on real issues that someone has - whatever their cause, is never a waste of my time. The only things that gets me mad are those who reject without considering, or who feel the need to insult those they disagree with (whether they are right or wrong). Since you do not fall in either category, feel free to say all you want! ;) |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 7th, 2003, 3:49pm Good, I'm glad you feel that way. For all the dry wit I use (I hope it's never misunderstood), I only post these questions because I have the deepest of respect for the minds of the regulars at this forum, and value their gentle correcting of my amateur understanding of these concepts. I would lik to extend my query then... Suppose then, by the accepted grid method, we have demonstrated the denumerability of the rationals to the set of natural numbers. Clearly, there can be no rational number that exists that is not a member of that set. Due to the one-to-one mapping I could talk about the nth member of the set, and I could call it member, n. For example, using the grid above, member 4 is 1/3, member 7 is 3/2, et cetera. I could convert the number, n, into an infinite decimal by placing 0. at the start, reversing the string, and adding an infinite set of trailing zeros after it. For example, member 134 [to] 0.431000... Clearly each member will be unique, and so there exists a one-to-one mapping between the member number, n, the rational number, and the infinite decimal. Equally, for every infinite decimal representation there exists a rational number and corresponding natural number. However, by the diagonal method, the list of decimals is not denumerable, and so there will always be another representation we can produce; therefore the list remains incomplete. Hence the rationals are not denumerable. Of course, it would be possible to apply the whole argument to the set of natural numbers, using the following mapping: 1[to]0.1000... 2[to]0.2000... 3[to]0.3000... ... 10[to]0.01000... 11[to]0.11000... ... 134[to]0.431000... and so on. Hence, by using the diagonal method, it is possible to show that the natural numbers are not denumerable to themselves. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Sep 7th, 2003, 10:35pm on 09/07/03 at 15:49:37, Sir Col wrote:
I don't there's any point in reversing the digits before appending the zeros, unless I'm missing something ... A set is denumerable if it can be put in a one-to-one mapping with the naturals. So by definition, the infinite decimals you've written in the quotation above are denumerable! You may think you've created all the reals with your mapping (and thus you hope to then apply the diagonalization argument), but this is not so. For instance, you have missed 1/9, a decimal consisting of an infinitude of 1s. All decimals in your construction must have a finite number of 1s. Even though the naturals in your mapping are tending to infinity, you must agree that every individual member of the set of naturals has a finite number of 1s. So you'll never get 1/9. Hopefully I didn't just add to your confusion :) |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 7th, 2003, 11:48pm But, if we write down a decimal in the following way... Begin by writing "0." Then write, next to it, any digit that is different to the 1st digit of the 1st number in my list (1). Then write next to that, any digit that is different to the 2nd digit of the 2nd number in my list. Continue this process, concatenating digits that are always different to the nth digit of the nth number in the list. This process is called the diagonal method and, the result of it, is that my new number cannot be the same as any number in my list. As the list was supposed to be complete, I have demonstated that a new number exists, hence it is not denumerable. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Sep 8th, 2003, 2:12am on 09/07/03 at 23:48:35, Sir Col wrote:
As I understand it, the idea of diagonalization is: 1) Assume that a set S is denumerable. Then it can be listed out. 2) Construct a new object x by deviating from the digits on the diagonal of the list. Then x cannot in the list, because it is different from every object in the list. 3) Because x satisfies properties which make it a member of S, the list must not have been complete, since the list missed x. Thus S is nondenumerable. Okay, now let's carefully characterize the set S of infinite decimals you have constructed. All of these strings have the following form: "0.", followed by some finite number of 0-9 digits, followed by an infinite stream of zeroes. Any string of this form must belong in S. I believe your argument fails on step 3. Yes, you made a new object that differs from every decimal in the list. But this new object doesn't belong in S anyways, so who cares. Unlike all the elements in S, the new object is not suffixed at some finite index by an infinite sequence of zeroes. The list was just supposed to be a complete listing of all elements in S alone. The fact that a listing of members of S lacks objects that are not members of S doesn't say anything about S's denumerability. Contrast this to applying the diagonalization argument to the reals in [0,1], in which case it's clear that the newly constructed number is a real [in][0,1], and yet the list somehow missed it. Thus the list is incomplete. P.S. As my posts regularly demonstrate, I'm very fallible, and not great with math. Perhaps Icarus will be breathing fire on the both of us tomorrow :-X In any case, I encourage and look forward to even the most nitpicky of corrections, in order to learn more from others. :) Edit 11:54 PM 9/8/2003: I asked a math PhD I know if this is the right counterargument, and he agrees. So go me. :) |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 8th, 2003, 3:22am on 09/08/03 at 02:12:54, william wu wrote:
My thoughts entirely; especially the last part. I continue to think it a privilege to be part of this community of great minds in both breadth and depth of experience and knowledge. What I enjoy most of all about learning mathematics is how clear and unquestionable concepts appear to yourself until someone points out the obvious, and then you can't understand how you ever thought it to be true or missed an idea in the first place. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by wowbagger on Sep 8th, 2003, 4:55am on 09/07/03 at 15:49:37, Sir Col wrote:
Correct (I think). Quote:
Here's where it gets a bit shaky, I'd say. There exists a rational number and corresponding natural number for those infinite decimals that are constructed in the way you stated. Quote:
Now you're talking about all decimals (if I didn't misunderstand you), including irrationals like sqrt(2). However, sqrt(2) clearly cannot be constructed by your method, as it is not rational, so it doesn't have a corresponding natural number. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 8th, 2003, 8:33am Okay, I'll lay my cards on the table... My intuition tells me that the diagonal method of showing that something is not denumerable is flawed. I believe that the continuous selection of different digits does not produce a real quantity. It is maybe analgous with trying to argue that as [sqrt]2 can be expressed as a continuous fraction, it is a rational number. 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. I still think that my demonstration of the non-denumerability of the natural numbers holds. The statement is conversely true: (i) each natural number has its own unique decimal representation, and, (ii) each decimal representation is equivalent to a unique natural number. In other words, both sets are complete, and no member of either set exists without a one-to-one mapping. As the diagonal method seems to produce a number that is not in the list, we are faced with my denumerability dilemma. I believe that this can only be justified by arguing that the new number does not exist and cannot ever be fully defined by the process. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by wowbagger on Sep 8th, 2003, 9:40am on 09/08/03 at 08:33:01, Sir Col wrote:
Are you saying that what we construct using the diagonal method is not a real number? Quote:
I would argue that the number we produce is well-defined if we work in base two. Starting with our supposedly complete table of real numbers r(n) (n [in] [bbn]) in [0;1], we define the nth binary digit of x to be xn = 1-r(n)n, where r(n)n is the nth binary digit of r(n). It can be shown (but maybe you just believe this) that the number thus constructed is in [0;1]. Furthermore, it is a real number, namely [sum]n=1oo xn 2-n. However, it differs from every number r(n) in the (supposedly complete) list at the nth binary digit. Sorry for reiterating the diagonal method, but I don't really see what you take issue with. Is it the infinite process involved in constructing x? Quote:
So what about my example of [sqrt]2? You didn't give any natural number it corresponds to. Maybe you can't? ::) |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 8th, 2003, 10:08am I hear what you're saying, but both of my 'methods' were applied to mapping the rational numbers, in the first instance, and the natural numbers to my infinite decimals, so I never suggested that irrational numbers would be included. I believe that my argument, for the natural numbers, proves that the diagonal method is flawed. It remains undefined as it is an infinite process which can never be completed. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by wowbagger on Sep 8th, 2003, 10:17am on 09/08/03 at 10:08:45, Sir Col wrote:
Hm, why don't you start one step earlier and question the table of reals (or rationals), indexed by natural numbers? As it's infinite, the table will never be completed either. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Sep 8th, 2003, 12:27pm on 09/08/03 at 08:33:01, Sir Col wrote:
0.111... is a decimal representation, but it does not map back to a natural number. To denumerate you need a bijection, All elements of the domain must map to a unique element in the image, and all elements in the image must be mapped to at least once from the domain. Clearly the natural numbers don't bijectively map to the all decimal representations in the way you propose (because not all decimal representations are mapped to). They do however nicely map to a subset of decimal representations, but that's not the same thing. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 8th, 2003, 1:08pm Good point, again, towr! ;) But how long is the decimal string, 0.1111....? How long can I make a natural number, 11111...? Perhaps I could redefine my mapping to say that, if all natural numbers terminate then, my decimal strings terminate. Whichever way, I could make the decimal string as wide as the list is tall and it is between these two sets that I claim a one-to-one unique and complete mapping exists. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Sep 8th, 2003, 2:00pm yes, but what do you want that to prove? It certainly doesn't say anything about all rational numbers, or decimal representations thereof, nor about reals or the decimal representation thereof. And if you apply the diagonal method (if that's what you intend, I'm not quite sure) the resulting decimal won't be in that set, nor is there any reason it should be. Which is different in the case of reals, the number constructed there has to be a real. Doing the same for, for instance, a set of rational numbers needn't give a rational number. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Sep 8th, 2003, 8:26pm Because I spent so much time giving my answer to the new posts in the 0.999... thread, I don't have time to review this in detail, but it seems to me that the flaw in your method has been amply demonstrated. Let's start with your last question: How long is 0.111...: Answer: Infinitely long. I.e. there are an infinite number of decimal places =1. How long can you make an integer of the form 1111... ? Answer: any FINITE length. Do you see the difference? The first is a single instance of something of infinite length. The second contains infinitely many objects, and there is no uniform limit to their length, but all the individual objects are themselve finite in length. None of them correspond under your mapping to the infinitely long 0.111... Thus, all of your natural numbers correspond to terminating decimals, but there is no fixed "width" to them, such as is implied by your last post. ...111 is not a natural number. You also say that you never included any irrational numbers. But then you try to apply the same logic used to show the uncountability of the Reals to your list. But here is the crux: The diagonal argument shows that any sequence of real numbers in [0,1] cannot include all real numbers in that interval, because one can be identified which is not equal to any element of the list. In your case, the exact same is true, the diagonalization procedure produces a real number not in your list. But unlike with the previous argument, we already knew this! There are lots of real numbers not in your list! So we have found one of them - this does not tell us anything new. Your mistake is that you then assume there is some natural number corresponding to the produced real number. I.e., that the number IS in your list after all. This provides the paradox of the Natural numbers not being denumerable. But you have not justified in any way this assumption - nor can you; it's not true. The number produced by the diagonalization process on your enumeration has to have an infinite number of non-zero digits. The natural numbers all correspond to decimals with only a finite number of non-zero digits. The reason you get a contradiction (that there is no bijection (1-1, onto mapping) of the natural numbers onto themselves, which is clearly ridiculous because the identity map is such a mapping) is because this thing you have assumed is false. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Sep 9th, 2003, 12:31am on 09/08/03 at 20:26:11, Icarus wrote:
You're right, there have been some excellent refutations of my idea – thanks for your patience guys! – but your post has knocked me off my fence of indecision. So it looks like the mathematical community can breathe a sigh of relief for the moment; but, in the words of Arnie... "I'll be back!" ;D |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Sep 9th, 2003, 3:47pm on 09/09/03 at 00:31:23, Sir Col wrote:
Cantor sleeps uneasy! ;) |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by James Fingas on Sep 10th, 2003, 12:46pm Here's a question: how countable is the Cantor set? |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Sep 10th, 2003, 1:22pm 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]::[hide]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.[/hide]::[/e] |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Sep 10th, 2003, 2:23pm An answer to Countability of the Cantor set: [hide] 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! [/hide] |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Sep 10th, 2003, 3:25pm 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]. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by James Fingas on Sep 11th, 2003, 6:05am Actually, the Cantor set doesn't include just rational numbers. For instance, it includes the number 0.202002000200002... in base 3. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Oct 6th, 2003, 12:55pm on 09/08/03 at 08:33:01, Sir Col wrote:
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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Oct 6th, 2003, 7:57pm 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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Oct 6th, 2003, 10:37pm Ah. OK, thanks; good to know. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Oct 7th, 2003, 9:39am on 10/06/03 at 12:55:38, william wu wrote:
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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Oct 7th, 2003, 5:26pm 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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Oct 8th, 2003, 12:49am 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 |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Barukh on Oct 8th, 2003, 3:02am 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... |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Oct 8th, 2003, 8:03pm 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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Oct 9th, 2003, 1:31am 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? |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Oct 9th, 2003, 2:40am on 10/09/03 at 01:31:20, Sir Col wrote:
Though sometimes in mathematics 1+1=0 , really depends on what system you work in :P Quote:
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:
Quote:
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) |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by wowbagger on Oct 9th, 2003, 4:08am on 10/09/03 at 01:31:20, Sir Col wrote:
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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Oct 9th, 2003, 7:01pm 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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Oct 10th, 2003, 3:27am 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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Oct 10th, 2003, 4:18am on 10/10/03 at 03:27:11, Sir Col wrote:
Quote:
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:
Quote:
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:
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:
1[approx]1 => 1+[epsilon]1 = 1+[epsilon]2 with 0 [le] |[epsilon]1,2| << 1 [epsilon]1,2 can be zero. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Sir Col on Oct 10th, 2003, 5:49am 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:
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? |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by wowbagger on Oct 10th, 2003, 7:39am on 10/10/03 at 05:49:34, Sir Col wrote:
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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by towr on Oct 10th, 2003, 12:04pm on 10/10/03 at 05:49:34, Sir Col wrote:
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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Nov 4th, 2003, 6:42pm 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/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. |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Jan 13th, 2004, 10:31pm Icarus, Interesting. May I ask where you read about Peirce's construction? |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Eigenray on Jan 13th, 2004, 11:05pm I remember reading about it in Graham, Knuth, and Patashnik's Concrete Mathematics; they called it the Stern-Brocot Tree (http://mathworld.wolfram.com/Stern-BrocotTree.html). |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by Icarus on Jan 14th, 2004, 7:38pm I found it in a collection of Martin Gardner's articles, called "The Colossal Book of Mathematics". |
||||||||||||
|
Title: Re: Denumerability Dilemma Post by william wu on Jan 14th, 2004, 7:58pm Thanks Eigenray and Icarus :) |
||||||||||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |