Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Albrecht on 29 Sep 2006 09:32 the_wign(a)yahoo.com schrieb: > Cantor's proof is one of the most popular topics on this NG. It > seems that people are confused or uncomfortable with it, so > I've tried to summarize it to the simplest terms: > > 1. Assume there is a list containing all the reals. > 2. Show that a real can be defined/constructed from that list. > 3. Show why the real from step 2 is not on the list. > 4. Conclude that the premise is wrong because of the contradiction. > > The steps are simple except for a possible debate about defined / > constructed. I don't think anyone believes the proof is invalid > because of that debate however. > > There seems to be another area that seems to be a problem > though. The problem is that step #2 doesn't seem valid. If we > assume the list contains all the real numbers, then defining or > constructing a real number in terms of that list would be > self-referential. The number from step #2, that is normally defined > digit-by-digit along the diagonal, must have its digits (or at least > one of them) defined as not equal to itself, if we are to assume the > list contains all the real numbers. Certainly the conclusion in that > case is that the premise is wrong or that the construction is not > valid, but the conclusion can't be simply that the premise is wrong. > > This same problem appears in the "power-set" theorem, where we > have a definition of a set, S, which is a subset of N, defined in > terms of the image of a function, f, whose image is assumed to be > the power-set of N. If the image of f is assumed to be the power-set > of N and S is defined in terms of f, then S must necessarily be > defined in terms of itself. Again, if we assume that the image of > f is P(N), then defining S as a set whose elements are defined > to be elements not in the image of f is a self-referential definition > of S because S is also a subset of N, making it meaningless. > Certainly a meaningless definition can't be used to prove a > contradiction. > > I'm guessing that the "discussions" that occur stem from the fact > that mathematicians disagree that the seemingly self-referential > definitions are a problem but it's not intuitively obvious why that is > so, therefore many people feel the need to try to refute the proofs. > The problem is that it really isn't clear why mathematicians seem to > accept the self-referential definitions. Cantor's argument shows just one only thing: there is no list of all reals - as there is no list of all naturals - as there isn't anything which is infinite and completed. To ask about a real which should be constructed from an infinite list is as to ask after the sum of all natural numbers. There is no sum of all natural numbers as there is no real which is constructed from all elements of an infinite list. Best regards Albrecht S. Storz
From: William Hughes on 29 Sep 2006 11:45 Albrecht wrote: > the_wign(a)yahoo.com schrieb: > > > Cantor's proof is one of the most popular topics on this NG. It > > seems that people are confused or uncomfortable with it, so > > I've tried to summarize it to the simplest terms: > > > > 1. Assume there is a list containing all the reals. > > 2. Show that a real can be defined/constructed from that list. > > 3. Show why the real from step 2 is not on the list. > > 4. Conclude that the premise is wrong because of the contradiction. > > > > The steps are simple except for a possible debate about defined / > > constructed. I don't think anyone believes the proof is invalid > > because of that debate however. > > > > There seems to be another area that seems to be a problem > > though. The problem is that step #2 doesn't seem valid. If we > > assume the list contains all the real numbers, then defining or > > constructing a real number in terms of that list would be > > self-referential. The number from step #2, that is normally defined > > digit-by-digit along the diagonal, must have its digits (or at least > > one of them) defined as not equal to itself, if we are to assume the > > list contains all the real numbers. Certainly the conclusion in that > > case is that the premise is wrong or that the construction is not > > valid, but the conclusion can't be simply that the premise is wrong. > > > > This same problem appears in the "power-set" theorem, where we > > have a definition of a set, S, which is a subset of N, defined in > > terms of the image of a function, f, whose image is assumed to be > > the power-set of N. If the image of f is assumed to be the power-set > > of N and S is defined in terms of f, then S must necessarily be > > defined in terms of itself. Again, if we assume that the image of > > f is P(N), then defining S as a set whose elements are defined > > to be elements not in the image of f is a self-referential definition > > of S because S is also a subset of N, making it meaningless. > > Certainly a meaningless definition can't be used to prove a > > contradiction. > > > > I'm guessing that the "discussions" that occur stem from the fact > > that mathematicians disagree that the seemingly self-referential > > definitions are a problem but it's not intuitively obvious why that is > > so, therefore many people feel the need to try to refute the proofs. > > The problem is that it really isn't clear why mathematicians seem to > > accept the self-referential definitions. > > > Cantor's argument shows just one only thing: > there is no list of all reals - as there is no list of all naturals - > as there isn't anything which is infinite and completed. A set does not have to be infinite to be countable. Cantor's proof works just fine for finite sets. So Cantor's proof can be used to show that the set of real numbers is not finite. [If this is not cracking a walnut with a sledgehammer, I don't know what is!] If you do not allow "completed infinite sets", then the meat of Cantor's proof (the cardinality of the reals is greater than that of the integers) cannot be done So, everyone who finds your "contradictions" to be convincing will find Cantor rather trivial. However, as far as I can see, 'everyone who finds your "contradictions" to be convincing', is a set with at most one element. -William Hughes
From: Randy Poe on 29 Sep 2006 12:56 georgie wrote: > Randy Poe wrote: > > > > Uh, no. We just assume that f is a function that takes naturals > > and produces reals. > > > > For instance, let f(x) = sqrt(x). > > > > Do I have to assume that f(x) "might have R as its image" in order > > to talk about f(x) = sqrt(x)? Can't I just talk about f(x) = sqrt(x) > > and examine what properties is has rather than speculating about > > what it might have? > > No, but f(x) = sqrt(x) isn't true in general. We don't take it as > being valid for all x. What do you mean "valid"? That's my definition of f(x). For any x, what I mean by f(x) is the value of sqrt(x). x in this context is a natural number, so sqrt(x) is a positive real for all x. - Randy
From: Dave L. Renfro on 29 Sep 2006 14:32 Dave L. Renfro wrote (in part): >> Each sequence of real numbers omits at least one real >> number. (Sequence being a 1-1 and onto function from the >> positive integers to the real numbers.) Jesse F. Hughes wrote: > Er, are you sure about that definition of sequence? Seems to > me that sequence is any function from the positive integers > to the reals. > > With your definition, the conclusion would be: every onto > function N->R is not onto. This is true, of course, but is > more likely to confuse the "Anti-Cantorians" rather than > enlighten them. Ooops, you're correct ... I messed up. I knew I should have stayed out of one of these kinds of threads. I was curious how mueckenh would respond to my bringing up other situations (in "real life") where one argues that something can't happen by showing that something contradictory (or at least, something not desirable) would arise if we assumed it did happen. He (she?) seemed to have ignored my examples, though. And what's with this other thing I saw in the thread, where someone argued that the diagonal argument is not complete because the assumption that the list of real numbers containing all the real numbers wasn't allowed for? That's just bizarre. If this person is _really_ concerned about that issue (rather than trolling, as I strongly suspect), why isn't he raising the same issue for _every_ argument? For example, in proving that 4 + 3 = 7 (using three applications of the successor function), he should complain that we didn't consider the case where 4 + 3 isn't 7, and when we consider this possibility, the proof fails. More generally, he should find fault with every proof of statements of the form "If P, then Q", including the arguments that he is using to support his position. Now that I think about it, don't a lot of these anit-Cantor arguments take the same form as what they're criticizing? They argue that something about diagonalizing is incorrect, because if it were correct, then [insert their attempt to obtain a contradiction]. Dave L. Renfro
From: Ross A. Finlayson on 29 Sep 2006 14:55
Dave L. Renfro wrote: > Dave L. Renfro wrote (in part): > > >> Each sequence of real numbers omits at least one real > >> number. (Sequence being a 1-1 and onto function from the > >> positive integers to the real numbers.) > > Jesse F. Hughes wrote: > > > Er, are you sure about that definition of sequence? Seems to > > me that sequence is any function from the positive integers > > to the reals. > > > > With your definition, the conclusion would be: every onto > > function N->R is not onto. This is true, of course, but is > > more likely to confuse the "Anti-Cantorians" rather than > > enlighten them. > > Ooops, you're correct ... I messed up. I knew I should have > stayed out of one of these kinds of threads. I was curious > how mueckenh would respond to my bringing up other situations > (in "real life") where one argues that something can't happen > by showing that something contradictory (or at least, something > not desirable) would arise if we assumed it did happen. He (she?) > seemed to have ignored my examples, though. > > And what's with this other thing I saw in the thread, where > someone argued that the diagonal argument is not complete > because the assumption that the list of real numbers containing > all the real numbers wasn't allowed for? That's just bizarre. > If this person is _really_ concerned about that issue (rather > than trolling, as I strongly suspect), why isn't he raising > the same issue for _every_ argument? For example, in proving > that 4 + 3 = 7 (using three applications of the successor > function), he should complain that we didn't consider the > case where 4 + 3 isn't 7, and when we consider this possibility, > the proof fails. More generally, he should find fault with > every proof of statements of the form "If P, then Q", including > the arguments that he is using to support his position. > > Now that I think about it, don't a lot of these anit-Cantor > arguments take the same form as what they're criticizing? > They argue that something about diagonalizing is incorrect, > because if it were correct, then [insert their attempt to > obtain a contradiction]. > > Dave L. Renfro Hi, Dave, I think it's more interesting to try and generate lists, or mappings, in certain ways and then observe the construction of the anti-diagonal. I don't care for calling the anti-diagonal argument the diagonal argument. There are basically anti-diagonal and powerset results to consider, and nested intervals, those comprise the core of what are called Cantorian results. With the anti-diagonal result, it's interesting to see how different bases of the numbers can provide different restrictions on the rules in selection of anti-diagonals. For example, you'll notice that the anti-diagonal argument is generally presented in base four or higher, where four resolves to two and etc., and not in some infinite base. With f(x) = x+1 and the powerset result, over the naturals as domain the missing element is the empty set. If your naturals don't have zero being the empty set, then there are some considerations possible about vacuity, the empty set, and how the empty set is a subset of any other set, besides itself, because it contains no elements not in the set, not because it contains elements from the set. There is no universe in ZF. The universe as a set in a set theory is its own powerset, violating the power set proof which does not necessarily apply to irregular sets. Where all infinite sets are irregular, hell, where all sets are irregular, the finite combinatorics results still are perfect. Then again, I'm post-Goedelian too. Ross |