Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!uunet!husc6!mit-eddie!uw-beaver!uw-june!uw-entropy!dataio!suvax1!spector From: spector@suvax1.UUCP (Mitchell Spector) Newsgroups: comp.ai Subject: Re: Langendoen and Postal (posted by: B Message-ID: <778@suvax1.UUCP> Date: Fri, 6-Nov-87 20:47:28 EST Article-I.D.: suvax1.778 Posted: Fri Nov 6 20:47:28 1987 Date-Received: Sun, 8-Nov-87 23:24:32 EST References: <8941@shemp.UCLA.EDU> <8300011@osiris.cso.uiuc.edu> Organization: Seattle University, Seattle, WA. Lines: 80 Summary: Uncountable sets are rarer than one might think. In article <8300011@osiris.cso.uiuc.edu>, goldfain@osiris.cso.uiuc.edu comments on an article by berke@CS.UCLA.EDU: > > > /* Written 10:34 am Nov 1, 1987 by berke@CS.UCLA.EDU in comp.ai */ > > /* ---------- "Langendoen and Postal (posted by: B" ---------- */ > > I just read this fabulous book over the weekend, called "The Vastness > > of Natural Languages," by D. Terence Langendoen and Paul M. Postal. > > ... > > Their basic proof/conclusion holds that natural languages, as linguistics > > construes them (as products of grammars), are what they call > > mega-collections, Quine calls proper classes, and some people hold cannot > > exist. That is, they maintain that (1) Sentences cannot be excluded from > > being of any, even transfinite size, by the laws of a grammar, and (2) > > Collections of these sentences are bigger than even the continuum. They are > > the size of the collection of all sets: too big to be sets. > > ... > > /* End of text from osiris.cso.uiuc.edu:comp.ai */ > > Hang on a minute! It *sounds* as though you are talking about Context-Free > Grammars/Languages (CFGs/CFLs) here. Most linguists (I'd wager) set up their > CFGs as admitting only finite derivations over a finite set of production > rules, each rule only allowing finite expansion. Thus, although usually a CFL > is only a proper subset of this, we are ALWAYS working WITHIN the set of > finite strings (of arbitrary length) over a finite alphabet. > Such a set is countably infinite. Far from being a proper class, this is > a very manageable set. If you move the discussion up to the cardinality of > the set of "discourses", which would be finite sequences of strings in the > language, you are still only up to the power set of the integers, which has > the same cardinality as the set of Real numbers. Again, this is a set, and > not a proper class. > > Mark Goldfain arpa: goldfain@osiris.cso.uiuc.edu > Department of Computer Science > University of Illinois at Shampoo-Banana The set of all finite sequences of finite strings in a language (the set of "discourses") is still just a countably infinite set (assuming that the alphabet is finite or countably infinite, of course). The set of infinite sequences of finite strings is uncountable, with the same cardinality as the set of real numbers, as is the set of infinite strings. (By infinite string or infinite sequence, I mean an object which is indexed by the natural numbers 0, 1, 2, ....) In general, sets of finite objects are finite or countably infinite. (A finite object is, vaguely speaking, one that can be identified by means of a finite representation. More specifically, this finite representation or description must enable you to distinguish this object from all the other objects in the set.) If you want to get an uncountable set, you must use objects which are themselves infinite as members of the set. Many people lose sight of the fact that a real number is an infinite object (although an integer or a rational number is a finite object). Any general method of identifying real numbers must use infinitely long or large representations (for example, decimals, continued fractions, Cauchy sequences, or Dedekind cuts). Real numbers are much more difficult to pin down than one might gather from many math classes. This misimpression is partly due to the fact that one deals only with a relative small (finite!) set of specific real numbers; these either have their own names in mathematics or they can be defined by a finite sequence of symbols in the usual mathematical notation. The other real numbers belong to a nameless horde which we use in general arguments but never by specific mention. I certainly agree with the general objections raised to the idea that natural languages are uncountably large (or, worse yet, proper classes), although I haven't read the book in question. Maybe somebody can state more precisely what the book claimed, but it seems at first glance to indicate a lack of understanding of modern set theory. By the way, logicians do study infinite languages, including both the possibility of infinitely many symbols and that of infinitely long sentences, but such languages are very different from what we think of as "natural language." It doesn't matter whether you're talking about context-free languages or more general sorts of languages -- in any language used by people for communication, the alphabet is finite, each word is finitely long, and each sentence is finitely long. -- Mitchell Spector |"Give me a Dept. of Computer Science & Software Eng., Seattle Univ.| ticket to Path: ...!uw-beaver!uw-entropy!dataio!suvax1!spector | Mars!!" or: dataio!suvax1!spector@entropy.ms.washington.edu | -- Zippy the Pinhead