tag:blogger.com,1999:blog-3722233.post116050670836900355..comments2020-05-22T22:05:47.580-04:00Comments on Computational Complexity: Wholly NaturalLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-1161144111886958642006-10-18T00:01:00.000-04:002006-10-18T00:01:00.000-04:00Alex,my convention is that a positive integer is n...Alex,<BR/>my convention is that a positive integer is not zero, but that a positive real number may be.<BR/><BR/>I've never seen the French use positive to allow zero, but (1) I wasn't looking for it and (2) I may only notice in fields that use the term so often the term has to trump the language (eg, nonpositive curvature, what I'd like to call negative curvature).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160588446566028402006-10-11T13:40:00.000-04:002006-10-11T13:40:00.000-04:00What about in other languages?In Italian, it has t...<I>What about in other languages?</I><BR/><BR/>In Italian, it has the same meaning as in English (i.e., positive <-> > 0)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160579998699847572006-10-11T11:19:00.000-04:002006-10-11T11:19:00.000-04:00Historically, it is hard to say that including 0 w...Historically, it is hard to say that including 0 was 'natural'.<BR/><BR/>In the late 1960's when New Math finally arrived in my 5th grade class, we were given a bunch of names for abstract properties that we had little reason to understand or care about other than to memorize (closure properties, associative, commutative, and distributive laws, etc). As part of this we were told that the 'natural or counting numbers' started at 1 and the 'whole numbers' included 0. The 'whole numbers' seemed pretty silly to me.<BR/>(More precisely, why would one care to make such a big deal about the difference between such similar concepts?) <BR/><BR/>In some of my first college courses there was a distinction made between 'blackboard N' and 'blackboard N_0' but the term 'whole numbers' totally disappeared. Was this just made up to put in grade-school texts?<BR/><BR/>The thing that convinced me that the natural #'s should include 0 was how the Peano axioms were a bit cleaner in that case:<BR/>FORALL x.(x+0=x) is nicer than<BR/>FORALL x.(x+1=s(x)) and<BR/>FORALL x.(x*0=0) is just as good as<BR/>FORALL x.(x*1=x).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160577808859906662006-10-11T10:43:00.000-04:002006-10-11T10:43:00.000-04:00Is it even clear that "positive integer" always me...Is it even clear that "positive integer" always means "> 0"? More precisely: is it true in all English speaking countries and in the older literature? In French "positif" means ">= 0". In Spanish it tends to mean "> 0", but it is not as clear-cut as in English. What about in other languages?Alexhttps://www.blogger.com/profile/10531171312916299127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160567729912152592006-10-11T07:55:00.000-04:002006-10-11T07:55:00.000-04:00A 'whole number' is, at least etymologically, the ...A 'whole number' is, at least etymologically, the same thing as an 'integer', isn't it? Both mean a number in its entirety, i.e., a non-fractional number. 0 seems to be a nice whole number when viewed in this way.<BR/><BR/>On the other hand, the notion of zero was discovered comparatively late in the human history, which may be an evidence that 0 may be somewhat 'unnatural', compared to any positive integers, at least to our ancestors who didn't know 0.<BR/><BR/>But of course, the two terms will forever be ambiguous, and in technical writings 'positive integers' and 'nonnegative interers' would be safer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160560567485733882006-10-11T05:56:00.000-04:002006-10-11T05:56:00.000-04:00Dear Anonymous logician, I'm afraid I can't fully ...Dear Anonymous logician, I'm afraid I can't fully understand you (which may be due to the fact that I am not a logician).<BR/><BR/>In your first argument, you respond to a <I>nominalist</I> who commented on this blog, arguing that it is "safe to say only neo-Platonists read this blog". Now, <I>that</I> seems to me like a contradiction.<BR/><BR/>Basing your second argument on religious beliefs is also a bit unconventional for a modern logician, isn't it?<BR/><BR/>(There's a good <A HREF="http://ist-socrates.berkeley.edu/~jsearle/AnthropologicalTheoryFNLversion.doc" REL="nofollow">article</A> about terms such as <I>epistemologically objective</I> and <I>ontologically subjective</I>, by John R. Searle)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160550523234637582006-10-11T03:08:00.000-04:002006-10-11T03:08:00.000-04:00"abstractions are ontologically subjective, that i..."abstractions are ontologically subjective, that is, abstractions don't exist without intelligent beings"<BR/><BR/>The first part "abstractions are ontologically subjective" is only true if you are a nominalist. I think it is safe to say only neo-platonists read this blog. Thus making nominalists ontologically subjective; or, at best, by your definition one exists!<BR/><BR/>The second part is not a restatement of the first, but rather a contradiction. If God is necessary (which He is) and intelligent (which He is), then there exists no world without intelligent beings. Thus abstractions are not ontologically subjective. <BR/><BR/>(I am a computer scientist and a logician).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160549552694913672006-10-11T02:52:00.000-04:002006-10-11T02:52:00.000-04:00I'm neither a theoretical computer scientist nor a...I'm neither a theoretical computer scientist nor a logician (nor very logical for that matter), so my view is a bit different.<BR/><BR/>I think that the only number <I>naturally</I> attributable to <I>physical objects</I> is one (1). The number zero (0) indicates nothingness, and there exists no "no physical object": Physical objects can only naturally exhibit their <I>existence</I> (“this is a brick”). They cannot exhibit their <I>non-existence</I> (“this is a no-brick”). <BR/><BR/>The number two (2) involves an abstract coupling of two physical objects (one object and one object), but abstractions are ontologically subjective, that is, <I>abstractions</I> don't exist without intelligent beings (yet the number two is pretty much an epistemologically objective thing).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160521270732448282006-10-10T19:01:00.000-04:002006-10-10T19:01:00.000-04:00That's nothing compared to terc's idea of 'calculu...That's nothing compared to <A HREF="http://wgquirk.com/TERC.html#change" REL="nofollow">terc's idea of 'calculus'</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160516602636581522006-10-10T17:43:00.000-04:002006-10-10T17:43:00.000-04:00One of my professors said that zero is natural num...One of my professors said that zero is natural number for computer scientists as it is natural to get a zero in a computer science exam.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160514914581235282006-10-10T17:15:00.000-04:002006-10-10T17:15:00.000-04:00A related problem: some students learn that "0 is...A related problem: some students learn that "0 is neither even nor odd" in grade school, and they still believe it when they come to the university. <BR/><BR/>I'm not sure why they're taught this. Maybe because it is confusing to say that 0 objects can be divided into two groups of equal size?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160513373033335602006-10-10T16:49:00.000-04:002006-10-10T16:49:00.000-04:00As I was trained in logic and not in number theory...As I was trained in logic and not in number theory, I have always reckoned 0 among the natural numbers for the reason Jim Aspnes says. I started teaching theory courses in 1975, and when Papadimitriou and I published our undergraduate text in 1978, that was the convention we followed. Every year there is at least one student who complains that 0 is not a natural number, citing some authority, and I now tend to reply that it's my classroom so I am the only authority that counts for the time being :) I have now abandoned our book in favor of Sipser's, which has 0 *not* being a natural number. But in my lectures I still insist that it is, because it seems so much more, well, natural to do so, and because it is helpful to keep reminding students to get in the habit of checking that the n=0 case of almost any statement makes sense. I am glad to have the additional rationale now that learning to deal with ambiguous notation is educational in itself!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160512728211302272006-10-10T16:38:00.000-04:002006-10-10T16:38:00.000-04:00I find it helpful to use the explicit notation \ma...I find it helpful to use the explicit notation \mathbb N_0 and \mathbb N_+Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1160508704199690662006-10-10T15:31:00.000-04:002006-10-10T15:31:00.000-04:00It's a dialect issue.If you're a logician, the nat...It's a dialect issue.<BR/><BR/>If you're a logician, the naturals are the finite cardinals, and if you don't throw in 0 you can't count the number of elements in the empty set.<BR/><BR/>If you're a number theorist, the naturals are the positive integers, because otherwise you have to keep writing "except 0" in any statement that depends on unique factorization.<BR/><BR/>This is similar to how different branches of mathematics handle 0^0 (obviously equal to 1 for combinatorialists and obviously undefined for analysts). It may be a good thing for students to see ambiguous terminology occasionally so they can learn that definitions are chosen because they are useful and not because they are right. But I imagine that the grade-school curriculum is not really designed to get this point across.Anonymousnoreply@blogger.com