Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: Virgil on 20 Jan 2007 19:04 In article <1169332163.222236.89960(a)v45g2000cwv.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Andy Smith schrieb: > > > mueckenh(a)rz.fh-augsburg.de writes > > > > > >Andy Smith schrieb: > > > > > >> I > > >> > > > > The union of all finite binary trees contains all levels > > >> > > > >which can be > > >> > > > > enumerated by natural numbers: > > >> > > > > > > >> > > > > 0 0. > > >> > > > > / \ > > >> > > > > 1 0 1 > > >> > > > > / \ / \ > > >> > > > > 2 0 1 0 1 > > >> > > > > ............................... > > >> > > > > > > >> > > >> Out of interest, aren't the set of all numbers defined by the union of > > >> all paths through a finite binary tree with N levels just all the > > >> numbers addressed by the first N bits? If so, why do you bother with > > >> the tree construction - does it have some special significance? > > > > > >The real numbers are represented as infinite paths in the "complete" > > >infinite tree. Some even twice. > > > > > >The union of all finite trees is an infinite tree. > > >Every finite tree contains only a finite set of paths. > > >The countable union of all paths of the finite trees is therefore the > > >countable union of all finite paths. > > >The countable union of all finite paths is in the union of all finite > > >trees. > > >The "complete" tree containing all paths is identical to the union of > > >al finite trees, with respect to nodes and edges. > > >Identical trees cannot contain different sets of paths. > > >Therefore, both trees contain the same set of paths. > > >Therefore the "complete" set of all path is countable. > > >Therefore the set of all real numbers is countable. > > >Therefore ZFC is inconsistent. > > > > I would have said that the set of all paths in a finite tree of depth N > > correspond 1:1 with the address range of N bits. > > You use N as a natural number? It is usual here to denote the set of > all natural numbers by N, a natual number by n. > > > > An infinite tree corresponds to a number encoded in a countably infinite > > set of bits. > > The nodes of the tree, yes. The edges of the tree too. The paths of the > tree, no. An infinite tree corresponds fairly closely to the set of all real numbers encodable in a countably infinite set of bits, except that some numbers have dual encodings. > > > > Cantor's diagonalisation argument then applies. > > It does not apply to the paths of the tree with all nodes, because this > tree contains the representations of all real numbers of the interval > [0, 1]. That does not prevent it from applying, and, in fact, the diagonalization argument applies perfectly to the set of all infinite sequences of binary bits, which is where it was originally applied. > > > But, I think that there > > are other reasons for thinking that the reals are uncountable anyway. > > Which reasons have you in mind? Cantor's first proof, among other things.
From: Franziska Neugebauer on 20 Jan 2007 19:13 mueckenh(a)rz.fh-augsburg.de wrote: > Franziska Neugebauer schrieb: > >> Whether a _meaning_ of >> >> T(1) U T(2) U T(3) U ... (inf-u) >> >> exists does _not_ depend on such question. It depends on a definition >> you have to provide. So please answer the question, what (inf-u) >> means and prove that it exists. >> >> > This is connected >> >> Whether that is "connected" is irrelevant to a possible definition of >> (inf-u). > > That is not a true statement. Nevertheless: > > Definition of the infinite union of trees by induction: If the finite > tree with n levels exists, the finite tree with n+1 levels exist. The > tree with 1 level exists. By induction you only define (if at all) every _finite_ union T(1) U ... U T(n) n e N which is already done: ,----[ <45af6ca0$0$97262$892e7fe2(a)authen.yellow.readfreenews.net> ] | 6. We now introduce the notion of the "union of a finite set of | trees" (sloppyly "union of trees") as: | | U V := T_1 U ... U T_n (n e N) | | Proof as an exercise that forall sets of finite trees V having card(V) | e N it holds that | | U V = T(max(D(V)). `---- I have asked for a definition of (inf-u). F. N. -- xyz
From: Virgil on 20 Jan 2007 19:20 In article <1169332384.876640.319580(a)a75g2000cwd.googlegroups.com>, mueckenh(a)rz.fh-augsburg.de wrote: > Franziska Neugebauer schrieb: > > > > Whether a _meaning_ of > > > > T(1) U T(2) U T(3) U ... (inf-u) > > > > exists does _not_ depend on such question. It depends on a definition > > you have to provide. So please answer the question, what (inf-u) means > > and prove that it exists. > > > > > This is connected > > > > Whether that is "connected" is irrelevant to a possible definition of > > (inf-u). > > That is not a true statement. Nevertheless: > > Definition of the infinite union of trees by induction: If the finite > tree with n levels exists, the finite tree with n+1 levels exist. The > tree with 1 level exists. Therefore, by induction, all finite n-lever trees for all n in N exist. But that is all that standard induction allows one to conclude. > > Proof of existence of the union tree by proofs of A, B, and C: > A) Proof of the existence of one infinite path by induction over the > indexes > {1} U {1, 2} U {1, 2, 3} U... U {1, 2, 3, ..., n}... U ... > is the same as the union of the ends of the initial segments > {1} U { 2} U {3} U... U {n}... U .. > which is N which exists. > B) Proof of the existence of all infinite paths: See proof of the > existence of all real numbers in [0, 1]. > C) Proof of the existence of all paths in the tree being infinite:: All > paths of a tree have same length by definition. First of all, the standard definition of finite binary trees does not require that all paths in such a tree be of the same length. It is only in our special examples here that we are making such a requirement, but it is not "by definition". Secondly, there are lots of different infinite binary trees in which every path is of infinite length. The one of major interest is that one having one path corresponding to every possible binary sequence, which we have been calling the complete binary tree. It has uncountably many paths. But there are also infinite binary trees containing the same set of nodes and the same set of edges but having only countably many paths. For example, the infinite binary tree having only "eventually constant" paths (all branchings are 0's or all 1's from some node on) has exactly the same set of nodes and exactly the same set of edges as the complete binary tree. So the range of such infinite binary trees includes both ones with only countably many paths and ones with uncountably many paths.
From: G. Frege on 20 Jan 2007 23:39 On Sat, 20 Jan 2007 18:21:06 -0500, David Marcus <DavidMarcus(a)alumdotmit.edu> wrote: > > mueckenh(a)rz.fh-augsburg.de wrote: >> >> The tree illustrates the following problem: >> >> 1) For every natural number n there is an natural number m >> such that m = n+1. >> >> In short, with n,m in N: An Em: m = n+1 >> > So, what's the problem [...]? > The problem is that WM suffers from quantifier dyslexia. From An e N Em e N: m = n+1 he concludes (correctly) An e N Em e N: m > n. And in his understanding this means (is logically equivalent to): * Em e N An e N: m > n. He's not able to grasp that AxEy(phi[x,y]) isn't equivalent to EyAx phi[x,y] in general. A quote from M�ckenheim's oeuvre: <begin quote> ....it is inconsistent to speak of /an infinite set of finite numbers/. Finite numbers can only form a potentially infinite set. An actually infinite set cannot exist other than including its cardinal number aleph_0 or the number "ordinal infinity", denoted by 'omega' This had been unconsciously acknowledged by Cantor himself already: "/Every number/ smaller than omega is a finite number, and its magnitude /is surpassed by other finite numbers/." Here the phrase "by other finite numbers" is obviously to be interpreted as "by such finite numbers which did not yet belong to the set containing /every finite number/". <end quote> [Contradiction! Since "omega is not a natural number."] <begin quote> Therefore an actually infinite set of only natural numbers, in particular the complete set of exclusively all natural numbers, usually abbreviated by N, cannot and does not exist at all [...], and the onus of finding a natural number n which does not take its finite place n in the sequence, rests on those who support this self-contradicting notion. Of course, we can denote this set by N as we can name dwarfs, fairies and unicorns. But that does not found its existence. <end quote> (W. M�ckenheim, The Meaning of Infinity) That's ...well... logic, man! F. P.S. Cantor wrote: "Jede kleinere Zahl als omega ist eine endliche Zahl und wird von anderen endlichen Zahlen n der Gr��e nach �bertroffen." *My* translation of this statement would be: "Every number smaller than omega is a finite number, and it is surpassed by other finite numbers in [by?] magnitude." In other words, for any (every) natural number there's a bigger one: An e N Em e N: m > n. Clearly, this does _not_ mean (as M�ckenheim "concludes"), that there is a natural number bigger than all natural numbers: * Em e N An e N: m > n. -- E-mail: info<at>simple-line<dot>de
From: G. Frege on 21 Jan 2007 00:29
On Sun, 21 Jan 2007 05:39:58 +0100, G. Frege <nomail(a)invalid> wrote: > > (W. M�ckenheim, The Meaning of Infinity) > Another pearl from this remarkable work: "[...] the existence of transcendental numbers proves the equivalence |N| = |R| (2) which, if no transcendental numbers would exist, was also true, because in that case only the set of algebraic numbers with its cardinality aleph_0 remained. Consequently, equivalence (2) is true in any case." (N = set of natural numbers, R = set of real numbers) F. -- E-mail: info<at>simple-line<dot>de |