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: Ken Quirici on 11 Feb 2010 22:54 On Feb 2, 9:59 pm, zuhair <zaljo...(a)gmail.com> wrote: > Hi all, > > I have some difficulty digesting the diagonal argument of Cantor's. > > The argument is that the set of all infinite binary sequences cannot > have a bijection to the set of all natural numbers, thereby proving > that the former set is uncountable? > > However the argument looks to me to be so designed as to reach to that > goal? > > One can look at matters from an alternative way such as to elude > Cantor's conclusion! > > Examine the following: > > Lets take the infinite binary sequences of the letters O and H > > so for example we have the sequence > > X = OHOHOH........ > > in which O is coupled to the even naturals and H coupled to the odd > naturals. > > so the sequence above is > > X= {<O,i>,<H,j>| i is an even natural, j is an odd natural} > > so X is just an example of a infinite binary sequence. > > However lets try to see weather we can have a bijection between > the set of all infinite binary sequences and the set w+1 > which is {0,1,2,....,w} > > so we'll have the following table: > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > w O, O , O, O ,... > > Now according to the above arrangement one CANNOT define a diagonal ! > since the w_th sequence do not have a w_th entry > to put H or O in it. > > So if we can have a diagonal then this would be of the set of all > infinite binary sequences except the w_th one, i.e. of the following > > 0 , 1 , 2 , 3 , ... > 0 H , O , O , H ,.... > 1 O , H , H , O ,.... > 2 H , H , H , H ,.... > 3 O ,O , H , H ,.... > . > . > . > . > > Suppose that the diagonal of those was D=HHHHH.... > i.e. D={<H,n>| n is a natural number} > > Now the counter-diagonal would be D' = OOOO... > i.e. D' = {<O,n>| n is a natural number} > > However there is nothing to prevent the w_th infinite binary sequence > from being D' ? > > So neither we can have a diagonal of all the infinite binary > sequences, nor the diagonal of a subset of these sequences would yield > a successful diagonal argument such as to conclude that the set of all > infinite binary sequences is uncountable? > > Thereby Cantor's argument fail in this situation! > > What I am trying to say is that this Diagonal argument seems to be > purposefully designed to reach the goal of concluding that > the set of all infinite binary sequences is uncountable, by merely > selecting a particular bijection with the set {0,1,2,3,....} > in a particular arrangement, such as to make a diagonal possible, such > as to conclude the uncountability of these infinite binary sequences, > While if we make simple re-arrangement like the one posed above then > this argument vanish! > > There must be something wrong with the way I had put things here, but > I would rather want to read the full proof of this diagonal argument > in Zermelo's set theory. > > Zuhair The proposition we are attempting to prove is that the reals are uncountable. If we show the reals in the interval [0,1) are uncountable, we're done. The reals in the interval [0,1} are all decimal representations of the form: 0.d11 d12 d13 d14 .... where each dij is a decimal digit. If the reals in the interval [0,1) are in fact countable we can list them - here is some arbitrary listing of them: r1 = 0.d11 d12 d13 d14 ... r2 = 0.d21 d22 d23 d24 ... r3 = 0.d31 d32 d33 d34 ... r4 = 0.d41 d42 d43 d44.... (I'm getting tired of writing) We can now construct a new decimal representation which differs from each rn in the nth place. Is the method of construction in dispute? If not, then we're done, aren't we, since we've found a valid decimal representation which differs from every decimal representation in an arbitrary list of the reals in [0,1). Therefore there IS no arbitrary list of the reals in [0,1), and since they can't be listed, they're not countable. Does that work?
From: Aatu Koskensilta on 12 Feb 2010 09:11 Nam Nguyen <namducnguyen(a)shaw.ca> writes: > Then, seems like you must be in that standard school of reasoning. Let's by all means stipulate I'm the most ardent conformist, a spineless lapdog of the orthodoxy, incessantly biting at the ankles of poor logical rebels -- but what is this "standard school of reasoning"? > (And many of your posts do seem to suggest so. No?) What my posts seem to suggest is for others to decide. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Nam Nguyen on 12 Feb 2010 11:29 Aatu Koskensilta wrote: > Nam Nguyen <namducnguyen(a)shaw.ca> writes: > >> Then, seems like you must be in that standard school of reasoning. > > Let's by all means stipulate I'm the most ardent conformist, a spineless > lapdog of the orthodoxy, incessantly biting at the ankles of poor > logical rebels -- but what is this "standard school of reasoning"? The school of reasoning in which those who subscribe to it would be, in your phrasing, "ardent conformist" and "lapdog orthodox" not just to the technical methods of reasoning (which is a good trait) but also to certain accumulated collective thoughts, traditions, philosophies, which are detrimental to the knowledge about mathematical abstraction (and which altogether is a bad trait, imho).
From: Nam Nguyen on 12 Feb 2010 12:24 Nam Nguyen wrote: > Aatu Koskensilta wrote: >> Nam Nguyen <namducnguyen(a)shaw.ca> writes: >> >>> Then, seems like you must be in that standard school of reasoning. >> >> Let's by all means stipulate I'm the most ardent conformist, a spineless >> lapdog of the orthodoxy, incessantly biting at the ankles of poor >> logical rebels -- but what is this "standard school of reasoning"? > > The school of reasoning in which those who subscribe to it would be, > in your phrasing, "ardent conformist" and "lapdog orthodox" not just > to the technical methods of reasoning (which is a good trait) but > also to certain accumulated collective thoughts, traditions, philosophies, > which are detrimental to the knowledge about mathematical abstraction > (and which altogether is a bad trait, imho). An example of such collective tradition would be the belief there isn't such a thing as a formula that it's impossible to assign a truth value in the naturals (i.e. arithmetically undecidable formula). Another example, is the undermining the rigidity of the rules of inference, as syntactical game of symbol manipulation. To this school, subjective interpretations, assumptions in models would override what we can *or can't* know about the undecidability of a T through rules of inference. To paraphrase, in meta level school would reason by intuition's "Basic Instincts" instead of logical strength and constraint of symbolic manipulations.
From: Transfer Principle on 12 Feb 2010 18:35
On Feb 10, 9:38 am, William Hughes <wpihug...(a)hotmail.com> wrote: > On Feb 9, 6:01 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > > 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. > Except for WM who actively denies the existence of a largest > integer. ....which I acknowledge in the very next sentence: > > 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. The original purpose of my post is to acknowledge that there are some posters so "crank"-y that even I shouldn't defend them. (To the standard theorists, of course, that describes _every_ "crank," but still, I'm trying to be somewhat more selective in which of the "cranks" I will defend.) I was trying to propose that WM is so "crank"-y that I shouldn't defend him, except that I mentioned Y-V in the same sentence, setting the standard theorists off. I've noticed that of the three criteria that I mentioned to identify the "cranks," the third one has received the least hostility from the standard theorists. Let me repeat this one for emphasis: > > III. Standard theorists prefer the use of symbolic object > > language to natural metalanguage. To standard theorists, > > natural languages such as English lack the mathematical > > precision of symbolic language, and so all axioms must be > > stated using symbolic language only. An axiom written in > > metalanguage isn't truly an axiom to standard theorists. > > "Cranks," on the other hand, prefer the use of metalanguage > > to object language. To "cranks," purely symbolic language > > lacks the direct applicability to real-world phenomena that > > can be described in metalanguage, and that working with > > symbolic language is merely playing around with symbols. An > > axiom written in object language isn't truly an axiom to > > the "cranks." It appears that of the three criteria that I listed, this one appears to be the most effective in distinguishing "cranks." After all, William Hughes writes: > In my opinion WM is a crank because of the way > he argues. E.g. > - he mostly refuses to give definitions, > and many of the definitions he does use > (generally implicitly) are idiosyncratic in > the extreme. Giving definitions, especially rigorous definitions that can be reduced to primitives, is obviously something that "cranks" are much less likely to do than standard theorists. It goes with what I'm saying above in III, namely that "cranks" feel that giving rigorous (especially symbolic) definitions is just playing around with symbols, not doing mathematics. This is likely one of the reasons WM calls such rigor "matheology" and not truly mathematics. Keeping this in mind, this means that the "crank"-iest posters are therefore those posters whose writing is as far from being a rigorous definition of anything as possible. Such posters include, for example, Ross Finlayson in this thread, and T.H. Ray in another active thread. Indeed, MoeBlee has quipped that it's easier to convince "a pastrami sandwhich to do the backstroke" than it is to convince RF to make his arguments more comprehensible. Standard theorists in the past have compared RF's writing to the Postmodern Generator, a website that chooses words at random, including many buzzwords, and grammatically combines them to form what appears on the surface to be an academic essay but in reality contains little content. Thus, if we judge "cranks" on a continuum from the most rigorous (i.e., formal symbolic language) to the least (i.e., writing resembling the PoMo generator), then RF and THR would be the "crank"-iest posters of all -- and therefore the posters whom even I shouldn't defend. But between the formalist rigor of the standard theorists and the PoMo-like writing of RF and THR, there must be some sort of middle ground. For example, we might have: 1. (Formalist) Axyz (xRx & (xRy <-> yRx) & ((xRy & yRz) -> xRz)) 2. (Middle) R is an equivalence relation. 3. (Po-Mo) "The equivalency function [...] works in general models of the reals [...]" (direct quote from RF) Option 3 is incomprehensible to read. Option 1, while comprehensible, requires some thought to process and may appear to be more "playing with symbols" with no connection to anything mathematical. To the standard theorists, those who write like Option 3 aren't really doing mathematics, and to the "cranks," those who write like Option 1 aren't really doing mathematics. My desire is that Option 2 will be a happy compromise. And if it isn't, then I want to change it so that it will be a happy compromise. I think about the pre-formalist writing of Euclid, who wrote (in Greek) axioms such as "equals added to equals are equal," which isn't Po-Mo but is less formal than Aabcd ((a=b & c=d) -> a+c=b+d). So, the standard theorists have convinced me of the following: 1. I no longer consider Y-V to be any sort of "crank." 2. RF and THR are cranks (without scare quotes), since their writing is too far removed from mathematical concepts. 3. WM is still up in the air. The "Axiom of Potential Infinity," written by WM himself and quoted elsewhere, appears to be written more rigorously than Po-Mo, but not symbolically, of course. This would put WM in the "crank" (with scare quotes) range -- someone who doesn't write as formally as the standard theorists and writes about concepts that contradict ZFC, but still wrote at least one axiom that can be the basic of a new non-ZFC theory. > [Note that your categorization of crank only applies > to construction of mathematics. E.g. your stuff does > not apply to JSH.] I admit that JSH doesn't fit in the categories I mentioned so far. But still, I usually avoid defending JSH (since to me, his latest claims of having proved the Twin Primes and Goldbach Conjectures in PA using only elementary math is indefensible). Thus, JSH will be considered a crank (no scare quotes). |