Re: The seven step series (december 2009)
Marty, On 10 Dec 2009, at 16:40, m.a. wrote: Bruno, This English version of the 7-Step Series is greatly appreciated and I am more than willing to accept its conclusions on faith. Unfortunately, it seems that the only proof of these concepts, at present, requires the traversing of long chains of logical formulae which I am unable to do. I assume that more easily demonstrable proofs will appear when predictions based on your ideas attain experimental reality e.g. teleportation, digital brain recording and so on. Till then I remain, without religious implications, a believer.m.a. You are welcome. It is not so much a question of a long chain of reasoning, it is much a question of developing a familiarity with each step of the reasoning. Take all your time, the fun is in staying interested in the subject. Have you read the book Mind's I edited by Hofstadter and Dennett, it introduced the mechanical mind-body problem. Sometimes (in my theses for example) I begin by the movie graph argument. But this is the hardest part for the physicists and for the logicians. It was a shortcut to explain what is the mind body problem. All the rest is harder for the philosopher of mind. It is the dificulty of working in interdisciplinary domain. You know, what I do is really asking question here, just making them precise by the discovery of the universal machine. A discovery in mathematics. Apparently I am explaining UDA in the Salvia Forum here, Marty, and some of you may follow, and intervenes. I guess. http://www.entheogen.com/forum/showthread.php?t=25685page=4 As exercise I let you guess what is my username on that forum. I don't dare to put my username on this list ;-) Bruno - Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Wednesday, December 09, 2009 2:25 PM Subject: Re: The seven step series (december 2009) On 09 Dec 2009, at 01:42, m.a. wrote: Bruno, This is a stupid question but I'm hoping it contains the kernel of an idea. Since logic is based on a few common definitions, do you really need all these complicated steps and permutations to prove a theory? Why can't you show us what you mean in a handful of clear, simple, logical statements?marty a. Have you an understanding of the six first steps, which does not use much of technics. Do you have the UDA slides in front of you? Then at the seven step, all you need it to accept the idea that there is a (finite) program which generates all programs together with all their executions. This follows from Church thesis, as I have explained, but you can skip those explanations. Yet for other, notably those who objected to the end of MGA (the Movie Graph Argument) that a movie made from a filmed brain could lived a conscious experience qua computatio, I have to prepare them better to the (necessarily technical) computational supervenience (how consciousness is associated to infinities of computations). Have you understand that my hypothesis is that the brain, or the body, or whatever you are willing to suppose responsible for your consciousness , is a machine (a digital machine, that is a machine such that we can frozen its state and copy it ?). Later we will relinquish a lot that assumption, note. Is the step 0, the definition of computationalism clear for you? It is equivalent as accepting classical teleportation as a mean for locomotion. The reasoning does not depend on the feasibility of this, but on its logical possibility. Or do you prefer I state only the result, in english. I think, that if you accept that a universal program like above exists (which it did with Church thesis), then I think you can understand in which sense physics arise in the mind of the machines, it is enough to get some familiarity with the first sixth steps. The result is that physics is derivable from computer science, assuming comp. And we get as expected gift an explanation for the physical sensations, as emerging from the difference between computers science (the truth, in the sense of Tarski 1944) and computer's computer science (the beliefs in the sense of Gödel 1931). As for AUDA there is a need to understand some mathematical theorems (Gödel, Löb, Solovay). A journalistic version would be that we can already make the UDA test to a universal machine, instead of you, and use the math to see the shadows of the emergence of the physical laws. This is what Lucas and Penrose missed, by the rather precise way they pretend to tefute mechanism, the machine can already refute their argument. This is known and completely uncontroversial in the community of logicians, and many physicists agrees. But for some reason that reflexion from the part of the machine is ignored. Historically this has
Re: The seven step series (december 2009)
Bruno, This English version of the 7-Step Series is greatly appreciated and I am more than willing to accept its conclusions on faith. Unfortunately, it seems that the only proof of these concepts, at present, requires the traversing of long chains of logical formulae which I am unable to do. I assume that more easily demonstrable proofs will appear when predictions based on your ideas attain experimental reality e.g. teleportation, digital brain recording and so on. Till then I remain, without religious implications, a believer. m.a. - Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Wednesday, December 09, 2009 2:25 PM Subject: Re: The seven step series (december 2009) On 09 Dec 2009, at 01:42, m.a. wrote: Bruno, This is a stupid question but I'm hoping it contains the kernel of an idea. Since logic is based on a few common definitions, do you really need all these complicated steps and permutations to prove a theory? Why can't you show us what you mean in a handful of clear, simple, logical statements? marty a. Have you an understanding of the six first steps, which does not use much of technics. Do you have the UDA slides in front of you? Then at the seven step, all you need it to accept the idea that there is a (finite) program which generates all programs together with all their executions. This follows from Church thesis, as I have explained, but you can skip those explanations. Yet for other, notably those who objected to the end of MGA (the Movie Graph Argument) that a movie made from a filmed brain could lived a conscious experience qua computatio, I have to prepare them better to the (necessarily technical) computational supervenience (how consciousness is associated to infinities of computations). Have you understand that my hypothesis is that the brain, or the body, or whatever you are willing to suppose responsible for your consciousness , is a machine (a digital machine, that is a machine such that we can frozen its state and copy it ?). Later we will relinquish a lot that assumption, note. Is the step 0, the definition of computationalism clear for you? It is equivalent as accepting classical teleportation as a mean for locomotion. The reasoning does not depend on the feasibility of this, but on its logical possibility. Or do you prefer I state only the result, in english. I think, that if you accept that a universal program like above exists (which it did with Church thesis), then I think you can understand in which sense physics arise in the mind of the machines, it is enough to get some familiarity with the first sixth steps. The result is that physics is derivable from computer science, assuming comp. And we get as expected gift an explanation for the physical sensations, as emerging from the difference between computers science (the truth, in the sense of Tarski 1944) and computer's computer science (the beliefs in the sense of Gödel 1931). As for AUDA there is a need to understand some mathematical theorems (Gödel, Löb, Solovay). A journalistic version would be that we can already make the UDA test to a universal machine, instead of you, and use the math to see the shadows of the emergence of the physical laws. This is what Lucas and Penrose missed, by the rather precise way they pretend to tefute mechanism, the machine can already refute their argument. This is known and completely uncontroversial in the community of logicians, and many physicists agrees. But for some reason that reflexion from the part of the machine is ignored. Historically this has been seen already by Godel in 1931, precisely proved by Hilbert and Bernays, clarified and exploited by Löb up to the discovery of G and G¨ by Solovay. Take it easy. Ask for specific questions and I may be able to be more specific too. I think. Bruno -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en. -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.
Re: The seven step series (december 2009)
On 09 Dec 2009, at 01:42, m.a. wrote: Bruno, This is a stupid question but I'm hoping it contains the kernel of an idea. Since logic is based on a few common definitions, do you really need all these complicated steps and permutations to prove a theory? Why can't you show us what you mean in a handful of clear, simple, logical statements?marty a. Have you an understanding of the six first steps, which does not use much of technics. Do you have the UDA slides in front of you? Then at the seven step, all you need it to accept the idea that there is a (finite) program which generates all programs together with all their executions. This follows from Church thesis, as I have explained, but you can skip those explanations. Yet for other, notably those who objected to the end of MGA (the Movie Graph Argument) that a movie made from a filmed brain could lived a conscious experience qua computatio, I have to prepare them better to the (necessarily technical) computational supervenience (how consciousness is associated to infinities of computations). Have you understand that my hypothesis is that the brain, or the body, or whatever you are willing to suppose responsible for your consciousness , is a machine (a digital machine, that is a machine such that we can frozen its state and copy it ?). Later we will relinquish a lot that assumption, note. Is the step 0, the definition of computationalism clear for you? It is equivalent as accepting classical teleportation as a mean for locomotion. The reasoning does not depend on the feasibility of this, but on its logical possibility. Or do you prefer I state only the result, in english. I think, that if you accept that a universal program like above exists (which it did with Church thesis), then I think you can understand in which sense physics arise in the mind of the machines, it is enough to get some familiarity with the first sixth steps. The result is that physics is derivable from computer science, assuming comp. And we get as expected gift an explanation for the physical sensations, as emerging from the difference between computers science (the truth, in the sense of Tarski 1944) and computer's computer science (the beliefs in the sense of Gödel 1931). As for AUDA there is a need to understand some mathematical theorems (Gödel, Löb, Solovay). A journalistic version would be that we can already make the UDA test to a universal machine, instead of you, and use the math to see the shadows of the emergence of the physical laws. This is what Lucas and Penrose missed, by the rather precise way they pretend to tefute mechanism, the machine can already refute their argument. This is known and completely uncontroversial in the community of logicians, and many physicists agrees. But for some reason that reflexion from the part of the machine is ignored. Historically this has been seen already by Godel in 1931, precisely proved by Hilbert and Bernays, clarified and exploited by Löb up to the discovery of G and G¨ by Solovay. Take it easy. Ask for specific questions and I may be able to be more specific too. I think. Bruno -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.
Re: The seven step series (december 2009)
Bruno, This is a stupid question but I'm hoping it contains the kernel of an idea. Since logic is based on a few common definitions, do you really need all these complicated steps and permutations to prove a theory? Why can't you show us what you mean in a handful of clear, simple, logical statements? marty a. - Original Message - From: Bruno Marchal To: everything-list List Sent: Monday, December 07, 2009 1:12 PM Subject: Re: The seven step series (december 2009) Hi, We may be at a cross of the seventh step and Why I am I? thread. Chose your favorite universal system. Like LISP, FORTRAN, the combinators, the diophantine equations, etc. Enumerate in lexicographical order the expressions corresponding to the algorithms of the partial computable function of one variable. (reread the math if necessary, or ask question). This enumerates, with repetition, all the partial (and thus the total) functions from N to N, usually described as the phi_i: phi_0, phi_1, phi_2, phi_3, phi_7 is the name of the 7th partial function in that enumeration. So the official definition of a universal number I am using, is, having fixed such an enumeration, a number u such that phi_u(x, y) = phi_x(y). Where x,y represent some coding of the couple (x, y). u is usually called the computer (hard version) or the interpreter (soft version). (Later, or before, for some, soft and hard will be shown to be more absolute than most people thought, and this as a consequence of comp; but in the present context it could help to think them as relative notion). In the definition of the universal number u, phi_u(x, y) = phi_x(y), u is called the computer, x is called the program, and y is called the data. phi_u itself is called the universal function, and u is just a program computing that universal function. From such a u, you can code easily a universal dovetailer. This is a program which generate all the programs i, and compute, by dovetailing of the phi_i executions, all those phi_i on all its different arguments, 0, 1, 2, ... I may come back to the seven step per se later. Having said what is a universal number, I may say what is a Löbian number. Or if you prefer, having said what is a universal machine, I may say what is a Löbian machine. A Löbian machine is a universal machine which knows, in a very weak and precise technical sense, that she is universal. I can prove that any of you are universal machine. And if you understand the proof, then I have a proof (for me!) that you are inhabited by a Löbian machine. It means also, that it is just a matter of some work, made by you, to convince yourself that a Löbian machine indeed inhabit your mind. Comp is the assumption that there is a level where you can hope your are such a Löbian machine. Now I tell you this. A formula like phi_u(x, y) = phi_x(y) (the definition of universal number) can be translated into an elementary formula of first order arithmetic (like Robinson Arithmetic, or Peano Aritmetic). It ease the things considerably to chose elementary arithmetic as initial universal system. It happens that classical logic makes the very weak theory, where 0, s(0), s(s(0)) ... represent the number 0 and its successors. For all x: x + 0 = x For all x and for all y: x + s(y) = s(x + y) For all x: x * 0 = 0 For all x and for all y: x * s(y) = (x * y) + x Those formula gives the usual recursive or inductive definition of addition and multiplication. Exercise: prove that 2 + 2 = 4. That is, prove that s(s(0)) + s(s(0)) = s(s(s(s(0. This theory is already universal, once we accept some coding of computations into proof in that theory (using classical logic). This is an amazing result, and actually is hard to prove. It is due mainly to Gödel, Hilbert Bernays, Löb). It is easier to prove that the combinators equation Kxy = y, Sxyz = xz(yz) are Turing universal, than to show that addition and multiplication are Turing universal (and thus simply universal with Church thesis). If you know Matiyasevitch theorem, you can derive the universality of addition and multiplication). Well, if you know that Conway's game of life (2-dim cellular automata) is universal, you know universality is cheap (yet non trivial). But the theory, For all x: x + 0 = x For all x and for all y: x + s(y) = s(x + y) For all x: x * 0 = 0 For all x and for all y: x * s(y) = (x * y) + x although universal, is not Löbian. You get a Löbian machine by adding some axioms, like For all x and for all y: NOT(x = y) - NOT(s(x) = s(y))(different numbers have different successors) For all x: NOT(0 = s(x)) (0 is not a successor) And above all the following infinity of axioms, known as the induction axioms. That is, for any first order logical formula A, you take the following
Re: The seven step series (december 2009)
Hi, We may be at a cross of the seventh step and Why I am I? thread. Chose your favorite universal system. Like LISP, FORTRAN, the combinators, the diophantine equations, etc. Enumerate in lexicographical order the expressions corresponding to the algorithms of the partial computable function of one variable. (reread the math if necessary, or ask question). This enumerates, with repetition, all the partial (and thus the total) functions from N to N, usually described as the phi_i: phi_0, phi_1, phi_2, phi_3, phi_7 is the name of the 7th partial function in that enumeration. So the official definition of a universal number I am using, is, having fixed such an enumeration, a number u such that phi_u(x, y) = phi_x(y). Where x,y represent some coding of the couple (x, y). u is usually called the computer (hard version) or the interpreter (soft version). (Later, or before, for some, soft and hard will be shown to be more absolute than most people thought, and this as a consequence of comp; but in the present context it could help to think them as relative notion). In the definition of the universal number u, phi_u(x, y) = phi_x(y), u is called the computer, x is called the program, and y is called the data. phi_u itself is called the universal function, and u is just a program computing that universal function. From such a u, you can code easily a universal dovetailer. This is a program which generate all the programs i, and compute, by dovetailing of the phi_i executions, all those phi_i on all its different arguments, 0, 1, 2, ... I may come back to the seven step per se later. Having said what is a universal number, I may say what is a Löbian number. Or if you prefer, having said what is a universal machine, I may say what is a Löbian machine. A Löbian machine is a universal machine which knows, in a very weak and precise technical sense, that she is universal. I can prove that any of you are universal machine. And if you understand the proof, then I have a proof (for me!) that you are inhabited by a Löbian machine. It means also, that it is just a matter of some work, made by you, to convince yourself that a Löbian machine indeed inhabit your mind. Comp is the assumption that there is a level where you can hope your are such a Löbian machine. Now I tell you this. A formula like phi_u(x, y) = phi_x(y) (the definition of universal number) can be translated into an elementary formula of first order arithmetic (like Robinson Arithmetic, or Peano Aritmetic). It ease the things considerably to chose elementary arithmetic as initial universal system. It happens that classical logic makes the very weak theory, where 0, s(0), s(s(0)) ... represent the number 0 and its successors. For all x: x + 0 = x For all x and for all y: x + s(y) = s(x + y) For all x: x * 0 = 0 For all x and for all y: x * s(y) = (x * y) + x Those formula gives the usual recursive or inductive definition of addition and multiplication. Exercise: prove that 2 + 2 = 4. That is, prove that s(s(0)) + s(s(0)) = s(s(s(s(0. This theory is already universal, once we accept some coding of computations into proof in that theory (using classical logic). This is an amazing result, and actually is hard to prove. It is due mainly to Gödel, Hilbert Bernays, Löb). It is easier to prove that the combinators equation Kxy = y, Sxyz = xz(yz) are Turing universal, than to show that addition and multiplication are Turing universal (and thus simply universal with Church thesis). If you know Matiyasevitch theorem, you can derive the universality of addition and multiplication). Well, if you know that Conway's game of life (2-dim cellular automata) is universal, you know universality is cheap (yet non trivial). But the theory, For all x: x + 0 = x For all x and for all y: x + s(y) = s(x + y) For all x: x * 0 = 0 For all x and for all y: x * s(y) = (x * y) + x although universal, is not Löbian. You get a Löbian machine by adding some axioms, like For all x and for all y: NOT(x = y) - NOT(s(x) = s(y))(different numbers have different successors) For all x: NOT(0 = s(x)) (0 is not a successor) And above all the following infinity of axioms, known as the induction axioms. That is, for any first order logical formula A, you take the following formula as axiom: (A(0) For all x: A(x) - A(s(x))) - For all x: A(x). This is enough to get a Löbian machine, (Peano Arithmetic) which, as AUDA will illustrate has already a stable and very complex theology, including its physical quanta and qualia. But before going to AUDA, I have to finish the seventh step properly, and probably come back to the Movie graph problems we have encountered. Why a movie of a computation is not a computation? What is the difference between a computation and a description of a computation? etc. I guess we could finish properly the seventh and the
Re: The seven step series (november 2009)
On 16 Nov 2009, at 17:45, Brent Meeker wrote: Bruno Marchal wrote: On 11 Nov 2009, at 19:52, Brent Meeker wrote: But how is the first person point of view defined? Can this theory tell me how many persons exist at a given time? I come back on this. The question how many persons? is a question which remains very hard in the mechanist theory. To answer it, let me ask you a question. Suppose that old fashioned time travel is possible, and that Brent Meeker of the future decides to travel in the past, and to say hello to the younger Brent Meeker. They met in a kitchen and drink coffee. Nobody else is present in the kitchen. How many person are there in the kitchen? What would you say? I think this: if you answer one, then I will tend to say that there is only one person in the multiverse, but it manifests itself in different overlapping contexts. If you answer two, then I will tend to say that there are an infinity of persons in the multiverse. What do you think? I think closed time-like loops are probably impossible. But your answer just points to possible equivocation on person. The time traveling Brent is a different person from the untraveled Brent because he has different memories just as the 70yr old Brent is a different person than the 10yr old Brent. But in another sense - causal continuity - they are the same person. It isn't necessary to introduce time travel to create this confusion of terms. But the first part of my question was about how a first person view is defined in this mathematical abstraction? What computations must my computer perform so that it has a first person view? UDA has been constructed so that we don't have to answer this question to understand that the physical laws emerge from numbers (assuming comp). It is just enough that we accept that there is a level of substitution. Then we can prove that we cannot know-for-sure which computations support consciousness, yet that we have to take into account an infinity of those computations (below the substitution level) to get the first person experiences measure. But AUDA provides a hint of a more precise answer. Consciousness is associated to the universal machine having the cognitive ability of a Lobian machine(*). So PA and ZF are already conscious. Their provability predicate obey Bp - BBp. And their knowledge pseudo- predicate defined by Kp = Bp p, obeys it too: Kp - KKp. But remember that, by the movie graph (UDA step 8) consciousness is not associated to the performance of a computer (= one computation/one universal machine), but to the existence of the computations (=infinity of computations and universal machines as defined in the standard model of arithmetic). Consciousness is associated to the logical relations between numbers which defined the alternate consistent extensions of the subject. You are, in that sense, the same person as PA, and probably ZF, like you are the same person as the young baby Brent. And probably: rich qualia (like our owns) need long and deep stories (very long computations capable of stabilizing on the interference of the infinity of computations which exists below our level of substitution). Bruno (*) Formally: it means they provability predicate obeys B(Bp - p) - Bp (Löb Formula). Bp - BBp can be derived from this. It is actually done in Smullyan's Forever Undecided. http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=.
Re: The seven step series (november 2009)
On 11 Nov 2009, at 19:52, Brent Meeker wrote: But how is the first person point of view defined? Can this theory tell me how many persons exist at a given time? I come back on this. The question how many persons? is a question which remains very hard in the mechanist theory. To answer it, let me ask you a question. Suppose that old fashioned time travel is possible, and that Brent Meeker of the future decides to travel in the past, and to say hello to the younger Brent Meeker. They met in a kitchen and drink coffee. Nobody else is present in the kitchen. How many person are there in the kitchen? What would you say? I think this: if you answer one, then I will tend to say that there is only one person in the multiverse, but it manifests itself in different overlapping contexts. If you answer two, then I will tend to say that there are an infinity of persons in the multiverse. What do you think? Note that in UDA, I use a definition of first person which identify a person with its personal memory, and so where many different persons can exist. But in AUDA, I use a more mathematical definition which eventually identify all persons. Then they can differentiate through a mixture of amnesia (they forget that they are the universal person), and personal memories (which they will use as self-identification means). Bruno http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=.
Re: The seven step series (november 2009)
Bruno Marchal wrote: On 11 Nov 2009, at 19:52, Brent Meeker wrote: But how is the first person point of view defined? Can this theory tell me how many persons exist at a given time? I come back on this. The question how many persons? is a question which remains very hard in the mechanist theory. To answer it, let me ask you a question. Suppose that old fashioned time travel is possible, and that Brent Meeker of the future decides to travel in the past, and to say hello to the younger Brent Meeker. They met in a kitchen and drink coffee. Nobody else is present in the kitchen. How many person are there in the kitchen? What would you say? I think this: if you answer one, then I will tend to say that there is only one person in the multiverse, but it manifests itself in different overlapping contexts. If you answer two, then I will tend to say that there are an infinity of persons in the multiverse. What do you think? I think closed time-like loops are probably impossible. But your answer just points to possible equivocation on person. The time traveling Brent is a different person from the untraveled Brent because he has different memories just as the 70yr old Brent is a different person than the 10yr old Brent. But in another sense - causal continuity - they are the same person. It isn't necessary to introduce time travel to create this confusion of terms. But the first part of my question was about how a first person view is defined in this mathematical abstraction? What computations must my computer perform so that it has a first person view? Brent The person I was when I was 3 years old is dead. He died because too much new information was added to his brain. -- Saibal Mitra Note that in UDA, I use a definition of first person which identify a person with its personal memory, and so where many different persons can exist. But in AUDA, I use a more mathematical definition which eventually identify all persons. Then they can differentiate through a mixture of amnesia (they forget that they are the universal person), and personal memories (which they will use as self-identification means). Bruno http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=. -- You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=.
Re: The seven step series (november 2009)
On 10 Nov 2009, at 19:29, Brent Meeker wrote: But this seems like creating a problem where none existed. The factorial is a certain function, the brain performs a certain function. Now you say we will formalize the concept of function in order to study what the brain does and perhaps understand what is consciousness. But there is nothing that requires that you start over with all possible computations. That is like explaining the factorial function by considering all possible computations that produce it (like the above). It's not wrong, but it doesn't follow from saying that the factorial is a function. That's why I say I take it as an ansatz - Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them. Hmm... The seventh step comes after six other steps. I think you confuse UDA and Tegmark or Egan speculation on the mathematical nature of physics. But when we assume comp, the physical appearance cannot be describe by *any* computation a priori: it *has* to be retrieve from all computation. Roughly speaking, if we are universal machine, we do belong to an infinity of computation, and matter, or anything below our substitution level, has to be described by all computations. It is an open problem if that sum converge toward something we could describe by one computation. It is the whole point of the reasoning. It is theorem in the comp theory that matter emerges from all computations. From this you can prove that comp implies the non- cloning of any piece of matter, like it proves the existence of a strong form of indeterminacy, etc. Could you remind me what the phi_i are? The enumerated partial functions? The enumerated so called partial /computable/ functions. To get them, take your favorite universal system (fortran, lisp, c++, java, whatever), write down the grammatically correct description of function (of one argument, say, that is, from N to N). Put those codes in lexicographical order, and you get the corresponding phi_i: phi_1, phi_2, ..., and their domain W_1, W_2, W_3, ... With Church thesis, all the computable functions (having the domain N) will belong to that list, but there will be no algorithm capable of telling in advance for any phi_i if it compute partial computable function or a computable functions. Given that this is a key point for everything which will follow, I have to be sure that most people understand exactly why this has to be so. Ok, I think I understand. It's probably not relevant here, but physicist usually think of functions which can be computed approximately by a uniformly convergent algorithm as computable (e.g. compute pi) but I think in the above you mean computable in the Turing sense that the computation stops with the answer (e.g. compute pi to 100 decimal places). Right? Right. There is a vocabulary problem about what is a function, and unfortunately english speaker and french speaker have different conventions, and sometimes I slip from one to other, and this does not help. Usually a function from N to N is supposed to be defined on all element of N. And thus a computable function will have an algorithm which does stop on all of its input. But the Kleene diagonalization shows that there is no computable list of all computable functions, so if a language is universal, it means that the computable functions can only belong to a list of something else. That something else are called partial computable function: they are allowed to be not necessarily define on some natural number. So to get ALL functions, in some computable way, we have to take something larger: all partial functions, and to get all execution of all algorithm, we will have to dovetail, and from the first person point of view, there is an emerging continuum of computations, and it plays the role of the background roots of the physical laws, below our substitution level. The physical world is not just a mathematical space among mathematical spaces, it is really a sort of summary of the whole border of the whole set of mathematical spaces as seen by mean universal machines. That the laws of physics seems computable is a mystery now. I am just showing that the comp theory reduces the mind-body problem to a pure arithmetical (or combinatorial, ...) body problem. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series (november 2009)
Rex Allen wrote: On Tue, Nov 10, 2009 at 1:29 PM, Brent Meeker meeke...@dslextreme.com wrote: That's why I say I take it as an ansatz - Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them. I would think that it's pretty much a given that out of all possible computations, we surely will be able to find some way of representing physics, the brain, and the contents of conscious experience. But it's the picking out that's problem. That's the generic problem with the everything-theories. Sure the UD generates all possible strings and physics must be in there somewhere - so what. Tegmark hypothesizes all possible mathematical structures exist - so yeah physics must be in there too. If we can't find some way to symbolically/logically represent these things...what would that mean? Wouldn't it mean that we ourselves aren't capable of grasping them? So, I don't think I see the significance of success in this project...I would think that success in finding some logico-mathematical representation of physics IF you can *find* it among all the detritus. and the rest is the expected outcome, and that conclusive failure would be big news. So with computationalism, you can't see beneath the substitution level to the underlying processor substrate of what really exists. The conscious experience that results from the computation doesn't have to reveal anything about the nature of the computer...below the substitution level could be neurons, transistors, falling dominoes, dust clouds (a la Egan), numbers, platonic objects, alien matter existing in some alternate universe, Wang's Carpet (Egan again), ROCKS...basically anything capable of supporting computation...who knows? It would all look the same to us above the substitution level, right? If we were to go with Bruno's proposal, wouldn't it be because a substrate of platonically existing numbers seemed like a more plausible substrate than a contingently existing physical universe of matter and energy and laws which sprang from...nothing? Has existed eternally? What? Platonic existence seems like a very thin concept to me and it's not very plausible (to me) that it can provide the ontology of the universe. I see numbers part of the description. That the universe sprang from nothing is a going theory in cosmogony supported by the observation that whatever conserved quantities are evaluated, energy, momentum, charge, entropy,..., the total for the universe comes out zero. The philosophical difference that seems to divide people is that some are happy to accept that some things are contingent and others feel it better to hypothesize infinities in order to secure determinism. Brent --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series (november 2009)
Bruno Marchal wrote: On 10 Nov 2009, at 19:29, Brent Meeker wrote: But this seems like creating a problem where none existed. The factorial is a certain function, the brain performs a certain function. Now you say we will formalize the concept of function in order to study what the brain does and perhaps understand what is consciousness. But there is nothing that requires that you start over with all possible computations. That is like explaining the factorial function by considering all possible computations that produce it (like the above). It's not wrong, but it doesn't follow from saying that the factorial is a function. That's why I say I take it as an ansatz - Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them. Hmm... The seventh step comes after six other steps. I think you confuse UDA and Tegmark or Egan speculation on the mathematical nature of physics. But when we assume comp, But it seems there is a shift the meaning of assume comp here. We start with comp = Consciousness is something a brain does. A brain does a lot of things (metabolizes, takes up space,...) but the thing it does that produces consciousness is a kind of computation, i.e. information processing. Almost all scientists and philosophers think that is good hypothesis and one they would assume. But then it seems you use comp2 = We - our stream of consciousness - IS a computation that exists in the Platonic sense. This seems slightly different. the physical appearance cannot be describe by *any* computation a priori: But the main evidence for the comp hypothesis is that physics is so successfully described by computations. it *has* to be retrieve from all computation. Roughly speaking, if we are universal machine, But assuming we are a universal machine is assuming more than our brains do computations and that produces consciousness. we do belong to an infinity of computation, and matter, or anything below our substitution level, has to be described by all computations. It is an open problem if that sum converge toward something we could describe by one computation. If it is proven that it doesn't, would that refute comp2? Would we be left with no explanation of the perceived unity of individual consciousness? It is the whole point of the reasoning. It is theorem in the comp theory that matter emerges from all computations. From this you can prove that comp implies the non-cloning of any piece of matter, like it proves the existence of a strong form of indeterminacy, etc. What's the non-cloning proof? Could you remind me what the phi_i are? The enumerated partial functions? The enumerated so called partial /computable/ functions. To get them, take your favorite universal system (fortran, lisp, c++, java, whatever), write down the grammatically correct description of function (of one argument, say, that is, from N to N). Put those codes in lexicographical order, and you get the corresponding phi_i: phi_1, phi_2, ..., and their domain W_1, W_2, W_3, ... With Church thesis, all the computable functions (having the domain N) will belong to that list, but there will be no algorithm capable of telling in advance for any phi_i if it compute partial computable function or a computable functions. Given that this is a key point for everything which will follow, I have to be sure that most people understand exactly why this has to be so. Ok, I think I understand. It's probably not relevant here, but physicist usually think of functions which can be computed approximately by a uniformly convergent algorithm as computable (e.g. compute pi) but I think in the above you mean computable in the Turing sense that the computation stops with the answer (e.g. compute pi to 100 decimal places). Right? Right. There is a vocabulary problem about what is a function, and unfortunately english speaker and french speaker have different conventions, and sometimes I slip from one to other, and this does not help. Usually a function from N to N is supposed to be defined on all element of N. And thus a computable function will have an algorithm which does stop on all of its input. But the Kleene diagonalization shows that there is no computable list of all computable functions, so if a language is universal, it means that the computable functions can only belong to a list of something else. That something else are called partial computable function: they are allowed to be not necessarily define on some natural number. So to get ALL functions, in some computable way, we have to take something larger: all partial functions, and to get all execution of all algorithm, we will have to dovetail, Thanks, I did understand, but sometimes I need reassurance that I've grasped it. and from the first person point of view, there is an emerging continuum of computations,
Re: The seven step series (november 2009)
On 11 Nov 2009, at 19:52, Brent Meeker wrote: Bruno Marchal wrote: On 10 Nov 2009, at 19:29, Brent Meeker wrote: But this seems like creating a problem where none existed. The factorial is a certain function, the brain performs a certain function. Now you say we will formalize the concept of function in order to study what the brain does and perhaps understand what is consciousness. But there is nothing that requires that you start over with all possible computations. That is like explaining the factorial function by considering all possible computations that produce it (like the above). It's not wrong, but it doesn't follow from saying that the factorial is a function. That's why I say I take it as an ansatz - Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them. Hmm... The seventh step comes after six other steps. I think you confuse UDA and Tegmark or Egan speculation on the mathematical nature of physics. But when we assume comp, But it seems there is a shift the meaning of assume comp here. We start with comp = Consciousness is something a brain does. A brain does a lot of things (metabolizes, takes up space,...) but the thing it does that produces consciousness is a kind of computation, i.e. information processing. Almost all scientists and philosophers think that is good hypothesis and one they would assume. But then it seems you use comp2 = We - our stream of consciousness - IS a computation that exists in the Platonic sense. This seems slightly different. When some materialists, like some neuroscientists, assume the brain does computations at some high level, like with neuronal processing. I am not sure all are aware of the digitality assumption needed for making sense to the word computation. But if we assume the brain obeys to the physical laws, then we assume comp already, given that the physical laws are, as far as we know, Turing emulable. Comp is NOT the hypothesis that consciousness is something brain does. This is not even a precise definition of comp, given that strictly speaking we don't know what a brain is, nor what consciousness. But that's ok, because comp is very close to that, perhaps equivalent deending of what you mean by consciousness is something brain does. Comp is two things: yes doctor, which means: there is a level such that I survive (or feel nothing) when may brain is substitute for digital part made at that level. This does not use any neither a definition of brain, except it is something which can be described by some machine (but not necessarily the one in the skull), nor any idea of consciousness, above what we can ask to a doctor (will I make it Doc?). And then I believe you did understand the seventh step. In a concrete universe with a UD running in it (even materially), well, if my comp state is S, my future subjective experience is given by a sum on all computations going through S. So if the laws of physics still applies, they have to be recover from the mathematics of computations, which is a branch of math. In physics the notion does not admit definition which is different from the one by mathematicians. And quantum computation, actually a mathematical notion, is already close to the idea of sum on infinities of computations. After the seven step, you can still invoke, to save both comp and materialist, that we live in a universe which is too little for a universal dovetailing to be executed integrally or on some large portion. That is why there is an eight step, which shows that the universal machine (that we all provably are, even if comp is false) cannot, once comp is true, make the difference, for a short time on which bear the probabilities, distinguish between any implementations made below its substitution level, notably between physically implemented or arithmetically implemented. Step 8 shows that consciousness is not produced by the brain. Consciousness is produced by the arithmetical relation (or XYZ-ical relation with XXX being a first order specification of any universal system. In that case the move to a little universe can not work, and reality, or more aptly the realities (corresponding to each points of view) have to emerge from the XYZ-relations. I don't need any more platonic reality than I need to explain what is Church thesis, what is a universal machine or number, etc. No book of physics assume less. the physical appearance cannot be describe by *any* computation a priori: But the main evidence for the comp hypothesis is that physics is so successfully described by computations. Not necessarily. If you take Old QM (SWE + Collapse), the collapse of the wave, and its result, IS NOT the output of a computation. If you take the new QM, which assumes comp, the physical appearance is already described by
Re: The seven step series (november 2009)
Bruno Marchal wrote: On 09 Nov 2009, at 20:43, Brent Meeker wrote: Bruno Marchal wrote: Hi, Let us come back on the seven step thread. Let me recall the initial motivation. The movie graph argument (cf the MGA thread) shows that it is senseless to attach consciousness to the physical activity of a brain or a computer. If we keep the computational thesis for the cognitive process, we have to associate consciousness to the computation, and not to its physical realization. Actually we have to explain what is a physical realization from the existence of computations. But then we have to understand better what we mean by computation, in the mathematical sense, given that we cannot use any physics, at this stage. Luckily, the notion of computation has been discovered last century by mathematicians. They were motivated by the foundation of mathematics after the crisis of set theory. So what is a computation? Let us try some definitions. Attempt 1: A computation is a sequence of computational states. If we agree with this, it remains to define what is a computational states. But the definition above misses something important. I suspect everything can be recoded as a sequence of computational states, and this could be the reason why some are willing to say that rock and thinks like that are conscious. A physicist could say that what is lacking is a genuine causality relation which links the states from the sequence of computational states. But: - in the context of the MGA argument, this should be seen as a red herring - the notion of causality is extremely vague, even for a materialist. So: Attempt 2: A computation is a sequence of computational states obtained sequentially through the activity of some machine. This is actually a good definition, except that we have to define (without using physics) what we mean by activity, and machine. This may be problematic because we want to define activity by a sequence of state of some machine ... So: I don't think it's very good since it depends on the notion of computational states to define computation. It is not clear that any sequence of states cannot be computational states. It seems to me that we really take as primitive the concept of a function, something that is given some information and transforms it into some other information. That's what we think brains do - and they do a lot of it which is not conscious. When we have abstracted away what the information is about, we can regard it just as a string or number and apply the ideas of Turing, Church, et al to the transformation as a computation. But we have left behind the idea that the information was about something or represented something. In the context of a computation as a consciousness this representation is a relation between the information being transformed and the world of which one is conscious. So it seems you have ignored physics rather than explained it. However, I can accept it as an ansatz in hope that the explanation will emerge in the end. The problem which appears taking only the function is that a function can be computed in many different way. For example here is a way to compute the factorial function: BEGIN READ INPUT N SIMULATE BRENT MEEKER DRINKING COFFEE IF BRENT SAYS GOOD OUTPUT N*(N-1)* ... *1 IF BRENT SAYS BAD OUTPUT N*(N-1)* ... *1 IF BRENT SAYS NOTHING, AFTER AWHILE, OUTPUT N*(N-1)* ... *1 END That program will go through the right computational state corresponding to you drinking coffee, yet compute the same function that any more reasonable way to compute the factorial. It will be impossible to dismiss those computational states if we want a comp supervenience thesis. But this seems like creating a problem where none existed. The factorial is a certain function, the brain performs a certain function. Now you say we will formalize the concept of function in order to study what the brain does and perhaps understand what is consciousness. But there is nothing that requires that you start over with all possible computations. That is like explaining the factorial function by considering all possible computations that produce it (like the above). It's not wrong, but it doesn't follow from saying that the factorial is a function. That's why I say I take it as an ansatz - Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them. Attempt 3: a computation is a sequence of states such that it exists a machine going through that sequence of states when computed by ... Well, we cannot refer to activity or to a physical implementation, so what? Attempt 4 A computation is a sequence of states of some machine when executed by some Universal Machine. That is a progress, in case we succeed in defining executed by some universal machine, without using physics. But now we have the problem Does a
Re: The seven step series (november 2009)
On Tue, Nov 10, 2009 at 1:29 PM, Brent Meeker meeke...@dslextreme.com wrote: That's why I say I take it as an ansatz - Let's consider all possible computations and see if we can pick out physics and the brain and consciousness from them. I would think that it's pretty much a given that out of all possible computations, we surely will be able to find some way of representing physics, the brain, and the contents of conscious experience. If we can't find some way to symbolically/logically represent these things...what would that mean? Wouldn't it mean that we ourselves aren't capable of grasping them? So, I don't think I see the significance of success in this project...I would think that success in finding some logico-mathematical representation of physics and the rest is the expected outcome, and that conclusive failure would be big news. So with computationalism, you can't see beneath the substitution level to the underlying processor substrate of what really exists. The conscious experience that results from the computation doesn't have to reveal anything about the nature of the computer...below the substitution level could be neurons, transistors, falling dominoes, dust clouds (a la Egan), numbers, platonic objects, alien matter existing in some alternate universe, Wang's Carpet (Egan again), ROCKS...basically anything capable of supporting computation...who knows? It would all look the same to us above the substitution level, right? If we were to go with Bruno's proposal, wouldn't it be because a substrate of platonically existing numbers seemed like a more plausible substrate than a contingently existing physical universe of matter and energy and laws which sprang from...nothing? Has existed eternally? What? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series (november 2009)
Bruno Marchal wrote: Hi, Let us come back on the seven step thread. Let me recall the initial motivation. The movie graph argument (cf the MGA thread) shows that it is senseless to attach consciousness to the physical activity of a brain or a computer. If we keep the computational thesis for the cognitive process, we have to associate consciousness to the computation, and not to its physical realization. Actually we have to explain what is a physical realization from the existence of computations. But then we have to understand better what we mean by computation, in the mathematical sense, given that we cannot use any physics, at this stage. Luckily, the notion of computation has been discovered last century by mathematicians. They were motivated by the foundation of mathematics after the crisis of set theory. So what is a computation? Let us try some definitions. Attempt 1: A computation is a sequence of computational states. If we agree with this, it remains to define what is a computational states. But the definition above misses something important. I suspect everything can be recoded as a sequence of computational states, and this could be the reason why some are willing to say that rock and thinks like that are conscious. A physicist could say that what is lacking is a genuine causality relation which links the states from the sequence of computational states. But: - in the context of the MGA argument, this should be seen as a red herring - the notion of causality is extremely vague, even for a materialist. So: Attempt 2: A computation is a sequence of computational states obtained sequentially through the activity of some machine. This is actually a good definition, except that we have to define (without using physics) what we mean by activity, and machine. This may be problematic because we want to define activity by a sequence of state of some machine ... So: I don't think it's very good since it depends on the notion of computational states to define computation. It is not clear that any sequence of states cannot be computational states. It seems to me that we really take as primitive the concept of a function, something that is given some information and transforms it into some other information. That's what we think brains do - and they do a lot of it which is not conscious. When we have abstracted away what the information is about, we can regard it just as a string or number and apply the ideas of Turing, Church, et al to the transformation as a computation. But we have left behind the idea that the information was about something or represented something. In the context of a computation as a consciousness this representation is a relation between the information being transformed and the world of which one is conscious. So it seems you have ignored physics rather than explained it. However, I can accept it as an ansatz in hope that the explanation will emerge in the end. Attempt 3: a computation is a sequence of states such that it exists a machine going through that sequence of states when computed by ... Well, we cannot refer to activity or to a physical implementation, so what? Attempt 4 A computation is a sequence of states of some machine when executed by some Universal Machine. That is a progress, in case we succeed in defining executed by some universal machine, without using physics. But now we have the problem Does a universal machine exist? And what is the mathematical meaning of execution. But now, Church Thesis (Post, Church, Turing, Markov Thesis) is a strengthening of the following weaker thesis: It exists a universal machine. And, all those machines, for Post, Turing, were mathematical construction, right at the beginning. Church thesis is strictly speaking the statement that his formal (mathematical) system, known as Lambda Calculus, is universal with respect to computability. The basic entity there are the lambda expressions (those little cousins of the combinators, for those who remembers old threads). Turing thesis is that the language describing Turing machines is universal with respect of that same class, and soon it will be proved that they are equivalent indeed, making Church thesis equivalent to Turing thesis, (and equivalent to Post law). Then Turing proved the existence of the universal Turing Machine, and indeed, since we know now that for each such universal system for such system the understanding of the language can be encoded in the language itself. So there is a universal lambda expression. There is a universal Turing Machine. A universal Post production system, or a Fortran interpreter (or compiled) in Fortran, or a Lisp intepreter in Lisp. Some may ask which universal machine?. But the whole point of classical computationalism (and UDA) consists in showing that below your (our common) substitution
Re: The seven step series
And didn't Russell decide that this type of paradox should be outlawed from allowable statements within the practice of logic? m.a. - Original Message - From: m.a. To: everything-list@googlegroups.com Sent: Saturday, October 10, 2009 7:30 PM Subject: Re: The seven step series Or the barber is a special exception to the group designated as men and exists on a higher level of being. Therefore he can shave himself without transgressing the rule as stated in the premise. Isn't this one of Russell's paradoxes? marty a. - Original Message - From: John Mikes To: everything-list@googlegroups.com Sent: Saturday, October 10, 2009 3:47 PM Subject: Re: The seven step series Bruno, we had similar puzzles in middle school in the 30s. The barber could not shave himself because he shaved only those who did not shave themselves (and shaved all). So for (Q #1) in the 1st vriant she(?) was a female, unless he(?) was a beardless male (and the 'all' refers to only the bearded males requiring a shave). * Q#2 is beyond me, I do not resort to a QM-pattern like Schrodinger's cat. (Sh/H)e is either-or, not both. John M On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal marc...@ulb.ac.be wrote: Hi, I am so buzy that I have not the time to give long explanations, so I give here a short exercise and a subject of reflexion instead. Exercise: There is Tyrannic country where by law it was forbidden for any man to have a beard. And there is village, in that country, and it is said that there is a barber in that village, who shaves all and only the men who don't shave themselves. Two questions: 1) What is the gender of the barber? 2) What the hell has all this to do with diagonalization, ... and universal machine? Have a good day, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi John, hi Marty, On 10 Oct 2009, at 21:47, John Mikes wrote: Bruno, we had similar puzzles in middle school in the 30s. The barber could not shave himself because he shaved only those who did not shave themselves (and shaved all). So for (Q #1) in the 1st vriant she(?) was a female, unless he(?) was a beardless male You are right. The barber gender is female. I don't see why you add that he could be a beardless male. It is part of the problem that we are in a tyrannic country where no man can have a beard. (and the 'all' refers to only the bearded males requiring a shave). * Q#2 is beyond me, I do not resort to a QM-pattern like Schrodinger's cat. (Sh/H)e is either-or, not both. I am not sure I understand, except that Q#2 remains unanswered, OK. I will first comment Marty's posts. On 11 Oct 2009, at 01:30, m.a. wrote: Or the barber is a special exception to the group designated as men and exists on a higher level of being. Therefore he can shave himself without transgressing the rule as stated in the premise. Isn't this one of Russell's paradoxes? marty a. Well, if the barber is not human, there is indeed no problem. But here the fact that it can be a woman, and that usually a barber is a human being, and that the question refer to a gender strongly suggest that the solution the barber is a woman is more reasonable that the barber is an extraterrestrial. I think. And didn't Russell decide that this type of paradox should be outlawed from allowable statements within the practice of logic? m.a. Nice you see the relation with Russel's paradox. This is a very deep paradox which shows we have to handle the notion of sets with some care. Torgny Tholerus already mentionned this, and he defended the idea this is an argument for ultrafinitism, which in my opinion is like throwing the baby (the infinite sets) with the water of the bath. If we dare to consider that the collection of *all* sets is itself a set, we have a nice example of a set which contains itself as an element. This is not problematical in itself, and in some axiomatic set theories, some sets can belong to themselves. What becomes problematical is the idea of defining a set in intension by using *any* criteria. Indeed, let us call *universe*, U, the set of all sets. U belongs-to U. But {1, 2} does not belongs to {1, 2}, so some sets belong to themselves and some sets don't. So it looks like we could define a new set E of which contains all the sets which does not belongs to themselves. For example clearly the set {1, 2} is an element of E, and U is not an element of E. But then we are in trouble. Does E belongs to E? If E belongs to E, then he contradicts the definition of E, which contains only those set which does not belong to themselves. So E has to not belong to E. But then E does verify its own definition, so that he does belong to E. So E belongs to E and E does not belong to E. Damned. Well, this proves that the intuitive idea of set is inconsistent. We do have to make the notion more precise to avoid such kind of reasoning. All the many very different attempts to make the notion of set precise have lead toward interesting mathematics, philosophy and even religion (i think). But this would lead us far away of the topic. We will have opportunity to come back on this. With the most usual axiomatic set theories, the set of all sets is not a set, and the criteria to defined set in intension is usually weakened. So much that some axioms have to be added to get a reasonably rich theory. Question 2. 2) What the hell has all this to do with diagonalization, ... and universal machine? Let us write (x y) to say that some relation between x and y exists. In the problem, for example, (x y) means that x shaves y, and x and y are supposed to be humans. In Russel's paradox (x y) means that x belongs to y, that is X contains y as an element, and x and y are supposed to be sets. Argument by diagonalization always proceeds by using the diagonal twice. Which diagonal? 1) the first diagonal: Well (x y) is a couple, and so belongs to the cartesian product of the set (of those x, y) with itself. Put in another way, if you look at all (x y) you get a matrix of pair of things (humans in the problem, sets in the paradox). OK? Well, the (x x) will constituted the diagonal of that matrix. x is supposed to vary in their respective domain (the humans in the village, the set, in the universe of all sets. In the village, this gives something like (Sophie Sophie) (Claude Claude) (Arthur Arthur) etc. As long as there are inhabitants in the village. With the sets, the diagonal is any couple (x x) with x an arbitrary set. The barber, let us call it B, and the paradoxical set E from above are defined in a very similar way, said by diagonalization, because it involves the diagonal (x, x). The barber is
Re: The seven step series
Bruno, we had similar puzzles in middle school in the 30s. The barber could not shave himself because he shaved only those who did not shave themselves (and shaved all). So for (Q #1) in the 1st vriant *she(?)* was a female, unless *he(?)* was a beardless male (and the 'all' refers to only the *bearded* males requiring a shave). * Q#2 is beyond me, I do not resort to a QM-pattern like Schrodinger's cat. (Sh/H)e is either-or, not both. John M On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal marc...@ulb.ac.be wrote: Hi, I am so buzy that I have not the time to give long explanations, so I give here a short exercise and a subject of reflexion instead. Exercise: There is Tyrannic country where by law it was forbidden for any man to have a beard. And there is village, in that country, and it is said that there is a barber in that village, who shaves all and only the men who don't shave themselves. Two questions: 1) What is the gender of the barber? 2) What the hell has all this to do with diagonalization, ... and universal machine? Have a good day, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Or the barber is a special exception to the group designated as men and exists on a higher level of being. Therefore he can shave himself without transgressing the rule as stated in the premise. Isn't this one of Russell's paradoxes? marty a. - Original Message - From: John Mikes To: everything-list@googlegroups.com Sent: Saturday, October 10, 2009 3:47 PM Subject: Re: The seven step series Bruno, we had similar puzzles in middle school in the 30s. The barber could not shave himself because he shaved only those who did not shave themselves (and shaved all). So for (Q #1) in the 1st vriant she(?) was a female, unless he(?) was a beardless male (and the 'all' refers to only the bearded males requiring a shave). * Q#2 is beyond me, I do not resort to a QM-pattern like Schrodinger's cat. (Sh/H)e is either-or, not both. John M On Fri, Oct 9, 2009 at 12:00 PM, Bruno Marchal marc...@ulb.ac.be wrote: Hi, I am so buzy that I have not the time to give long explanations, so I give here a short exercise and a subject of reflexion instead. Exercise: There is Tyrannic country where by law it was forbidden for any man to have a beard. And there is village, in that country, and it is said that there is a barber in that village, who shaves all and only the men who don't shave themselves. Two questions: 1) What is the gender of the barber? 2) What the hell has all this to do with diagonalization, ... and universal machine? Have a good day, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi, I am so buzy that I have not the time to give long explanations, so I give here a short exercise and a subject of reflexion instead. Exercise: There is Tyrannic country where by law it was forbidden for any man to have a beard. And there is village, in that country, and it is said that there is a barber in that village, who shaves all and only the men who don't shave themselves. Two questions: 1) What is the gender of the barber? 2) What the hell has all this to do with diagonalization, ... and universal machine? Have a good day, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi, I sum up the definition and results seen so far. N = {0, 1, 2, ...}, the set of natural numbers (also called positive integers). N^N = {f such that f is a function from N to N} = the set of functions from N to N. Universal language: a language in which we can describe formally how to compute any intuitively computable functions. Weak Church thesis: there exists a universal language. Church thesis: lambda-calculus is universal. Turing thesis: the Turing machine specification language is universal Markov thesis: the Markov formalism is universal Post laws: production system is universal Beniov-Deutsch: quantum turing machine is universal etc. All such thesis have been proved equivalent. Instead of lambda calculus, turing machines, Markov systems or Post production rules, ... you can use your favorite programming language (ADA, FORTRAN, LISP, Prolog, C++, etc.). Thanks to Church thesis, I will not need to actually use any of those formal systems, and what we prove will be true for any of them. Actually I am using only the weak Church thesis. Computable = programmable in my favorite universal language (this definition use the (weak) Church thesis) N^N-comp = {f such that f is a computable function from N to N} N^N-comp+ = {f such that f is a computable function from a subset of N to N} = {f such that f is a partial computable function} Note that N is a particular subset of N; so a computable function (defined on the whole N) is a particular case of a partial function, so N^N-comp is included in N^N-comp+ Training exercise: try to reprove for your own benefit that: N^N is non enumerable N^N-comp is enumerable N^N-comp is non computably enumerable (the bijection exists but is not computable) N^N-comp+ is enumerable N^N-comp+ is computably enumerable (allowing repetition: different numbers can correspond to the same function). Bruno On 21 Sep 2009, at 19:47, Bruno Marchal wrote: On 18 Sep 2009, at 17:00, I wrote: On the set N^N of all functions from N to N, Cantor diagonal shows that N^N is non enumerable. On the set N-N-comp, the diagonal shows that N^N-comp, although enumerable is non computably enumerable. OK? take the time to swallow this, and ask question if this seems not clear. We are at the crux of the subject. Next anticipative exercise. If N^N-comp is not or non *computably* enumerable, so that we cannot enumerate mechanically, using some recipe, the f_n, is there still some hope to develop a *universal* machine, or a *universal* language, or a *universal* dovetailer? all capable of computing ALL computable function? How to escape the diagonal contradiction? We would appreciate that a universal could be able, given the nth program (identified by the number n), and the datum m, to compute f_n(n). Indeed that is how we will *define* universal machine. But if the machine cannot find mechanically the f_n, what can we do or hope for? What is the price of universality? Gödel's theorem has forced us to abandon the notion of universal provability (in the realm of the relations and functions on numbers), and this results mainly from the use of a diagonal argument 5Godel 1931). So when Church told him that he decided to define computable by the formal language of Lambda-calculus, Kleene thought this was impossible, and that he could by diagonalization refute that universality pretension. But 'overnight', after failing to diagonalize against lambda-calculus, he realize that Church *may* be correct, and he invented the vocable of Church thesis. CHURCH's (original) thesis: a function from N to N is computable if we can explain in lamdda-calculus how to compute it. What could be so special about Church language that it could define ALL computable functions from N to N, and yet be immune to the diagonal argument? OK. I have defined a computable function (from N to N) as being a function which can computed from a finite description in some language, and this makes them intuitively enumerable. The admittedly vague idea here, is that any set of finite things is either finite or enumerable. But of course, this is not entirely convincing, we could use a non enumerable set to multiply non enumerably finite beings, and a case could be made that if we allow a non enumerable set of languages, or a non enumerable set of beings understanding those languages, we could find for *any* functions, a language defining that function or a being computing that function, making all function computable, by some being, and this would make the notion of computability relative if not trivial. Let me do something which illustrates this in a non trivial way, though, but which relies on what I have already said about the ordinals some times ago. I will repeat the definition. I will write as if I was criticizing myself. The notion of computable function does not make sense, by the argument above. To
Re: The seven step series
On 18 Sep 2009, at 17:00, I wrote: On the set N^N of all functions from N to N, Cantor diagonal shows that N^N is non enumerable. On the set N-N-comp, the diagonal shows that N^N-comp, although enumerable is non computably enumerable. OK? take the time to swallow this, and ask question if this seems not clear. We are at the crux of the subject. Next anticipative exercise. If N^N-comp is not or non *computably* enumerable, so that we cannot enumerate mechanically, using some recipe, the f_n, is there still some hope to develop a *universal* machine, or a *universal* language, or a *universal* dovetailer? all capable of computing ALL computable function? How to escape the diagonal contradiction? We would appreciate that a universal could be able, given the nth program (identified by the number n), and the datum m, to compute f_n(n). Indeed that is how we will *define* universal machine. But if the machine cannot find mechanically the f_n, what can we do or hope for? What is the price of universality? Gödel's theorem has forced us to abandon the notion of universal provability (in the realm of the relations and functions on numbers), and this results mainly from the use of a diagonal argument 5Godel 1931). So when Church told him that he decided to define computable by the formal language of Lambda-calculus, Kleene thought this was impossible, and that he could by diagonalization refute that universality pretension. But 'overnight', after failing to diagonalize against lambda-calculus, he realize that Church *may* be correct, and he invented the vocable of Church thesis. CHURCH's (original) thesis: a function from N to N is computable if we can explain in lamdda-calculus how to compute it. What could be so special about Church language that it could define ALL computable functions from N to N, and yet be immune to the diagonal argument? OK. I have defined a computable function (from N to N) as being a function which can computed from a finite description in some language, and this makes them intuitively enumerable. The admittedly vague idea here, is that any set of finite things is either finite or enumerable. But of course, this is not entirely convincing, we could use a non enumerable set to multiply non enumerably finite beings, and a case could be made that if we allow a non enumerable set of languages, or a non enumerable set of beings understanding those languages, we could find for *any* functions, a language defining that function or a being computing that function, making all function computable, by some being, and this would make the notion of computability relative if not trivial. Let me do something which illustrates this in a non trivial way, though, but which relies on what I have already said about the ordinals some times ago. I will repeat the definition. I will write as if I was criticizing myself. The notion of computable function does not make sense, by the argument above. To define a notion of computability, you have to define first a fixed language L, in which the correct grammatical expressions will be definition of functions, that is will correspond to the description of how to compute those functions, on each of their arguments. In that case, the f_n are clearly *computably* enumerable. The bijection n - f_n has to be computable, then. But in that case, the g function, the one defined by g(n) = f_n(n) + 1, is clearly computable, and the Cantor-like diagonal argument just showed that that g is NOT *definable* in the language L. L cannot be universal. And given that the argument seems not to depend on which language L, it looks like we have proved that there is no universal language. After all I could build a new language now, by adding a primitive computing g to the L language. Diagonalizing again would provide a new function g2, which we can add as new primitive again, and so one, getting L, g, g2, g3, g4, ... I could even build a more powerful language by adding a primitive which computes all gi automatically, giving a new primitive, that I can add to L, so that this process can be extended into the constructive tranfinite (if you remember the post on the growing functions, and the ordinals). Could such a process converge toward a language computing all computable functions? That is, is there a universal language in which we can define all computable function? It will not converge for any effective, or constructive of computable ordinal, because if it does, we would get a computable bijection from N to N^N-comp. This we already know cannot exist, the diagonal leads to 0 = 1. Could it converge on non effective ordinals. Yes, and this can be used to make precise the idea that by liberalizing enough the notion of language we can define universal language. But using a non effective ordinal
Re: The seven step series
On 17 Sep 2009, at 18:17, John Mikes wrote: Dear Bruno, it is not very convincing when you dissect my sentences and interject assuring remarks on statements to come later in the sentence, negating such remarks in advance, on a different basis. I argued that - upon what you (and the rest of the multimillion mathematicians past and present) live with - the applied nomenclature is incomplete. It is not a counter-argument that it is used by many or for so many purposes. Of course it is in use, that was my point. I am not basing my position on opinions from within the argued position. (May the -2 level point to a 'total senselessness' of my opinion? I did not understand it, nor did I the (N + *) structure, which therefore I find irrelevant in the question what I raised. (I, not Rieman, Cantor, etc.). There is the idea of including 'quantities' in our worldview (excuse my naive reference, but you illustrated earlier 2 as II and 3 as III etc. and THIS in my mind means sort of a quantity) and such 'system' would be qualitatively infinite if we try to include quantities from all directions (math is the level of handling such quantities that 'came up' in the past - gradually - and we may expect more to come, new discoveries, extending the qualitative inventory) although in your words 'everything' can be expressed by (many many?) of your natural numbers (except square root 2?) - what is exactly my point. I did not want to open a scientific argument - I am no match for you, or any other 'mathematically educated' person. I scribbled a 'qualitative' idea of thinking in 'wider' terms than the defined 'natural numbers' in a worldview of a (qualitative) totality - what I pursue, but do not understand in my sci.fic agnosticism. I am sorry if I bored you with my remark. I apologize if I gave that impression, but I try sometimes to be not too much long in the mails, and being short can have given that impression. Sorry. My point was just that there is a sense where natural numbers are not enough in math, and that is why mathematicians have extended the set N. N, then Z, then Q, then R, then the complex numbers, then the quaternions, octonions, etc. But, once we assume comp, N is ontologically enough, all other sort of numbers do necessarily appear as unavoidable epistemological constructions, if only to understand the (additive-multiplicative) behavior of the natural numbers, a bit like Riemann use complex numbers to provide information on the prime (natural) numbers. Without digging a bit more on the technical issue, I can hardly say more than my usual: there is only natural number, together with the additive and multiplicative law. This, assuming comp, already defines a matrix of number's dreams, and those cannot avoid the internal phenomenological appearance of richer structures, like the other numbers, and indeed like the whole physical appearances. Does this help you a little bit? Best, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Yes, Bruno, it helps - however: I did not want to put you into any apology! The list is a free communication among free spirits and controversy is part of it. What I 'read' in your reply still sticks within 'math' and my principal point is: the image represented is STILL what a human mind MAY think, irrespective of 'machines' above it - as well humanly thought out. Of course smart mathematicians came up with ideas similar to what I thought and produced 'remedies' to cover the uncovered. Math extends as we go. *...But, once we assume comp, N is ontologically enough, all other sort of numbers do necessarily appear as unavoidable epistemological constructions,...* I am not for the *'ontological'* because that is based on whatever we KNOW and I prefer the '*epistemological' (*in spe acquirable) totality. Extending *yesterday's* ontology into *tomorrow's* by epistemic enrichment . We cannot override the capabilities of our 'mind', restricted by the brain- tissue - function and bordered by our 'existence'. And - I condone it happily: the best we can do is math-ways (not mathematics) with all freedom within. WITHIN is the word. I represent in my thinking the humbleness of being restricted. I call it my scientific agnosticism - *allowing* things beyond our limitations. This is why I don't use truth or even everything. And I use common sense. (Mine - that is G) So far you always pronounced the (infinite?) series of NATURAL numbers and I jumped on a number-wise defined item that was outside of them. Sorry, when it comes to speculation, I am jumpy. I did not know about those non-natural naturals. Have a good day John On Fri, Sep 18, 2009 at 3:23 AM, Bruno Marchal marc...@ulb.ac.be wrote: On 17 Sep 2009, at 18:17, John Mikes wrote: Dear Bruno, it is not very convincing when you dissect my sentences and interject assuring remarks on statements to come later in the sentence, negating such remarks in advance, on a different basis. I argued that - upon what you (and the rest of the multimillion mathematicians past and present) live with - the applied nomenclature is incomplete. It is not a counter-argument that it is used by many or for so many purposes. Of course it is in use, that was my point. I am not basing my position on opinions from within the argued position. (May the -2 level point to a 'total senselessness' of my opinion? I did not understand it, nor did I the (N + *) structure, which therefore I find irrelevant in the question what I raised. (I, not Rieman, Cantor, etc.). There is the idea of including 'quantities' in our worldview (excuse my naive reference, but you illustrated earlier 2 as II and 3 as III etc. and THIS in my mind means sort of a quantity) and such 'system' would be qualitatively infinite if we try to include quantities from all directions (math is the level of handling such quantities that 'came up' in the past - gradually - and we may expect more to come, new discoveries, extending the qualitative inventory) although in your words 'everything' can be expressed by (many many?) of your natural numbers (except square root 2?) - what is exactly my point. I did not want to open a scientific argument - I am no match for you, or any other 'mathematically educated' person. I scribbled a 'qualitative' idea of thinking in 'wider' terms than the defined 'natural numbers' in a worldview of a (qualitative) totality - what I pursue, but do not understand in my sci.fic agnosticism. I am sorry if I bored you with my remark. I apologize if I gave that impression, but I try sometimes to be not too much long in the mails, and being short can have given that impression. Sorry. My point was just that there is a sense where natural numbers are not enough in math, and that is why mathematicians have extended the set N. N, then Z, then Q, then R, then the complex numbers, then the quaternions, octonions, etc. But, once we assume comp, N is ontologically enough, all other sort of numbers do necessarily appear as unavoidable epistemological constructions, if only to understand the (additive-multiplicative) behavior of the natural numbers, a bit like Riemann use complex numbers to provide information on the prime (natural) numbers. Without digging a bit more on the technical issue, I can hardly say more than my usual: there is only natural number, together with the additive and multiplicative law. This, assuming comp, already defines a matrix of number's dreams, and those cannot avoid the internal phenomenological appearance of richer structures, like the other numbers, and indeed like the whole physical appearances. Does this help you a little bit? Best, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to
Re: The seven step series
I give the answer. On 17 Sep 2009, at 16:27, Bruno Marchal wrote: On 16 Sep 2009, at 18:12, Bruno Marchal wrote: If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion. We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N. We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N. The question is: is there a bijection from N to N^N-comp ? This is a tricky question. I give you an argument that there is a bijection between N and N^N- comp. Followed by an argument that there is no bijection between N and N^N-comp. Which one is wrong? 1) A proof that N^N-comp is enumerable. I said that a function from N to N, is computable (and thus in N^N- comp), if there is a recipe explaining how to compute it. But this means that there has to be a language in which we can describe or encode that explanation. A language is a set of finite expressions build from some finite alphabet. But we have seen that the set of finite expressions build on an alphabet (which is always a finite set) is enumerable. Those expressions, corresponding to the explanation describing the recipe for a computable function, will constitute a subset of the set of all expressions, and is thus enumerable. So N^N-comp is enumerable. That is correct. N^N-comp is enumerable. 2) A proof that N^N-comp is NOT enumerable. Suppose N^N-comp is enumerable, and let f_n be such an enumeration, with n in {0, 1, 2, ...}. Consider the diagonal function g defined by g(n) = f_n(n) + 1. All f_n are computable, and surely + 1 is computable, so g is a computable function. That is wrong. It is true that all the f_n are computable, and that + 1 is computable. But to compute g on n I have to find f_n, and although all f_n are computable, the bijection itself which send n to f_n cannot be computable. Why? Well if it is, given that by the reasoning above shows correctly that N^N-comp is enumerable, what follows would lead to 0 = 1. But then g has to belong to f_n, which enumerates the computable functions. So there is a k such that g = f_k. But then g(k) = f_k(k) = f_k(k) + 1. But f_k is a computable function from N to N, so f_k(k) is a number, which I can subtract on both side, so 0 = 1. So N^N^comp is not enumerable. Well, there is a problem, isn't it? N^N-comp cannot be both enumerable and non enumerable. So one of those proofs has to be wrong. Which one? So it was the second proof which was wrong. We have implicitly assumed that the enumeration f_n was a computable enumeration. The reasoning above in 1) has show that there is a bijection between N and N^N-comp, and not that such an enumeration could be done by a *computable* bijection between N and N^N. We say that the f_n are, although enumerable, not computably enumerable. On the set N^N of all functions from N to N, Cantor diagonal shows that N^N is non enumerable. On the set N-N-comp, the diagonal shows that N^N-comp, although enumerable is non computably enumerable. OK? take the time to swallow this, and ask question if this seems not clear. We are at the crux of the subject. Next anticipative exercise. If N^N-comp is not or non *computably* enumerable, so that we cannot enumerate mechanically, using some recipe, the f_n, is there still some hope to develop a *universal* machine, or a *universal* language, or a *universal* dovetailer? all capable of computing ALL computable function? How to escape the diagonal contradiction? We would appreciate that a universal could be able, given the nth program (identified by the number n), and the datum m, to compute f_n(n). Indeed that is how we will *define* universal machine. But if the machine cannot find mechanically the f_n, what can we do or hope for? What is the price of universality? Gödel's theorem has forced us to abandon the notion
Re: The seven step series
Bruno, I loved your post on the square root of 2! (I also laughed at it, to stay at the puns). You went out of your way and did not save efforts to prove how inadequate and wrong (y)our number system is. (ha ha). Statement: *if square-rooting is right* (allegedly, and admittedly) *then THERE IS such a 'quantity'* (call it number and by this definition it must be natural) *we consider as the square root of '2'*. You gave the plastic elemenary rule, how to get to it. Thankyou. Accepted. I believe the '1' and the sophistication of Pythagoras. *(provided that * * 1^2 = 1 which is also 'funny') a n d :* If it is not part of your series *of* - what you call: - *natural numbers*, then *YOUR* series is wrong. We need another system (if we really need it). Your math pupil John, the 'commonsenser'. On Wed, Sep 9, 2009 at 3:21 AM, Bruno Marchal marc...@ulb.ac.be wrote: This is the last post before we proof Cantor theorem. It is an antic interlude. We are about 2000 years back in time. *The square root of 2.* It is a number x such that x^2 = 2. It is obviously smaller than 2 and bigger than 1. OK? It cannot be a natural number. But could it be a fraction? The square root of two is the length of the diagonal of a square with side one unity. Do you see that? I can't draw, so you have to imagine a square. You may draw it. And then draw or imagine the square which sides the diagonal (of you square unity). Draw it with its diagonals and you will see, in your mind or on the paper that the second square is made of four times the half of your square unity: meaning that the square which sides the diagonal has an area twice the area of the square unity. But this means that if you call d the length of the diagonal of the square unity, you have, by the law of the area of square, d^2 = 2. OK? So the length of the diagonal d = square root of 2. It is a 'natural' length occurring in geometry (and quantum mechanics!). The function or operation taking the square root of two is the inverse operation of taking the square. (In term of the couples defining the function as set, it means that if (x, y) belongs-to taking the square root of two then (y, x) belongs-to taking the square of). Now, please continue to imagine the diagonal, and try to evaluate its length. Is is not clearly less than two unities, and clearly more than one? Is it 3/2 i.e. 1.5? Well, 1.5 should give two when squared, but (1.5)^2 = 2,25. That's too much! Is 1,4? Oh, 1.4 gives 1.96, not too bad, it is slightly more, may be 1.41? 1.41^2 gives 1,9881, we get closer and closer, but will such a search ends up with the best approximation? This would mean we can divide the side of the square unity in a finite number of smaller unities, and find a sufficiently little unity which could measure the diagonal exactly. It would mean d is equal to p * 1/q, where q is the number of divisions of the side of the square unity. If we find such a fraction the diagonal and the sided would be said commensurable. Is there such a fraction? It is not 3/2, we know already. Is it 17/12 (= 1,4166...)? (1712)^2 = 2,006944). Close but wrong. Is it 99/70? (= 1,414285714...) (99/70)^2 = 2,000204082...). Very close, but still wrong! ... is it 12477253282759/8822750406821 ? My pocket computer says that the square of that fraction is 2. Ah, but this is due to its incompetence in handling too big numbers and too little numbers! It is still wrong! How could we know if that search will end, or not end? Sometimes, we can know thing in advance. Why, because things obeys laws, apparently. Which laws of numbers makes the problem decidable? Here is one: - a number is even if and only if the square of that number is even, similarly - a number is odd if and only if the square of that number is odd. Taking the square of an integer leaves invariant the parity (even/odd) of the number. Why? suppose n is odd. There will exist a k (belonging to {0, 1, 2, 3, ...} such that n = 2k+1. OK? So n^2 = (2k+1)^2 = 4k^2 + 4k + 1, OK? and this is odd. OK. And this is enough to show that if n^2 is even, then n is even. OK? And why does this answer the question. Let us reason 'by absurdo. Suppose that there are number p and q such (p/q)^2 = 2. And let us suppose we have already use the Euclid algorithm to reduce that fraction; so that p and q have no common factor. p^2 / q^2 = 2. OK? Then p^2 = 2q^2 (our 'Diophantine equation). OK? Then p^2 is even. OK? (because it is equal to 2 * an integer). Then p is even. OK? (by the law above). This means p is equal to some 2*k (definition of even number). OK? But p^2 = 2q^2 (see above), and substituting p by 2k, we get 4k^2 = 2q^2, and thus, dividing both sides by 2, we get that 2k^2 = q^2. So q^2 is even. OK? So q is even. (again by the law above). OK? So both p and q are even, but this means they have a common factor (indeed, 2), and this is absurd, given that the
Re: The seven step series
Hi John, On 17 Sep 2009, at 15:14, John Mikes wrote: You went out of your way and did not save efforts to prove how inadequate and wrong (y)our number system is. (ha ha). Wrong ? Statement: if square-rooting is right (allegedly, and admittedly) Well, it is certainly right if we want that to measure by a number length of the diagonal of the square unity. then THERE IS such a 'quantity' (call it number and by this definition it must be natural) It cannot be natural number. It has to be strictly bigger than 1, and strictly bigger than 2. But there was some hope that it could be the ratio of two natural number, so that it can live in arithmetic with addition and multiplication. we consider as the square root of '2'. You gave the plastic elemenary rule, how to get to it. Thankyou. Accepted. I believe the '1' and the sophistication of Pythagoras. (provided that 1^2 = 1 which is also 'funny') a n d : If it is not part of your series of - what you call: - natural numbers, then YOUR series is wrong. You could as well told something like My cave is at the level -2 (minus two) of the building ... We need another system (if we really need it). That is why N (the set of natiral numbers, alias positive integers) has been extended into Z, all the integers, itself included in Q (he ratio). The my point was that Q was still not enough to define the length of the diagonal, we need the real numbers, which are more difficult to define in the structure (N, +, *). From a logical point of view, N, Z, and Q are roughly equivalent. The real numbers are not, most are not definable in the structure N. yet, and we will see this (probably), most real numbers that we encounter in math and physics can still be defined in the structure (N,+,*). It is an open problem in math and physics if there is anything we cannot define in (N,+,*), and indeed it is an indirect consequence of COMP that we can. This probably why formal set theory is studied only by logicians. Of course Riemann and number theorists, and knot theorists, are used to escape from the (N, +, *) structure all the time, and that is why we use analysis (based on the real numbers). But we have not yet find a theorem which *needs* to escape the structure (N, +, *), except those found by logicians to just provide examples. In the mechanical theory of mind, we have to escape the structure (N, +, *). Indeed the first person notion needs even more than Cantor paradise, from its point of view, and that is why and how the epistemology of comp is necessarily far bigger than its ontology. I may come back on this, but it asks for more model theory and logic to address the question technically. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 16 Sep 2009, at 18:12, Bruno Marchal wrote: If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion. We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N. We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N. The question is: is there a bijection from N to N^N-comp ? This is a tricky question. I give you an argument that there is a bijection between N and N^N- comp. Followed by an argument that there is no bijection between N and N^N-comp. Which one is wrong? 1) A proof that N^N-comp is enumerable. I said that a function from N to N, is computable (and thus in N^N- comp), if there is a recipe explaining how to compute it. But this means that there has to be a language in which we can describe or encode that explanation. A language is a set of finite expressions build from some finite alphabet. But we have seen that the set of finite expressions build on an alphabet (which is always a finite set) is enumerable. Those expressions, corresponding to the explanation describing the recipe for a computable function, will constitute a subset of the set of all expressions, and is thus enumerable. So N^N-comp is enumerable. 2) A proof that N^N-comp is NOT enumerable. Suppose N^N-comp is enumerable, and let f_n be such an enumeration, with n in {0, 1, 2, ...}. Consider the diagonal function g defined by g(n) = f_n(n) + 1. All f_n are computable, and surely + 1 is computable, so g is a computable function. But then g has to belong to f_n, which enumerates the computable functions. So there is a k such that g = f_k. But then g(k) = f_k(k) = f_k(k) + 1. But f_k is a computable function from N to N, so f_k(k) is a number, which I can subtract on both side, so 0 = 1. So N^N^comp is not enumerable. Well, there is a problem, isn't it? N^N-comp cannot be both enumerable and non enumerable. So one of those proofs has to be wrong. Which one? Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Dear Bruno, it is not very convincing when you dissect my sentences and interject assuring remarks on statements to come later in the sentence, negating such remarks in advance, on a different basis. I argued that - upon what you (and the rest of the multimillion mathematicians past and present) live with - *the applied nomenclature is incomplete*. It is not a counter-argument that it is used by many or for so many purposes. Of course it is in use, that was my point. I am not basing my position on opinions from within the argued position. (May the -2 level point to a 'total senselessness' of my opinion? I did not understand it, nor did I the (N + *) structure, which therefore I find irrelevant in the question what I raised. (I, not Rieman, Cantor, etc.). There is the idea of including 'quantities' in our worldview (excuse my naive reference, but you illustrated earlier 2 as II and 3 as III etc. and THIS in my mind means sort of a quantity) and such 'system' would be qualitatively infinite if we try to include quantities from all directions (math is the level of handling such quantities that 'came up' in the past - gradually - and we may expect more to come, new discoveries, extending the qualitative inventory) although in your words 'everything' can be expressed by (many many?) of * your* natural numbers (except square root 2?) - what is exactly my point. I did not want to open a scientific argument - I am no match for you, or any other 'mathematically educated' person. I scribbled a 'qualitative' idea of thinking in 'wider' terms than the *defined* 'natural numbers' in a worldview of a (qualitative) totality - what I pursue, but do not understand in my sci.fic agnosticism. I am sorry if I bored you with my remark. John M On Thu, Sep 17, 2009 at 10:01 AM, Bruno Marchal marc...@ulb.ac.be wrote: Hi John, On 17 Sep 2009, at 15:14, John Mikes wrote: You went out of your way and did not save efforts to prove how inadequate and wrong (y)our number system is. (ha ha). Wrong ? Statement: *if square-rooting is right* (allegedly, and admittedly) Well, it is certainly right if we want that to measure by a number length of the diagonal of the square unity. *then THERE IS such a 'quantity'* (call it number and by this definition it must be natural) It cannot be natural number. It has to be strictly bigger than 1, and strictly bigger than 2. But there was some hope that it could be the ratio of two natural number, so that it can live in arithmetic with addition and multiplication. *we consider as the square root of '2'*. You gave the plastic elemenary rule, how to get to it. Thankyou. Accepted. I believe the '1' and the sophistication of Pythagoras. *(provided that * * 1^2 = 1 which is also 'funny') a n d :* If it is not part of your series *of* - what you call: - *natural numbers*, then *YOUR* series is wrong. You could as well told something like My cave is at the level -2 (minus two) of the building ... We need another system (if we really need it). That is why N (the set of natiral numbers, alias positive integers) has been extended into Z, all the integers, itself included in Q (he ratio). The my point was that Q was still not enough to define the length of the diagonal, we need the real numbers, which are more difficult to define in the structure (N, +, *). From a logical point of view, N, Z, and Q are roughly equivalent. The real numbers are not, most are not definable in the structure N. yet, and we will see this (probably), most real numbers that we encounter in math and physics can still be defined in the structure (N,+,*). It is an open problem in math and physics if there is anything we cannot define in (N,+,*), and indeed it is an indirect consequence of COMP that we can. This probably why formal set theory is studied only by logicians. Of course Riemann and number theorists, and knot theorists, are used to escape from the (N, +, *) structure all the time, and that is why we use analysis (based on the real numbers). But we have not yet find a theorem which *needs* to escape the structure (N, +, *), except those found by logicians to just provide examples. In the mechanical theory of mind, we have to escape the structure (N, +, *). Indeed the first person notion needs even more than Cantor paradise, from its point of view, and that is why and how the epistemology of comp is necessarily far bigger than its ontology. I may come back on this, but it asks for more model theory and logic to address the question technically. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this
Re: The seven step series
I give the solution. On 15 Sep 2009, at 16:30, Bruno Marchal wrote: OK? Take your time to compare with the last post, and to understand what happens. Training exercise: prove, using that notation, that 2^N is non enumerable. Hint: use a slightly different g. 2^N is non enumerable. 2^N is the set of functions from N to {0, 1}, and I will again note or identify a function from N to {0, 1} with an infinite sequence of 1 and 0. For example, the function {(0, 0), (1, 1), (2, 0), (3, 1), (4, 0), (5, 1), ...} is identified with the sequence 010101010... OK? I reason by absurdum,... again with the two notations. Suppose that 2^N *is* enumerable, then there is a bijection from N to 2^N, which is something like 0 000110100111011010011100 ... 1 110110010010... 2 0100... 3 101010101010101010101000... 4 11100010... 5 11001110100101001100... 6 ... 7 11100011100011100011... 8 11101101... 9 0001... ... If the bijection exists, all the 1 and 0 are well defined in the infinite diagram, and the diagonal sequence is well defined too. So the diagonal sequence, made up from the diagonal sequence where all 0 are changed into 1 and vice versa, is well defined too. It is 1011001...(print it, and use a rule to verify!) OK? Suc a sequence cannot appears in the enumeration. Indeed, if it appears in the diagram, it appears at some line, let us say the kth line. But at the intersection of the diagonal and the kth line, there will be a problem. By the construction of the diagonal, the kth element of the kth sequence has to be simultaneously equal to 0 and 1. Contradiction. OK? So 2^N is non enumerable. OK? I do the proof with the usual notation: Suppose f_n is an enumeration of the functions from N to {0, 1}. Let g be the function which send n on 1 - f_n(n). g is a function from N to 2 (because both 1 - 1, and 1 - 0 gives 0 or 1). We write g(n) = 1 - f_n(n). g is a function from N to 2, yet cannot belong to the enumeration f_i. Why? Suppose g is in the enumeration f_n. It means there is a number k such that g = f_k. Thus for all n, g(n) = f_k(n). In particular g(k) = f_k(k). But by definition, for all n g(n) = 1 - f_n(n). In particular g(k) = 1 - f_k(k). So we have that g(k) is equal to both f_k(k) and 1 - f_k(k). And f_k is a function from N to {0, 1}, so we get either 0 = 1 (if f_k(k) = 0), and 1 = 0 if f_k(k) = 1. Contradiction. We can say it is the same proof than the proof that N^N is non enumerable. The only change is in the diagonal function g. Yesterday it was g(n) = f_n(n) + 1, and today it is g(n) = 1 - f_n(n). This comes from the fact that we want g to belong to N^N and 2^N respectively. OK? * If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion. We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N. We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N. The question is: is there a bijection from N to N^N-comp ? Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi, I will introduce notation for functions, and prove again Cantor theorem, without making any diagram. I will lazily write the diagram 0 = 34, 6, 678, 0, 6, 77, 8, 9, 39, 67009, ... 1 = 0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ... 2 = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... 3 = 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... 4 = 1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ... 5 = 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ... ... in the following way 0 = f_0 1 = f_1 2 = f_2 3 = f_3 4 = f_4 5 = f_5 Here the label f_1 plays the role of a name for the function {(0, 34), (1, 6), (2, 678), (3, 0), ...}. Indeed it plays the role of the name of the function which is the image by the bijection, which we were supposing the existence. To say that f_1 send 0 to 34, or 1 to 6, ... is usually written by either f_0: 0 -- 34, f_0 : 1 -- 6, ... or by f_0(0) = 34, f_0(1) = 6, ... More generally if f is a name for a function, to say that (x, y) belongs to f, we write very often f(x) = y, or y = f(x). For example we say that factorial(5) = 120. Now, because I am even more lazy, instead of writing 0 = f_0 1 = f_1 2 = f_2 3 = f_3 4 = f_4 5 = f_5 I will write: i = f_i which is much shorter. I could even write just f_i. the index i is supposed to vary from 0 to infinity (excluded). I mean that i belongs to {0, 1, 2, ...}, or just that it is natural number. So with that notation, I could begin the proof by saying this: Let us assume that there is a bijection B: i == f_i between N and N^N. OK? This is the absurd hypothesis, that is the one we want to show leading to a contradiction. I call that bijection B to fix the idea. Now the proof continues. Let us consider the function from N to N which is defined by g(n) = f_n(n) + 1. Do you recognize g? if n varies from 0 to infinity, with the f_i given by the diagram above, f_n(n) describes the diagonal 34 677 4, 2, 6, 0, ... And f_n(n) + 1, which is g(n), describes 35 678, 5, 3, 7, 1, ... It is the function which is supposed not be in the range of the supposed bijection. Not only this can satisfy my lazy mood, but more importantly, it is easier to show now more clearly the contradiction. Indeed, suppose that g is in the range of the bijection. This means there is some number k which is send on g by the bijection. This means that there is some k such that g is equal to f_k. OK? But if g = f_k, it follows that g(n) = f_k(n) for any n. Right? But then if g is applied to k, its own image under the bijection, we have that g(k) = f_k(k). But by definition of g, g(n) = f_n(n) + 1. So g(k) = f_k(k) + 1. It follows that f_k(k) = f_(k) + 1. OK? This follows by the Leibniz rule (two quantities equal to a third one are equal with each other), applied on the two preceding line. Now, each f_i is a function from N to N, so each f_i(n) are well defined number (if the bijection exists), so we can substract f_(k) on both side of the equality f_k(k) = f_(k) + 1, so we get 0 = 1. Contradiction. Such a bijection cannot exist. Again, this makes N^N non enumerable. If you consider an enumeration (bijection from N to a set) f_i, it will means its corresponding diagonal g function. OK? Take your time to compare with the last post, and to understand what happens. Training exercise: prove, using that notation, that 2^N is non enumerable. Hint: use a slightly different g. Bruno - On 14 Sep 2009, at 16:40, Bruno Marchal wrote: On 09 Sep 2009, at 09:21, Bruno Marchal wrote: Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets. After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc. CANTOR'S FIRST RESULT There is NO bijection between N and N^N (N^N is the set of functions from N to N. N = (0, 1, 2, ...} Proof 1) preliminaries Like for the irrationality of the square root of 2, we will proceed by a reduction to an absurdity. First note that there are many obvious injection (= one-one function) from N to N^N. For example the function which sends the number n on the constant function from N to N which send all numbers to n: 0 == {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0) } 1 == {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) } 2 == {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) } 3 ... ... Such correspondence is one-one: two different numbers are send to two different functions from N to N. OK? With Cantor, inspired by what
Re: The seven step series
On 09 Sep 2009, at 09:21, Bruno Marchal wrote: Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets. After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc. CANTOR'S FIRST RESULT There is NO bijection between N and N^N (N^N is the set of functions from N to N. N = (0, 1, 2, ...} Proof 1) preliminaries Like for the irrationality of the square root of 2, we will proceed by a reduction to an absurdity. First note that there are many obvious injection (= one-one function) from N to N^N. For example the function which sends the number n on the constant function from N to N which send all numbers to n: 0 == {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0) } 1 == {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) } 2 == {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) } 3 ... ... Such correspondence is one-one: two different numbers are send to two different functions from N to N. OK? With Cantor, inspired by what happens in the case of finite sets, I will say that the cardinal of A is little or equal (≤) than the cardinal of B, when A and B are infinite sets, when there is a one-one function, also called injection, from A to B. The injection described in the diagram above shows that the cardinal of N is little or equal than the cardinal of N^N. I will say that the cardinal of A is equal to the cardinal of B when there is a bijection between the two sets. I will also use the canonical bijection between the set of functions from N to N and the set of infinite sequences of numbers, to write any function from N to N, as a sequence of numbers. This will make the things more readable. The diagram above becomes: 0 == 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 1 == 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 2 == 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... etc. OK? We can do that because we have all in mind the canonical order of the natural numbers: 0, 1, 2, 3, so that the sequence of numbers can be seen a short way to describe a function from N to N. 2) the proof Let us do the Cantor's reduction to the absurd. Suppose there is a bijection from N to N^N. It will have some shape like: 0 = 34, 6, 678, 0, 6, 77, 8, 9, 39, 67009, ... 1 = 0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ... 2 = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... 3 = 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... 4 = 1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ... 5 = 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ... ... May be you recognize some functions in the correspondence. The first two functions seems arbitrary. The third one seems to be the power of two, the fourth one is the constant function sending all numbers on 2, the fifth one seems to be the factorial functions, the sixth one seems to be an arbitrary function from N to {0, 1}. From such finite set of data we can never be sure, given that the ... could in this context mean practically anything. BUT, if there is a bijection between N and N^N, the correspondence is well defined, at least in Platonia, or in the mind of God. This means that each line must be thought as representing *some*, perhaps unknown, precise function. In particular, all numbers, including the double infinity of numbers that we have not represented, are well defined, perhaps unknown by us, numbers. But then, Cantor reasons, if the whole diagram above makes some sense, it is easy to conceive a NEW function, which can be shown not belonging to the diagram. That is there will be a function from N to N which is not represented at any line of the above diagram. Indeed the following sequence will play that role: 35, 678, 5, 3, 7, 1, ... Do you see where it comes from? It comes from the diagonal elements, from up-left to down-right, with one added to them: 34+1, 677+1, 4+1, 2+1, 6+1, 0+1, ... Why does such sequence not belong to the diagram? Because it differs from the first sequence for the first output. Indeed the first output at the first line is 34, and the new function outputs 35. It differs from the second sequence at the second outputs. Indeed the second output of the second sequence is 677, and the second output of the new sequence is 678, etc. So, by construction, the new function differs from all the sequence in the list above. We proceed diagonally to be sure that by changing a function, we don't come back on some distinction already introduced. All the function being well defined, in Platonia, or in God's eyes (or in the eye of some omniscient being),
Re: The seven step series
This is the last post before we proof Cantor theorem. It is an antic interlude. We are about 2000 years back in time. The square root of 2. It is a number x such that x^2 = 2. It is obviously smaller than 2 and bigger than 1. OK? It cannot be a natural number. But could it be a fraction? The square root of two is the length of the diagonal of a square with side one unity. Do you see that? I can't draw, so you have to imagine a square. You may draw it. And then draw or imagine the square which sides the diagonal (of you square unity). Draw it with its diagonals and you will see, in your mind or on the paper that the second square is made of four times the half of your square unity: meaning that the square which sides the diagonal has an area twice the area of the square unity. But this means that if you call d the length of the diagonal of the square unity, you have, by the law of the area of square, d^2 = 2. OK? So the length of the diagonal d = square root of 2. It is a 'natural' length occurring in geometry (and quantum mechanics!). The function or operation taking the square root of two is the inverse operation of taking the square. (In term of the couples defining the function as set, it means that if (x, y) belongs-to taking the square root of two then (y, x) belongs- to taking the square of). Now, please continue to imagine the diagonal, and try to evaluate its length. Is is not clearly less than two unities, and clearly more than one? Is it 3/2 i.e. 1.5? Well, 1.5 should give two when squared, but (1.5)^2 = 2,25. That's too much! Is 1,4? Oh, 1.4 gives 1.96, not too bad, it is slightly more, may be 1.41? 1.41^2 gives 1,9881, we get closer and closer, but will such a search ends up with the best approximation? This would mean we can divide the side of the square unity in a finite number of smaller unities, and find a sufficiently little unity which could measure the diagonal exactly. It would mean d is equal to p * 1/q, where q is the number of divisions of the side of the square unity. If we find such a fraction the diagonal and the sided would be said commensurable. Is there such a fraction? It is not 3/2, we know already. Is it 17/12 (= 1,4166...)? (1712)^2 = 2,006944). Close but wrong. Is it 99/70? (= 1,414285714...) (99/70)^2 = 2,000204082...). Very close, but still wrong! ... is it 12477253282759/8822750406821 ? My pocket computer says that the square of that fraction is 2. Ah, but this is due to its incompetence in handling too big numbers and too little numbers! It is still wrong! How could we know if that search will end, or not end? Sometimes, we can know thing in advance. Why, because things obeys laws, apparently. Which laws of numbers makes the problem decidable? Here is one: - a number is even if and only if the square of that number is even, similarly - a number is odd if and only if the square of that number is odd. Taking the square of an integer leaves invariant the parity (even/odd) of the number. Why? suppose n is odd. There will exist a k (belonging to {0, 1, 2, 3, ...} such that n = 2k+1. OK? So n^2 = (2k+1)^2 = 4k^2 + 4k + 1, OK? and this is odd. OK. And this is enough to show that if n^2 is even, then n is even. OK? And why does this answer the question. Let us reason 'by absurdo. Suppose that there are number p and q such (p/q)^2 = 2. And let us suppose we have already use the Euclid algorithm to reduce that fraction; so that p and q have no common factor. p^2 / q^2 = 2. OK? Then p^2 = 2q^2 (our 'Diophantine equation). OK? Then p^2 is even. OK? (because it is equal to 2 * an integer). Then p is even. OK? (by the law above). This means p is equal to some 2*k (definition of even number). OK? But p^2 = 2q^2 (see above), and substituting p by 2k, we get 4k^2 = 2q^2, and thus, dividing both sides by 2, we get that 2k^2 = q^2. So q^2 is even. OK? So q is even. (again by the law above). OK? So both p and q are even, but this means they have a common factor (indeed, 2), and this is absurd, given that the fraction has been reduced before. So p and q does not exist, and now we know that our search for a finite or periodic decimal, or for a fraction, will never end. The diophantine equation x^2 = 2y^2 has no solution in the integers, and the number sqrt(2) = square root of two is not the ratio of two integers/ Such a number will be said irrational. If we want associate a number to each possible length of line segment, we have to expand the rational number (the reduced fraction, the periodic decimal) with the irrational number. The numerical value of the sqrt(2) can only be given through some approximation, like sqrt(2) = 1,414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 376 948 073 176 679 737 990 732 478... OK? I have to go now. Please ask any question. Does the beginners see that (2k+1)^2 = 4k^2 + 4k + 1? This comes from the
Re: The seven step series
Hi, I want to add something. I said recently to John that the excluded middle principle should be seen as a tolerance-of-ignorance principle. Actually this will play an important role later, and it justifies the arithmetical realism: what it is, and why it is important. Let me illustrate this on the following problem. You have to prove the existence of two irrational numbers x and y such that x^y is rational. We don't ask that x is different from y.. This is not obvious. If x is not a fraction, and y is not a fraction, how could we hope that x^y gives a fraction? Yet a very simple proof shows that there exists such a couple of irrational numbers. Do you agree that a number x is either rational, or is not rational? If you answer yes, you are arithmetical realist. You believe that either there exist integers p and q such that x is equal to p/q, or that such integers don't exist. We already know that sqrt(2) is irrational. That was the peurpose of the preceding post. OK? Now, let us consider S = sqrt(2) ^ sqrt(2). By arithmetical realism, either S is rational or it is not rational. OK? But if S is rational, then our problem is solved. x = y = sqrt(2) are not rational, and x^y is rational. But if S is not rational, then our problem is solved too. Indeed is S is not rational then S^sqrt(2) is a solution. Indeed S^sqrt(2) = [sqrt(2) ^ sqrt(2)]^sqrt(2) = sqrt(2) ^[sqrt(2) * sqrt(2)] = sqrt(2) ^ 2 = 2; which is rational(*). So by admitting that either sqrt(2) ^ sqrt(2) is rational or is not rational, we know that either sqrt(2) ^ sqrt(2) is our solution of [sqrt(2) ^ sqrt(2)]^sqrt(2 is our solution. So we know that a solution exists(**). We may feel uneasy here, because although we know there is a solution, we remain unable to provide one. But we were not asked to provide a solution. We are asked if a solution exist. And we know that either S or S^sqrt(2) is a solution. We know that the solution belongs to the set {S, S^sqrt(2)}, although we don't know which one among S and S^sqrt(2) is the solution. It is like a crime inquest which concludes that the murderer is either Arthur or Penelope, but is incapable to know which one. Such a proof is called non constructive. It proves that something exists, yet does not provide the existing object. All what the proof provides is a set, and a proof that what we are searching for is in the set. It is in that sense that such a proof provides incomplete information. The non constructive reasoning tolerates some amount of ignorance. Non constructive reasoning is usually accepted by most mathematicians, and even by enginers, but not by intuitionists who ask always for constructive existence proof. Actually in theoretical artificial intelligence, and in mathematical theology not only such non constructive proofs abound, but in many case it can be proved that there are no better existence proof. That is we can prove that the proof is necessarily not constructive. It is that phenomenon which makes eventually comp a vaccine against reductionism. We can prove the existence of very 'clever' machine, but then we can prove that nobody can recognize as such, such a machine. This is not the case for the present problem. It can be shown that S (sqrt(2)^sqrt(2)) is irrational, and this provides a constructive solution. The proof that S is irrational is not elementary at all. Such a phenomenon will already appears in the post on Kleene's theorem. Bruno (*) We have used the laws of exponentiation: (a^b)^c = a^(b*c). (**) That proof is sometimes attributed to Jarden. On 09 Sep 2009, at 09:21, Bruno Marchal wrote: This is the last post before we proof Cantor theorem. It is an antic interlude. We are about 2000 years back in time. The square root of 2. It is a number x such that x^2 = 2. It is obviously smaller than 2 and bigger than 1. OK? It cannot be a natural number. But could it be a fraction? The square root of two is the length of the diagonal of a square with side one unity. Do you see that? I can't draw, so you have to imagine a square. You may draw it. And then draw or imagine the square which sides the diagonal (of you square unity). Draw it with its diagonals and you will see, in your mind or on the paper that the second square is made of four times the half of your square unity: meaning that the square which sides the diagonal has an area twice the area of the square unity. But this means that if you call d the length of the diagonal of the square unity, you have, by the law of the area of square, d^2 = 2. OK? So the length of the diagonal d = square root of 2. It is a 'natural' length occurring in geometry (and quantum mechanics!). The function or operation taking the square root of two is the inverse operation of taking the square. (In term of the couples defining the function as set, it means that if (x, y) belongs-to taking
Re: The seven step series
On 31 Aug 2009, at 19:31, Bruno Marchal wrote: Next: I will do some antic mathematic, and prove the irrationality of the square root of two, for many reasons, including some thought about what is a proof. And then I will prove Cantor theorem. Then I will define what is a computable function. I will explain why Cantor reasoning seems to prove, in that context, the impossibility of the existence of universal machine, and why actually Cantor reasoning will just make them paying the big price for their existence. Any question, any comment? I guess that I am too quick for some, too slow for others. Don't forget the exercise: show that there is always a bijection between A+ and N. (A+ = set of finite strings on the alphabet A). This is important and will be used later. I illustrate the solution on a simple alphabet. An alphabet is just any finite set. Let us take A = {a, b, c}. A+ is the set of words made with the letters taken in A. A word is any finite sequence of letters. To build the bijection from N to A+, the idea consists in enumerating the words having 0 letters (the empty word), then 1 letter, then 2 letters, then 3 letters, and so on. For each n there is a finite numbers of words of length n, and those can be ordered alphabetically, by using some order on the alphabet. In our case we will decide that a b, and b c (a b should be read a is before b). So we can send 0 on the empty word. Let us note the empty word as *. 0 -- * then we treat the words having length 1: 1 -- a 2 -- b 3 -- c then the words having length 2: 4 --- aa 5 -- ab 6 -- ac 7 -- ba 8 -- bb 9 -- bc 10 -- ca 11 -- cb 12 -- cc Then the words having lenght 3. There will be a finite number of such words, which can be ranged alphabetically, etc. Do you see that this gives a bijection from N = {0, 1, 2, 3 ...} to A+ = {*, a, b, c, aa, ab, ac, ba, bb, bc, ...} It is one-one: no two identical words will appears in the enumeration. It is onto: all words will appear soon or later in the enumeration. I will call such an enumeration, or order, on A+, the lexicographic order. Its mathematical representation is of course the set of couples: {(0, *), (1, a), (2, b), (3, c), (4, aa), ...} OK? No question? Next, I suggest we do some antic mathematics. It will, I think, be helpful to study a simple impossibility theorem, before studying Cantor theorems, and then the many impossibilities generated by the existence of universal machines. It is also good to solidify our notion of 'real numbers', which does play some role in the computability general issue. Here are some preparation. I let you think about relationship between the following propositions. I recall that: the square root of X is Y means that Y^2 = X. (It is the 'inverse function of the power 2 function). The square root of 9 is 3, for example, because 3^2 = 3*3 = 9. OK? - There exists incommensurable length (finite length segment of line with no common integral unity) - the Diophantine equation x^2 = 2(y^2) has no solution (Diophantine means that x and y are supposed to be integers). - the square root of 2 is irrational (= is not the ratio of integers) - The square root of 2 has an infinite and never periodic decimal. - If we want to measure by numbers any arbitrary segment of line, we need irrational numbers Take it easy, explanation will follow. This antic math interlude will not presuppose the 'modern math' we have seen so far. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Bruno, Just to let you know that while I can't do the exercises, I am following as best I can. I think I understand that powersets of sets lead to ladders of larger and larger infinities and hope your exposition of how this results in the existence of universal machines will be equally clear. Best wishes, marty a. - Original Message - From: Bruno Marchal marc...@ulb.ac.be To: everything-list@googlegroups.com Sent: Tuesday, September 08, 2009 4:43 AM Subject: Re: The seven step series On 31 Aug 2009, at 19:31, Bruno Marchal wrote: Any question, any comment? I guess that I am too quick for some, too slow for others. http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Thanks for telling me Marty, I wish you the best, Bruno On 08 Sep 2009, at 14:17, m.a. wrote: Bruno, Just to let you know that while I can't do the exercises, I am following as best I can. I think I understand that powersets of sets lead to ladders of larger and larger infinities and hope your exposition of how this results in the existence of universal machines will be equally clear. Best wishes, marty a. - Original Message - From: Bruno Marchal marc...@ulb.ac.be To: everything-list@googlegroups.com Sent: Tuesday, September 08, 2009 4:43 AM Subject: Re: The seven step series On 31 Aug 2009, at 19:31, Bruno Marchal wrote: Any question, any comment? I guess that I am too quick for some, too slow for others. http://iridia.ulb.ac.be/~marchal/ http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Bruno Marchal wrote: Ouh la la ... Mirek, You may be right, but I am not sure. You may verify if this was not in a intuitionist context. Without the excluded middle principle, you may have to use countable choice in some situation where classical logic does not, but I am not sure. Please see http://en.wikipedia.org/wiki/Countable_set the sketch of proof that the union of countably many countable sets is countable is in the second half of the article. I don't think it has anything to do with the law of excluded middle. Similar reasoning is described here http://at.yorku.ca/cgi-bin/bbqa?forum=ask_a_topologist_2008;task=show_msg;msg=1545.0001 My opinion on choice axioms is that there are obviously true, and this despite I am not a set realist. OK, thanks. I am glad, nevertheless that ZF and ZFC have exactly the same arithmetical provability power, so all proof in ZFC of an arithmetical theorem can be done without C, in ZF. This can be seen through the use of Gödel's constructible models. I am sorry, but I have no idea what might an arithmetical provability power refer to. Just give me a hint ... I use set theory informally at the metalevel, and I will not address such questions. As I said, I use Cantor theorem for minimal purpose, and as a simple example of diagonalization. OK. Fair enough. I am far more puzzled by indeterminacy axioms, and even a bit frightened by infinite game theory I have no intuitive clues in such fields. Do you have some links please? Just to check it and write down few new key words. Cheers, Mirek On 01 Sep 2009, at 14:30, Mirek Dobsicek wrote: The reason why I am puzzled is that I was recently told that in order to prove that * the union of countably many countable sets is countable one needs to use at least the Axiom of Countable Choice (+ ZF, of course). The same is true in order to show that * a set A is infinite if and only if there is a bijection between A and a proper subset of A (or in another words, * if the set A is infinite, then there exists an injection from the natural numbers N to A) Reading the proofs, I find it rather subtle that some (weaker) axioms of choices are needed. The subtlety comes from the fact that many textbook do not mention it. In order to understand a little bit more to the axiom of choice, I am thinkig if it has already been used in the material you covered or whether it was not really needed at all. Not being able to answer it, I had to ask :-) Please note that I don't have any strong opinion about the Axiom of Choice. Just trying to understand it. May I ask about your opinion? Mirek Bruno Marchal wrote: Hi Mirek, On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote: I am puzzled by one thing. Is the Axiom of dependent choice (DC) assumed implicitly somewhere here or is it obvious that there is no need for it (so far)? I don't see where I would have use it, and I don't think I will use it. Cantor's theorem can be done in ZF without any form of choice axioms. I think. Well, I may use the (full) axiom of choice by assuming that all cardinals are comparable, but I don't think I will use this above some illustrations. If you suspect I am using it, don't hesitate to tell me. But so far I don't think I have use it. Bruno --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 02 Sep 2009, at 17:16, Mirek Dobsicek wrote: Bruno Marchal wrote: Ouh la la ... Mirek, You may be right, but I am not sure. You may verify if this was not in a intuitionist context. Without the excluded middle principle, you may have to use countable choice in some situation where classical logic does not, but I am not sure. Please see http://en.wikipedia.org/wiki/Countable_set the sketch of proof that the union of countably many countable sets is countable is in the second half of the article. I don't think it has anything to do with the law of excluded middle. I was thinking about the equivalence of the definitions of infinite set (self-injection, versus injection of omega), which, I think are inequivalent without excluded middle, but perhaps non equivalent with absence of choice, I don't know) Similar reasoning is described here http://at.yorku.ca/cgi-bin/bbqa?forum=ask_a_topologist_2008;task=show_msg;msg=1545.0001 I am not sure ... I may think about this later ... My opinion on choice axioms is that there are obviously true, and this despite I am not a set realist. OK, thanks. I am glad, nevertheless that ZF and ZFC have exactly the same arithmetical provability power, so all proof in ZFC of an arithmetical theorem can be done without C, in ZF. This can be seen through the use of Gödel's constructible models. I am sorry, but I have no idea what might an arithmetical provability power refer to. Just give me a hint ... By arithmetical provability power, I mean the set of first order arithmetical sentences provable in the theory, or by a machine. I will say, for example, that the power of Robinson Arithmetic is smaller than the power of Peano Aritmetic, *because* the set of arithmetical theorems of Robinson Ar. is included in the set of theorems of Peano Ar. Let us write this by RA PA. OK? Typically, RA PA ZF = ZFC ZF + k (k = there exists a inaccessible cardinal). The amazing thing is ZF = ZFC (in this sense!). Any proof of a theorem of arithmetic using the axiom of choice, can be done without it. I use set theory informally at the metalevel, and I will not address such questions. As I said, I use Cantor theorem for minimal purpose, and as a simple example of diagonalization. OK. Fair enough. I am far more puzzled by indeterminacy axioms, and even a bit frightened by infinite game theory I have no intuitive clues in such fields. Do you have some links please? Just to check it and write down few new key words. This is not too bad, imo, (I should have use determinacy, it is a better key word): http://en.wikipedia.org/wiki/Determinacy Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Bruno, I am puzzled by one thing. Is the Axiom of dependent choice (DC) assumed implicitly somewhere here or is it obvious that there is no need for it (so far)? Thanks! mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Mirek, On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote: I am puzzled by one thing. Is the Axiom of dependent choice (DC) assumed implicitly somewhere here or is it obvious that there is no need for it (so far)? I don't see where I would have use it, and I don't think I will use it. Cantor's theorem can be done in ZF without any form of choice axioms. I think. Well, I may use the (full) axiom of choice by assuming that all cardinals are comparable, but I don't think I will use this above some illustrations. If you suspect I am using it, don't hesitate to tell me. But so far I don't think I have use it. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
The reason why I am puzzled is that I was recently told that in order to prove that * the union of countably many countable sets is countable one needs to use at least the Axiom of Countable Choice (+ ZF, of course). The same is true in order to show that * a set A is infinite if and only if there is a bijection between A and a proper subset of A (or in another words, * if the set A is infinite, then there exists an injection from the natural numbers N to A) Reading the proofs, I find it rather subtle that some (weaker) axioms of choices are needed. The subtlety comes from the fact that many textbook do not mention it. In order to understand a little bit more to the axiom of choice, I am thinkig if it has already been used in the material you covered or whether it was not really needed at all. Not being able to answer it, I had to ask :-) Please note that I don't have any strong opinion about the Axiom of Choice. Just trying to understand it. May I ask about your opinion? Mirek Bruno Marchal wrote: Hi Mirek, On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote: I am puzzled by one thing. Is the Axiom of dependent choice (DC) assumed implicitly somewhere here or is it obvious that there is no need for it (so far)? I don't see where I would have use it, and I don't think I will use it. Cantor's theorem can be done in ZF without any form of choice axioms. I think. Well, I may use the (full) axiom of choice by assuming that all cardinals are comparable, but I don't think I will use this above some illustrations. If you suspect I am using it, don't hesitate to tell me. But so far I don't think I have use it. Bruno --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Ouh la la ... Mirek, You may be right, but I am not sure. You may verify if this was not in a intuitionist context. Without the excluded middle principle, you may have to use countable choice in some situation where classical logic does not, but I am not sure. I know that in intuitionist math, the definition of infinite set by there is an injection on a subset is NOT equivalent with the traditional definition. My opinion on choice axioms is that there are obviously true, and this despite I am not a set realist. I am glad, nevertheless that ZF and ZFC have exactly the same arithmetical provability power, so all proof in ZFC of an arithmetical theorem can be done without C, in ZF. This can be seen through the use of Gödel's constructible models. I use set theory informally at the metalevel, and I will not address such questions. As I said, I use Cantor theorem for minimal purpose, and as a simple example of diagonalization. I am far more puzzled by indeterminacy axioms, and even a bit frightened by infinite game theory I have no intuitive clues in such fields. And yet, the few I understand makes me doubt even of the consistency of ZFC. But this is 99% due, I think, to my own incompetence in the subject. Bruno On 01 Sep 2009, at 14:30, Mirek Dobsicek wrote: The reason why I am puzzled is that I was recently told that in order to prove that * the union of countably many countable sets is countable one needs to use at least the Axiom of Countable Choice (+ ZF, of course). The same is true in order to show that * a set A is infinite if and only if there is a bijection between A and a proper subset of A (or in another words, * if the set A is infinite, then there exists an injection from the natural numbers N to A) Reading the proofs, I find it rather subtle that some (weaker) axioms of choices are needed. The subtlety comes from the fact that many textbook do not mention it. In order to understand a little bit more to the axiom of choice, I am thinkig if it has already been used in the material you covered or whether it was not really needed at all. Not being able to answer it, I had to ask :-) Please note that I don't have any strong opinion about the Axiom of Choice. Just trying to understand it. May I ask about your opinion? Mirek Bruno Marchal wrote: Hi Mirek, On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote: I am puzzled by one thing. Is the Axiom of dependent choice (DC) assumed implicitly somewhere here or is it obvious that there is no need for it (so far)? I don't see where I would have use it, and I don't think I will use it. Cantor's theorem can be done in ZF without any form of choice axioms. I think. Well, I may use the (full) axiom of choice by assuming that all cardinals are comparable, but I don't think I will use this above some illustrations. If you suspect I am using it, don't hesitate to tell me. But so far I don't think I have use it. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
I give the solution to the last exercises. On 26 Aug 2009, at 19:06, Bruno Marchal wrote: Hi, I sum up, a little bit, and then I go quickly, just to provide some motivation for the sequel. We have seen the notion of set. We have seen examples of finite sets and infinite sets. For example the sets A = {0, 1, 2}, B = {2, 3} are finite. The set N = {0, 1, 2, 3, ...} is infinite. We can make the union of sets, and their intersection: A union B = {x such-that x is in A OR x is in B} = {0, 1, 2, 3} A intersection B = {x such-that x is in A AND x (the same x) is in B} = {2}. 2 is the only x being both in A and B. OK? We have seen the notion of subset. X is a subset of Y, if each time that x is in X, x is also in Y. And we have seen the notion of powerset of a set. The powerset is the set of all subset of a set. Example: the powerset of {2, 3} is the set {{ }, {2}, {3}, {2, 3}}. OK? In particular we have seen that the number of element of the powerset of a set with n elements is 2^n. Example: {2, 3} has two elements, and the powerset of {2, 3}, i.e. {{ }, {2}, {3}, {2, 3}} has 2^2 = 4 elements. OK? We have seen the notion of function from a set A to a set B. It is just a set of couples (x, y) with x in A and y in B. x is supposed to be any elements of A, and y some element of B. To be a function, a set of couples has to verify the *functional condition* that no x is send to two or more different y. This is because we want y be depending on x. Think about the function which describes how the temperature evolves with respect to time: an instant t cannot be send on two different temperature. Let A = {1, 2} and B = {a, b, c} F1 = {(1, a), (2, a)} F2 = {(1, c}, (2, a)} F1 and F2 are functions. But the following are not: G1 = {(1, a), (2, b}, (2, c)} because 2 is send on two different elements G2 = {(1, a), (2, b), (1, b)} because 1 is send on two different elements. OK? We have then consider the set of all functions from A to B, written B^A, and seen that this number is equal to card(B) ^card(A) where card(A) is the number of elements of A.A is supposed to be a finite set, and later we will see how Cantor will generalize the notion of cardinal for infinite sets. We have then studied the notion of bijection. A function from A to B is a bijection from A to B when it is both - ONE-ONE two different elements of A are send to two different elements of B - ONTO, this means that all elements of B are in the range of the function, i.e. for any y in B there is some couple (x, y) in the function. Example: F from {a, b} to {1, 2} with F = {(a, 1}, (b, 2)} is a bijection, but G = {(a, 1), (b, 1)} is not because G is not ONTO, nor ONE-ONE. OK? We have seen that if A and B are two finite sets, then we have A and B have the same number of element if and only if there exists a bijection from A to B. OK? Now I can give you the very ingenious idea from Cantor. Cantor will say that two INFINITE sets have the same cardinality if and only if there exists a bijection between them. This leads to some surprises. Let N = {0, 1, 2, 3, ...} be the usual set of all natural numbers. This is obviously an infinite set, all right? Let 2N = {0, 2, 4, 6, } be the set of even numbers. This is obviously a subset of N OK?, and actually an infinite subset of N. Now consider the function from N to 2N which send each n on 2*n. This function is one-one. Indeed if n is different from m, 2*n is different from 2*m. OK? And that function, from N to 2N is onto. Indeed any element of 2N, has the shape 2*n for some n, and (n, 2*n) belongs to the function. In extension the bijection is {(0, 0), (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), (6, 12), ...} So here we have the peculiar fact that a bijection can exist between a set and some of its proper subset. (A subset of A is a proper subset of A if it is different of A). The first who discovered this is GALILEE. But, alas, he missed Cantor discovery. Like Gauss later, such behavior was for them an argument to abandon the study of infinite sets. They behave too much weirdly for them. OK? At first sight we could think that all infinite sets have the same cardinality. After all those sets are infinite, how could an infinite set have a bigger cardinality than another infinite set? This is the second surprise, and the main discovery of Cantor: the fact that there are some infinite sets B such that there is no bijection between N and B. Cantor will indeed show that there is no bijection between N and N^N, nor between N and 2^N. We will study this. Cantor will prove a general theorem, know as Cantor theorem, which asserts that for ANY set A, there are no bijection between A and the powerset of A. The powerset operation leads to a ladder of bigger infinities. I will
Re: The seven step series
Hi, I sum up, a little bit, and then I go quickly, just to provide some motivation for the sequel. We have seen the notion of set. We have seen examples of finite sets and infinite sets. For example the sets A = {0, 1, 2}, B = {2, 3} are finite. The set N = {0, 1, 2, 3, ...} is infinite. We can make the union of sets, and their intersection: A union B = {x such-that x is in A OR x is in B} = {0, 1, 2, 3} A intersection B = {x such-that x is in A AND x (the same x) is in B} = {2}. 2 is the only x being both in A and B. OK? We have seen the notion of subset. X is a subset of Y, if each time that x is in X, x is also in Y. And we have seen the notion of powerset of a set. The powerset is the set of all subset of a set. Example: the powerset of {2, 3} is the set {{ }, {2}, {3}, {2, 3}}. OK? In particular we have seen that the number of element of the powerset of a set with n elements is 2^n. Example: {2, 3} has two elements, and the powerset of {2, 3}, i.e. {{ }, {2}, {3}, {2, 3}} has 2^2 = 4 elements. OK? We have seen the notion of function from a set A to a set B. It is just a set of couples (x, y) with x in A and y in B. x is supposed to be any elements of A, and y some element of B. To be a function, a set of couples has to verify the *functional condition* that no x is send to two or more different y. This is because we want y be depending on x. Think about the function which describes how the temperature evolves with respect to time: an instant t cannot be send on two different temperature. Let A = {1, 2} and B = {a, b, c} F1 = {(1, a), (2, a)} F2 = {(1, c}, (2, a)} F1 and F2 are functions. But the following are not: G1 = {(1, a), (2, b}, (2, c)} because 2 is send on two different elements G2 = {(1, a), (2, b), (1, b)} because 1 is send on two different elements. OK? We have then consider the set of all functions from A to B, written B^A, and seen that this number is equal to card(B) ^card(A) where card(A) is the number of elements of A.A is supposed to be a finite set, and later we will see how Cantor will generalize the notion of cardinal for infinite sets. We have then studied the notion of bijection. A function from A to B is a bijection from A to B when it is both - ONE-ONE two different elements of A are send to two different elements of B - ONTO, this means that all elements of B are in the range of the function, i.e. for any y in B there is some couple (x, y) in the function. Example: F from {a, b} to {1, 2} with F = {(a, 1}, (b, 2)} is a bijection, but G = {(a, 1), (b, 1)} is not because G is not ONTO, nor ONE-ONE. OK? We have seen that if A and B are two finite sets, then we have A and B have the same number of element if and only if there exists a bijection from A to B. OK? Now I can give you the very ingenious idea from Cantor. Cantor will say that two INFINITE sets have the same cardinality if and only if there exists a bijection between them. This leads to some surprises. Let N = {0, 1, 2, 3, ...} be the usual set of all natural numbers. This is obviously an infinite set, all right? Let 2N = {0, 2, 4, 6, } be the set of even numbers. This is obviously a subset of N OK?, and actually an infinite subset of N. Now consider the function from N to 2N which send each n on 2*n. This function is one-one. Indeed if n is different from m, 2*n is different from 2*m. OK? And that function, from N to 2N is onto. Indeed any element of 2N, has the shape 2*n for some n, and (n, 2*n) belongs to the function. In extension the bijection is {(0, 0), (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), (6, 12), ...} So here we have the peculiar fact that a bijection can exist between a set and some of its proper subset. (A subset of A is a proper subset of A if it is different of A). The first who discovered this is GALILEE. But, alas, he missed Cantor discovery. Like Gauss later, such behavior was for them an argument to abandon the study of infinite sets. They behave too much weirdly for them. OK? At first sight we could think that all infinite sets have the same cardinality. After all those sets are infinite, how could an infinite set have a bigger cardinality than another infinite set? This is the second surprise, and the main discovery of Cantor: the fact that there are some infinite sets B such that there is no bijection between N and B. Cantor will indeed show that there is no bijection between N and N^N, nor between N and 2^N. We will study this. Cantor will prove a general theorem, know as Cantor theorem, which asserts that for ANY set A, there are no bijection between A and the powerset of A. The powerset operation leads to a ladder of bigger infinities. I will come back with some detail later. Some surprises were BAD surprises. Conceptual problems which Cantor will hide in its desk, to treat them later. The so-called paradoxes of naïve set
Re: The seven step series
m.a. wrote: a towel into the ring. I simply don't have the sort of mind that takes to juggling letters, numbers and symbols in increasingly fine-grained, complex arrangements. [...] Marty, If I can ask, I'd be really interested what do you think of this socratic experiment http://www.garlikov.com/Soc_Meth.html Cheers, mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Mirek, I think it must be a very effective method of teaching binary numbers. Perhaps I'll try it on my grandchildren. My four-year-old grandson calls VCR tapes rectangular DVD's. So he's probably ready for abstract thinking. Thanks for the lesson. marty a. - Original Message - From: Mirek Dobsicek m.dobsi...@gmail.com To: everything-list@googlegroups.com Sent: Saturday, August 22, 2009 11:05 AM Subject: Re: The seven step series Marty, If I can ask, I'd be really interested what do you think of this socratic experiment http://www.garlikov.com/Soc_Meth.html Cheers, mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 21 Aug 2009, at 01:24, meekerdb @dslextreme.com wrote: On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchalmarc...@ulb.ac.be wrote: Hi, I give the solution of the first of the last exercises. ... This motivates the definition of the following function from N to N, called factorial. factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if is n is different from 0. Note this: if n is different from 0, for each n we have that fact(n) = n*fact(n). Of course you meant fact(n)=n*fact(n-1). Yes, indeed. Note that later we will see stronger form of recursion, but here it is just a typo mistake. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Bruno, I'm terribly sorry to disappoint you and ashamed to admit that I'm throwing in the towel. This is an idiom used in professional boxing; when a coach decides that his fighter can't take anymore punishment, he ends the fight by throwing a towel into the ring. I simply don't have the sort of mind that takes to juggling letters, numbers and symbols in increasingly fine-grained, complex arrangements. I think that in any endeavor, when we struggle towards a goal, there should be some satisfaction...some sense of accomplishment...in each step along the way. But in this quest, I find each step to be difficult and unrewarding in and of itself. Sometimes the goal is so compelling that we force ourselves to overcome huge impediments to reach it; but in this case, I already know what the goal is, and I am only motivated by the desire to understand how it is proven. Well, I must be content to leave verification of the proof to people who are far better able than I to follow its intricacies. I trust they have checked it accurately and will point out inconsistencies in this open forum if such exist. Meanwhile, I'm happy to take it on faith. I shall certainly continue to lurk here gleaning what I can from the philosophical debates whose endless probing of the foundations of existence is a source of constant fascination. Best, marty a. - Original Message - From: Bruno Marchal marc...@ulb.ac.be To: everything-list@googlegroups.com Sent: Friday, August 21, 2009 3:47 AM Subject: Re: The seven step series On 21 Aug 2009, at 01:24, meekerdb @dslextreme.com wrote: On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchalmarc...@ulb.ac.be wrote: Hi, I give the solution of the first of the last exercises. ... This motivates the definition of the following function from N to N, called factorial. factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if is n is different from 0. Note this: if n is different from 0, for each n we have that fact(n) = n*fact(n). Of course you meant fact(n)=n*fact(n-1). Yes, indeed. Note that later we will see stronger form of recursion, but here it is just a typo mistake. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Thanks for telling Marty. It is a pity you stop just before Cantor Theorem, but it could ask for some work if your math disposition have been dormant for a too long time. I am sure you could come by, because what will follow will be a recurrent use of the same idea. The difficulty, for many, is to understand what is a mathematical computation, but to explain this we have to explain what are the mathematical objects which will computed and be computed. Sets of numbers and functions from numbers to numbers are those things which will be either computable or not computable. Up to now, I am only introducing vocabulary, so that we can avoid future misunderstanding. Numbers, sets, functions are common in exact science, but rarely well known ... I will soon explain Cantor theorem. And soon after should the mathematical discovery of the (mathematical) universal machine appear. I have to explain a minimal amount of theoretical computer science to give a precise sense to the comp supervenience thesis. I like to summarize 20th century computer science by its two main 'discoveries', really two creative bombs, the universal machine, and the other universal machine. The universal machine, and the quantum universal machine. I put 'discoveries' in quote because strictly speaking they are thesis or hypothesis. Take a look on what follows because it happen that some beginners understand math the day they understand the first non trivial result, but take it easy any way. It is a pleasure to share interest wherever we come from, and I appreciate your open mind, Bruno On 21 Aug 2009, at 16:22, m.a. wrote: Bruno, I'm terribly sorry to disappoint you and ashamed to admit that I'm throwing in the towel. This is an idiom used in professional boxing; when a coach decides that his fighter can't take anymore punishment, he ends the fight by throwing a towel into the ring. I simply don't have the sort of mind that takes to juggling letters, numbers and symbols in increasingly fine-grained, complex arrangements. I think that in any endeavor, when we struggle towards a goal, there should be some satisfaction...some sense of accomplishment...in each step along the way. But in this quest, I find each step to be difficult and unrewarding in and of itself. Sometimes the goal is so compelling that we force ourselves to overcome huge impediments to reach it; but in this case, I already know what the goal is, and I am only motivated by the desire to understand how it is proven. Well, I must be content to leave verification of the proof to people who are far better able than I to follow its intricacies. I trust they have checked it accurately and will point out inconsistencies in this open forum if such exist. Meanwhile, I'm happy to take it on faith. I shall certainly continue to lurk here gleaning what I can from the philosophical debates whose endless probing of the foundations of existence is a source of constant fascination. Best, marty a. - Original Message - From: Bruno Marchal marc...@ulb.ac.be To: everything-list@googlegroups.com Sent: Friday, August 21, 2009 3:47 AM Subject: Re: The seven step series On 21 Aug 2009, at 01:24, meekerdb @dslextreme.com wrote: On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchalmarc...@ulb.ac.be wrote: Hi, I give the solution of the first of the last exercises. ... This motivates the definition of the following function from N to N, called factorial. factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if is n is different from 0. Note this: if n is different from 0, for each n we have that fact(n) = n*fact(n). Of course you meant fact(n)=n*fact(n-1). Yes, indeed. Note that later we will see stronger form of recursion, but here it is just a typo mistake. Bruno http://iridia.ulb.ac.be/~marchal/ http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi, I give the solution of the first of the last exercises. I reason aloud. I go slowly for those who did not get some math courses, or just forget them. I cannot stress the importance of the notion of bijection in the mathematical discovery of the universal machine (the quote means that a nuance will be added here). Counting is not so important. Th exercise motivation is in to develop familiarity with the notion of function and bijection. Then counting things provides example of functions from N to N. 1) count the number of bijections from a set A to itself. (= card{x such that x is bijection from A to A}) This does not seem very obvious, so let us begin with the simplest set, for example the one which admits the shorter description when written in extension, that is the empty set { }. The question in this case is: count the number of bijection between { } and { }. Hmm... This smells the subtle trap and it may be a good advise to avoid the simplest set or number. Zero and the empty set may be simplest in term of description but may be harder conceptually. A simple case, in this and many cases, would be a set with not much elements. Let us count the number of bijections from {a, b} to itself. i.e. the bijections from {a, b} to {a, b}. Here some beginners could have a trouble: I don't remember what is a bijection. Well, the exercise is obviously with notes. I am not yet asking to buy a webcam so that I can look if you are not cheating, all right? Two things can happen. Either you find the passage in your diary where I explain bijection with the legendary story of the humans who cannot count, and compare the bigness of sets by using ropes. You may remember how the farmer compare their *set* of animals, without being able to count. They compare two sets of animals by attaching a rope to ONE animal belonging to the set of your animals, say, and you bring that to ONE animal of your neighbor. Three things can happen: 1) All your animals get attached to a rope, and got attached to some neighbor's animals, but some other animal of the neighbor are still freely going here and there. In this situation we say damned, the set of animals of my neighbor is bigger than mine. 2) All your animals get they rope, and got attached to the neighbor's animals. And all neighbor's animals are attached. In this situation we say OK, my set of animals has the same cardinality than the set of my neighbor animals. Cardinality is the measure of set, when we compare it in this way. Now, this is the situation where a bijection exists. 3) All the neighbor's animal are attached to the rope, yet some of your own animals remain free. You can attach the rope to those free animals, but you will be unable to attach them to some neighbor animal, they are already all attached. In this situation you say nothing, because you are polite, you just let the neighbor saying damned, the set of animals of my neighbor is bigger than mine. Or you don't remember that story, so you consult the austere notes with the definition. A, B ... represent sets. A bijection between A and B is a function from A to B which is ONE-ONE and ONTO. And what is a function? A set of couples (x, y), x in A, y in B, verifying the condition that no x in A is sent on different y in B. In a very large sense, the element of B depend on the element of A, and that dependence is represented by a couple (x, y). With the farmer, the couples where made with one animal x attached by a rope to one animal y: (x, y). Well let us go back to the bijections from {a, b} to {a, b}. Oh, I see some anxiousness can rise due to the fact that we have the same set of both side. Why would ever a farmer compare the bigness of its set of animals with the bigness of its set of animals? Is that not a pure mathematical absurdity? To ease the pain, in math, consists always in simplifying, so, just to keep the intuition provided by the farmer, let us distinguish the animal's neighbor, those which makes the arrival set, by different letters. And let us first search the bijections from {a, b} to {c, d}. {a, b} is the set of my animals. {c, d} is the set of animals of my neighbor. OK? Well I have to build a bijection, which is a set, so I have to begin by {, indicating I am building a set. Of course, this is implicit in the farmer's mind, because his goal consists in just comparing the two sets. But our goal is to find all bijections. So we have to be clear about them as mathematically represented objects, and bijections, like functions, have been defined or represented as sets. Now I have to choose one of my animals; let us choose a. and attach the rope. The description of the bijection looks like: {(a, I have to choose an animal belonging to the set of my neighbor's animals. Well, I have two choices: c or d. Let us choose c. The description of the bijection looks
Re: The seven step series
On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchalmarc...@ulb.ac.be wrote: Hi, I give the solution of the first of the last exercises. ... This motivates the definition of the following function from N to N, called factorial. factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if is n is different from 0. Note this: if n is different from 0, for each n we have that fact(n) = n*fact(n). Of course you meant fact(n)=n*fact(n-1). Brent --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi, Just a reminder, for me, and perhaps some training for you. In preparation to the mathematical discovery of the universal machine. exercises: 1) count the number of bijections from a set A to itself. (= card{x such that x is bijection from A to A}) 2) describe some canonical bijection between 2^A and the powerset of A. 3) I say that a set S is a proper subset of A if it is a subset of A, and different from A. We have seen that there is a bijection between N and 2N = {0, 2, 4, 6, ...}. (see below *) 2N is a proper subset of N. So we see that an infinite set can have a bijection with a proper subset. The question is, could that be possible for a finite set? The bijection between N and 2N is the set {(0,0), (1,2), (2, 4), (3, 6), (4, 8), ...}. More schematically, if you remember the ropes: N 2N 0 --- 0 1 2 2 4 3 6 4) Be sure that you have been convinced by Brent that there is a bijection between N and NxN, and between N and NxNxN, and etc. That is be sure there is a bijection between N and N^m for each N. 5) Key exercise for the sequel. First a definition. An alphabet A is a non empty finite set. I call its elements letter. Exemple. A = {a, b, c},, B = {0, 1}.. By A+ I mean the set of finite words on the alphabet A. A word is a finite sequence of letters, from some alphabet, like, on the alphabet A, aaabab, acbababcccacab, etc. IA+ is obviously infinite, it contains *notably* a, aa, aaa, , a, aa, aaa, ... The word word has a larger meaning in math than in natural language. On the usual alphabet {A, B, ... Z}, an expression like HHYUJLIFSEFGXWKKODENN is a fully respectable word. Show that for any alphabet A, there is a bijection between N and A+ Soon (asap, though) the proof of many theorems found by Cantor. Notably that there is NO bijection from N to N^N. Then Cantor proof will be done again and again, and again, ... in deeper and deeper and deeper contexts. Please ask any questions. It is not too late before we go in the *very* interesting matter, and very illuminating with respect to the question of the existence of universal machines, languages and numbers. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 19 Aug 2009, at 23:03, meekerdb @dslextreme.com wrote: On Wed, Aug 19, 2009 at 12:12 PM, Bruno Marchalmarc...@ulb.ac.be wrote: Hi, Just a reminder, for me, and perhaps some training for you. In preparation to the mathematical discovery of the universal machine. exercises: ... 4) Be sure that you have been convinced by Brent that there is a bijection between N and NxN, and between N and NxNxN, and etc. That is be sure there is a bijection between N and N^m for each N. Don't you mean for each m? Yes. Sorry. I type too much quickly. I made other mistakes of that type. Hope you can see them and make the correction. In case of doubt ask, like Brent. Some people seems afraid asking questions, please, do. Nobody judge you. We have different baggages. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Brent, I said: this is food for Friday and the week-end, and you provide already the solutions! It is OK, and you are correct. Thanks for playing. I add short comments. I have not much time till monday, and I intend to come back on some issues. I will comment the important recent post by David though. On 13 Aug 2009, at 22:49, Brent Meeker wrote: Bruno Marchal wrote: ... 4) Key questions for the sequel, on which you can meditate: - is there a bijection between N and NxN? (NxN = the cartesian product of N with N) - is there a bijection between N and N^N? You're making me think, Bruno. :-) A bijection between N and NxN can be constructed by enumerating all the N pairs summing to 0, followed by those summing to 1, followed by those summing to 2 as follows (per Cantor): N - NxN 1 0,0 2 1,0 3 0,1 4 2,0 5 1,1 6 0,2 7 3,0 8 2,1 9 1,2 10 0,3 ... OK. I hope everyone see that your bijection is indeed one-one and onto. Each number is sned on one couple, and each couple is touched by the bijection. I take it as a function from N to NxN. New exercises for the adventurous: In the context of sets, 2 will represent the set {0, 1}. OK? And 3 will represent {0, 1, 2}, etc. Find a bijection between NxN and N^2 this means find a bijection between NXN and the set of functions from 2(= {0,1}) to N. Since there are two elements in the domain {0,1}, if we write down all pairs of numbers (n,m) and map 0 to the first and 1 to the second we will have constructed all functions from 2 to N. But above we've already enumerated all pairs of numbers, NxN. So we just map 0 to the number in first one and 1 to the second and we have an enumerated list of the functions from 2 to N. N - NxN - N^2 1 0,0 {(0,0) (1,0)} 2 1,0 {(0,1) (1,0)} 3 0,1 {(0,0) (1,1)} 4 2,0 {(0,2) (1,0)} 5 1,1 {(0,1) (1,1)} 6 0,2 {(0,0) (1,2)} 7 3,0 ... 8 2,1 9 1,2 10 0,3 ... Define NxNxN by Nx(NxN), with (x,y,z) represented (bijectively) by (x, (y,z)) OK? Find a bijection between NxNxN and N^3 Show that there is a bijection between NxNxNxNxNx ... xN (m times) and N^m, in the sense of above. That is NxNxNxNxNx ... xN is defined by Nx(Nx(Nx ... ), and N^m is the set of functions from m to N, and m = {0, 1, ... m-1}. First note that we can use the mapping NxN - N to reduce NxNx...xN (m times) to NxNx...xN (m-1 times) by substituting for a pair in NxN the number from N determined by the above bijection. So we can construct a bijection NxNx...xN - N. OK. Second, N^m is the set of mappings from m to all m-tuples of numbers to N. So if we write down the m-tuples, i.e. the elements of NxNx...xN (m times) as we did the pairs above and then for each m- tuple map 0 to the first element, 1 to the second, and so forth up to the mth element we will have constructed all the functions N^m and we will have enumerated them, i.e. shown a bijection between N^m and N. Since bijection is transitive, this also shows there is a bijection between NxNx...xN (n times) and N^m (n and m not necessarily equal). For the very adventurous: Find a bijection between NxNxNx and N^N? Hmmm? I could say I've already proven it above or that it follows from the above by induction, but the scheme would require writing down infinitely many infinite lists so I'm not sure the above proof generalizes to N^N. I will come back on this next week. A simple way to see that there is indeed a bijection between NxNx and N^N, consists in observing that an element of NxNx... is really an infinite-uple. A couple is a 2- uple, a triple is a 3-uple, and an element of NxNxNx... is really an infinity-uple (a, b, c, ). This is just a sequence of number. The canonical bijection is given by (a, b, c, ...) {(0, a), (1, b), (2, c), } A function from N to N is really just an infinite sequence of numbers. This generalize your correspondence above between NxN and N^2 (with 2 = {0, 1}). So now we know that there is a bijection between NxNxNx ...xN (m times) and N^m. And you have shown all those sets can be put in bijection with N. And we know that the infinite cartesian product NxNx... is in bijection with N^N. But the question which remains is: does there exist a bijection between NxNx and N? Despite perhaps the appearances, all those new exercises are rather easy. The above in 4) key questions are more difficult. Oh! I forget to ask you the simplest exercise : Find a bijection between N and N^1, with 1 = {0}. N^1 is of course the set of functions from 1 to N, i.e. from {0} to N. You did not solve this one? Too much easy perhaps :) An element of N^1 is a function from {0}
Re: The seven step series
On 12 Aug 2009, at 19:55, Bruno Marchal wrote: 1) Convince yourself that if A and B are finite sets, then there exists a bijection between A and B if and only if card(A) = card(B). Only you can convince yourself. I try to help by going very slowly, but people should really mind it y themselves, without hesitating to reread the definitions in case of doubt, or to attack me on the typo errors, I mean it is not very difficult, but revise well the definitions if problems. I provide a detailed solution of the first problem, hints for the other problems, and new problems for the adventurous. 2) If A has n elements (card(A) = n), how many bijections exists from A to B? Again start with simple examples, and try to generalize. For example, how many bijections from {a, b, c} to {1, 2}. How many bijections from (a, b, c} to {a, b, c}? How many bijections are there from {a, b, c} to {1, 2}? Let us try to build one. A bijection is a function which has to be one- one and onto. So I start from {a, b, c}, and I build my bijective function, so I open the accolades { , I open the parenthesis ( of the first couple of my function, and I choose a in {a, b, c}, which is the set of input/argument of my function. This very beginning looks like {(a, And I have to decide where in the set {1, 2} a will be sent. Remembering all the times that I am building a function, so that once a is sent, I can no more send it again, and that my goal here is to build a bijection, so that I cannot send two different elements of my starting set on the same element in the arrival set. Nor should I miss an element of the arrival set. Well, cool, I *can* continue, I have actually two choices, I can send a on 1, or I can send a on 2. I decide to send it on 1, This means (a, 1) will belong to my bijection, well, the one I try to build. My future bijection looks like {(a, 1), And I have to decide where b is send, now: {(a, 1), (b, Could I send b to 1? No. I can't. The function would not be one- one! I do have a solution yet, I can send b on 2. Note that our freedom has decreased, here. Now my bijection looks like {(a, 1), (b, 2), And I have to decide where I will send c. {(a, 1), (b, 2), (c, Could I send it on 1? No. I can't. The function would not be one-one! Could I send it on 2? No. I can't. The function would not be one-one! Is there anywhere else? Well, the function is from {a, b, c} to {1, 2}. If you want a function which i just ONTO, it is OK, send c on 1 or 2 as you wish, but none of such function can be one-one. Or attempt has failed. OK. Perhaps it is like in the Sudoku, and our first choice was bad. My be we should have send a, not on 1, but on 2, After all we get two choices at the beginning. Surely we have made the bad choice. So let us try again: {(a, 2), and then {(a, 2), (b, 1), we realize with some anxiousness that the number of choices has gone again from 2 to 1, and now we have to send c on something which has to be different from 1 and 2, and yet in the arrival set {1, 2}. Zero possibility, we are trapped. Perhaps, we should have begin by sending b. This would not change anything. We have to conclude that there is no bijection from {a, b, c} to {1, 2}. Is there a bijection from {1, 2} to {a, b, c}. No. In this case convince yourself that you can build a function which is one-one, but that there is no onto functions. Convince yourself that if there is a bijection from A to B, then there is a bijection from B to A. That is why we talk also of bijection between A and B. Hint: show that to each bijection from A to B, you can associate canonically a bijection from B to A. How many bijections from (a, b, c} to {a, b, c}? I let you search. Hint: look what happen to our choices above, compare to the choices in our previews counting. 3) can you find, or define a bijection between the infinite set N, and the infinite set E = {0, 2, 4, 6, 8, ...} (E for even). This means, by definition of bijection, can you find a function from N to E which is both one-one and onto. Example: The identity function which send n on n, that is I = {(0,0), (1,1), (2,2), (3, 3) ...} is a function from N to N which is onto and one- one. It is a bijection between N and itself. But it is not a function from N to E. The function which send n on 8*n, that is, f8 = {(0,0) (1,8) (2,16), (3, 24), ...} is a function from N to E. And it is one-one. But it is not onto. The number 4 in E remains untouched by it, like 6, or 66, or 82, and many other numbers in E. To find a bijection between N and E, just search for a function which is one and onto, from N to E. 4) Key questions for the sequel, on which you can meditate: - is there a bijection between N and NxN? (NxN = the cartesian product of N with N) - is there a bijection between N and N^N? New exercises for the adventurous: In the context of sets, 2
Re: The seven step series
Bruno Marchal wrote: ... 4) Key questions for the sequel, on which you can meditate: - is there a bijection between N and NxN? (NxN = the cartesian product of N with N) - is there a bijection between N and N^N? You're making me think, Bruno. :-) A bijection between N and NxN can be constructed by enumerating all the N pairs summing to 0, followed by those summing to 1, followed by those summing to 2 as follows (per Cantor): N - NxN 1 0,0 2 1,0 3 0,1 4 2,0 5 1,1 6 0,2 7 3,0 8 2,1 9 1,2 10 0,3 ... New exercises for the adventurous: In the context of sets, 2 will represent the set {0, 1}. OK? And 3 will represent {0, 1, 2}, etc. Find a bijection between NxN and N^2 this means find a bijection between NXN and the set of functions from 2(= {0,1}) to N. Since there are two elements in the domain {0,1}, if we write down all pairs of numbers (n,m) and map 0 to the first and 1 to the second we will have constructed all functions from 2 to N. But above we've already enumerated all pairs of numbers, NxN. So we just map 0 to the number in first one and 1 to the second and we have an enumerated list of the functions from 2 to N. N - NxN - N^2 1 0,0 {(0,0) (1,0)} 2 1,0 {(0,1) (1,0)} 3 0,1 {(0,0) (1,1)} 4 2,0 {(0,2) (1,0)} 5 1,1 {(0,1) (1,1)} 6 0,2 {(0,0) (1,2)} 7 3,0 ... 8 2,1 9 1,2 10 0,3 ... Define NxNxN by Nx(NxN), with (x,y,z) represented (bijectively) by (x, (y,z)) OK? Find a bijection between NxNxN and N^3 Show that there is a bijection between NxNxNxNxNx ... xN (m times) and N^m, in the sense of above. That is NxNxNxNxNx ... xN is defined by Nx(Nx(Nx ... ), and N^m is the set of functions from m to N, and m = {0, 1, ... m-1}. First note that we can use the mapping NxN - N to reduce NxNx...xN (m times) to NxNx...xN (m-1 times) by substituting for a pair in NxN the number from N determined by the above bijection. So we can construct a bijection NxNx...xN - N. Second, N^m is the set of mappings from m to all m-tuples of numbers to N. So if we write down the m-tuples, i.e. the elements of NxNx...xN (m times) as we did the pairs above and then for each m-tuple map 0 to the first element, 1 to the second, and so forth up to the mth element we will have constructed all the functions N^m and we will have enumerated them, i.e. shown a bijection between N^m and N. Since bijection is transitive, this also shows there is a bijection between NxNx...xN (n times) and N^m (n and m not necessarily equal). For the very adventurous: Find a bijection between NxNxNx and N^N? Hmmm? I could say I've already proven it above or that it follows from the above by induction, but the scheme would require writing down infinitely many infinite lists so I'm not sure the above proof generalizes to N^N. Brent Despite perhaps the appearances, all those new exercises are rather easy. The above in "4)" key questions are more difficult. Oh! I forget to ask you the simplest exercise : Find a bijection between N and N^1, with 1 = {0}. N^1 is of course the set of functions from 1 to N, i.e. from {0} to N. Don't worry, if this last exercise didn't give the clue (for the new exercises), I will explain why this new exercises are really simple, and why it is simpler than the key questions. OK, this is food for friday and the week-end, Ask any questions, or do any remarks. We approach surely to the first big theorem (Cantor). Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
There is an explicit formula that maps N onto Q.. I found it some years back. Brent Meeker wrote: Bruno Marchal wrote: ... 4) Key questions for the sequel, on which you can meditate: - is there a bijection between N and NxN? (NxN = the cartesian product of N with N) - is there a bijection between N and N^N? You're making me think, Bruno. :-) A bijection between N and NxN can be constructed by enumerating all the N pairs summing to 0, followed by those summing to 1, followed by those summing to 2 as follows (per Cantor): N - NxN 1 0,0 2 1,0 3 0,1 4 2,0 5 1,1 6 0,2 7 3,0 8 2,1 9 1,2 10 0,3 ... New exercises for the adventurous: In the context of sets, 2 will represent the set {0, 1}. OK? And 3 will represent {0, 1, 2}, etc. Find a bijection between NxN and N^2 this means find a bijection between NXN and the set of functions from 2(= {0,1}) to N. Since there are two elements in the domain {0,1}, if we write down all pairs of numbers (n,m) and map 0 to the first and 1 to the second we will have constructed all functions from 2 to N. But above we've already enumerated all pairs of numbers, NxN. So we just map 0 to the number in first one and 1 to the second and we have an enumerated list of the functions from 2 to N. N - NxN - N^2 1 0,0 {(0,0) (1,0)} 2 1,0 {(0,1) (1,0)} 3 0,1 {(0,0) (1,1)} 4 2,0 {(0,2) (1,0)} 5 1,1 {(0,1) (1,1)} 6 0,2 {(0,0) (1,2)} 7 3,0 ... 8 2,1 9 1,2 10 0,3 ... Define NxNxN by Nx(NxN), with (x,y,z) represented (bijectively) by (x, (y,z)) OK? Find a bijection between NxNxN and N^3 Show that there is a bijection between NxNxNxNxNx ... xN (m times) and N^m, in the sense of above. That is NxNxNxNxNx ... xN is defined by Nx(Nx(Nx ... ), and N^m is the set of functions from m to N, and m = {0, 1, ... m-1}. First note that we can use the mapping NxN - N to reduce NxNx...xN (m times) to NxNx...xN (m-1 times) by substituting for a pair in NxN the number from N determined by the above bijection. So we can construct a bijection NxNx...xN - N. Second, N^m is the set of mappings from m to all m-tuples of numbers to N. So if we write down the m-tuples, i.e. the elements of NxNx...xN (m times) as we did the pairs above and then for each m-tuple map 0 to the first element, 1 to the second, and so forth up to the mth element we will have constructed all the functions N^m and we will have enumerated them, i.e. shown a bijection between N^m and N. Since bijection is transitive, this also shows there is a bijection between NxNx...xN (n times) and N^m (n and m not necessarily equal). For the very adventurous: Find a bijection between NxNxNx and N^N? Hmmm? I could say I've already proven it above or that it follows from the above by induction, but the scheme would require writing down infinitely many infinite lists so I'm not sure the above proof generalizes to N^N. Brent Despite perhaps the appearances, all those new exercises are rather easy. The above in 4) key questions are more difficult. Oh! I forget to ask you the simplest exercise : Find a bijection between N and N^1, with 1 = {0}. N^1 is of course the set of functions from 1 to N, i.e. from {0} to N. Don't worry, if this last exercise didn't give the clue (for the new exercises), I will explain why this new exercises are really simple, and why it is simpler than the key questions. OK, this is food for friday and the week-end, Ask any questions, or do any remarks. We approach surely to the first big theorem (Cantor). Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 11 Aug 2009, at 22:24, Mirek Dobsicek wrote: Well, A^B is the set of functions from B to A. By definition of set exponentiation. I'd just like to point out that Bruno in his previous post in the seven step serii made a small typo A^B - the set of all functions from A to B. It should have been from B to A. The latest post is correct in this respect. And now Simplicius is coming back and asks: but why do you define the exponentiation of sets, A^B, by the set of functions from B to A?. The answer of the sadistic teacher: this is a DEFINITION, and is part of the program. If you have complains about the program, write a letter to the minister of education. Hmm... A better answer is given by the solution of the preceding exercise: If card(A) = n, and card(B) = m. What is card(A^B)? It happens that if A^B is defined as the set of functions from B to A, then card(A^B) is given by card(A)^card(B) How many functions exist from a set with m elements in a set with n elements? n^m. Hope you see that n^m is NOT equal to m^n (when n and m are different). 3^4 = 3x3x3x3 = 81, and 4^3 = 4x4x4 = 64. 2^7 = 128, 7^2 = 49. In that way, A^B generalizes for set what n^m is for numbers. And why card(A^B) = card(A)^card(B) ? You can see this in the following way: let card(A) = m, and card(B) = n. We must understand why card(A^B) = n^m. For example a function from {a, b, c, d, e, f, g} in {0, 1, 2, 3, 4}. To fix the idea. So m = 7, and n = 5. OK? Let us build an arbitrary function F. Well,we begin with F = {(a, ..., and we have to say where a is sent. We have five (n) choices, and then we have to choose where b is sent, and we have again n choices, and for each first choice any second choice is acceptable so we have 5 (n) choices multiplied by 5 (n) choices, itself multiplied by 5 (n) choices, as many times there are elements in the starting set, that is 7 (m). This gives 5 x 5 x 5 x 5 x 5 x 5 x 5, that is 5^7. or more generally n x n x n x n x ... x n, m times. OK? We will be interested in N^N. That is, the set of functions from N to N. The set of computable functions will be an important subset of that set. Let me give a precise definition of bijection, as I promise. I need two rather useful definitions. - I will say that a function from A to B is ONTO, if all elements of B appears in the couples of the function. Note that card(B) has to be less or equal to card(A) to make that possible, by the functional condition. - I will say a function is ONE-ONE, if two different elements of A are sent to two different elements of B. Note that card(A) has to be less or equal to card(B) to make that possible. The condition one-one is the reverse of the functional condition. The functional conditions says that an element cannot be sent on two different elements (a time cannot give two temperature!), and the one- one condition says that two different elements cannot be sent on one element. Exercises: build many examples with little finite sets. You may search examples for infinite sets. OK. The definition of bijection. I will say that a function is a bijection between A and B if it is both a function ONTO from A to B, and a function ONE-ONE from A to B. we say more quicky that f is a bijection if f is both onto and one-one. Exercises: for 2) below, the real needed exercise is: do you understand the question? Unless you like to count things, but such skills are not needed for the sequel. 1) Convince yourself that if A and B are finite sets, then there exists a bijection between A and B if and only if card(A) = card(B). 2) If A has n elements (card(A) = n), how many bijections exists from A to B? Again start with simple examples, and try to generalize. For example, how many bijections from {a, b, c} to {1, 2}. How many bijections from (a, b, c} to {a, b, c}? 3) can you find, or define a bijection between the infinite set N, and the infinite set E = {0, 2, 4, 6, 8, ...} (E for even). 4) Key questions for the sequel, on which you can meditate: - is there a bijection between N and NxN? (NxN = the cartesian product of N with N) - is there a bijection between N and N^N? Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
3) compute { } ^ { } and card({ } ^ { }) If card(A) = n, and card(B) = m. What is card(A^B)? I find it neat to write | {} ^ {} | = | { {} } | = 1 :-) It's almost like ASCII art. Just wanted to signal that I'm following. mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 11 Aug 2009, at 15:32, Mirek Dobsicek wrote: 3) compute { } ^ { } and card({ } ^ { }) If card(A) = n, and card(B) = m. What is card(A^B)? I find it neat to write | {} ^ {} | = | { {} } | = 1 :-) You will make panic those who are not familiar with symbols! It's almost like ASCII art. Just wanted to signal that I'm following. Thank for telling me. OK, people, good time to solve the problems. Please don't read this post, unless you find it is the good time for you to do some math. If not, postpone until a good time. Technical posts have to be studied, not read. Take the time needed. Tell me if I am too quick. The solution of 3) has been given. Let us look at: If card(A) = n, and card(B) = m. What is card(A^B)? card(A) = n This means A is a finite set with n elements. card(B) = m This means B is a finite set with m elements. Let us simplify by supposing that m = 3, and n = 2. Hoping that the reasoning done for finding the solution on the particular case will inspire the reasoning for finding the solution in the general case. Let us imagine that A is the set {a, b, c}, with its three elements, and that B is the set {1, 2}, with its two elements. And let us try now to remember what is the question. The question is: what is card(A^B)? Well, card(A^B) is the number of elements of A^B. By definition of the cardinal. What is A^B? Well, A^B is the set of functions from B to A. By definition of set exponentiation. Well, if the question was just what is card(A^B)?, this would provide the best solution, or the best note if you want. But the teacher provided the information that A has n elements, and that B has m elements, and intuitively we can bet that the number of functions from a set to another can depend on the number of elements of each sets involved, so that what is card( A^B)? meant probably how to compute card(A^B) in function of card(A) and card(B). Ok, we decided to look on the particular case with A = {a, b, c}, and B = {1, 2}. A^B = the set of all functions from B to A. That is the set of functions from {1, 2} to {a, b, c}. Well, let us try to find, or to build, one function from B to A. But , here a moment of panic can occur, (empirical observation). For the unnameable sake, what *is* a function? What is a function from B to A. Well, if it is an open manual home work, such panic can be eased by looking in the math notes. You may remember the motivation or the informal sense of what a function represents, which is a relation of dependency, and this is in the most general sense, so that all possible dependency are tolerated. For a function from B to A, it means the element of A depends in function of the elements of B. Such a dependency is well described by a couple (x, y) with x in B and y in A. we have (x,y) belongs-to F representing the meaning that y depends in the function F of x. Think about x as time and y as temperature. So, a function from B to A is just a set of couples (x, y) with x in B and y in A, with the functional restriction that x is not send to two different values y. At each time x, you can have only one temperature y. That is, here: a set of couples (x, y) with x in {1, 2} and y in {a, b, c}, and such that if (1, x) belongs-to F, no other (1, y) belongs to F. Let us build one function from {1, 2} to {a, b, c}. OK, 1, from B, can determine what in A ? Well, we have three possibilities a, b and c. OK, i will use my free will to decide that for this function I want now, 1 will determine a. So I put the couple (1, a) in the function. At this stage, the function looks like {(1, a)}. Finished? No, a function from a set to another one gives a values, outcomes, outputs for all elements of its domain. I have to say what is determine by 2, in B. OK, I will use my free will again, and decide to add the couples (2, a). At this stage, the function looks like {(1, a) (2, a)}. Finished? Yes. We do have a function from B to A. The set {(1, a) (2, a)} describes completely a function from B to A, a so-called constant function. think of 1 and 2 as moment of times, and think of a, b, c, as possible temperature. The function {(1, a) (2, a)} describe a case here the temperature is constant and equal to a. Finished? No, we have to find all functions from B to A. All functions from {1, 2} to {a, b, c}. Well actually, we need to find only the number of such functions. For 1 I have three choices, then for 2, I have still three choices, and the choices are independent, so that for each choice the remaining three choice will lead to distinct functions, this make 3 X 3 functions = 9 functions: {(1, a) (2, a)} {(1, a) (2, b)} {(1, a) (2, c)} {(1, b) (2, a)} {(1, b) (2, b)} {(1, b) (2, c)} {(1, c) (2, a)} {(1, c) (2, b)} {(1, c) (2, c)} so A^B = {{(1, a) (2, a)}, {(1, a) (2, b)}, {(1, a) (2, c)}, ... , {(1, c) (2, c)}}, and card(A^B) = 9. In this case. This give
Re: The seven step series
On 11 Aug 2009, at 22:24, Mirek Dobsicek wrote: Well, A^B is the set of functions from B to A. By definition of set exponentiation. I'd just like to point out that Bruno in his previous post in the seven step serii made a small typo A^B - the set of all functions from A to B. I wrote that? I was wrong. Thanks for saying. It should have been from B to A. Yes! The latest post is correct in this respect. Thank God! Apologies for typos, mispelling, and believe me, I can do even bigger mistakes. I will. Be vigilant. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Mirek, On 05 Aug 2009, at 00:52, Mirek Dobsicek wrote: I've ordered the dialogue from a second-hand book shop :-) The Stanford encyclopedia says Arguably, it is his (Plato) greatest work on anything. So I'll give it a try :-) I love that book, and it is also my favorite piece of Plato. To be sure, I don't think it is needed to understand neither UDA nor AUDA, but it can help. This is probably the key problem for me. I know next to nothing about provability, the logic of provability, PA/ZF provers. I know that quite often you reference Boolos 1993 - The Logic of Provability. I took a look at it at Google Books preview but ... there is something missing in my education. From the beginning I am puzzled with Why?, what?. What a headache :-) You miss an introductory course on mathematical logic. Have you herad about Gödel's incompletness theorem. Boolos book explains the sequel. I thought that, after Hofstadter best selling book on Gödel's theorem (Gödel, Escher, Bach), it would be possible to talk on mathematical logic to the layman, like we can talk on physics to the layman. But I was wrong. Gödel's theorem is not yet part of the common knowledge, and when it is used by non mathematician, in general it is abused. x divides y if and only if it exists a number z such that y = x*z. I don't dare to correct your english but there is/exists a number ... is what I would write. Thanks. Ad 3) If natural numbers and their relations are the only entities which do exist then me, you, everything is a recipe of a Turing-computable number. No. Not at all. Sorry. Gosh, you will be very surprised if you follow the UDA-7. On the contrary. Arithmetical truth VASTLY extends the computable domain. Most relations between numbers are not Turing emulable. Aha! Then I really have a wrong mental picture of your work. I understood to arithmetical realism along the lines of this quotation from the Stanford article on realism: According to a platonist about arithmetic, the truth of the sentence '7 is prime' entails the existence of an abstract object, the number 7. This object is abstract because it has no spatial or temporal location, and is causally inert. A platonic realist about arithmetic will say that the number 7 exists and instantiates the property of being prime independently of anyone's beliefs, linguistic practices, conceptual schemes, and so on. That is quite correct. All mathematicians are realist about arithmetic, and most are realist about sets. But set realism is a much more stronger belief than arithmetical realism. Comp necessitates arithmetical realism if only to be able to state Church thesis. Theoretical computer scientist are realist, because they belief that all machine either stop or not stop. So I thought that you essentially take a) Numbers and their properties and relations exists. Yes, but some people put to much sense in exists. It is the mathematical usual sense, like when you derive there exists a prime number from the statement 17 is a prime number. No need to invoke Plato Heaven, in the assumption. b) Now, since you don't assume existence of anything else = your body, your bike and coffee must emerge as patterns in the world of numbers. I am agnostic. I assume neither that something else exists nor that it does not exist, and then I prove from the assumption that we are turing emulable, that physics is no more the fundamental science. I prove that if we are machine then matter has to be an emerging epistemological concept, and physics is a branch of machine biology/ psychology/theology, or mathematical computer science. b) is obviously non valid. The fact that bike an coffee must emerge from numbers is really the conclusion of the whole UD reasoning. It is not because I don't assume them, it is because their independent existence is shown contradictory. I show that mechanism makes physicalism epistemologically inconsistent. Even if matter really exists, it cannot be used to justify our belief in matter. A slight application of Occam razor eliminates matter, at that stage. c) Taking the Church-Turing thesis, these patterns are Turing- computable. Not at all. The world of number is provably not Turing-computable. Only a very tiny part of the world of number is computable. There is a whole branch of mathematical logic devoted to the study of the degree of non computability of the relations existing among the numbers. Church thesis asserts only that the *computable* patterns are Turing computable. It is just the assertion that Turing computability can be used to define computability. d) Definitely, the vast majority of all patterns is not Turing- computable. I don't understand. This is how I have thought about your working framework. Notice, that I don't talk about what you try to show, argue for, want to end up with etc. My framework,
Re: The seven step series
Bruno, just to take off some mal-deserved feathers: I think Theaetetus has two different 'e' sounds one after the other (anybody can pronounce him better?) and in Hungarian we have them (' e ' like in 'have' and e' like in 'take') with a 3rd variation where the accent is not applied: a closed and an open ' e ' sound (instrumental in dialects). So I have no problem to pronounce the discussing gentleman as The'-etetus. Maybe he called himself (?) Te-aythetos? Ask Plato you are close to him. (And I always proudly thought that Hungarian - vs. English - has a simple vowel-code in an unchanging uniform pronunciation...). German proverb: Fremdworter sind glucksache (= foreign words are a matter of luck). A friend added: you can NEVER know what they mean. John On Tue, Aug 4, 2009 at 11:06 AM, Bruno Marchal marc...@ulb.ac.be wrote: John, Thanks for those informations. I thought that the æ was just a french, if not an old french, usage. Note that when I wrote Theatetus, it is just a mispelling. I tend to forget that second e, but your remark will help me to remind it. Note that Miles Burnyeat, in his book The Theaetetus of Plato, and Levett in his traduction wrote simply Theaetetus. But in french too, more and more people forget to attach the o and e in words like oeuvre, or soeur (sister). Bruno On 04 Aug 2009, at 15:05, John Mikes wrote: Bruno and Mirek, concerning Theateticus vs. Theaeteticus: in my strange linguistic background I make a difference betwee ai and ae - the spelling in Greek and Latin of the name. As far as I know, nobody knows for sure how did the 'ancient' Greeks pronounce their ai - maybe as the flat 'e' like in German lehr while the 'e' pronounciation might have been clsoer to (between) 'make' and 'peck' - the reason why the Romans transcribed it by their *ONE letter* *ae,* (lehr) and not as English would read: *'a'+'ee'*. The spelling you gave points to this latter. The Latin 'ae' is not TWO separate letters (a+e), it is a twin, as marked in the Wiki article ...*Theætetus... **and not Theaetetus * which looked strange to me from the beginning . *(I wonder if the e-mail reproduces the (ae) one sign? look up in Wiki's Theaetetus Dialogue (in the title with the wrong spelling) the 1st line brings the merged-together double 'æ'.) * *** *English spelling always does a job on classical words, the Greek 'oi' has been transcribed into Latin sometimes as 'oe' and pronounced as in girl (oeuvre) while many think it was a sound like what the pigs say: as oy. then comes America, with it's Phoenix (pron: feenix) * I don't think the Romans were much better off, centuries after and a world apart from the ancient (classical for them) Greeks. And who knows today if the great orator was Tzitzero or Kikero to turn later into Tchitchero? *** *The Old Man did quite a job on us at the tower of Babel. * *** *[[ - I am enjoying your 'other' post where you spelled out my own vocabulary as indeed thinking functions as relations, lately not as a static description, but also the interchanging factor - ]]* ** *John* http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Bruno and Mirek, concerning Theateticus vs. Theaeteticus: in my strange linguistic background I make a difference betwee ai and ae - the spelling in Greek and Latin of the name. As far as I know, nobody knows for sure how did the 'ancient' Greeks pronounce their ai - maybe as the flat 'e' like in German lehr while the 'e' pronounciation might have been clsoer to (between) 'make' and 'peck' - the reason why the Romans transcribed it by their *ONE letter* *ae,* (lehr) and not as English would read: *'a'+'ee'*. The spelling you gave points to this latter. The Latin 'ae' is not TWO separate letters (a+e), it is a twin, as marked in the Wiki article ...*Theætetus... **and not Theaetetus * which looked strange to me from the beginning . *(I wonder if the e-mail reproduces the (ae) one sign? look up in Wiki's Theaetetus Dialogue (in the title with the wrong spelling) the 1st line brings the merged-together double 'æ'.) * *** *English spelling always does a job on classical words, the Greek 'oi' has been transcribed into Latin sometimes as 'oe' and pronounced as in girl (oeuvre) while many think it was a sound like what the pigs say: as oy. then comes America, with it's Phoenix (pron: feenix) * I don't think the Romans were much better off, centuries after and a world apart from the ancient (classical for them) Greeks. And who knows today if the great orator was Tzitzero or Kikero to turn later into Tchitchero? *** *The Old Man did quite a job on us at the tower of Babel. * *** *[[ - I am enjoying your 'other' post where you spelled out my own vocabulary as indeed thinking functions as relations, lately not as a static description, but also the interchanging factor - ]]* ** *John* On Mon, Aug 3, 2009 at 4:55 AM, Bruno Marchal marc...@ulb.ac.be wrote: On 02 Aug 2009, at 23:20, Mirek Dobsicek wrote: I am in a good mood and a bit picky :-) Do you know how many entries google gave me upon entering Theaetetical -marchal -bruno Well 144? Good way to find my papers on that. The pages refer quickly to this list or the FOR list. I am sorry for the delay, I've just got back from my vacation. Hmm. The above written search should not return any references to your papers/letters as the minus sign in front of your name asks for an exclusion. Given that it works as supposed google then gives only 1 hit in my location (Sweden). That hit is a translation of the word Theaetetical into some eastern characters. Thus, I end up with zero meaningful hits and a feeling that you might be the only one using this word. That makes me insists a little bit more (in a very polite way) that, occasionally, your work is difficult to read unless one is willing to undertake long discussions, clarifications and position adjustments. I am writing this in a reference to your complains that sometimes you have troubles to get enough relevant feedback to your work. Come on Mirek: Theaetetical is an adjective I have forged from Theatetus. Theatetus gives 195.000 results on Google. Theatetus wiki 4310. By theatetical notion of knowledge, I mean the well known attempts to define knowledge by Theaetetus in Plato's Theaetetus. The most known definition is truye justified belief, that Bill taylor just mentionned on the FOR list recently as: This old crock should have been given a decent burial long ago. I guess I will have to make a comment ... My work is, without doubt, very difficult to read because it crosses three or four fields: mathematical logic, philosophy of mind and computer science; + quantum mechanics to evaluate the plausibility of the derived computationalist physics. This does not help in an epoch of hyper-specialization. I am also using a deductive approach in the philosophy of mind. I am apparently the first to *postulate* mechanism. Most philosophers of mind accept mechanism as the only rational theory, or reject it with some passion. Few, if any, use it as an hypothesis, in a deductive strategy. Then mathematical logic is virtually unknown, except by mathematical logicians, who, for historical reasons, do not want to come back to the earlier philosophical motivations: they want to be accepted as pure mathematicians. Except the philosophical logicians, who in majority criticized classical logic, and see philosphy as a mean to criticize classical philosophy. Mathematicians are so used to classical philosophy, that they consider it as science, and hate to be remind that this is still a philosophical. I have no feedback for purely contingent reason related to facts which have nothing to do with the startling feature of the conclusion of the reasoning. Up to now, I heard continuously about critics on an imaginary work I have never done. The price of the best PhD thesis that I got in France has eventually only spread those rumor from Brussels to elsewhere. All real scientist who have studied my work and have accepted to meet me, or to write a real
Re: The seven step series
Come on Mirek: Theaetetical is an adjective I have forged from Theatetus. Theatetus gives 195.000 results on Google. Theatetus wiki 4310. Of course, after all you reference the dialogue Theaetetus in your papers thus one can easily match the word Theaetetical agains it. Let me quickly summarize the experience I had with theatetical notion of knowledge while reading one of your papers for the first time. Maybe I am an ignorant, then shame on me, but I have not read the Theaetetus. So I took a look at the Wikipedia and read In this dialogue, Socrates and Theaetetus discuss three definitions of knowledge: knowledge as nothing but perception, knowledge as true judgment, and, finally, knowledge as a true judgment with an account. Each of these definitions are shown to be unsatisfactory. Hmm that really helps .., I told to myself and continued with reading. With an uneasy feeling of stepping into the water I eventually settled down to conclusion that you likely mean something as true justified belief. I really wished you wrote it more straightforwardly without turning your readers quite unnecessarily down to the Theaetetus and inventing new words such as Theaetetical. Anyway, I'd like to stop discussing this issue :-) since my only point was to give you a hint why I said that it is not easy to read your papers/letters. Feel free to ask for any clarification, position adjustments, question, at any level ...Do you understand what is the comp hypothesis? Let us see if I get it right. Your comp hypothesis is 1) I'm a machine, 2) Each possible computation is Turing-computable, 3) Natural numbers and their relations do exist. This should not be confused with other quite common comp hypothesis that the universe is a big computer. This hypothesis entails the existence of a physical computer. Ad 1) I take the position that I is only a convenient temporary pointer to a part of universe. The pointer Socrates' thoughts is of the same quality. Ad 2) Breath taking. While 1) and 3) are assumptions of the kind OK, let's think for a while that ..., 2) has the status of a thesis. I don't have any firm position on what could an objective reality be (and without a justification I tend to think it is inaccessible to us), but if there is any objective reality, 2) could be a statement about it. Ad 3) If natural numbers and their relations are the only entities which do exist then me, you, everything is a recipe of a Turing-computable number. OK, that is it. This is how I understand to your starting assumptions. Mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
John, Thanks for those informations. I thought that the æ was just a french, if not an old french, usage. Note that when I wrote Theatetus, it is just a mispelling. I tend to forget that second e, but your remark will help me to remind it. Note that Miles Burnyeat, in his book The Theaetetus of Plato, and Levett in his traduction wrote simply Theaetetus. But in french too, more and more people forget to attach the o and e in words like oeuvre, or soeur (sister). Bruno On 04 Aug 2009, at 15:05, John Mikes wrote: Bruno and Mirek, concerning Theateticus vs. Theaeteticus: in my strange linguistic background I make a difference betwee ai and ae - the spelling in Greek and Latin of the name. As far as I know, nobody knows for sure how did the 'ancient' Greeks pronounce their ai - maybe as the flat 'e' like in German lehr while the 'e' pronounciation might have been clsoer to (between) 'make' and 'peck' - the reason why the Romans transcribed it by their ONE letter ae, (lehr) and not as English would read: 'a'+'ee'. The spelling you gave points to this latter. The Latin 'ae' is not TWO separate letters (a+e), it is a twin, as marked in the Wiki article ...Theætetus... and not Theaetetus which looked strange to me from the beginning . (I wonder if the e-mail reproduces the (ae) one sign? look up in Wiki's Theaetetus Dialogue (in the title with the wrong spelling) the 1st line brings the merged-together double 'æ'.) * English spelling always does a job on classical words, the Greek 'oi' has been transcribed into Latin sometimes as 'oe' and pronounced as in girl (oeuvre) while many think it was a sound like what the pigs say: as oy. then comes America, with it's Phoenix (pron: feenix) I don't think the Romans were much better off, centuries after and a world apart from the ancient (classical for them) Greeks. And who knows today if the great orator was Tzitzero or Kikero to turn later into Tchitchero? * The Old Man did quite a job on us at the tower of Babel. * [[ - I am enjoying your 'other' post where you spelled out my own vocabulary as indeed thinking functions as relations, lately not as a static description, but also the interchanging factor - ]] John http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Mirek, Long and perhaps key post. On 04 Aug 2009, at 15:32, Mirek Dobsicek wrote: Come on Mirek: Theaetetical is an adjective I have forged from Theatetus. Theatetus gives 195.000 results on Google. Theatetus wiki 4310. Of course, after all you reference the dialogue Theaetetus in your papers thus one can easily match the word Theaetetical agains it. Let me quickly summarize the experience I had with theatetical notion of knowledge while reading one of your papers for the first time. Maybe I am an ignorant, then shame on me, but I have not read the Theaetetus. There is no shame in being ignorant. Only in staying ignorant :) I feel a bit sorry with my last post. I hate to look like patronizing, but it is a professional deformation. Apology. Note that all the Theaetetus' stuff is really needed just to motivate the arithmetical definition of the knower, alias the first person, alias the universal soul, and this concerns AUDA (the arithmetical UDA), which should be done normally after getting straight the UDA's point, ... unless you are mathematical logician, who are the only one who can find AUDA more easy than UDA. So I took a look at the Wikipedia and read In this dialogue, Socrates and Theaetetus discuss three definitions of knowledge: knowledge as nothing but perception, knowledge as true judgment, and, finally, knowledge as a true judgment with an account. Each of these definitions are shown to be unsatisfactory. Socrates asks Theaetetus to define knowledge. That is a very difficult question. Then Socrates shows that all attempts made by Theaetetus lead to difficulties. He literally concludes that the problem is open, and this is debated in the philosophical literature since then. The remarkable thing is that if you accept to modelize account by sound machine provability, which can be done for the not too complex machine, like Peano Arithmetic provers, or Zermelo Fraenkel Set Theory prover, the definitions of Theaetetus make sense, and can be use to show, at least, that many philosopher are deductively invalid in their critics. Actually, even the critics by Socrates have to be weakened. All the arithmetical hypostases (in the Plotinus paper) are variant of Theaetetus definition. The main one (corresponding to Plotinus primary hypostases) are the following one: p (the truth of p) Bp (the provability of p, the account of p) Bp p (the provability of p when p is true) The amazing thing is that the incompleteness theorem can be used to show that, about sound machine, we have Bp - Bp p. But this equivalence is true but not provable by the machine, making the ideal knower already obeying a different logic than the ideal prover. This introduces a non trivial notion of first person for the machines. If you remember G and G*, the equivalence between proof and knowledge belongs to G* minus G. The corona of the true but unprovable (by the machine) statements. Yet they prove (know) the same arithmetical p, yet, from those points of view, it appears very different. Hmm that really helps .., I told to myself and continued with reading. With an uneasy feeling of stepping into the water I eventually settled down to conclusion that you likely mean something as true justified belief. I have found dozen of different translations, in french and in english, of the greek expressions. I really wished you wrote it more straightforwardly without turning your readers quite unnecessarily down to the Theaetetus and inventing new words such as Theaetetical. In french students are burned alive if they dare to create new adjective, and I thought that in English we have more freedom, but I may be wrong. Sorry. Anyway, I'd like to stop discussing this issue :-) since my only point was to give you a hint why I said that it is not easy to read your papers/letters. There are other reasons, if only the difficulty of the subject. Feel free to ask for any clarification, position adjustments, question, at any level ...Do you understand what is the comp hypothesis? Let us see if I get it right. Your comp hypothesis is 1) I'm a machine, OK. This of course could be interpreted in many ways, and that is why I have introduce the quasi-operational yes doctor. It makes clear hat the I is the conscious first person I, not the third person body. 2) Each possible computation is Turing-computable, OK. That is Church thesis. Very few people doubt it, but it is a refutable statement. If a human find a well defined function with an account of how human can compute it, but no machine can, then CT will be refuted. Only Kalmar did pretend to have such a function, but eventually his function was not well defined. 3) Natural numbers and their relations do exist. This is arithmetical realism. Just a way to prevent infinite discussion about intutionism and ultrafinitism. It is no more than the belief of
Re: The seven step series
Hi Bruno, Bruno Marchal wrote: Hi Mirek, Long and perhaps key post. Thank you a lot for a prompt and long reply. I am digesting it :-) Just some quick comments. There is no shame in being ignorant. Only in staying ignorant :) I've ordered the dialogue from a second-hand book shop :-) The Stanford encyclopedia says Arguably, it is his (Plato) greatest work on anything. So I'll give it a try :-) judgment, and, finally, knowledge as a true judgment with an account. The remarkable thing is that if you accept to modelize account by sound machine provability, This is probably the key problem for me. I know next to nothing about provability, the logic of provability, PA/ZF provers. I know that quite often you reference Boolos 1993 - The Logic of Provability. I took a look at it at Google Books preview but ... there is something missing in my education. From the beginning I am puzzled with Why?, what?. What a headache :-) In french students are burned alive if they dare to create new adjective, and I thought that in English we have more freedom, but I may be wrong. Sorry. I'd grant this freedom to rational native speakers only :-) x divides y if and only if it exists a number z such that y = x*z. I don't dare to correct your english but there is/exists a number ... is what I would write. Ad 3) If natural numbers and their relations are the only entities which do exist then me, you, everything is a recipe of a Turing-computable number. No. Not at all. Sorry. Gosh, you will be very surprised if you follow the UDA-7. On the contrary. Arithmetical truth VASTLY extends the computable domain. Most relations between numbers are not Turing emulable. Aha! Then I really have a wrong mental picture of your work. I understood to arithmetical realism along the lines of this quotation from the Stanford article on realism: According to a platonist about arithmetic, the truth of the sentence '7 is prime' entails the existence of an abstract object, the number 7. This object is abstract because it has no spatial or temporal location, and is causally inert. A platonic realist about arithmetic will say that the number 7 exists and instantiates the property of being prime independently of anyone's beliefs, linguistic practices, conceptual schemes, and so on. So I thought that you essentially take a) Numbers and their properties and relations exists. b) Now, since you don't assume existence of anything else = your body, your bike and coffee must emerge as patterns in the world of numbers. c) Taking the Church-Turing thesis, these patterns are Turing-computable. d) Definitely, the vast majority of all patterns is not Turing-computable. This is how I have thought about your working framework. Notice, that I don't talk about what you try to show, argue for, want to end up with etc. Cheers, Mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 02 Aug 2009, at 23:20, Mirek Dobsicek wrote: I am in a good mood and a bit picky :-) Do you know how many entries google gave me upon entering Theaetetical -marchal -bruno Well 144? Good way to find my papers on that. The pages refer quickly to this list or the FOR list. I am sorry for the delay, I've just got back from my vacation. Hmm. The above written search should not return any references to your papers/letters as the minus sign in front of your name asks for an exclusion. Given that it works as supposed google then gives only 1 hit in my location (Sweden). That hit is a translation of the word Theaetetical into some eastern characters. Thus, I end up with zero meaningful hits and a feeling that you might be the only one using this word. That makes me insists a little bit more (in a very polite way) that, occasionally, your work is difficult to read unless one is willing to undertake long discussions, clarifications and position adjustments. I am writing this in a reference to your complains that sometimes you have troubles to get enough relevant feedback to your work. Come on Mirek: Theaetetical is an adjective I have forged from Theatetus. Theatetus gives 195.000 results on Google. Theatetus wiki 4310. By theatetical notion of knowledge, I mean the well known attempts to define knowledge by Theaetetus in Plato's Theaetetus. The most known definition is truye justified belief, that Bill taylor just mentionned on the FOR list recently as: This old crock should have been given a decent burial long ago. I guess I will have to make a comment ... My work is, without doubt, very difficult to read because it crosses three or four fields: mathematical logic, philosophy of mind and computer science; + quantum mechanics to evaluate the plausibility of the derived computationalist physics. This does not help in an epoch of hyper-specialization. I am also using a deductive approach in the philosophy of mind. I am apparently the first to *postulate* mechanism. Most philosophers of mind accept mechanism as the only rational theory, or reject it with some passion. Few, if any, use it as an hypothesis, in a deductive strategy. Then mathematical logic is virtually unknown, except by mathematical logicians, who, for historical reasons, do not want to come back to the earlier philosophical motivations: they want to be accepted as pure mathematicians. Except the philosophical logicians, who in majority criticized classical logic, and see philosphy as a mean to criticize classical philosophy. Mathematicians are so used to classical philosophy, that they consider it as science, and hate to be remind that this is still a philosophical. I have no feedback for purely contingent reason related to facts which have nothing to do with the startling feature of the conclusion of the reasoning. Up to now, I heard continuously about critics on an imaginary work I have never done. The price of the best PhD thesis that I got in France has eventually only spread those rumor from Brussels to elsewhere. All real scientist who have studied my work and have accepted to meet me, or to write a real report on it, have understood it. True, some took a rather long time to understand, but that is normal: the subject matter is very complex, and still taboo, especially for the atheists, and other religious-based thinkers. But when they study it, they quickly discover that I use the scientific method, that is I am just asking a question, what is wrong with the following reasoning? ... The reasoning is decomposed in easy steps, so people accepting (for personal belief or for the sake of the argument) the hypotheses and wanting to reject the conclusion have a way to put their fingers on some problems. UDA has been judged to obvious and simple in Brussels, and that is why I have augmented the thesis with the AUDA, which unfortunately is considered as ... too much simple for logicians, and too much difficult for non logicians. But AUDA is not needed at all to understand the simple and clear result: if we are digitalisable machine, the laws of physics emerge from a statistics on computations, in a verifiable way (quantitatively and qualitatively). The result is very simple and clear: the reasoning which leads to that result is much more subtle and difficult. I am not at all pretending that reasoning is correct. Science progress when people do errors, but we have to find them, and sometimes, if we don't find them, we have to accept momentarily the conclusion, perhaps with the hope an error will be find later. But the attitude of a (tiny but influencing) part of the community consists in hiding the reasoning, or deforming it completely. This can't help. Some people, even here recently (see 1Z's post) and recently on the FOR list, attributes me a curious theory, where they confuse the conclusion with the
Re: The seven step series
I am in a good mood and a bit picky :-) Do you know how many entries google gave me upon entering Theaetetical -marchal -bruno Well 144? Good way to find my papers on that. The pages refer quickly to this list or the FOR list. I am sorry for the delay, I've just got back from my vacation. Hmm. The above written search should not return any references to your papers/letters as the minus sign in front of your name asks for an exclusion. Given that it works as supposed google then gives only 1 hit in my location (Sweden). That hit is a translation of the word Theaetetical into some eastern characters. Thus, I end up with zero meaningful hits and a feeling that you might be the only one using this word. That makes me insists a little bit more (in a very polite way) that, occasionally, your work is difficult to read unless one is willing to undertake long discussions, clarifications and position adjustments. I am writing this in a reference to your complains that sometimes you have troubles to get enough relevant feedback to your work. I let those interested to meditate on two questions (N is {0, 1, 2, 3, 4, ...}): 1) What is common between the set of all subsets of a set with n elements, and the set of all finite sequences of 0 and 1 of length n. 2) What is common between the set of all subsets of N, and the set of all infinite sequences of 0 and 1. Just some (finite and infinite) bread for surviving the day :) I am going to catch up with the thread ... Cheers, mirek --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi, Bruno, let me skip the technical part and jump on the following text. *F u n c t i o n* as I believe is - for you - the y = f(x) *form*. For me: the *activity -* shown when plotting on a coordinate system the f(x) values of the Y-s to the values on the x-axle resulting in a relation (curve). And here is my problem: who does the plotting? (Do not say: YOU are, or Iam, that would add to the function concept the homunculus to make it from a written format into a F U N C T I O N ). John M On Wed, Jul 29, 2009 at 11:59 AM, Bruno Marchal marc...@ulb.ac.be wrote: SOLUTIONS OK. I give the solution of the exercises of the last session, on the cartesian product of sets. I recall the definition of the product A X B. A X B= {(x,y) such that x belongs to A and y belongs to B} I gave A = {0, 1}, and B = {a, b}. In this case, A X B = {(0,a), (0, b), (1, a), (1, b)} The cartesian drawing is, for AXB : a (0, a) (1, a) b (0, b) (1, b) 0 1 Exercise: do the cartesian drawing for BXA. Solution: 1 (a, 1) (b, 1) 0 (a, 0) (b, 0) a b You see that B X A = {(a,0), (a,1), (b,0), (b, 1)} You should see that, not only A X B is different from B X A, but AXB and BXA have an empty intersection. They have no elements in common at all. But they do have the same cardinal 2x2 = 4. 1) Compute {a, b, c} X {d, e} = I show you a method (to minimize inattention errors): I wrote first {(a, _), (b, _), (c, _), (a, _), (b, _), (c, _)} two times because I have seen that {d, e} has two elements. Then I add the second elements of the couples, which comes from {d, e}: {(a, d), (b, d), (c, d), (a, e), (b, e), (c, e)} OK? {d, e} X {a, b, c} = {(d, a), (d, b), (d, c), (e, a), (e, b), (e, c)} {a, b} X {a, b} = {(a, a), (a, b), (b, a), (b, b)} {a, b} X { } = { }. OK? 2) Convince yourself that the cardinal of AXB is the product of the cardinal of A and the cardinal of B. A and B are finite sets here. Hint: meditate on their cartesian drawing. Question? This should be obvious. No? 3) Draw a piece of NXN.(with, as usual, N = {0, 1, 2, 3, ...}): .. . . . . . . .. . . . . .. .. . . . . . . 5(0,5) (1,5) (2,5) (3,5) (4,5) (5,5) ... 4(0,4) (1,4) (2,4) (3,4) (4,4) (5,4) ... 3(0,3) (1,3) (2,3) (3,3) (4,3) (5,3) ... 2(0,2) (1,2) (2,2) (3,2) (4,2) (5,2) ... 1(0,1) (1,1) (2,1) (3,1) (4,1) (5,1) ... 0(0,0) (1,0) (2,0) (3,0) (4,0) (5,0) ... 0 1 2 3 4 5 ... OK? N is infinite, so N X N is infinite too. Look at the diagonal: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) ... definition: *the diagonal of AXA,* a product of a set with itself, is the set of couples (x,y) with x = y. All right? No question? Such diagonal will have a quite important role in the sequel. Next: I will say one or two words on the notion of relation, and then we will define the most important notion ever discovered by the humans: the notion of function. Then, the definition of the exponentiation of sets, A^B, is very simple: it is the set of functions from B to A. What is important will be to grasp the notion of function. Indeed, we will soon be interested in the notion of computable functions, which are mainly what computers, that is universal machine, compute. But even in physics, the notion of function is present everywhere. That notion capture the notion of dependency between (measurable) quantities. To say that the temperature of a body depends on the pressure on that body, is very well described by saying that the temperature of a body is a function of the pressure. Most phenomena are described by relation, through equations, and most solution of those equation are functions. Functions are everywhere, somehow. I have some hesitation, though. Functions can be described as particular case of relations, and relations can be described as special case of functions. This happens many times in math, and can lead to bad pedagogical decisions, so I have to make a few thinking, before leading you to unnecessary complications. Please ask questions if *any*thing is unclear. I suggest the beginners in math take some time to invent exercises, and to solve them. Invent simple little sets, and compute their union, intersection, cartesian product, powerset. You can compose exercises: for example: compute the cartesian product of the powerset of {0, 1} with the set {a}. It is not particularly funny, but it is like music. If you want to be able to play some music instrument, sometimes you have to faire ses gammes,we say in french; you know, playing repetitively annoying musical patterns, if only to teach your lips or fingers to do the right
Re: The seven step series
Hi John, and the other. John motivates me to explain what is a function, for a mathematician. On 30 Jul 2009, at 17:53, John Mikes wrote: Hi, Bruno, let me skip the technical part OK. But I remind you this current thread *is* technical. and jump on the following text. F u n c t i o n as I believe is - for you - the y = f(x) form. For me: the activity - shown when plotting on a coordinate system the f(x) values of the Y-s to the values on the x-axle resulting in a relation (curve). And here is my problem: who does the plotting? (Do not say: YOU are, or Iam, that would add to the function concept the homunculus to make it from a written format into a F U N C T I O N ). But I have not yet say what is a function. I just mentioned that they are everywhere to open the appetite of the audience. F u n c t i o n as I believe is - for you - the y = f(x) form. You take a risk believing things - for me -. Actually the y = f(x) form will come later, with the goal of distinguishing clearly the key difference between a function and the many possible forms of a function. Ah! but you force me to define what is a function right on (for a mathematician of course). Take it easy. You can skip to the sum-up line below. OK, ready? I mean the others among those who pursue this mathematical shortcut toward the seventh step (the UD step, actually). We have already seen functions. If you remember the bijection between A = {a,b,c,d,e,f,g} and B = {1, 2, 3, 4, 5, 6, 7}. a -- 7 b -- 2 c -- 3 d -- 4 e -- 5 f -- 6 g -- 1 I said that the following set of couples {(a,1), (b,2) (c,3) (d,4), (e,5), (f,6), (g,7)} was a nice set theoretical representation of the bijection, and that the bijection is an example of function. We can give it a name, F, for example. F = {(a,1), (b,2) (c,3) (d,4), (e,5), (f,6), (g,7)}. A function is a mathematical object, actually a set, which embodies an association between the elements of two sets. Here the two sets involved are A and B. A is said to be the domain of F. B is said to be the range of F. And the function itself, F, get a nice set theoretical form of a set. The set of all the couples which determine or define the association. Here it is the set {(a,1), (b,2) (c,3) (d,4), (e,5), (f,6), (g,7)}. Arbitrary set of couples will appear as very good way to describe relation, in general. But for function a key condition, the functional condition, has to be applied: - If (a, b) belongs to F then if (a, c) belongs to F we have that b = c. (the functional condition). This means, that if F is a function from the set A to the set B, you cannot associate to one object of A, many objects of B. For example the temperature in a place can be a function of time, because at each moment of time you will not associate two temperatures. It is the key point for seeing that a function from A to B, describe a very general notion of dependency. We will be interested in functions from N to N. (With N = {0, 1, 2, ...}. Where examples abound. Take the function which associates to each natural number its successor. The function is (or is represented fully) by the infinite set of couples {(0, 1), (1,2), (2,3), (3,4), (4,5), (5, 6), (6, 7), ...} We will be interested in function having two arguments. Those will be the function from NXN to N. Example: take addition. This is a function, because when you add any numbers, 3 and 6, for example, 3+6, you don't expect two results. So the functional condition is respected. OK? So the function addition can be defined or represented by the set {((0, 0), 0), ((0, 1) 1) ... ((4, 8) 12) ... } With the numbers, all the operations are functions. The same with the sets. To sum up: a function is a set of couples, most of the time infinite, respecting the functional condition. A good training consists in searching all functions between little sets: Exercise: 1) how many functions and what are they, from the set {0, 1} to himself. What are the functions from {0, 1) to {0, 1}? Solution: {(0,0), (1,0)} the constant function which associates zero to any value of its argument. {(0,1), (1,1)} the constant function which associates one to any value of its argument. {(0,0), (1,1)} the identity function, which output its argument as value. {(0,1), (1,0)}, the NOT function, which associate 0 to 1, and 1 to 0. There is four functions from {0, 1} to {0, 1}. 2) how many functions, and what are they, from the set cartesian product {0, 1} X {0, 1} to {0, 1} Among them many are celebrities, you know. The AND, the OR, and many (how many?) others. For a beginner in math, this is not at all an easy exercise. The real useful exercise is to try to understand the enunciation of the question. We will take the time needed. 3) A bit tricky perhaps: how many functions exist from { }
Re: The seven step series
Ronald, On 28 Jul 2009, at 12:51, ronaldheld wrote: Bruno: I meant the mathematical formalism you are teaching us. When we eventually get to the UDA steps, I wil be better able to do that assessment. OK. Note that the first 6 steps have already be done recently, with Kim, and even before. But there is no problem to come back on this, later. The key point there consists in explaining the first person indeterminacy, and its invariance for set of transformations (adding delays in the computation, going from real to virtual, etc.). You may prepare yourself by reading the relevant portion of the sane04 paper. Eventually the seventh step itself somehow recapitulates the 6 preceding steps, so it is OK. Best, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
SOLUTIONS OK. I give the solution of the exercises of the last session, on the cartesian product of sets. I recall the definition of the product A X B. A X B= {(x,y) such that x belongs to A and y belongs to B} I gave A = {0, 1}, and B = {a, b}. In this case, A X B = {(0,a), (0, b), (1, a), (1, b)} The cartesian drawing is, for AXB : a (0, a) (1, a) b (0, b) (1, b) 0 1 Exercise: do the cartesian drawing for BXA. Solution: 1 (a, 1) (b, 1) 0 (a, 0) (b, 0) a b You see that B X A = {(a,0), (a,1), (b,0), (b, 1)} You should see that, not only A X B is different from B X A, but AXB and BXA have an empty intersection. They have no elements in common at all. But they do have the same cardinal 2x2 = 4. 1) Compute {a, b, c} X {d, e} = I show you a method (to minimize inattention errors): I wrote first {(a, _), (b, _), (c, _), (a, _), (b, _), (c, _)} two times because I have seen that {d, e} has two elements. Then I add the second elements of the couples, which comes from {d, e}: {(a, d), (b, d), (c, d), (a, e), (b, e), (c, e)} OK? {d, e} X {a, b, c} = {(d, a), (d, b), (d, c), (e, a), (e, b), (e, c)} {a, b} X {a, b} = {(a, a), (a, b), (b, a), (b, b)} {a, b} X { } = { }. OK? 2) Convince yourself that the cardinal of AXB is the product of the cardinal of A and the cardinal of B. A and B are finite sets here. Hint: meditate on their cartesian drawing. Question? This should be obvious. No? 3) Draw a piece of NXN.(with, as usual, N = {0, 1, 2, 3, ...}): .. . . . . . . .. . . . . .. .. . . . . . . 5(0,5) (1,5) (2,5) (3,5) (4,5) (5,5) ... 4(0,4) (1,4) (2,4) (3,4) (4,4) (5,4) ... 3(0,3) (1,3) (2,3) (3,3) (4,3) (5,3) ... 2(0,2) (1,2) (2,2) (3,2) (4,2) (5,2) ... 1(0,1) (1,1) (2,1) (3,1) (4,1) (5,1) ... 0(0,0) (1,0) (2,0) (3,0) (4,0) (5,0) ... 0 1 2 3 4 5 ... OK? N is infinite, so N X N is infinite too. Look at the diagonal: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) ... definition: the diagonal of AXA, a product of a set with itself, is the set of couples (x,y) with x = y. All right? No question? Such diagonal will have a quite important role in the sequel. Next: I will say one or two words on the notion of relation, and then we will define the most important notion ever discovered by the humans: the notion of function. Then, the definition of the exponentiation of sets, A^B, is very simple: it is the set of functions from B to A. What is important will be to grasp the notion of function. Indeed, we will soon be interested in the notion of computable functions, which are mainly what computers, that is universal machine, compute. But even in physics, the notion of function is present everywhere. That notion capture the notion of dependency between (measurable) quantities. To say that the temperature of a body depends on the pressure on that body, is very well described by saying that the temperature of a body is a function of the pressure. Most phenomena are described by relation, through equations, and most solution of those equation are functions. Functions are everywhere, somehow. I have some hesitation, though. Functions can be described as particular case of relations, and relations can be described as special case of functions. This happens many times in math, and can lead to bad pedagogical decisions, so I have to make a few thinking, before leading you to unnecessary complications. Please ask questions if *any*thing is unclear. I suggest the beginners in math take some time to invent exercises, and to solve them. Invent simple little sets, and compute their union, intersection, cartesian product, powerset. You can compose exercises: for example: compute the cartesian product of the powerset of {0, 1} with the set {a}. It is not particularly funny, but it is like music. If you want to be able to play some music instrument, sometimes you have to faire ses gammes,we say in french; you know, playing repetitively annoying musical patterns, if only to teach your lips or fingers to do the right movement without thinking. Math needs also such a kind of practice, especially in the beginning. Of course, as Kim said, passive understanding of music (listening) does not need such exercises. Passive understanding of math needs, alas, many simple exercises. Active understanding of math, needs difficult exercises up to open problems, but this is not the goal here. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this
Re: The seven step series
Bruno: I meant the mathematical formalism you are teaching us. When we eventually get to the UDA steps, I wil be better able to do that assessment. Ronald On Jul 27, 1:27 pm, Bruno Marchal marc...@ulb.ac.be wrote: On 27 Jul 2009, at 16:07, ronaldheld wrote: I am following, but have not commented, because there is nothing controversal. Cool. Even the sixth first steps of UDA? When you are done, can your posts be consolidated into a paper or a document that can be read staright through? I should do that. Bruno On Jul 23, 9:28 am, Bruno Marchal marc...@ulb.ac.be wrote: On 23 Jul 2009, at 15:09, m.a. wrote: Bruno, Yes, yours and Brent's explanations seem very clear. I hate to ask you to spell things out step by step all the way, but I can tell you that when I'm confronted by a dense hedge or clump of math symbols, my mind refuses to even try to disentangle them and reels back in terror. So I beg you to always advance in baby steps with lots of space between statements. I want to assure you that I'm printing out all of your 7-step lessons and using them for study and reference. Thanks for your patience, m.a. Don't worry, I understand that very well. And this illustrates also that your despair is more psychological than anything else. I have also abandoned the study of a mathematical book until I realize that the difficulty was more my bad eyesight than any conceptual difficulties. With good spectacles I realize the subject was not too difficult, but agglomeration of little symbols can give a bad impression, even for a mathematician. I will make some effort, tell me if my last post, on the relation (a^n) * (a^m) = a^(n + m) did help you. You are lucky to have an infinitely patient teacher. You can ask any question, like Bruno, is (a^n) * (a^m) the same as a^n times a^m? Answer: yes, I use often *, x, as shorthand for times, and I use ( and ) as delimiters in case I fear some ambiguity. Bruno -- Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 12:20 PM Subject: Re: The seven step series Marty, Brent wrote: On 21 Jul 2009, at 23:24, Brent Meeker wrote: Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000 001 010 011 100 101 110 111 and you have all strings of length 3. Then you wrote I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best, m . (mathematically hopeless) a. Let me rewrite Brent's explanation, with a tiny tiny tiny improvement: Take all strings of length 2 00 01 10 11 Make two copies of each first copy: 00 01 10 11 second copy 00 01 10 11 add a 0 to the end of the strings in the first copy, and then add a 1 to the end of the strings in the second copy: first copy: 000 010 100 110 second copy 001 011 101 111 You get all 8 elements of B_3. You can do the same reasoning with the subsets. Adding an element to a set multiplies by 2 the number of elements of the powerset: Exemple. take a set with two elements {a, b}. Its powerset is {{ } {a} {b} {a, b}}. How to get all the subset of {a, b, c} that is the set coming from adding c to {a, b}. Write two copies of the powerset of {a, b} { } {a} {b} {a, b} { } {a} {b} {a, b} Don't add c to the set in the first copy, and add c to the sets in the second copies. This gives { } {a} {b} {a, b} {c} {a, c} {b, c} {a, b, c} and that gives all subsets of {a, b, c}. This is coherent with interpreting a subset {a, b} of a set {a, b, c}, by a string like 110, which can be conceived as a shortand for Is a in the subset? YES, thus 1 Is b in the subset? YES thus 1 Is c in the subset? NO thus 0. OK? You say also: The example of Mister X only confuses me more. Once you understand well the present post, I suggest you reread the Mister X examples, because it is a key in the UDA reasoning. If you still have problem with it, I suggest you quote it, line by line, and ask question. I will answer (or perhaps someone else). Don't be afraid to ask any question. You are not mathematically hopeless. You are just not familiarized with reasoning in math. It is normal to go slowly. As far
Re: The seven step series
Bruno, I have searched my notes for an exposition of BIJECTION and found only one mention in an early email which promises to define it in a later lesson. Do you have a reference to that lesson or perhaps an instant explanation of it? Thanks, Chief Ignoramus - Original Message - From: Bruno Marchal marc...@ulb.ac.be To: everything-list@googlegroups.com Sent: Monday, July 27, 2009 4:54 PM Subject: Re: The seven step series We have discovered SBIJECTION between powersets of a set with cardinal n, and the set of binary strings of length n. And we have presented reasons for the existence of a bijection between the powerset of N = {0, 1, 2, ...} and the set of infinite binary strings. OK? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 28 Jul 2009, at 17:36, m.a. wrote: Bruno, I have searched my notes for an exposition of BIJECTION and found only one mention in an early email which promises to define it in a later lesson. Do you have a reference to that lesson or perhaps an instant explanation of it? Thanks, Chief Ignoramus I hope you are not stuck by that, given that the cartesian product does not rely on the understanding of bijection. An instant explanation of bijection is this: Suppose you have two sets A and B, and you would like to know if they have the same number of elements. For example: A = {a,b,c,d,e,f,g} and B = {1, 2, 3, 4, 5, 6, 7} Suppose that you cannot count. You forget the lessons for counting! But you have ficelles, I mean ropes, cords, or strings. So you can line up the two sets, and try to attach to each elements of A a piece of rope, and joint them to one element of the set B. IF you succeed doing that, and respecting the one-one or 1-1link, and getting all the elements of B (the onto condition), THEN you have shown the existence of a bijection between the two sets. Let us see if that work on the example. The -- represent the pieces of rope. OK? a -- 1 b -- 2 c -- 3 d -- 4 e -- 5 f -- 6 g -- 7 So there is a bijection between A and B. The bijection *is* that association, as we will defined much later(*). Other bijections can exist between A and B, like a -- 7 b -- 2 c -- 3 d -- 4 e -- 5 f -- 6 g -- 1 It is enough that one exist, to conclude the sets have the same number of elements, or same cardinal. Convince you that if two sets have different number of elements, there is no bijection in between. It has to be 1-1, and onto (no missing element). Exercise (but no hurry): Verify if you can see some bijections existing between the powerset of a set with 2 elements, and B_2. The same for the powerset of a set with 3 elements, and B_3. Bruno !*) Oh! I can give you the particular mathematical bijection, existing between A and B, given that I have already define the notion of couple. It is the set of couples representing naturally those rope association: {(a,1), (b,2) (c,3) (d,4), (e,5), (f,6), (g,7)}.Take it easy, and be sure you have read what I say about the couples before. http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 27 Jul 2009, at 16:07, ronaldheld wrote: I am following, but have not commented, because there is nothing controversal. Cool. Even the sixth first steps of UDA? When you are done, can your posts be consolidated into a paper or a document that can be read staright through? I should do that. Bruno On Jul 23, 9:28 am, Bruno Marchal marc...@ulb.ac.be wrote: On 23 Jul 2009, at 15:09, m.a. wrote: Bruno, Yes, yours and Brent's explanations seem very clear. I hate to ask you to spell things out step by step all the way, but I can tell you that when I'm confronted by a dense hedge or clump of math symbols, my mind refuses to even try to disentangle them and reels back in terror. So I beg you to always advance in baby steps with lots of space between statements. I want to assure you that I'm printing out all of your 7-step lessons and using them for study and reference. Thanks for your patience, m.a. Don't worry, I understand that very well. And this illustrates also that your despair is more psychological than anything else. I have also abandoned the study of a mathematical book until I realize that the difficulty was more my bad eyesight than any conceptual difficulties. With good spectacles I realize the subject was not too difficult, but agglomeration of little symbols can give a bad impression, even for a mathematician. I will make some effort, tell me if my last post, on the relation (a^n) * (a^m) = a^(n + m) did help you. You are lucky to have an infinitely patient teacher. You can ask any question, like Bruno, is (a^n) * (a^m) the same as a^n times a^m? Answer: yes, I use often *, x, as shorthand for times, and I use ( and ) as delimiters in case I fear some ambiguity. Bruno -- Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 12:20 PM Subject: Re: The seven step series Marty, Brent wrote: On 21 Jul 2009, at 23:24, Brent Meeker wrote: Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. Then you wrote I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best, m . (mathematically hopeless) a. Let me rewrite Brent's explanation, with a tiny tiny tiny improvement: Take all strings of length 2 00 01 10 11 Make two copies of each first copy: 00 01 10 11 second copy 00 01 10 11 add a 0 to the end of the strings in the first copy, and then add a 1 to the end of the strings in the second copy: first copy: 000 010 100 110 second copy 001 011 101 111 You get all 8 elements of B_3. You can do the same reasoning with the subsets. Adding an element to a set multiplies by 2 the number of elements of the powerset: Exemple. take a set with two elements {a, b}. Its powerset is {{ } {a} {b} {a, b}}. How to get all the subset of {a, b, c} that is the set coming from adding c to {a, b}. Write two copies of the powerset of {a, b} { } {a} {b} {a, b} { } {a} {b} {a, b} Don't add c to the set in the first copy, and add c to the sets in the second copies. This gives { } {a} {b} {a, b} {c} {a, c} {b, c} {a, b, c} and that gives all subsets of {a, b, c}. This is coherent with interpreting a subset {a, b} of a set {a, b, c}, by a string like 110, which can be conceived as a shortand for Is a in the subset? YES, thus 1 Is b in the subset? YES thus 1 Is c in the subset?NO thus 0. OK? You say also: The example of Mister X only confuses me more. Once you understand well the present post, I suggest you reread the Mister X examples, because it is a key in the UDA reasoning. If you still have problem with it, I suggest you quote it, line by line, and ask question. I will answer (or perhaps someone else). Don't be afraid to ask any question. You are not mathematically hopeless. You are just not familiarized with reasoning in math. It is normal to go slowly. As far as you can say I don't understand, there is hope you will understand. Indeed, concerning the UDA I suspect many in the list cannot say I don't understand, they believe it is philosophy, so they feel like they could object on philosophical ground, when the whole point is to present a deductive argument in a theory. So it is false, or you have to accept the theorem in the theory
Re: The seven step series
Hi, OK, I will come back on the square root of 2 later. We have talked on sets. Sets have elements, and elements of a set define completely the set, and a set is completely defined by its elements. Example: here is a set of numbers {1, 2, 3} and a set of sets of numbers {{1, 2}, {3}, { }}. We can do some operations, like their union, or their intersection. Examples: {1,2,3} union {3,4,5} = {1,2,3,4,5}, {1,2,3} intersection {3,4,5} = { }. We can verify if some relation hold for them, like equality, or inclusion. {1, 2} = {2, 1, 1} (yes!) {1, 2} included-in {3, 2, 1} {1, 2} not-included-in {1, 3} We can compute their powerset. Powerset {1, 2} = {{ }, {1}, {2}, {1, 2}} We have discovered SBIJECTION between powersets of a set with cardinal n, and the set of binary strings of length n. And we have presented reasons for the existence of a bijection between the powerset of N = {0, 1, 2, ...} and the set of infinite binary strings. OK? Today, I suggest we look at two new operations on sets. The product of sets, and the exponentiation of sets. Well, I will probably do only the product today. First I have to introduce a new, well actually *very* well known, and absolutely important, notion: the couple. A couple is when there is two things, but with some order. It looks like a pair, but the order counts. Usually a couple of things a , b is designated, in math, like this: (a, b). It looks like a pair {a, b}, but it is not. Indeed, {a, b} = {b, a}, but the couple (a, b) is NOT equal to the couple (b, a). When are two couples (a, b) and (c, d) equal? Only when a = c and b = d. Examples. the couple of number (2, 3) is not equal to the couple (3, 2), but the couple (0, 666) is equal to the couple (0, 666). OK? APARTE: Are couples sets? No. Nor are numbers. But yes, you can easily represent them by sets, so we could work only with sets, but we will not do that. Much later we will work only with numbers, in fact. The very notion of representation will be important, though. Now we are ready to define the so called cartesian product of sets. It is indeed a cousin of Descartes' discovery that you can represent a point of the plane by a couple of (real) numbers. I read somewhere that Descartes discovered this by trying to describe a spider walking on a window with squared little piece of glass. But such a localization works also for cities like Los Angeles where you address is something like 15th avenue 61th street. The whole field of analytical geometry is founded on this idea. That cartesian idea generalises on sets A and B. It is written A X B, and it is defined by the set of couples (x, y) such that x belongs to A, and y belongs to B. AXB = {(x, y) such-that x belongs-to A, and y belongs to B}. (compare with the preceding definitions). Example: what is the product {0, 1} X {a, b}? Well it is the set of all the couples made from elements of A in company of elements of B, and in that order, with A = {0, 1}, and B = {a, b}. So (0, a) is in there, and there are others. The product of {0, 1) with {a, b} is equal to {(0,a), (0, b), (1, a), (1, b)} The convenient usual cartesian drawing is, for AXB, with A = {0, 1}, and B = {a, b} : a (0, a) (1, a) b (0, b) (1, b) 0 1 A product of numbers a and b, ab, can be conceived as the area of a rectangle of sides a and b. Here you can see that the product of sets AXB can fit in a rectangle when you dispose horizontally the elements of A, and vertically the elements of B. By convention, usually A is put horizontally, and B vertically. But note that if the number ab is equal to the number ba, it is not the case that the set AXB is equal to the set BXA. (0, a) does not belong to BXA, for example. Exercise: to the cartesian drawing for BXA. 1) Compute {a, b, c} X {d, e} = {d, e} X {a, b, c} = {a, b} X {a, b} = {a, b} X { } = 2) Convince yourself that the cardinal of AXB is the product of the cardinal of A and the cardinal of B. A and B are finite sets here. Hint: meditate on their cartesian drawing. 3) Draw a piece of NXN. Solution and sequel tomorrow. Any question? Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Bruno, I asked Brent Meeker a question which he referred back to you. Will you be covering it? (see para in bold below) - Original Message - From: Brent Meeker meeke...@dslextreme.com To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 11:49 PM Subject: Re: The seven step series * 000100100011 0100010101100111 1000 1001 1010 1011 1100 1101 1110 * ** *and this is the binary sequence of length 4.* Right, it's all the binary strings of length 4 ** *How do these translate into ordinary numerals? 1,2,3,4...* Bruno's using them to represent sets and subsets. So if we have a set {a b c} we can represent the subset {a c} by 101 and {a b} by 110, etc. That's quite different from using a binary string to represent a number in positional notation. I'll leave it to Bruno whether he wants to go into that. Brent --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Bruno, Yes, yours and Brent's explanations seem very clear. I hate to ask you to spell things out step by step all the way, but I can tell you that when I'm confronted by a dense hedge or clump of math symbols, my mind refuses to even try to disentangle them and reels back in terror. So I beg you to always advance in baby steps with lots of space between statements. I want to assure you that I'm printing out all of your 7-step lessons and using them for study and reference. Thanks for your patience, m.a. -- Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 12:20 PM Subject: Re: The seven step series Marty, Brent wrote: On 21 Jul 2009, at 23:24, Brent Meeker wrote: Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. Then you wrote I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best, m. (mathematically hopeless) a. Let me rewrite Brent's explanation, with a tiny tiny tiny improvement: Take all strings of length 2 00 01 10 11 Make two copies of each first copy: 00 01 10 11 second copy 00 01 10 11 add a 0 to the end of the strings in the first copy, and then add a 1 to the end of the strings in the second copy: first copy: 000 010 100 110 second copy 001 011 101 111 You get all 8 elements of B_3. You can do the same reasoning with the subsets. Adding an element to a set multiplies by 2 the number of elements of the powerset: Exemple. take a set with two elements {a, b}. Its powerset is {{ } {a} {b} {a, b}}. How to get all the subset of {a, b, c} that is the set coming from adding c to {a, b}. Write two copies of the powerset of {a, b} { } {a} {b} {a, b} { } {a} {b} {a, b} Don't add c to the set in the first copy, and add c to the sets in the second copies. This gives { } {a} {b} {a, b} {c} {a, c} {b, c} {a, b, c} and that gives all subsets of {a, b, c}. This is coherent with interpreting a subset {a, b} of a set {a, b, c}, by a string like 110, which can be conceived as a shortand for Is a in the subset? YES, thus 1 Is b in the subset? YES thus 1 Is c in the subset?NO thus 0. OK? You say also: The example of Mister X only confuses me more. Once you understand well the present post, I suggest you reread the Mister X examples, because it is a key in the UDA reasoning. If you still have problem with it, I suggest you quote it, line by line, and ask question. I will answer (or perhaps someone else). Don't be afraid to ask any question. You are not mathematically hopeless. You are just not familiarized with reasoning in math. It is normal to go slowly. As far as you can say I don't understand, there is hope you will understand. Indeed, concerning the UDA I suspect many in the list cannot say I don't understand, they believe it is philosophy, so they feel like they could object on philosophical ground, when the whole point is to present a deductive argument in a theory. So it is false, or you have to accept the theorem in the theory. It is a bit complex, because it is an applied theory. The mystery are in the axioms of the theory, as always. So please ask *any* question. I ask this to everyone. I am intrigued by the difficulty some people can have with such reasoning (I mean the whole UDA here). (I can understand the shock when you get the point, but that is always the case with new results: I completely share Tegmark's idea that our brain have not been prepared to have any intuition when our mind try to figure out what is behind our local neighborhood). Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Marty, I can if you really want it, but it is out of topic and could introduced some confusion. I suggest we could come back on this later perhaps. But if you insist, I can do it. have you get my last post? Note that I have also already explained how binary strings can represent number in some older post. Honestly we will not need this, so it is better not to accumulate too many new materials, especially when I can fear some confusion. It is good to be familiar with the object binary strings seen as an object by itself. Bruno On 23 Jul 2009, at 14:02, m.a. wrote: Hi Bruno, I asked Brent Meeker a question which he referred back to you. Will you be covering it? (see para in bold below) - Original Message - From: Brent Meeker meeke...@dslextreme.com To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 11:49 PM Subject: Re: The seven step series * 000100100011 0100010101100111 1000 1001 1010 1011 1100 1101 1110 * ** *and this is the binary sequence of length 4.* Right, it's all the binary strings of length 4 ** *How do these translate into ordinary numerals? 1,2,3,4...* Bruno's using them to represent sets and subsets. So if we have a set {a b c} we can represent the subset {a c} by 101 and {a b} by 110, etc. That's quite different from using a binary string to represent a number in positional notation. I'll leave it to Bruno whether he wants to go into that. Brent http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 23 Jul 2009, at 15:09, m.a. wrote: Bruno, Yes, yours and Brent's explanations seem very clear. I hate to ask you to spell things out step by step all the way, but I can tell you that when I'm confronted by a dense hedge or clump of math symbols, my mind refuses to even try to disentangle them and reels back in terror. So I beg you to always advance in baby steps with lots of space between statements. I want to assure you that I'm printing out all of your 7-step lessons and using them for study and reference. Thanks for your patience, m.a. Don't worry, I understand that very well. And this illustrates also that your despair is more psychological than anything else. I have also abandoned the study of a mathematical book until I realize that the difficulty was more my bad eyesight than any conceptual difficulties. With good spectacles I realize the subject was not too difficult, but agglomeration of little symbols can give a bad impression, even for a mathematician. I will make some effort, tell me if my last post, on the relation (a^n) * (a^m) = a^(n + m) did help you. You are lucky to have an infinitely patient teacher. You can ask any question, like Bruno, is (a^n) * (a^m) the same as a^n times a^m? Answer: yes, I use often *, x, as shorthand for times, and I use ( and ) as delimiters in case I fear some ambiguity. Bruno -- Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 12:20 PM Subject: Re: The seven step series Marty, Brent wrote: On 21 Jul 2009, at 23:24, Brent Meeker wrote: Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. Then you wrote I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best, m . (mathematically hopeless) a. Let me rewrite Brent's explanation, with a tiny tiny tiny improvement: Take all strings of length 2 00 01 10 11 Make two copies of each first copy: 00 01 10 11 second copy 00 01 10 11 add a 0 to the end of the strings in the first copy, and then add a 1 to the end of the strings in the second copy: first copy: 000 010 100 110 second copy 001 011 101 111 You get all 8 elements of B_3. You can do the same reasoning with the subsets. Adding an element to a set multiplies by 2 the number of elements of the powerset: Exemple. take a set with two elements {a, b}. Its powerset is {{ } {a} {b} {a, b}}. How to get all the subset of {a, b, c} that is the set coming from adding c to {a, b}. Write two copies of the powerset of {a, b} { } {a} {b} {a, b} { } {a} {b} {a, b} Don't add c to the set in the first copy, and add c to the sets in the second copies. This gives { } {a} {b} {a, b} {c} {a, c} {b, c} {a, b, c} and that gives all subsets of {a, b, c}. This is coherent with interpreting a subset {a, b} of a set {a, b, c}, by a string like 110, which can be conceived as a shortand for Is a in the subset? YES, thus 1 Is b in the subset? YES thus 1 Is c in the subset?NO thus 0. OK? You say also: The example of Mister X only confuses me more. Once you understand well the present post, I suggest you reread the Mister X examples, because it is a key in the UDA reasoning. If you still have problem with it, I suggest you quote it, line by line, and ask question. I will answer (or perhaps someone else). Don't be afraid to ask any question. You are not mathematically hopeless. You are just not familiarized with reasoning in math. It is normal to go slowly. As far as you can say I don't understand, there is hope you will understand. Indeed, concerning the UDA I suspect many in the list cannot say I don't understand, they believe it is philosophy, so they feel like they could object on philosophical ground, when the whole point is to present a deductive argument in a theory. So it is false, or you have to accept the theorem in the theory. It is a bit complex, because it is an applied theory. The mystery are in the axioms of the theory, as always. So please ask *any* question. I ask this to everyone. I am intrigued by the difficulty some people can have with such reasoning (I mean the whole UDA here). (I can understand the shock when you get the point
Re: The seven step series
Hi Brent, I really appreciate the help and I hate to impose on your patience but...(see below) - Original Message - From: Brent Meeker meeke...@dslextreme.com To: everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 5:24 PM Subject: Re: The seven step series Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best, m. (mathematically hopeless) a. Brent m.a. wrote: *Thanks Brent,* * Could you supply some illustrative examples?* * marty a.* ** - Original Message - From: Brent Meeker meeke...@dslextreme.com mailto:meeke...@dslextreme.com To: everything-list@googlegroups.com mailto:everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 3:57 PM Subject: Re: The seven step series Each binary string of length n has two possible continuations of length n+1, one of them by appending a 0 and one of them by appending a 1. So to get all binary strings of length n+1 take each string of length n, make two copies, to one copy append a 0 and to the other copy append a 1. Brent m.a. wrote: Hi Bruno, I'm not clear on the sentence in bold below, especially the word correspondingly. The example of Mister X only confuses me more. Could you please give some simple examples? Thanks, marty a. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Marty, Brent wrote: On 21 Jul 2009, at 23:24, Brent Meeker wrote: Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. Then you wrote I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best, m . (mathematically hopeless) a. Let me rewrite Brent's explanation, with a tiny tiny tiny improvement: Take all strings of length 2 00 01 10 11 Make two copies of each first copy: 00 01 10 11 second copy 00 01 10 11 add a 0 to the end of the strings in the first copy, and then add a 1 to the end of the strings in the second copy: first copy: 000 010 100 110 second copy 001 011 101 111 You get all 8 elements of B_3. You can do the same reasoning with the subsets. Adding an element to a set multiplies by 2 the number of elements of the powerset: Exemple. take a set with two elements {a, b}. Its powerset is {{ } {a} {b} {a, b}}. How to get all the subset of {a, b, c} that is the set coming from adding c to {a, b}. Write two copies of the powerset of {a, b} { } {a} {b} {a, b} { } {a} {b} {a, b} Don't add c to the set in the first copy, and add c to the sets in the second copies. This gives { } {a} {b} {a, b} {c} {a, c} {b, c} {a, b, c} and that gives all subsets of {a, b, c}. This is coherent with interpreting a subset {a, b} of a set {a, b, c}, by a string like 110, which can be conceived as a shortand for Is a in the subset? YES, thus 1 Is b in the subset? YES thus 1 Is c in the subset?NO thus 0. OK? You say also: The example of Mister X only confuses me more. Once you understand well the present post, I suggest you reread the Mister X examples, because it is a key in the UDA reasoning. If you still have problem with it, I suggest you quote it, line by line, and ask question. I will answer (or perhaps someone else). Don't be afraid to ask any question. You are not mathematically hopeless. You are just not familiarized with reasoning in math. It is normal to go slowly. As far as you can say I don't understand, there is hope you will understand. Indeed, concerning the UDA I suspect many in the list cannot say I don't understand, they believe it is philosophy, so they feel like they could object on philosophical ground, when the whole point is to present a deductive argument in a theory. So it is false, or you have to accept the theorem in the theory. It is a bit complex, because it is an applied theory. The mystery are in the axioms of the theory, as always. So please ask *any* question. I ask this to everyone. I am intrigued by the difficulty some people can have with such reasoning (I mean the whole UDA here). (I can understand the shock when you get the point, but that is always the case with new results: I completely share Tegmark's idea that our brain have not been prepared to have any intuition when our mind try to figure out what is behind our local neighborhood). Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
m.a. wrote: Hi Brent, I really appreciate the help and I hate to impose on your patience but...(see below) - Original Message - From: Brent Meeker meeke...@dslextreme.com mailto:meeke...@dslextreme.com To: everything-list@googlegroups.com mailto:everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 5:24 PM Subject: Re: The seven step series Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. *I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best,* ** * m. (mathematically hopeless) a.* They aren't permutations. They're just sticking a 0 or 1 on the end. One copy of 01 becomes 010 and the other become 011. Brent --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Going a step further... (see below) - Original Message - From: Brent Meeker meeke...@dslextreme.com To: everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 12:57 PM Subject: Re: The seven step series m.a. wrote: Hi Brent, I really appreciate the help and I hate to impose on your patience but...(see below) - Original Message - From: Brent Meeker meeke...@dslextreme.com mailto:meeke...@dslextreme.com To: everything-list@googlegroups.com mailto:everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 5:24 PM Subject: Re: The seven step series Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. *I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best,* ** They aren't permutations. They're just sticking a 0 or 1 on the end. One copy of 01 becomes 010 and the other become 011. Then I assume the next step would be making two copies of each of those: 000000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 ...and sticking a 0 or 1 at the end: 000100100011 01000101011001111000 1001 1010 1011 1100 1101 1110 and this is the binary sequence of length 4. How do these translate into ordinary numerals? 1,2,3,4... Brent --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
m.a. wrote: *Going a step further... (see below)* ** - Original Message - From: Brent Meeker meeke...@dslextreme.com mailto:meeke...@dslextreme.com To: everything-list@googlegroups.com mailto:everything-list@googlegroups.com Sent: Wednesday, July 22, 2009 12:57 PM Subject: Re: The seven step series m.a. wrote: Hi Brent, I really appreciate the help and I hate to impose on your patience but...(see below) - Original Message - From: Brent Meeker meeke...@dslextreme.com mailto:meeke...@dslextreme.com mailto:meeke...@dslextreme.com To: everything-list@googlegroups.com mailto:everything-list@googlegroups.com mailto:everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 5:24 PM Subject: Re: The seven step series Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. *I can see where adding 0 to the first and 1 to the second gives 000 and 001 and I think I see how you get 010 but the rest of the permutations don't seem obvious to me. P-l-e-a-s-e explain, Best,* ** They aren't permutations. They're just sticking a 0 or 1 on the end. One copy of 01 becomes 010 and the other become 011. *Then I assume the next step would be making two copies of each of those:* ** *000**000 001 001 010 010 011 011 100 100 101 101 110 110 111 111* ** *...and sticking a 0 or 1 at the end:* ** * 000100100011 0100010101100111 1000 1001 1010 1011 1100 1101 1110 * ** *and this is the binary sequence of length 4.* Right, it's all the binary strings of length 4 ** *How do these translate into ordinary numerals? 1,2,3,4...* Bruno's using them to represent sets and subsets. So if we have a set {a b c} we can represent the subset {a c} by 101 and {a b} by 110, etc. That's quite different from using a binary string to represent a number in positional notation. I'll leave it to Bruno whether he wants to go into that. Brent --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Hi Bruno, I'm not clear on the sentence in bold below, especially the word correspondingly. The example of Mister X only confuses me more. Could you please give some simple examples? Thanks, marty a. - Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Monday, July 20, 2009 3:17 PM Subject: Re: The seven step series On 20 Jul 2009, at 15:34, m.a. wrote: And then we have seen that such cardinal was given by 2^n. You can see this directly by seeing that adding an element in a set, double the number of subset, due to the dichotomic choice in creating a subset placing or not placing the new element in the subset. Likewise with the strings. If you have already all strings of length n, you get all the strings of length n+1, by doubling them and adding zero or one correspondingly. This is also illustrated by the iterated self-duplication W, M. Mister X is cut and paste in two rooms containing each a box, in which there is a paper with zero on it, in room W, and 1 on it in room M. After the experience, the 'Mister X' coming out from room W wrote 0 in his diary, and the 'Mister X' coming out from room M wrote 1 in his diary. And then they redo each, the experiment. The Mister-X with-0-in-his-diary redoes it, and gives a Mister-X with-0-in-his-diary coming out from room W, and adding 0 in its diary and a Mister-X with-0-in-his-diary coming out from room M, adding 1 in its diary: they have the stories Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Each binary string of length n has two possible continuations of length n+1, one of them by appending a 0 and one of them by appending a 1. So to get all binary strings of length n+1 take each string of length n, make two copies, to one copy append a 0 and to the other copy append a 1. Brent m.a. wrote: Hi Bruno, I'm not clear on the sentence in bold below, especially the word correspondingly. The example of Mister X only confuses me more. Could you please give some simple examples? Thanks, marty a. - Original Message - *From:* Bruno Marchal mailto:marc...@ulb.ac.be *To:* everything-list@googlegroups.com mailto:everything-list@googlegroups.com *Sent:* Monday, July 20, 2009 3:17 PM *Subject:* Re: The seven step series On 20 Jul 2009, at 15:34, m.a. wrote: And then we have seen that such cardinal was given by 2^n. You can see this directly by seeing that adding an element in a set, double the number of subset, due to the dichotomic choice in creating a subset placing or not placing the new element in the subset. *Likewise with the strings. If you have already all strings of length n, you get all the strings of length n+1, by doubling them and adding zero or one correspondingly.* This is also illustrated by the iterated self-duplication W, M. Mister X is cut and paste in two rooms containing each a box, in which there is a paper with zero on it, in room W, and 1 on it in room M. After the experience, the 'Mister X' coming out from room W wrote 0 in his diary, and the 'Mister X' coming out from room M wrote 1 in his diary. And then they redo each, the experiment. The Mister-X with-0-in-his-diary redoes it, and gives a Mister-X with-0-in-his-diary coming out from room W, and adding 0 in its diary and a Mister-X with-0-in-his-diary coming out from room M, adding 1 in its diary: they have the stories Bruno http://iridia.ulb.ac.be/~marchal/ http://iridia.ulb.ac.be/%7Emarchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Thanks Brent, Could you supply some illustrative examples? marty a. - Original Message - From: Brent Meeker meeke...@dslextreme.com To: everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 3:57 PM Subject: Re: The seven step series Each binary string of length n has two possible continuations of length n+1, one of them by appending a 0 and one of them by appending a 1. So to get all binary strings of length n+1 take each string of length n, make two copies, to one copy append a 0 and to the other copy append a 1. Brent m.a. wrote: Hi Bruno, I'm not clear on the sentence in bold below, especially the word correspondingly. The example of Mister X only confuses me more. Could you please give some simple examples? Thanks, marty a. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
Take all strings of length 2 00 01 10 11 Make two copies of each 00 00 01 01 10 10 11 11 Add a 0 to the first and a 1 to the second 000001 010 011 100 101 110 111 and you have all strings of length 3. Brent m.a. wrote: *Thanks Brent,* * Could you supply some illustrative examples?* * marty a.* ** - Original Message - From: Brent Meeker meeke...@dslextreme.com mailto:meeke...@dslextreme.com To: everything-list@googlegroups.com mailto:everything-list@googlegroups.com Sent: Tuesday, July 21, 2009 3:57 PM Subject: Re: The seven step series Each binary string of length n has two possible continuations of length n+1, one of them by appending a 0 and one of them by appending a 1. So to get all binary strings of length n+1 take each string of length n, make two copies, to one copy append a 0 and to the other copy append a 1. Brent m.a. wrote: Hi Bruno, I'm not clear on the sentence in bold below, especially the word correspondingly. The example of Mister X only confuses me more. Could you please give some simple examples? Thanks, marty a. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 20 Jul 2009, at 15:34, m.a. wrote: Bruno, I don't know about Kim, but I'm ready to push on. I'm waiting for the answer to problem 2) see below. And could you please retstate that problem as I'm not sure which one it is? Thanks, marty a. Let us see: 1) What is common between the set of all subsets of a set with n elements, and the set of all finite sequences of 0 and 1 of length n. 2) What is common between the set of all subsets of N, and the set of all infinite sequences of 0 and 1. Let me restate by introducing a definition (made precise later). The cardinal of a set S is the number of elements in the set S. The cardinal of { } = 0. All singletons have cardinal one. All pairs, or doubletons, have cardinal two. Problem 1 has been solved. They have the same cardinal, or if you prefer, they have the same number of elements. The set of all subsets of a set with n elements has the same number of elements than the set of all strings of length n. Let us write B_n for the sets of binary strings of length n. So, B_0 = { } B_1 = {0, 1} B_2 = {00, 01, 10, 11} B_3 = {000, 010, 100, 110, 001, 011, 101, 111} We have seen, without counting, that the cardinal of the powerset of a set with cardinal n is the same as the cardinal of B_n. And then we have seen that such cardinal was given by 2^n. You can see this directly by seeing that adding an element in a set, double the number of subset, due to the dichotomic choice in creating a subset placing or not placing the new element in the subset. Likewise with the strings. If you have already all strings of length n, you get all the strings of length n+1, by doubling them and adding zero or one correspondingly. This is also illustrated by the iterated self-duplication W, M. Mister X is cut and paste in two rooms containing each a box, in which there is a paper with zero on it, in room W, and 1 on it in room M. After the experience, the 'Mister X' coming out from room W wrote 0 in his diary, and the 'Mister X' coming out from room M wrote 1 in his diary. And then they redo each, the experiment. The Mister-X with-0-in-his- diary redoes it, and gives a Mister-X with-0-in-his-diary coming out from room W, and adding 0 in its diary and a Mister-X with-0-in-his- diary coming out from room M, adding 1 in its diary: they have the stories 00 01, and then the Mister-X-coming-from room W, and with 1 written in the diary, similarly redoes the experiment, and this gives two more Misters X, having written in their diaries 10 11. Obviously the iteration of the self-duplication, gives as result 2x2x2x2x...x2 number of Mister X. If those four Mister X duplicate again, there will be 8 of them, with each of those guys having an element of B_3 written in his diary. OK. And we have seen that a powerset of a set with n elements can but put in a nice correspondence with B_n. For example: The powerset of {a, b}, that is {{ }, {a}, {b}, {a, b}}, has the following nice correspondence 00 .. { } 01 .. {a} 10 ...{b} 11 ...{a, b} Each 0 and 1 corresponding to the answer to the yes/no questions 'is a in the subset?', is 'b in the subset?'. Such a nice correspondence between two sets is called a BIJECTION, and will be defined later. What we have seen, thus, is that there is a bijection between the powerset of set with n elements, and the set of binary strings B_n. And the second question? What is common between the subsets of N, and the set of infinite binary sequences. An infinite binary sequence is a infinite sequences of 0 and 1. For example: 000..., with only zero is such a sequence. It could be the first person story of 'the mister X who comes always from room W. Or, if the zero and one represents the result of the fair coin throw experiment, it could be the result of the infinitely unlucky guy: he always get the head. Another one quite similar is ..., the infinitely lucky guy. A more 'typical' would be 11001001110110101010001000... (except that this very one *is* typical, it is PI written in binary; PI = 11. 00100...). The link with the subsets of N? It is really the same as above, except that we extend the idea on the infinite. A subset of N, that is, a set included in N, is entirely determined by the answer to the following questions: Is 0 in the subset? Is 1 in the subset? Is 2 in the subset? Is 3 in the subset? etc. You will tell me that nobody can answer an infinity of questions. I will answer that in many situation we can. Let us take a simple subset of N, the set {3, 4, 7}. It seems to me we can answer to the infinite set of corresponding question: Is 0 in the subset?NO Is 1 in the subset?NO Is 2 in the subset? NO Is 3 in the subset? YES Is 4 in the subset?YES Is 5 in the subset?NO Is 6 in the subset? NO Is 7 in
Re: The seven step series
On 15 Jul 2009, at 04:15, m.a. wrote: - Original Message - From: Bruno Marchal To: everything-list@googlegroups.com Sent: Tuesday, July 14, 2009 4:40 AM Subject: Re: The seven step series Hi Kim, Marty, Johnathan, John, Mirek, and all... Bruno: May I advise you about an instance of English usage? The word supposed in the next sentence is often used as sarcasm to imply serious doubt about the statement. In this context it can be interpreted as a slight. I think you meant to say assumed which implies an evident fact. Please don't apologize, we are most grateful for your efforts in using English and are happy to make allowances for minor slips. B = {Kim, Marty, Russell, Bruno, George, Jurgen} is a set with 5 elements which are supposed to be humans. Thanks for letting me know. In french I assume is the same as I suppose. I'm afraid it will take time for me not doing that error again. But don't hesitate to remind me of the false friend behavior. Sorry for the unintended sarcasm. To be sure it is not really an assumption, and a supposition means more like an obvious implicit fact we should take into account without mentioning, as opposed to an assumption which is more akin to a key hypothesis. Here I was referring to conventions only, but then, as yopu point out, an non intended sarcasm could be see. Difficult. That is why I prefer to stick on less ambiguous, purely mathematical examples of sets. I also have a question: see below: We have seen INTERSECTION, and UNION. The intersection of the two sets S1 = {1, 2, 3} and S2 = {2, 3, 7, 8} will be written (S1 \inter S2), and is equal to the set of elements which belongs to both S1 and S2. We have (S1 \inter S2) = {2, 3} We can define (S1 \inter S2) = {x such-that ((x belongs-to S1) and (x belongs-to S2))} 2 belongs to (S1 \inter S2) because ((2 belongs-to S1) and (2 belongs-to S2)) 8 does not belongs to (S1 \inter S2) because it is false that ((2 belongs-to S1) and (2 belongs-to S2)). Indeed 8 does not belong to S1. Doesn't the statement in bold (above) contradict the statement immediately preceding (also in bold)? You are completely right. I just did a copy and past, and forget to substitute the 2 by the 8. So the statements are: 2 belongs to (S1 \inter S2) because ((2 belongs-to S1) and (2 belongs- to S2)) 8 does not belongs to (S1 \inter S2) because it is false that ((8 belongs-to S1) and (8 belongs-to S2)). Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 15 Jul 2009, at 09:09, Kim Jones wrote: On 14/07/2009, at 6:40 PM, Bruno Marchal wrote: The intersection of the two sets S1 = {1, 2, 3} and S2 = {2, 3, 7, 8} will be written (S1 \inter S2), and is equal to the set of elements which belongs to both S1 and S2. We have (S1 \inter S2) = {2, 3} We can define (S1 \inter S2) = {x such-that ((x belongs-to S1) and (x belongs-to S2))} 2 belongs to (S1 \inter S2) because ((2 belongs-to S1) and (2 belongs-to S2)) 8 does not belongs to (S1 \inter S2) because it is false that ((2 belongs-to S1) and (2 belongs-to S2)). Indeed 8 does not belong to S1. Quick (silly) questions: 1. why do you have to write \inter ? Why not just write inter ? Typing \ causes me to make use of a key on my keyboard I have never used before which is scary ;-) For the intersection of two sets S1 and S1, I have used 1) S1 ∩ S2 But the math symbol ∩ did not go through all emailing system, so, I have used 2) S1 INTERSECTION S2 But then I recall that in mails, capital letters seems aggressive, loudly ..., so I have used 3) S1 intersection S2 But then the difference between what is supposed to be represent a mathematical symbols, and a word in english, disappears, so I have used 4) S1 \intersection S2 But this, on the last post, seems to me to be a little too long, and so I am using now 5) S1 \inter S2 Only God knows what I will use tomorrow. You should learn that there is no standard of mathematical notations, and no two mathematicians use the same symbols, and not one mathematician use the same symbols in two different texts. What is nice, is that, usually, mathematicians quickly redefine what they mean by any symbols at the beginning of their books and papers. Of course doing math on mails aggravates apparently this search for the symbols which could satisfy everyone. Sorry to scare you, 2. such-that is surely such that but the hyphen might just mean something (this is mathematics; there are dots and dashes and slashes all over the place so you have to know what they all mean) likewise belongs-to would still mean the same thing if we wrote belongs to would it not? Same remark. I should have use \such-that, and \belongs-to. Note that at this stage it is really not important to be aware of the difference between a symbol and what the symbols refer too, but in logic such differences acquire some importance at some point, and I just try to prepare you for such nuances, having the sequel of this introduction in my mind. You question are not silly and makes sense, as you see, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
*Please read between your lines included in bold* letters *John * On Thu, Jul 16, 2009 at 4:13 AM, Bruno Marchal marc...@ulb.ac.be wrote: On 15 Jul 2009, at 00:50, John Mikes wrote: Bruno, I appreciate your grade-school teaching. We (I for one) can use it. I still find that whatever you explain is an 'extract' of what can be thought of a 'set' (a one representing a many). Your 'powerset' is my example. All those elements you put into { }s are the same as were the physical objects to Aristotle in his 'total' - the SUM of which was always MORE than the additives of those objects. Relations! The set is not an inordinate heap (correct me please, if I am off) of the elements, the elements are in SOME relation to each other and the set-idea of their ensemble, to *form* a SET. You stop short at the naked elements *together*, as I see. You get the idea. We can add structure to sets, by explicitly endowing them with operations and relations. *Furhter below you also expose the contrary (to simplify) - **I am afraid your operations and relations are restricted to the numbers-based (math?) domain, which is not what I mean by 'totality'. * ** *They wear cloths and hold hands. Mortar is among them.* Maybe your math-idea can tolerate any sequence and hiatus concerning to the 'set', and it still stays the same, as far as the *math-idea you need*goes, Yes, it is the methodology. but if I go further (and you indicated that ANYTHING can form a set) More precisily, we can form a set of multiple thing we can conceive or defined. *I would not restrict 'a set' to what WE can conceive, or define now. (Not even within the 'math'-related domain).* the relations of the set-partners comes into play. Not only those which WE choose for 'interesting' to such set, but ALL OF THEM influencing the character of that *ONE.* *Just musing.* It is OK. The idea consists in simplifying the things as much as possible, and then to realize that despite such simplification we are quickly driven to the unprovable, unnameable, un-reductible, far sooner than we could have imagine. *I may suggest (or: assume?) that instead of despite it would make more sense to write: AS A CONSEQUENCE * *- think about it.* ** Bruno *John* On Tue, Jul 14, 2009 at 4:40 AM, Bruno Marchal marc...@ulb.ac.be wrote: Hi Kim, Marty, Johnathan, John, Mirek, and all... We were studying a bit of elementary set theory to prepare ourself to Cantor's theorem, and then Kleene's theorem, which are keys to a good understanding of the universal numbers, and to Church thesis, which are the keys of the seven steps. I intend to bring you to the comp enlightenment :) But first some revision. Read the following with attention! A set is a collection of things, which in general can themselves be anything. Its use consists in making a many into a one. If something, say x, belongs to a set S, it is usually called element of S. We abbreviate this by (x \belongs-to S). Example: A = {1, 2, 56}. A is a set with three elements which are the numbers 1, 2 and 56. We write: (1 \belongs-to {1, 2, 56}), or (1 \belongs-to A), or simply 1 \belongs-to A, when no confusions exist. The parentheses ( and ) are just delimiters for easing the reading. I write \belongs-to the relation belongs to to remind it is a mathematical symbol. B = {Kim, Marty, Russell, Bruno, George, Jurgen} is a set with 5 elements which are supposed to be humans. C = {34, 54, Paul, {3, 4}} For this one, you may be in need of spectacles. In case of doubt, you can expand it a little bit: C = {34, 54,Paul, {3, 4} } You see that C is a sort of hybrid set which has 4 elements: - the number 34 - the number 54 - the human person Paul - the set {3, 4} Two key remarks: 1) the number 3 is NOT an element of C. Nor is the number 4 an element of C. 3 and 4 are elements of {3, 4}, which is an element of C. But, generally, elements of elements are not elements! It could happen that element of element are element, like in D = {3, 4, {3, 4}}, the number 3 is both an element of D and element of an element of D ({3, 4}), but this is a special circumstance due to the way D is defined. 2) How do I know that Paul is a human, and not a dog. How do I know that Paul does not refer just to the string paul. Obvioulsy the expression paul is ambiguous, and will usually be understood only in some context. This will not been a problem because the context will be clear. Actually we will consider only set of numbers, or set of mathematical objects which have already been defined. Here I have use the person Paul just to remind that typically set can have as elements any object you can conceive. What is the set of even prime number strictly bigger than 2. Well, to solve this just recall that ALL prime numbers are odd, except 2. So this set is empty. The empty set { } is the set which has no elements. It
Re: The seven step series
On 14 Jul 2009, at 10:40, Bruno Marchal wrote: snip So the subsets of {a, b} are { }, {a}, {b}, {a, b}. But set have been invented to make a ONE from a MANY, and it is natural to consider THE set of all subsets of a set. It is called the powerset of that set. So the powerset of {a, b} is THE set {{ }, {a}, {b}, {a, b}}. OK? Train yourself on the following exercises: What is the powerset of { } What is the powerset of {a} What is the powerset of {a, b, c} I give the answer, and I continue slowly. 1) What is the powerset of {a, b, c}? By definition, the powerset of {a, b, c} is the set of all subsets of {a, b, c}. I go slowly. Is the set {d, e, f} a subset of {a, b, d}? No. None of the elements of {d, e, f} are elements of {a, b, c}. The question was ridiculous. Is the set {a, b, d} a subset of {a, b, c}? No. One element of {a, b, d}, indeed, d, does not belong to {a, b, c}, so {a, b, d} cannot be a subset of {a, b, c}. The question was ridiculous again, but less obviously so. Is the set {a, b, c} a subset of {a, b, c}. Yes. All elements of {a, b, c} are elements of {a, b, c}. {a, b, c} is included in {a, b, c}. Can we conclude from this that the powerset of {a, b, c} is {{a, b, c}}. No. We can conclude only that {{a, b, c}} is included in the powerset. It is very plausible that there are other subsets! Indeed, Is {a, b} included in {a, b, c}? Yes, all elements of {a, b} are elements of {a, b, c}. This take two verifications: we have to verify that a belongs to {a, b, c}. And that b belongs to {a, b, c}. Can we conclude from this that the powerset of {a, b, c} is {{a, b, c} {a, b}}. No, we could still miss other subsets. I accelerate a little bit. Is {a, c} a subset of {a, b, c}? Yes, by again two easy verification. Is there another doubleton (set with two elements) having elements in {a, b, c}? Yes. {c, b}. It is easy to miss them, so you have to be careful. All two elements of {c, b} are elements of {a, b, c}, as can be verified by two easy verification. Is {b, c} a subset of {a, b, c}. Yes, but we have already consider it. Indeed the set {b, c} is the same set as {c, b}. Is there another doubleton? No. Why? I search and don't find it. is there yet some subset to find? Yes, the set with one element, notably. They are called singleton. Here it is easy to guess that there will be as many singletons included in (a, b, c} that there is elements in {a, b, c}. So the singletons are {a}, {b}, and {c}. This can be verified by one verification for each. Are there still subset? Yes. We have seen that the empty set { } is included in any set. This can be (re)verify by 0 verifications, given that there is 0 element in { }.. Conclusion: There are 8 subsets in {a, b, c}, which are { }, {a}, {b}, {c}.{a, b}, {a, c}, {c, b} and {a, b, c}. And thus, The powerset of {a, b, c} is the set { { }, {a}, {b}, {c}.{a, b}, {a, c}, {c, b} {a, b, c}}. 2) What is the powerset of {a}? Answer {{ } {a}}. It has two elements. 3) What is the powerset of { } We could think at first sight that there are no subsets, given that { } is empty. But we have seen that { } is included in any set. So { } is included in { }. Again you can verify this by zero verification! But then the powerset of { }, which is the set of sets included in { } is not empty: It has one element, the empty set. It is {{ }}. Think that {{ }} is a box containing that empty box. Attempt toward a more general conclusion. The powerset of a set with 0 element has been shown having 1 elements, and no more. The powerset of a set with 1 element has been shown having 2 elements, and no more. The powerset of a set with 2 elements has been shown having 4 elements, and no more. (preceding post) The powerset of a set with 3 elements has been shown having 8 elements, and no more. The powerset of a set with 4 elements has been shown having 16 elements, and no more. (older post) In math we like to abstract things. Let us look at the preceding line with all the words dropped! This gives --- 0 1 --- --- 1 2 --- --- 2 4 --- --- 3 8 --- --- 4 16 --- On the left, we see, vertically disposed, the natural numbers, appearing with their usual order. On the right, we see, vertically disposed, some natural numbers, which seems to depend in some way from what numbers appears on the left. It looks like there is a functional relation, that is a function. The notion of function is the most important and pervading notion in math, physics, science in general, and we will have to come back on that very notion soon enough. The idea that there is a function lurking there, is the idea that we can guess a general law, capable of providing the answer to the general line: The powerset of a set with n element has been shown having ? elements, and no more. Can we determine ? from n. Surely it depends on n. In this case, a simple guess can be
Re: The seven step series
Bruno, I have no idea how to even begin to answer these questions. Have you given us the definitions we need to do so? marty a. - Original Message - From: Bruno Marchal marc...@ulb.ac.be I let those interested to meditate on two questions (N is {0, 1, 2, 3, 4, ...}): 1) What is common between the set of all subsets of a set with n elements, and the set of all finite sequences of 0 and 1 of length n. 2) What is common between the set of all subsets of N, and the set of all infinite sequences of 0 and 1. http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: The seven step series
On 16 Jul 2009, at 15:17, John Mikes wrote: I would not restrict 'a set' to what WE can conceive, or define now. (Not even within the 'math'-related domain). Nor do I. I never say so. On the contrary we will see how different are sets when seen by machines and gods, but to explain this it is necessary we agree on elementary properties and definitions on sets, so that we can proceed. Here by we you are free to take the we by any entities (machines, humans, gods, or whatever). the relations of the set-partners comes into play. Not only those which WE choose for 'interesting' to such set, but ALL OF THEM influencing the character of that ONE. Just musing. It is OK. The idea consists in simplifying the things as much as possible, and then to realize that despite such simplification we are quickly driven to the unprovable, unnameable, un-reductible, far sooner than we could have imagine. I may suggest (or: assume?) that instead of despite it would make more sense to write: AS A CONSEQUENCE - think about it. It could make sense. This would lead to finitism and or mechanism, which I am trying to share with you. But again, this is an anticipation, and can hardly been made precise if we don't train ourselves to think about those simple things before. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---