ellis@spar.UUCP (Michael Ellis) (11/21/85)
{
For newcomers, `ineffable' numbers are those which cannot be
named. The naming convention may include any of the common methods
used in math, including a convention for specifying infinite
summations, taking the root(s) of arbitrary polynomials,
evaluating the solutions to integrals or differential equations
or whatever you might wish!
The assertion is that the vast majority of real numbers are
ineffable, since there are only denumerably many names but
an uncountable number of real numbers.
}
>Here is a more elegant and direct treatment of Todd Moody's
>"ineffable number" model than in my previous response. The con-
>struction is by Bill Homer, of Intermetrics, Inc. Whatever the
>language for number naming, it produces a unique unnameable
>("ineffable") number, thus refuting Todd's thesis that an example
>of an individual ineffable number cannot be given. (If the naming
>language is powerful enough to include the construction itself,
>this is a paradox).
>The construction is a straightforward application of Cantor's diagonal
>method: Consider "nameable" numbers in the interval (0,1). Since the set is
>countable, assign each number a positive integer. This can be done in a
>constructive way, say, by ordering the *names* lexicographically and in the
>order of increasing length, and discarding extra names for the same number.
>Now consider the decimal notation of each number.
>Construct the number X such that the i'th decimal digit of i equals the i'th
>decimal digit of the i'th number plus 1 mod 10. Then X cannot be an element
>of the set of nameable numbers and is, therefore, ineffable. (There is a
>tiny snag with numbers that have two notations, e.g, 0.1000... and 0.0999...
>; but it is so easy to fix that I won't spell it out). -Jan Wasilewsky
You've just proven that any set of effables E(0) can be expanded into a
larger set of effables E(1), by a complex Cantorian diagonal process
you mentioned which is equivalent to expanding the naming convention.
Indeed, you could continue this process infinitely, producing E(2),
E(3)... But the size of your list would still always be denumerably
infinite, and, as the order of numbers in the interval (0,1) has
the power of the continuum (which is a vastly larger infinity)
there would always be an uncountable infinity of numbers in (0,1)
that are not included in any E(n).
In other words, the particular set of `effables' is determined by
the naming convention used. This set of effables can always
be expanded by incorporating improvements into the naming convention,
but there always remain ineffables that have not been included.
Thus, I still believe in Todd Moody's ineffables.
-michaellazarus@brahms.BERKELEY.EDU (Andrew J &) (11/25/85)
These so-called 'ineffable' numbers date back to one of the turn-of-the-century paradoxes. I think it's the Burali-Forti paradox, but that course was many years ago and I don't remember. Essentially it is easy to derive paradoxes involving these objects. The Cantorian construction posted previously is quite cute, viz., 1. The effable (?!) numbers in [0,1] are countable since the number of names is countable.... 2. Use Cantorian diagonalization to derive a number not in the effable list.... 3. But this number is effable (contradiction) However, a better question might be "So What". Paradoxes arising from circular definitions like effability are common. I somehow recall the specific violation of set theory involved is called "impermissible quantification". andy
g-rh@cca.UUCP (Richard Harter) (11/27/85)
In article <> lazarus@brahms.UUCP (Andrew J Lazarus) writes: >These so-called 'ineffable' numbers date back to one of the >turn-of-the-century paradoxes. I think it's the Burali-Forti >paradox, but that course was many years ago and I don't remember. > The Burali-Forti paradox: Consider the set of all ordinals, W. This set is ordered by the well-ordered order relationship of ordinals and has, in turn, and ordinal greater than that of any ordinal in W. If ordinals are defined in the usual manner in set theory, this can be stated more succinctly by saying that the set of all ordinals, W, is an ordinal larger than any member of W. The Cantor paradox: Cantor's theorem says that the set of all subsets of a given set has a cardinality greater than that of the given set. Consider the universal set, V, of all sets. It is equal to its set of all subsets and hence its cardinality is the same as that of its set of all subsets. The Russell paradox: Consider the set of all sets which do not contain themselves as members. From its definition it contains itself if and only if it does not contain itself. Rusell's set arises naturally in applying the Cantor diagonalization process used in proving Cantor's theorm to the universal set V. These paradoxes (antimonies is the term usually used) are the major ones of naive set theory. They are avoided in axiomatic set theory by restricting the admissable predicates which determine sets. There are also a class of so-called semantic paradoxes of which the most important is Richard's paradox. This is, in effect, the paradox being discussed here. Richard's paradox: Consider the set of all numbers between o and 1 that can be uniquely characterized by English words. Let R be the enumerated set of such numbers. Define r as the real number between 0 and 1 whose n'th digit is the cyclic sequent of the n-th digit of the n-th number in the enumeration under consideration. Then r has been defined by the above English sentence and yet is not a member of R by construction. Semantic paradoxes are resolved by recognizing that not all definitions are effectively computable. In the case of Richard's paradox the problem is that there are English sentences which purport to specify numbers but for which there is not way to determine what that number is. The particular importance of Richard's paradox is that Godel's incompleteness theorem is based on a formalization of Richard's paradox. Richard Harter, SMDS decvax!cca!g-rh
nemo@rochester.UUCP (Wolfe) (12/02/85)
In article <5086@cca.UUCP> g-rh@cca.UUCP (Richard Harter) writes: > ... There are also a > class of so-called semantic paradoxes of which the most > important is Richard's paradox. This is, in effect, > the paradox being discussed [by previous posters]. > >Richard's paradox: Consider the set of all numbers between o and 1 >that can be uniquely characterized by English words. Let R be the >enumerated set of such numbers. Define r as the real number between >0 and 1 whose n'th digit is the cyclic sequent of the n-th digit >of the n-th number in the enumeration under consideration. Then >r has been defined by the above English sentence and yet is not a >member of R by construction. > > Semantic paradoxes are resolved by recognizing that not > all definitions are effectively computable. In the case > of Richard's paradox the problem is that there are English > sentences which purport to specify numbers but for which > there is not way to determine what that number is. The > particular importance of Richard's paradox is that Godel's > incompleteness theorem is based on a formalization of > Richard's paradox. > > Richard Harter, SMDS > decvax!cca!g-rh Thanks for the roundup of famous paradoxes. The problem is not limited to English (or any natural language), as pointed out by G. L. Peterson ("Succinct Representation, Random Strings, and Complexity Classes", Univ. of Rochester CS Dep't. TR 69, Aug. 1980. Also Proc. 21st FOCS), but is a danger possible with any descriptive system. He starts with another paradox similar to Richard's, namely a variation of Berry's paradox (see Whitehead & Russell, _Principa_Mathematica_): "The smallest number requiring more than a hundred words to describe" is ill-defined since it has just been described with fewer than 100 words. Peterson goes on to relate succinctness of representation to randomness, and shows that "the existence of certain strings which are random with respect to one measure and not random for another measure indicates the difference between the two corresponding complexity classes." Just thought those interested in this stuff might like another pointer... Nemo -- Internet: nemo@rochester.arpa UUCP: {decvax, allegra, seismo, cmcl2}!rochester!nemo Phone: [USA] (716) 275-5766 school 232-4690 home USMail: 104 Tremont Circle; Rochester, NY 14608 School: Department of Computer Science; University of Rochester; Rochester, NY 14627