December 2003 - cypherpunks-legacy

Re: Numbers we cannot talk about
by ichudov＠algebra.com 17 Dec '03

17 Dec '03

Paul Elliott wrote: > -----BEGIN PGP SIGNED MESSAGE----- > > At 10:48 PM 1/18/1997, Secret Squirrel wrote: > > >Is it REALLY true that there are real numbers that cannot be > > >generated by any algorithm? Some guy said that since the set of > > >algorithms is countable, but the set of real numbers is more than > > >countable, there must be some numbers for which there is no > > >algorithms that generate them. > > > > There are sets of real numbers whose existence we can prove, but which > > we cannot otherwise describe. This is more extreme than being > > "generated by an algorithm". We can't even tell somebody which > > numbers to generate! (I take "to generate" here to mean "to compute a > > decimal approximation.") > > > > The set of real numbers is uncountable as is the set of subsets of the > > real numbers. Yet, we have only countably infinite ways to describe > > sets of numbers. > > > > All sets of numbers which we can describe can be described with a > > finite set of symbols. (Human beings are unable to distinguish > > between an infinite number of states.) The set of combinations of > > this finite set is infinite, but countable. > > > > Perhaps the axioms in set theory that tells us that the integers > have an uncountable number of subsets is, in point of fact, false. > Perhaps only those subsets of the integers that can be described > by an algorithm exist (actually, contrary to what the usual axioms of > set theory assert). It is very interesting. My limited understanding of this approach is that they say that only things that can be constructed by some positive method exist (please correct me if I am mistaken). But the question is, where do they stop and what exactly is "construction?" Say, does sqrt(2) "exist" in their sense of the world? We know we can calculate any given number of digits in it, is that enough? > We know that the set of axioms which tell us that there are unaccountably > many reals can be satisfied by a countable model! > (Downward Louwenheim Skolem Tarski theorem.) > > I know that Standard mathematical axioms yields lots of interesting > results, but when it talks of the infinite and we are dealing > with a practical subject like cryptography or even physics it > should not be taken too seriously. (With respect to uncountable sets.) Some of the applications of these theories are very relevant. For example, a theorem that proves that it is impossible to write a program that would determine if any other program would stop or loop forever, is very relevant and interesting. - Igor.

1 0

THIS IS THE FIRST MESSAGE TO THE MODERATED CYPHERPUNKS LIST
by John Gilmore 17 Dec '03

17 Dec '03

If you see this, Sandy has approved it and forwarded it to the list. Of course, this is modulo glitches and bugs. It may take a few days to get everything 100% right. And the messages will undoubtedly arrive on your site in a different order than the order in which they were sent (due to queueing at various places, mostly on toad.com) Welcome to (what I hope is) a more useful and less confrontative cypherpunks list. Now, can we get back to talking about cryptography? John Gilmore

1 0

[Math Noise]
by mpd＠netcom.com 17 Dec '03

17 Dec '03

Jim Choate <ravage(a)EINSTEIN.ssz.com> writes: >> One can construct the reals from the rationals quite easily >> using any of several well-known methods, such as >> equivalence classes of Cauchy sequences, or Dedikind cuts. > So you are saying that the Reals are a subset (ie can be > constructed from) of the Rationals? Yes, the Reals can be constructed from the Rationals. No, the Reals are not a subset of the Rationals. Fortunately, construction in mathematics is not simply limited to the taking of subsets. The Rationals can be constructed from the Integers, for instance, by multiplication and the taking of appropriate equivalence classes. In fact, everything can be built out of two sets and the axioms of Set Theory. > I can create a number which is not representable by the > ratio of two integers from two numbers which are > representable by ratios of two integers? Er, no. But you can create a number which is not representable as a fraction as a limit point of very many fractions. > That's a nifty trick indeed, I am really impressed. Thank-you. :) > Cauchy produced a test for testing convergence. I fail to > see the relevance here, but please expound... Cauchy sequences are useful for adding limit points to a set of things because their convergence criteria is very simple, and it is conceptually easy to take all Cauchy sequences whose elements come from a given set. If we then consider equivalence classes of those Cauchy sequences which converge to the same limit, and consider an element of the original set to correspond to the class containing the sequence all of whose members are that element, we can consider the classes to form a "completion" of the original set by addition of all its limit points. Similarly, the Reals are the completion of the Rationals. > Dedekind Cut: > "Thus a nested sequence of rational intervals give rise to > a seperation of all rational numbers into three classes." > Just exactly where does this allow us to create Reals? Finite ordered sets have maximum elements. Bounded infinite ordered sets have Least Upper Bounds, which may be a limit point as opposed to being an actual member of the set. Dedekind Cuts are a simple abstraction, often used to construct the Reals from the Rationals in undergraduate calculus courses. Conceptually, one makes a single "cut" in the set of Rationals, dividing it into two parts, all of the members of one part being greater than all of the members of the other. The number of ways of doing this correspond to the Reals. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd(a)netcom.com $ via Finger. $

1 0

THIS IS THE FIRST MESSAGE TO THE MODERATED CYPHERPUNKS LIST
by John Gilmore 17 Dec '03

17 Dec '03

If you see this, Sandy has approved it and forwarded it to the list. Of course, this is modulo glitches and bugs. It may take a few days to get everything 100% right. And the messages will undoubtedly arrive on your site in a different order than the order in which they were sent (due to queueing at various places, mostly on toad.com) Welcome to (what I hope is) a more useful and less confrontative cypherpunks list. Now, can we get back to talking about cryptography? John Gilmore

1 0

Re: AIDAS, SHMADIDAS
by ichudov＠algebra.com 17 Dec '03

17 Dec '03

alright, i retract my statement. Thank you, Sandy. igor Sandy Sandfort wrote: > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > SANDY SANDFORT > . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . > > C'punks, > > On Sun, 19 Jan 1997 ichudov(a)algebra.com wrote: > > > I would love to hear Sandy's statement as to whether AIDAS is Sandy > > Sandfort or not. If Sandy says no, I will believe him, because his > > reputation has a longer time span than AIDAS's. > > > > In case Sandy says that AIDAS is not him, I will publicly retract my > > statement, which by the way I made to AIDAS privately (I have no idea > > why he posted it to the mailing list, although I do not really mind). > > Normally, I would not comment one way or the other on this sort > of thing. We have a whole alphabet soup of aliases out there and > I don't intend to waste time with denials. Heck, it helps keep > an air of mystery about the list. But Igor has been a fair and > reasoned contributor to this list, so as a personal favor I will > admit that I AM NOT AIDAS. Sorry, but that's the truth. > > > S a n d y > > P.S. I'm not Igor either. > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > - Igor.

1 0

Re: Numbers we cannot talk about
by ichudov＠algebra.com 17 Dec '03

17 Dec '03

Paul Elliott wrote: > -----BEGIN PGP SIGNED MESSAGE----- > > At 10:48 PM 1/18/1997, Secret Squirrel wrote: > > >Is it REALLY true that there are real numbers that cannot be > > >generated by any algorithm? Some guy said that since the set of > > >algorithms is countable, but the set of real numbers is more than > > >countable, there must be some numbers for which there is no > > >algorithms that generate them. > > > > There are sets of real numbers whose existence we can prove, but which > > we cannot otherwise describe. This is more extreme than being > > "generated by an algorithm". We can't even tell somebody which > > numbers to generate! (I take "to generate" here to mean "to compute a > > decimal approximation.") > > > > The set of real numbers is uncountable as is the set of subsets of the > > real numbers. Yet, we have only countably infinite ways to describe > > sets of numbers. > > > > All sets of numbers which we can describe can be described with a > > finite set of symbols. (Human beings are unable to distinguish > > between an infinite number of states.) The set of combinations of > > this finite set is infinite, but countable. > > > > Perhaps the axioms in set theory that tells us that the integers > have an uncountable number of subsets is, in point of fact, false. > Perhaps only those subsets of the integers that can be described > by an algorithm exist (actually, contrary to what the usual axioms of > set theory assert). It is very interesting. My limited understanding of this approach is that they say that only things that can be constructed by some positive method exist (please correct me if I am mistaken). But the question is, where do they stop and what exactly is "construction?" Say, does sqrt(2) "exist" in their sense of the world? We know we can calculate any given number of digits in it, is that enough? > We know that the set of axioms which tell us that there are unaccountably > many reals can be satisfied by a countable model! > (Downward Louwenheim Skolem Tarski theorem.) > > I know that Standard mathematical axioms yields lots of interesting > results, but when it talks of the infinite and we are dealing > with a practical subject like cryptography or even physics it > should not be taken too seriously. (With respect to uncountable sets.) Some of the applications of these theories are very relevant. For example, a theorem that proves that it is impossible to write a program that would determine if any other program would stop or loop forever, is very relevant and interesting. - Igor.

1 0

[Math Noise] (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Only countably many real numbers, or members of any uncountable > set, are denumerable. It is the property of being uncountable, > rather than of being real or complex, which is important here. In short you are saying there are Reals which can not be expressed in the format: AmEm + Am-1Em-1 + ... + A0E0 . B0E-1 + B1E-2 + ... + BnE-n+1 where m and n -> infinity. Another way of saying this is that there are Reals for which membership in a set of Reals, because they are uncountable and therefore unrepresentable, is not possible. From a set perspective this means, R = [[-infinity, ..., m] [n, ..., 0] [0, ..., p] [q, ..., +infinity]] such that there are uncountable numbers between m,n or p,q; etc. Clearly in contradiction with the base axioms of mathematics as described by Euclid in defining a line. > In general, only countably many members of any uncountable set > can be precisely specified within any formal system, given names > comprised of strings of symbols, or other similar things. And I contend that ANY number which is Real can be expressed by the decimal expansion above. Which clearly qualifies as a formal system. There are three ways of looking at the total of mathematics, symbolic set theory (Bourbaki School) geometric (Euclidian) While it is true the 3 are equivalent, the choice of approach does have a relevance on how difficult, if even tractible, the proof is for any particular concept. > It is often convenient, such as when drawing contour maps, to > consider the complex numbers to be in 1-1 correspondence with the > points of the plane. However, I wouldn't necessarily consider > regions of the complex plane to have "area" in the Euclidian > sense. The Euclidian plane IS a complex plane. The -j or -i used in Complex symboligy simply means 'rotate the second axis of measure 90 degree counter-clockwise (by agreement) to the axis of the first measure'. If it requires 2 or more numbers (integer or real) taken as a set to represent the quantity it is a Complex. Regions of a Complex plane are directly comparable (1-to-1) with the concept of 'area' on the Euclidian plane. > We can't physically draw a line segment to arbitrary high > precision. Irrelevant. If the hole in my approach is that I can't draw a line of arbitrary precision in practice then your own 'uncountable numbers' argument falls for the same reason because if it is truly uncountable you can't point to it on a number line and say "there is an uncountable". This discussion is one of principles, not one of practice. > We can conceive of the notion of line segments being > in 1-1 correspondence with the reals, but we can specify at most > countably many "finitely denumerable" line segments if we wish to > discuss their lengths individually. To say there are Reals for which there is no linear representation is the same as saying there are lengths which can't be measured. Now since a line is nothing but a set of points, which don't have size, but only position this obviously holds no water, unless you are saying it is not possible to place two points arbitrarily close together, which would imply that points have some sort of width, clearly against the definition of a point. This all goes back to what I said in a earlier post, the problem comes from our axiomatic (ie taken on faith, unprovable) use of infinity. Without a clear and precise dilineation of those axioms prior to the proof such conclusions are worthless. Several of you have said "infinity is not a number", this is an axiom. Change the axioms and the whole structure changes. I am simply saying that perhaps we should look at the "infinity is not a number" axiom, much as geometers look at Euclids Fifth Postulate. There is nothing inherent in nature that prefers one axiomatic expression of infinity over the other. By changing our axiomatic definition of infinity we reduce the sets we have to work with from [Integer, Irrational, Real, Complex] to [Integer, Real, Complex]. Now, whether it is worth the trouble is at this time unanswerable because nobody has ever done the research. Jim Choate CyberTects ravage(a)ssz.com "The laws of mathematics, as far as they refer to reality, are not certain, and as far as they are certain, do not refer to reality." Albert Einstein

1 0

[Math Noise]
by Mike Duvos 17 Dec '03

17 Dec '03

Jim Choate <ravage(a)EINSTEIN.ssz.com> writes: >> One can construct the reals from the rationals quite easily >> using any of several well-known methods, such as >> equivalence classes of Cauchy sequences, or Dedikind cuts. > So you are saying that the Reals are a subset (ie can be > constructed from) of the Rationals? Yes, the Reals can be constructed from the Rationals. No, the Reals are not a subset of the Rationals. Fortunately, construction in mathematics is not simply limited to the taking of subsets. The Rationals can be constructed from the Integers, for instance, by multiplication and the taking of appropriate equivalence classes. In fact, everything can be built out of two sets and the axioms of Set Theory. > I can create a number which is not representable by the > ratio of two integers from two numbers which are > representable by ratios of two integers? Er, no. But you can create a number which is not representable as a fraction as a limit point of very many fractions. > That's a nifty trick indeed, I am really impressed. Thank-you. :) > Cauchy produced a test for testing convergence. I fail to > see the relevance here, but please expound... Cauchy sequences are useful for adding limit points to a set of things because their convergence criteria is very simple, and it is conceptually easy to take all Cauchy sequences whose elements come from a given set. If we then consider equivalence classes of those Cauchy sequences which converge to the same limit, and consider an element of the original set to correspond to the class containing the sequence all of whose members are that element, we can consider the classes to form a "completion" of the original set by addition of all its limit points. Similarly, the Reals are the completion of the Rationals. > Dedekind Cut: > "Thus a nested sequence of rational intervals give rise to > a seperation of all rational numbers into three classes." > Just exactly where does this allow us to create Reals? Finite ordered sets have maximum elements. Bounded infinite ordered sets have Least Upper Bounds, which may be a limit point as opposed to being an actual member of the set. Dedekind Cuts are a simple abstraction, often used to construct the Reals from the Rationals in undergraduate calculus courses. Conceptually, one makes a single "cut" in the set of Rationals, dividing it into two parts, all of the members of one part being greater than all of the members of the other. The number of ways of doing this correspond to the Reals. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd(a)netcom.com $ via Finger. $

1 0

[Math Noise] (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > Yes, the Reals can be constructed from the Rationals. No, the > Reals are not a subset of the Rationals. An arbitrary Real can be constructed from the Rationals. If we accept the proposition, as posed apparently by you and others, of uncountable Reals then your 'assumption' fails, otherwise the 'uncountable' members would be countable. > Er, no. But you can create a number which is not representable > as a fraction as a limit point of very many fractions. A 'limit point' is not the same as 'equal to'. Arbitrarily close is not equivalent, inherent in the definition of a limit point is the concept of 'little o' and 'big o', or worded differently our axiomatic definition of infinity. > If we then consider equivalence classes of those Cauchy sequences > which converge to the same limit, and consider an element of the > original set to correspond to the class containing the sequence > all of whose members are that element, we can consider the > classes to form a "completion" of the original set by addition of > all its limit points. We can, but there is no fundamental rule in mathematics that requires me to ignore the small but distinct difference between the element in the original set and the sequences used to approximate it. It is something that must be agreed upon by accepting a particular axiomatic definition of infinity. > Dedekind Cuts are a simple abstraction, often used to construct > the Reals from the Rationals in undergraduate calculus courses. > Conceptually, one makes a single "cut" in the set of Rationals, > dividing it into two parts, all of the members of one part being > greater than all of the members of the other. The number of ways > of doing this correspond to the Reals. The number of cuts are 1-to-1 with the Reals, they are not the Reals. There is no way I can make a cut which is 3.1527, only 1-to-1 with the number(s). Important distinction. Jim Choate CyberTects ravage(a)ssz.com "The best lack all conviction, while the worst are full of passionate intensity." Yeats

1 0

Don't send this to the moderated list...
by David E. Smith 17 Dec '03

17 Dec '03

Send this message to cp-flames and cp-unedited, not to the moderated list. Not only is is devoid of crypto content, but it'll allow me to verify that I've been subscrived :) to the appropriate list (also to see if the headers are changed to the point where I have to modify my filters, etc.) dave ----- David E. Smith, P O Box 324, Cape Girardeau MO USA 63702 dsmith(a)prairienet.org http://www.prairienet.org/~dsmith send mail with subject of "send pgp-key" for my PGP public key " . . . but I'm an AMERICAN criminal lunatic!" --- The Joker

1 0