Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Dave L. Renfro on 28 Sep 2006 11:53 mueckenh(a)rz.fh-augsburg.de wrote: > But the set of all lists is countable (as is any quantized > or discontinuous set), so is the set of all list entries. > Nevertheless, there is no real number missing in every > list? So every real number is in at least one of the > list? So every real number is one element of a countable > set of entries? And there is nothing real really outside > of this countable set? The set of all lists of _what_? Also, "lists" is a term that for some people means one thing, and for other people it can mean something else. If you're going to argue about details, rather than give a general overview of what's going on, you should use the correct mathematical terms, such as one-to-one correspondences (i.e. bijective functions). Otherwise, the discussion is going to degenerate into disagreements over word usage. In fact, you're doing it yourself by bringing up "quantized" and "discontinuous", two words that, to most people in math, have no direct relevance to the discussion at hand. It never ceases to amaze me that people can have so much trouble with the main gist (not the details) of the argument. It's the same way that people argue in so many other situations, if not as rigorously. If your boss says you have to do such and such, and you want to explain why it's not possible, you say, well, if I did such and such, then ... [insert consequence boss would not wish to allow]. If you want to prove someone is innocent of a crime in a court of law, it's often enough to prove that the defendant was somewhere else at the time (the contradiction being that one person can't be in two places at the same time). If you want to prove that someone isn't your child, a negative DNA match will do it (the contradiction being that a sufficiently strong DNA mismatch cannot occur in a parent/offspring pair). If you want to prove the set of real numbers is uncountable, one way is to show that it's impossible for the set of real numbers to be countable. I realize there are some issues related to the law of excluded middle, but it seems to me that the confusion people have with the diagonal argument is more rooted in the details than with the overall issue of the law of excluded middle. Anyway, as has been said over and over again in here, the diagonal argument for the uncountability of the reals doesn't have to be an indirect argument. One can simply state and prove the result in the following form: 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.) Dave L. Renfro
From: jmorriss@idirect.com on 28 Sep 2006 12:29 the_wign(a)yahoo.com wrote: > 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. Isn't it important to ASSUME that the original list (in #1 above) is in a one-to-one correspondence to the integers. You need this to count down and across to construct a real that CAN'T be one of these in the list. You need a bigger infinity... Similarly, if you make a horizontal and vertical list of all integers, going to infinity in both directions, then ANY rational can be placed uniquely on that grid, and assigned a unique integer position number. You DON'T need a bigger infinity here...
From: Arturo Magidin on 28 Sep 2006 12:39 In article <1159460966.428700.102970(a)h48g2000cwc.googlegroups.com>, jmorriss(a)idirect.com <jmorriss(a)idirect.com> wrote: > >the_wign(a)yahoo.com wrote: >> 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. > > >Isn't it important to ASSUME that the original list (in #1 above) is in >a one-to-one correspondence to the integers. I assume you mean "positive integers"... (obviously, it is also true if you use all integers, but the OP is trying to simplify...) > You need this to count >down and across to construct a real that CAN'T be one of these in the >list. You need a bigger infinity... Hmmm... A "list" in this context is understood to be a function from the natural number (or from the positive integers) into the reals. The proof does not require the function to be one-to-one, but it ->does<- require it to be a ->function<- (defined at all inputs). As noted elsewhere, the argument does NOT really require the assumption that the list is complete (i.e., that the map is ->surjective<-). Even assuming that, you do not need the map to be injective in order for steps 2 and 3 to work. You just need the map to be defined at every n>0. -- ====================================================================== "It's not denial. I'm just very selective about what I accept as reality." --- Calvin ("Calvin and Hobbes" by Bill Watterson) ====================================================================== Arturo Magidin magidin-at-member-ams-org
From: Dave Seaman on 28 Sep 2006 12:44 On 28 Sep 2006 09:29:26 -0700, jmorriss(a)idirect.com wrote: > the_wign(a)yahoo.com wrote: >> 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. > Isn't it important to ASSUME that the original list (in #1 above) is in > a one-to-one correspondence to the integers. You need this to count > down and across to construct a real that CAN'T be one of these in the > list. You need a bigger infinity... No, you don't need any such assumption in order to apply the diagonal argument. The construction of a real depends only on the existence of a mapping f: N -> R. It is not necessary to assume that f is injective, surjective, or bijective. For each such f, the proof yields a real number not in the range of f. Hence, it follows that no such f can be surjective. > Similarly, if you make a horizontal and vertical list of all integers, > going to infinity in both directions, then ANY rational can be placed > uniquely on that grid, and assigned a unique integer position number. > You DON'T need a bigger infinity here... You don't need a bigger infinity to apply the diagonal argument. You are putting the cart before the horse. It is a *consequence* (not a prerequisite) of the diagonal argument that |R| > |N|. -- Dave Seaman U.S. Court of Appeals to review three issues concerning case of Mumia Abu-Jamal. <http://www.mumia2000.org/>
From: Virgil on 28 Sep 2006 13:04
In article <1159441583.959829.20360(a)d34g2000cwd.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Peter Webb schrieb: > > > You produce ANY list of all Reals, I can show you a missing real. Therefore > > I can do it for ALL lists, and hence there is no complete list of Reals. > > > > Obviously you have to tell me the list first, as there is no single Real > > which is missing from every list, > > No? > > But the set of all lists is countable (as is any quantized or > discontinuous set), so is the set of all list entries. Nevertheless, > there is no real number missing in every list? So every real number is > in at least one of the list? So every real number is one element of a > countable set of entries? And there is nothing real really outside of > this countable set? > > Regards, WM That presumes, falsely, that the set of lists is itself countable, |