eklhad@ihnet.UUCP (K. A. Dahlke) (10/04/85)
< What do you mean the line-eating bug is fixed?!?! > I sort of enjoyed this problem, maybe you will too. First, some notation for Cantor's various infinities is appropriate. Let me call the cardinality of the integers A0 (sorry purists, that funny symbol just isn't on my HP keyboard). Somewhat predictably, let me call the cardinality of the reals C. I shall call the cardinality of the set of real valued functions CC. By the way, is there a standard symbol for this flavor of infinity? My question is: how many *continuous* real valued functions are there? The set is at least C, since F(x) = R (R any real number) is a valid continuous function. Is the set CC? I first reviewed my diagonalization argument for *unconstrained* functions. If the set of real valued functions is C, there is some correspondence map between R1 and functions of R1. Construct a new function Y(), where Y(x) = F[x](x) + 1. In other words, to compute Y(x), take the function associated with x, evaluate it at x, and add one. This new function cannot be associated with any real number. Fine for unconstrained functions, but Y() is not necessarily continuous. Back to the drawing board. It turns out that the set of continuous functions is C, but I won't spoil things by giving the proof now. This means, there is (theoretically) a procedure for ordering all continuous functions. Is x^2+3 > sin(x)*x? I guess continuity is a much stronger constraint than I had realized. There is an unimaginable sea of fuzzy jumpy functions out there. -- When You ferst realise that you're net artical contains spelling and grammatically errors, and sentense fragments. Karl Dahlke ihnp4!ihnet!eklhad
usenet@ucbvax.ARPA (USENET News Administration) (10/06/85)
Since the cardinality of the set of polynomials mapping R -> R is C, and any continuous function mapping R -> R is the limit of a sequence of polynomials (the card of the set of such sequences again being C), therefore the card of the set of continuous functions is also C.
yena@pur-ee.UUCP (Anthony T Yen) (10/07/85)
>> Since the cardinality of the set of polynomials >> mapping R -> R is C, and any continuous function >> mapping R -> R is the limit of a sequence of **>> polynomials (the card of the set of such sequences **>> again being C), therefore the card of the set of >> continuous functions is also C. Nope. Consider: Each real number is the limit of a sequence of rational numbers, but reals are uncountable and rationals are. The reason is that each limit is (sort of) defined by a countable subset of (in your case) polynomials, so there are as many limits as there are countable subsets (actually, there are less, but that can be taken care of easily [details are left for homework :-) ]). There are C polynomials ---> there are aleph-0 * C countable subsets. Incidentally, C = aleph-1. ( C <= the number of finite subsets of reals = aleph-1 and C >= the number of reals = aleph-1 --> C = aleph-1) and so aleph-0 * C = aleph-2. ================================================ Hao-Nhien Qui Vu ( pur-ee!vu ) Purdue University
usenet@ucbvax.ARPA (USENET News Administration) (10/08/85)
In article <3368@pur-ee.UUCP> yena@pur-ee.UUCP (Anthony T Yen) writes: > > >> Since the cardinality of the set of polynomials > >> mapping R -> R is C, and any continuous function > >> mapping R -> R is the limit of a sequence of >**>> polynomials (the card of the set of such sequences >**>> again being C), therefore the card of the set of > >> continuous functions is also C. > >Nope. Consider: Each real number is the limit of a sequence of >rational numbers, but reals are uncountable and rationals are. > >The reason is that each limit is (sort of) defined by a countable >subset of (in your case) polynomials, so there are as many limits >as there are countable subsets (actually, there are less, but that >can be taken care of easily [details are left for homework :-) ]). >There are C polynomials ---> there are aleph-0 * C countable subsets. > >Incidentally, C = aleph-1. >( C <= the number of finite subsets of reals = aleph-1 >and C >= the number of reals = aleph-1 --> C = aleph-1) >and so aleph-0 * C = aleph-2. > >================================================ >Hao-Nhien Qui Vu ( pur-ee!vu ) Purdue University I don't understand what is wrong with the original argument. I'm too tired to deal with this now, can someone check this out?
cjh@petsd.UUCP (Chris Henrich) (10/08/85)
[] In article <3368@pur-ee.UUCP> yena@pur-ee.UUCP (Hao-Nhien Qui Vu) writes: [ quoting another article in which it is asserted that the set of sequences of polynomials has cardinality C ] >Nope. Consider: Each real number is the limit of a sequence of >rational numbers, but reals are uncountable and rationals are. > >The reason is that each limit is (sort of) defined by a countable >subset of (in your case) polynomials, so there are as many limits >as there are countable subsets (actually, there are less, but that >can be taken care of easily [details are left for homework :-) ]). >There are C polynomials ---> there are aleph-0 * C countable subsets. In fact the number of countable subsets is C ** aleph-0. > >Incidentally, C = aleph-1. ... >and so aleph-0 * C = aleph-2. Actually aleph-0 * aleph-1 = aleph-1. But also, C ** aleph-0 = aleph-1. Proof: C ** aleph-0 = aleph-1 ** aleph-0 = ( 2 ** aleph-0) ** aleph-0 = 2 ** (aleph-0 ** aleph-0) = 2 ** aleph-0 = aleph-1. References: College-level books on set theory. One by Halmos, _Naive_Set_Theory_, is quite good. By "Naive" he means that he does not go into the most perplexing issues. If you want something a good deal more difficult, try the appendix in Kelley, _General_Topology_. Regards, Chris -- Full-Name: Christopher J. Henrich UUCP: ..!(cornell | ariel | ukc | houxz)!vax135!petsd!cjh US Mail: MS 313; Perkin-Elmer; 106 Apple St; Tinton Falls, NJ 07724 Phone: (201) 758-7288
ttp@kestrel.ARPA (10/08/85)
What is the cardinality of continuous functions? (aleph 1). try this?: A Continuous Function on the Reals is completely defined (by continuity) by the values it takes on the Rationals (because the rationals are dense in the reals), thus the number of Continuous Functions on the Reals is in One-to-One correspondence with a subset of the Functions defined on the Rationals. The cardinality of functions on the Rationals is the cardinality of the Reals. -tom
jbuck@epicen.UUCP (Joe Buck) (10/09/85)
This message is empty.
chuck@dartvax.UUCP (Chuck Simmons) (10/11/85)
> C ** aleph-0 = aleph-1 ** aleph-0 > = ( 2 ** aleph-0) ** aleph-0 > = 2 ** (aleph-0 ** aleph-0) > = 2 ** aleph-0 > = aleph-1. Now wait a minute. (1) Since when is the exponentiation operator associative (lines 2-3). (2) aleph-0 ** aleph-0 is NOT aleph-0. Proof: 2 < aleph-0 -> 2 ** aleph-0 <= aleph-0 ** aleph-0 -> aleph-1 <= aleph-0 ** aleph-0 Since aleph-0 < aleph-1, it follows that aleph-0 < aleph-0 ** aleph-0. chuck@dartvax
stark@sbcs.UUCP (Eugene Stark) (10/11/85)
> > In fact the number of countable subsets is C ** aleph-0. > > > >Incidentally, C = aleph-1. > ... > >and so aleph-0 * C = aleph-2. > > Actually aleph-0 * aleph-1 = aleph-1. But also, > C ** aleph-0 = aleph-1. Proof: > > C ** aleph-0 = aleph-1 ** aleph-0 > = ( 2 ** aleph-0) ** aleph-0 > = 2 ** (aleph-0 ** aleph-0) The previous line should read: 2 ** (aleph-0 * aleph-0) (exponentiation is not associative) > = 2 ** aleph-0 > = aleph-1. > > > References: College-level books on set theory. One by Halmos, > _Naive_Set_Theory_, is quite good. Not to split hairs, but aleph-0 = the cardinality of the natural numbers = the least infinite cardinal aleph-1 = the least cardinal strictly greater than aleph-0 2**aleph-0 = the cardinality of the continuum = the cardinality of the powerset of a countably infinite set The equality of aleph-1 and 2**aleph-0 is the "continuum hypothesis", which is independent of the other axioms of set theory. (See, for example Shoenfield, "Mathematical Logic" Chapter 9, or any book on axiomatic set theory.) Gene Stark
bhuber@sjuvax.UUCP (B. Huber) (10/11/85)
It looks like nothing except an explicit one - to - one correspondence will satisfy you guys. Since it is pretty clear that the set C(R,R) of continuous functions with real values defined on all the real numbers has at least aleph-one elements, I will give you an injection from C(R,R) into the set R of real numbers. Because the cardinality of R is aleph-one, the Schroder-Bernstein theorem (which is intuitively obvious) asserts that the cardinality of C(R,R) is at most aleph-one, thereby finishing the demonstration that its cardinality is exactly aleph-one. First, any continuous function is uniquely determined by its values on the subset Q of rational numbers, because every other real number is a limit of rationals. Q is enumerable. So do it: count the rationals, letting q1 be the first,... and qn the nth. Express all real numbers in base two. Now here's the injection: Let f: R----->R be a continuous function. f(q1) is expressed as one string of zeros and ones in base two; corresponding to each digit is its 'place', which ranges among the integers. (The place is the power of two represented by the digit.) let r1 be the real number which has a zero in every even place, and in place 2k-1, has the digit appearing in the kth place of f(q1). That is, we scatter the digits of f(q1) by inserting zeros between any two successive ones. Next, scatter the digits of f(q2) among the places in r1 which are odd multiples of two, in a systematic manner (as we did to f(q1) above). Call the result r2. From r2 you can recover both f(q1) and f(q2), by looking in the odd places for the digits of f(q1), and in the odd multiple of two places for the digits of f(q2). Continue in this manner, scattering the digits of f(qn) in sequence among the places of r(n-1) which are odd multiples of 2**(n-1), to create rn. f(q1), ..., f(qn) can all be recovered from rn. We have thus managed to encode complete information about all of the values f(q1), ..., f(qn), ... in one 'limit' real, r(infinity), in such a way that examination of r(inifinity) reveals the value of any f(qn), for all positive integers n. Since this sequence of values uniquely determines f, we see that there are no more continuous functions than there are real numbers. I apologize for the length of this rather simple explanation; but in light of the preceding discussion, an unassailable and elementary proof seemed important. --Bill Huber, St Joseph's University, Philadelphia.
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (10/12/85)
> > C ** aleph-0 = aleph-1 ** aleph-0 > > = ( 2 ** aleph-0) ** aleph-0 > > = 2 ** (aleph-0 ** aleph-0) should have been = 2 ** (aleph-0 * aleph-0) > > = 2 ** aleph-0 > > = aleph-1.
dmr@dutoit.UUCP (10/12/85)
There seems to be a general belief in recent messages here that aleph-1 (second infinite cardinal) equals C (power of the continuum). C is defined as the cardinality of the real numbers, and by simple Cantorian arguments is equal to the cardinality of the subsets of integers, which is what is meant by 2^aleph-0. But the other belief is called the Continuum hypothesis, and Paul Cohen showed about 20 years ago that it is independent of the usual axioms of set theory (can't be proved; may consistently be asserted or denied). You are free to assume that C is much bigger than practically any aleph you can name (well, not aleph-C). In particular, the following fragment is lunacy: >There are C polynomials ---> there are aleph-0 * C countable subsets. > >Incidentally, C = aleph-1. >( C <= the number of finite subsets of reals = aleph-1 >and C >= the number of reals = aleph-1 --> C = aleph-1) >and so aleph-0 * C = aleph-2. Dennis Ritchie
cjh@petsd.UUCP (Chris Henrich) (10/12/85)
[] In article <3686@dartvax.UUCP> chuck@dartvax.UUCP (Chuck Simmons) writes: > [quoting some equations of mine] >Now wait a minute. (1) Since when is the exponentiation operator >associative (lines 2-3). (2) aleph-0 ** aleph-0 is NOT aleph-0. Murphy made me do it. Here's a less erroneous version: >> C ** aleph-0 = aleph-1 ** aleph-0 >> = ( 2 ** aleph-0) ** aleph-0 >> = 2 ** (aleph-0 * aleph-0) ^ multiplication not exponentiation... this rule is valid for transfinite cardinals just as for finite ones. >> = 2 ** aleph-0 >> = aleph-1. Regards, Chris -- Full-Name: Christopher J. Henrich UUCP: ..!(cornell | ariel | ukc | houxz)!vax135!petsd!cjh US Mail: MS 313; Perkin-Elmer; 106 Apple St; Tinton Falls, NJ 07724 Phone: (201) 758-7288