Cantor's Diagonal?
in [Logic]
|
Prev: The set theoretic content of the transfinite recursion theorem
Next: Geometry surface area Contact; related to "flatness"; Pedestal-Geometry #386 Correcting Math
From: Tim Little on 8 Feb 2010 19:41 On 2010-02-04, zuhair <zaljohar(a)gmail.com> wrote: > On the other hand the Diagonal argument seems to require well > ordering The *mathematical* content of the diagonal argument is simply this: for any f:X->A^X, show that there exists g in A^X having the property that for all x, g(x) != f(x)(x). Therefore no such f is surjective. No well-ordering is used, in fact no ordering at all. The argument gets its name from the f(x)(x) terms which lie on the "diagonal" of a table of the function. The illustrative table that gives the argument its name is not required for the proof itself, though, which works for sets that cannot possibly be illustrated. - Tim
From: Tim Little on 8 Feb 2010 19:49 On 2010-02-04, zuhair <zaljohar(a)gmail.com> wrote: > I was speaking of the diagonal argument that uses infinite binary > sequences, and not of the other kinds of arguments (although Arturo > say they the same). An infinite binary sequence *is defined as* a function from N to {0,1}, and the set of all such functions is 2^N. The theorem is that no f:N->2^N is surjective. The diagonal proof is that there exists g in 2^N such that for all n, g(n) != f(n)(n). The sequence h in 2^N defined by h(n) = f(n)(n) is called "the diagonal". Now do you see why they are the same? >> The argument using the map that Russell's Paradox presented, and which >> gives the proof for the above almost at once, remains the same... > > what Russell's paradox has to do with this? It is an instance of a very similar type of construction. However, you are confused enough about the basic diagonal argument that I doubt it would be fruitful to discuss it any further. - Tim
From: Nam Nguyen on 8 Feb 2010 23:05 Transfer Principle wrote: > > I. Standard theorists think of mathematics in terms of the > objects that they want to _exist_ in their own conception > of the mathematical universe. > > "Cranks," on the other hand, think of mathematics in terms > of the objects that they _don't_ want to exist. What about those posters who subscribe to none of those "thinking"? Are they "crank", or "standard"?
From: FredJeffries on 9 Feb 2010 11:14 On Feb 7, 10:55 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > > Therefore, _ultra_finitists such as WM and > Yessenin-Volpin will now be considered cranks (and that's > _without_ the scare quotes, since the label is deserved). That you consider Alexander Yessenin-Volpin a crank does not say much for your method of classification.
From: Transfer Principle on 9 Feb 2010 17:01
On Feb 9, 8:14 am, FredJeffries <fredjeffr...(a)gmail.com> wrote: > On Feb 7, 10:55 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > > Therefore, _ultra_finitists such as WM and > > Yessenin-Volpin will now be considered cranks (and that's > > _without_ the scare quotes, since the label is deserved). > That you consider Alexander Yessenin-Volpin a crank does not say much > for your method of classification. I believe that Yessenin-Volpin is a "crank" if and only if WM is a "crank." (For this post, I return to scare quotes until the "crank"-hood of WM and Y-V is settled.) Recall that Yessenin-Volpin is the mathematician famous for, upon being asked "Is n a natural number?" (for the standard or Peano natural n), waiting until a time proportional to the magnitude of n has passed before answering "yes." In other words, he waits until time nt has passed (for some fixed constant time t) before answering the question. There are many similarities between Yessenin-Volpin and WM that lead me to believe that each deserves to be a "crank" if the other so deserves. These similarities include: 1. Both are ultrafinitists. 2. Neither actually has a fixed upper bound on the magnitude of a permissible natural number. Thus Y-V can't answer the question "What is the largest number?" WM has also stated that although some Peano natural numbers "don't exist," there is no largest permissible natural number. 3. Both rely on the physical universe to determine whether a natural number is permissible. Y-V's definition depends on the physical property of _time_ -- in particular, whether there is enough time for him to answer the question. WM also relies on a temporal notion -- namely, whether there is sufficient time for its digits to be calculated. 4. For completeness, Y-V was affiliated with a university (Boston U). WM is also affiliated with a university. (One key difference between Y-V and WM is that for the former, if n is a permissible natural number and m<n is a Peano natural number, then m is also permissible. This is because in order for Y-V to answer "Is n a natural number?" a period of time nt must pass, while for him to answer "Is m a natural number?" a period of mt must pass. Since m<n, mt<nt, and so if time nt is available, then so is the shorter time interval mt. On the other hand, WM's natural numbers contain gaps, a fact admitted by WM himself.) Notice that Y-V is currently 85 years old. Thus, he'd just now be answering yes to the question (if posed at his birth) "Is 2.7 billion a natural number?" for t=1 second. He'd never be able to answer the question "Is the size of President Obama's latest stimulus package in dollars, rounded to the nearest dollar, a natural number?" in his lifetime, unless we were to reduce the constant t to about one millisecond. Even if we were to reduce t to a very short interval, such as the Planck time, Y-V would only be able to reach about 10^52. Even if Y-V were eternal, and we posed the question right after the Big Bang, and Y-V could count until the Heat Death, he'd still be hundreds of orders of magnitude shy of the largest RSA numbers. So Y-V can never answer the question "Is RSA-2048 a natural number?" despite its usefulness in computing and cryptography. (On the other hand, note that to WM, RSA-2048 is a natural number since we know all of its digits!) The main point here is not to attack ultrafinitism, but merely to point out that if I hold Y-V and WM to my same standards, then either both are "cranks," or neither are. But Fred Jeffries wrote, to repeat: > That you consider Alexander Yessenin-Volpin a crank does not say much > for your method of classification. strongly implying that in Jeffries's own method of classification Y-V isn't a "crank," even though WM is. The ball is now in Jeffries's court to defend his classification and give the differences between Y-V and WM such that the latter is a "crank," but not the former. Since the standard theorists like Jeffries are the ones who came up with the term "crank" in the first place, if Jefferies says that Y-V isn't a "crank," then Y-V indeed isn't a "crank." If Jeffries would please explain why Y-V isn't a "crank" despite making several WM-like statements... (Note: "Y-V is a mathematician and WM isn't" is insufficient. To me, that's little different from saying "WM is a 'crank' because he's a 'crank,' and Y-V isn't because he isn't.") (Recently there is a debate in the AP threads in which AP, while not truly a finitist, is trying to argue that 10^500 is the largest number useful to physics, and that any natural number larger than 10^500 is "incognitum," not finite. Later on today, I might find and propose in one of the AP threads that a finite natural number be defined as a number to which Y-V will answer "Yes, that is a natural number," and "incognitum" as one to which Y-V cannot so answer. Then "finite" and "incognitum" will be reduced to the whims of Y-V -- a mathematician considered to be a non-"crank" by the standard theorist Jeffries.) |