How real are real numbers? (2004)(arxiv.org) |
How real are real numbers? (2004)(arxiv.org) |
Timing wise Cantors proof was done the year before Lebesque was born; Cantor was a generation before Lebesgue, and Fourier a generation before that iirc. Godel's is a generation younger than Lebesgue. Lesbesgue and Borel were working at the same time - Godel was very young when he published his incompleteness theorem in the 1930s.
Areas of maths which are not number theory basically never mention the number which is twice five at all, and could be done happily without ever knowing that there was some privileged base in which we count the naturals.
2. The Planck length is the smallest unit of distance with any meaning.
3. The universe has finite diameter.
Discuss.
4. For extra credit: Given 2 and 3, above, it follows that both the diameter and circumference of the universe can be expressed in Planck lengths as integers with a finite number of digits. Discuss the concept that Pi is a ratio of two finite integers.
> Theoretical significance
> There is currently no proven physical significance of the Planck length.
4: At the precision of the Planck Length, you have two integers that are the closest physically-meaningful values whose ratio approximates pi.
In both cases, you're confusing mathematical abstractions with what is physically realizable in a discrete system. You can't (meaningfully) do that.
Intuitionism is a form of a constructive foundation for mathematics which (a) notes that any attempt to deny the uncountability of reals leads to difficulties and (b) any attempt to internally define them violates constructivity.
The resolution proposed is to posit the existence of "free choice sequences". These are essentially "unpredictable" sequences of potentially infinite binary choices. As there is no a priori reason to believe that they can be predicted they are able to be much larger than what is computable and thus can be used to give a characterization of the reals. Atop this you build a constructive understanding of free choice reals which behaves very nicely (at least foundationally... it points out all kinds of weirdnesses about what we assume classically to be the structure of reals).
What's very nice about this solution is that it sidesteps the difficulty. Free choice is a weaker thing to ask for than finite/constructive reals, but finite/constructive reals could be transparently encoded into free choice sequences and all the math would just work.
[0] https://www.amazon.com/Elements-Intuitionism-Oxford-Logic-Gu...
Of course, most mathematicians are not finitist, so they require neither intuitionism nor formalism -- both essentially finitist philosophies -- and are Platonists, believing that even ideal objects that are beyond physical reality and computation have a "real existence" in some Platonic sense.
BTW, I think that after Turing (who used Brouwer's choice sequences in his construction of computable numbers) it is no longer necessary to rely on "free choice" (or lawless) sequences because of the halting theorem, and both lawlike and lawless sequences can be unified, and Brouwer's "creating subject" identified with a Turing machine. But I'm not sure about that. Turing -- who was a mathematical philosopher himself -- rejected any dogmatic a priory philosophy of mathematics, except for common sense, as the one true foundation, and suggested that the value of a formal system be derived not from its a priori philolosphy but from its ad hoc utility.
Without knowing too much about about the subject, I've vaguely wondered about this idea for a long time, now, but I figured it likely an un-respectable position. I think it's too bad that beginners are often shielded from controversies in foundations.
Within the past few years I ran across an alternate approach to calculus, which if I recall correctly, achieves the same basic results, but without the same notion of infinitely small slices and so on... now I can't find it to link.
I don't have a real, formal horse in this race, but the way that I have things arranged in my mind is that these are all disagreements on the notion two things in logical foundations: the need to consider time/resources and the conception of logical systems as closed or open.
Brouwer and Hilbert accept that time is a factor, but handle it in different implicit ways. Hilbert differentiates between finite (time accessible) and infinite (not finite) and then makes a plea that this divide doesn't much matter. His Program sought to prove it and then Turing and Godel and the like shattered that dream. Brouwer philosophically treated proof as communication and thus Intuitionism handles time and resource naturally (though not explicitly like a Kripke model).
Brouwer was forced by this choice to leave his mathematical foundations open ended as well. At any given level of effort there is a finite set of things we can prove/talk about/know and the rest must be left unknown, but likewise at any point in time we can incrementally increase our knowledge. Intuitionism is complex in order to handle that openness.
Bringing Turing in makes openness and expense/time immediately obvious. Turing machines are a model for an open world of knowledge: once you have a partial halting oracle G I can build a new program which your oracle fails on. Godel took it to the next level: your own formal system cannot prove its own consistency, but using it I can create a larger universe where it can be proven consistent.
In each case, the result arises from wanting a formal closure of your foundation and both use self-reference to create a (co-)inductive means of incrementally enlarging your system forever.
So I think Brouwer beats them to the punch in a certain way by taking that continuous finitary expansion as foundational itself.
Free choice can't be modeled formally by "Turing machines" because we possess a means for writing them all down. On the other hand, if I give you the trace of a Turing machine you have no (finite) means to predict it so "Turing machine traces" do provide the largeness you need. I don't really know how to handle the fact that someone might want to form a bijection between the two. To me it makes me think immediately of information hiding behind an abstract interface: even though you could eventually know an implementation of the interface, you spend most of your time working ignorant to it and often have more power for doing so.
I'm definitely no expert here, but I think it's all really fascinating. Definitely agree that Brouwer didn't produce anything of much use to day-to-day mathematicians, but that's sort of Hilbert's (and Turing's) point: practical common sense doesn't seem too impeded by this.
I think as computer scientists we're essentially carrying out a certain mathematical/philosophical program in this debate, fwiw. Turing showed that if you take working computationally very seriously that you will run into open-endedness and time-as-resource constraints very quickly. Programming is a long exercise in discovering just have very seriously you have to take both of those things (interfaces, abstraction on one side, resources, human patience on the other).
Brouwer and intuitionism are subsequently having a bit of a resurgence in mechanized proving. The non-computability of reals shows its ugly head every time someone working in computational optimization has to write `compare_espilon` instead of just `equals`. Or, perhaps even better, every time someone gets bitten by thinking IEEE reals are "mathematical reals".
I also really like to imagine this because I love this idea that each programmer is unknowingly taking very tiny steps along a grand philosophical program. Unromantically it's obviously true, but there's something fun in trying to imagine just how profoundly computers may yet still impact our understanding of the world.
Sure you can state them as a "fact", but that undermines quantum theory itself and the Universe.
If you want to do the math right you really need to consider terms as peak probabilities and work from there. (See Chaos theory)
IMHO
Of course doing math with hard constraints is perfectly adequate for most macroscopic calculations.
That said, errors do add up given sufficient entropy and time.
It's quite simple to add fuzziness into the equations but quite a pain in the ass to compute with, plus you will in most cases get the same answer anyway.
As far as real numbers, they are no different from integers, just shift the decimal.
I think Borel has confused names with things. The fact that we can only write down only countably many expressions for numbers doesn't mean that there are numbers that we may never write expressions for - only that in a single symbolic system we can't have expressions for all of them at once.
Besides, if you confuse extant with useful you might end up believing that some random large integers aren't "there!"
One thing that I think is important to note though is that the jump from real numbers to complex numbers is nothing compared to the jump from integers/rational numbers/etc. to real numbers. The complex numbers come about by simply adding one dimension whereas the real numbers come about from an abstract "completion" of (say) the rational numbers in a very specific mathematical sense.
My point is that deriding "imaginary numbers" (as many do) is total nonsense if you accept real numbers.
Here is how far: Everything written in words about the physical universe is, by necessity, discrete. Thus all information that can be encoded in human languages is discrete. Any non-discrete behavior of the physical universe which causes a change in the discrete information available to us, must, by assumption, have a component which is orthogonal to all of the prior discrete information (otherwise it is fully discrete). Since this component is independent of all previously available information, it looks like randomness.
In other words: from the viewpoint of a discrete (linguistic) observer, the behavior of a continuous universe looks identical to that of a discrete universe that contains random fluctuations.
What is interesting, then, is that observationally, our discrete observable universe is full of random fluctuations. Speculation as to their true continuous underpinnings is, however, unfalsifiable, unless the randomness itself can be made to disappear. I usually turn the question around: is it inconceivable that there would be a continuous universe with inhabitants that used a discrete language?
So:
>According to these ideas the amount of information in any physical system is bounded
"the amount of observable information in any physical system" -- any unobservable continuous information shows up as unpredictable changes in the observable information.
Tegmark takes a similar, but rather extreme, MW approach in his book 'Our Mathematical Universe'.
Personally, I struggle with Tegmark's use of Measure Theory, and proponents of various Anthropic Principles, because they seem to have a completely broken frequentist view of probability and inference.
I really enjoyed the beauty of this statement.
http://www.mathrix.org/liquid/archives/the-history-of-the-ch...
"God has chosen that which is the most simple in hypotheses and the most rich in phenomena. But when a rule is extremely complex, that which conforms to it passes for random."
"Everything can be summarized in one thing, but the thing itself cannot be reached."
"Mathematical facts are true by chance."
"To make all things from nothing, unity suffices."
So I would argue that it illustrates nothing of significance under either of those issues.
Paper:
https://arxiv.org/abs/1609.01421
https://math.ucr.edu/home/baez/continuum.pdf
Blog summary with discussion:
https://johncarlosbaez.wordpress.com/2016/09/08/struggles-wi...
https://johncarlosbaez.wordpress.com/2016/09/09/struggles-wi...
If you only have one finger then zero and one are just as real (ahem) as numbers that arise naturally when you have 10 fingers. The 10 toes are a bonus. I doubt that we can really know what Pythagoras really thought but given some of the results attributed to him I think Chaitin does him a disservice.
Getting wound up over whether French is a sophisticated enough language to describe numbers and some of the odder consequences of allowing construction to equate existence will probably only lead to a headache.
As a civilian wandering on the outskirts of all this philosophical foot stamping, I believe there are a fair few pretty rigorous arguments out there that can't be denied by resorting to "it looks wrong, cos reasons" style illustrations in a 13 page pdf.
Unless I have completely missed the point then he has simply stated a way to generate another member of the set of French texts which of course is part of that set and so on.
You can easily squint hard enough to generalize to all texts in all languages, now, earlier and possible then allow that grammar, spelling and so can be pretty slack. Now translate that lot into numbers in some way (a bunch of IT bods should be able to manage that!) To be honest French on it's own is probably more than enough.
"How very embarrassing! Here is a real number that is simultaneously nameable yet at the same time it cannot be named using any text in French."
The very act of naming the number (in French) constructs the French text that adds to the set of possible French texts.
I think that the set of possible French texts is exactly as large as the set of reals. So is the set of all language texts and that the "paradox" is merely trying to use the Cantor argument backwards.
Here is the direct link: https://arxiv.org/pdf/math/0411418.pdf
"Indeed, the most important thing in understanding a complex system is to understand how it processes information. This viewpoint regards physical systems as information processors, as performing computations. This approach also sheds new light on microscopic quantum systems, as is demonstrated in the highly developed field of quantum information and quantum computation. An extreme version of this doctrine would attempt to build the world entirely out of discrete digital information, out of 0 and 1 bits."
It would indeed be quite a blast to discover we are to a high degree of probability in a simulation.
Now: one of the proofs in the paper relied on an assumption that all possible computer programs are countable, which I think implies that they are finite in length. But it is fairly trivial to generate computer programs that are infinitely long, say by assigning characters or expressions in some language to the digits of transcendental numbers such as pi. It is also possible to generate infinitely many such programs, simply by using pi/2, pi/3... etc.
Now, the proof as presented fails, since these programs cannot be ordered by size.
Can the proof be modified to take account of this? I don't know... comments invited.
For example, you suggest an assignment of expressions to digits of pi. Now how would you run such a program? Presumably by generating the digits of pi, interpreting them as expressions, and evaluating the expressions, etc.
But the program you used to do that was finite. So are you running the infinite program? I think it's more fair to say you are running the finite one.
And again, even the point about describing the world in 1s and 0s at the end seems to me to be repetitive of Whitehead & Russell's Principia Mathematica which (and please correct me) used logic to construct the integers?
Neither molecular biology nor the sane part of physics has any of em.
Btw, it is heuristic - if there are numbers involved then it is human made. Reality as it is has no such notion. Biology does not count.
Numbers require an observer, which is a by-product of the processes in vastly complex brain structures of the cortex, and cannot be the basis of anything in the underlying universe.
Any good (which means Eastern) philosophy arrived at these simple conclusions millennia ago.
Some would argue that PI is not an actual number; but that it is a concept, like infinity
I don't think that's true. There are only countably many different symbolic systems[1], and as we can only express countably many numbers in each, we don't leave the realm of countable.
[1] - A "symbolic system" must at least come with a procedure to tell whether a sequence is a part of it, and, unless you disbelieve the Church-Turing thesis, there are only countably many procedures.
Not saying I believe it, just teasing out assumptions. If one is arguing whether the universe is continuous and using the Church-Turing thesis as justification for something, there's a danger of circular reasoning.
Also, I think the parent commenter is getting more at naming vs existence rather than naming versus "could be named in the future." Is the argument boiling down to that something does not exist (is not "real") if it cannot be named?
Whereas the point being made is different and needs some math background which is the work of Cantor. Countable can include all natural numbers that you count until infinity, and the reals are uncountable in that they exceed even this.
The proof of this fact(Reals are uncountable), has the same idea involved in Turing machines halting problem and also Godel's theorem. The general version is the power set of a set(set of subsets of a set) cant be put in one to one correspondence with original set. If you assume such a correspondence, then (<guess the clever trick>) leads to a contradiction.
Reals are sequences of naturals which include sequences of 1's and 0's which can be interpreted as subsets of naturals(a sequence represents the subset of indexes which get assigned the value 1). So reals are bigger than the power set of naturals.
Also, the infinite countable union of countable sets is countable. The number of grid points(integer coordinates) on a plane is the same as the number of grid points on a line. You can set up a zig-zag correspondence. A salesman can visit all grid points on a plane in infinte time. This is used to prove rationals are countable. So even countably infinitely different symbolic systems doesnt help.
But what happens if we open it up to have statements be true, false, or currently unknown? That is we develop a system of mathematics that could be in principle done inside of a Turing machine?
Then Cantor's diagonalization argument falls apart because of all of those "currently unknown" options. See https://news.ycombinator.com/item?id=13843725 for a previous explanation that I gave of this.
Yes it does: there are countably many numbers we can define, and the reals are uncountable, therefore there are uncountably many numbers that cannot be defined.
A Platonist may believe that those numbers exist in an abstract space we cannot reach. A Formalist simply defines "existence" in such a way that this is true without worrying about whether they really exist. And a Constructivist denies the existence of things that cannot actually be written down, at least in theory.
> One occasionally hears the argument — let us call it the math-tea argument, for perhaps it is heard at a good math tea — that there must be real numbers that we cannot describe or define, because there are are only countably many definitions, but uncountably many reals. Does it withstand scrutiny?
then explains in detail why it does not withstand scrutiny.
EDIT: How do you know that a large number is "there" if you can't count to it? What would it mean for a large number to "be there."
Being-there is something special. ;-)
Consider that great big set. It's still countable. The thing that makes "real numbers" bigger than integers, the "extra" that real numbers have must be very, very peculiar.
You might be interested in:
https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf
"A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random(its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly noncomputable. The aim of this paper is to describe a procedure, that combines Java programming and mathematical proofs, to compute the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000"
You didn't prove that statement, and actually Cantor's diagonal arguments [1] proves you wrong:
Consider the set of «all real numbers which you can actually specify IN ANY FASHION AT ALL». If you can count it, you can order them in a certain fashion: n0, n1, n2, n3 … It's easy to specify a number X which is not part of this set (which is in contradiction with the definition of this set, and demonstrates ad absurdum that this set is not countable). To build such X, consider the n-th decimal of the n-th number: if it's zero, the n-th decimal of X is 1, otherwise the n-th decimal is 0. Then by construction, X is different from any number of this set, which mean X is not a part of the set. □
[1]: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure?
What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore?
I just making counter-examples to Jules Richard paradox formulation, showing that it's not properly formalized, but rather expressed in vague language, so cannot be considered strict mathematics.
In all seriousness, I don't know that we know for sure that the former doesn't in fact exactly mean the latter.
https://plato.stanford.edu/entries/platonism-mathematics/#Ex...
However, you might be interested in the effective topos. This is an alternate mathematical universe in which one can't define construct this real number. It has a number of curious properties:
* The statement "1 + 1 = 2" is true in that topos, just like it is in the ordinary topos.
* The statement "any number is either prime or not prime" is true in that topos, just like it is in the ordinary topos, however its truth is not trivial.
* The statement "any real number is either equal to zero or not equal to zero" is false in that topos.
* The statement "any function is computable" is true in that topos (and wildly false in the standard topos).
* The statement "any function is continuous" is true in that topos (and wildly false in the standard topos).
Details are in this set of slides:
https://rawgit.com/iblech/mathezirkel-kurs/master/superturin...
Questions are welcome!
It depends, as they say, on what the definition of is is. What does it mean for a number to exist if it cannot be described? What does it mean for a construction to exist if it cannot be constructed?
>if you confuse extant with useful you might end up believing that some random large integers aren't "there!"
The question isn't whether it's useful to claim the existence of uncomputable reals; the question is whether it's meaningful. A construction needn't be useful to be meaningful, but surely it must be meaningful to be useful.
All numbers ever written are rationals and thus countable. But those endless irrational numbers make a lot of ways of reasoning simpler, or possible at all.
If that were so, might it not offer a way to an "explanation" for the Banach-Tarski paradox that even the likes of I could imagine I understood? - that duplicate volume you constructed is made from the same reals, specified differently!
Not that that would be an argument for the proposition quoted.
I was going to say that I am not a mathematician, but that would be redundant.
In addition to the points already made about the "all at once" claim, every integer (every rational number, even) can be given a finite description (just write it down).
So I guess that probability has to be a rational number?
Pedantic positivist?
Reals are a useful sensory abstraction. Countability is another sensory abstraction, although for most people it's a rather less useful one.
There's no particular obligation for sensory abstractions to be logically watertight - if only because logic is an abstraction itself.
Complex numbers are also best thought of (in my opinion) as an abstract completion of the reals under the operation of taking roots of polynomials.
Because otherwise, what would be the difference between the real plane and the complex numbers? They are topologically identical, after all. There has to be something more substantial than simply adding a dimension.
In general, completing the rationals into the reals is more complex than constructing the complex plane from the real numbers. For the latter, you just need to adjoin a single element (sqrt(-1)), enforce existing arithmetic rules, and the rest falls into place. For the former, you can't just adjoin a single new element like sqrt(2). Doing so will get you the ring (actually field) Q[sqrt(2)], but not R.
If you take R and adjoin two special new elements (sqrt(-1) and the point at infinity), you do obtain a topologically different result: the Riemann sphere. This sphere is in many ways the more natural domain for complex analysis than the complex plane.
If you want you can write them down as matrices acting on vectors in an orthonormal basis by matrix multiplication:
[a -b]
[b a]
Or if you want you can write them using a length and an angle measure, and use high school trigonometry to figure out how they apply to vectors.
The difference between the real plane and the complex numbers is that for two vectors in the plane, the product is not a vector. (Indeed, if you use Clifford’s geometric product, then the product of two vectors is a complex number (scalar + bivector).)
Convergence is determined in the "Cauchy" sense by having a vanishing distance between subsequent sequence entries, so as not to rely on the (potentially nonexistent) limit.
Exactly. Real numbers are an invention to make mathematics simpler and cleaner. If you don't have continuous reals, it takes extensive case analysis to prove relatively simple things for, say, a binary floating point representation. It's possible to do that; Boyer and Moore did work like that to formalize floating point and check its correctness. (That work was funded by AMD, after the famous Pentium divide bug.)
Newtonian mechanics assumed that the physical universe is described by real numbers. But today, it seems that time, length, and mass are all quantized. There's thus not a physical basis for the existence of reals.
Maybe reals should be viewed merely as a useful convenience for analysis, not some fundamental part of mathematics.
"God created the integers. All the rest is the work of Man." - Kronecker
This is actually not the case. Space and time are not regarded as quantized by the majority of physicists and there's also absolutely no evidence suggesting that. To the contrary, such quantization would lead to inconsistencies – e.g. with relativity – pretty quickly.
Fur further reading:
https://physics.stackexchange.com/questions/9076/does-quantu...
https://physics.stackexchange.com/questions/67899/is-time-qu...
I have this concept of "materialization" and wonder if there is a formal mathematical term for it. Complex numbers are actual, in the sense that they can be used in calculations that finally would give us a number we can make sense of (materialization), even if we cannot actually imagine a complex quantity.
In the same way, what if we invent a new class of real numbers that are quantized (such that there exists a smallest quantity x)?
What if we propose the existence an "imaginary" algorithm (call it omega, if you like) that can decide the halting problem?
These mathematical objects do not have to "exist" for them to be useful. I think there is a whole lot of new and interesting math that would be unlocked by dispensing with our logical blinders.
Although our mathematical systems rely on the existence of computable procedures (that halt) to e.g indicate whether a formula is well formed or verify a proof, they have no trouble talking about uncomputable functions. There actually ends up being a hierarchy, as once you allow "solve the halting problem for this Turing machine" as an operation the expanded set of computable functions is now unable to solve its own halting problem: https://en.wikipedia.org/wiki/Arithmetical_hierarchy
> These mathematical objects do not have to "exist" for them to be useful. I think there is a whole lot of new and interesting math that would be unlocked by dispensing with our logical blinders.
These kind of things are actually pretty well studied. Some interesting examples are:
* The hyperreal numbers which include infinitely many distinct numbers which are infinite or infinitesimal: https://en.wikipedia.org/wiki/Hyperreal_number
* The surreal numbers which include all ordered fields as a subfield (reals, complex numbers, hyperreals, etc.): https://en.wikipedia.org/wiki/Surreal_number
* The quaternions and octonions, which along with complex numbers are the only finite-dimensional algebras over the real numbers that can have "division" and "absolute value" in the usual sense: https://en.wikipedia.org/wiki/Hurwitz%27s_theorem_(compositi...
In general, mathematicians are really good at investigating things of the form "Okay we have structure X with properties A, B, C. What if we get rid of C? How about B? How about B and a weaker version of A? ...".
This is called an oracle (https://en.wikipedia.org/wiki/Oracle_machine). We can posit oracles for solving computable problems in constant time (e.g. factoring the product of two arbitrarily large primes) as well as for solving uncomputable problems (e.g. halting problems).
Oracles are a great tool for studying complexity and computability, since oracle machines have their own complexity and computability limits; an oracle machine for the halting problem can determine whether a simple Turing machine will halt, but cannot determine whether it itself will halt (this is called a Turing jump). Thus oracle machines for halting problems form a class hierarchy, which Post's theorem shows is precisely the arithmetic hierarchy.
It depends on exactly what you mean by this, but I would argue that we do this absolutely everywhere. For example, matrices have similar properties to numbers. You can add/subtract them, you can multiply them, you can (sometimes) divide them. Depending upon how you restrict your set of matrices, ab might equal ba or it might be the case that ab makes sense while ba does not (i.e. not only is it not commutative, but it doesn't even make sense to multiply the other way).
> In the same way, what if we invent a new class of real numbers that are quantized (such that there exists a smallest quantity x)?
Here's an example of something similar:
https://en.wikipedia.org/wiki/Dual_number
Basically you're adding in a number smaller than everything else that squares to 0.
> What if we propose the existence an "imaginary" algorithm (call it omega, if you like) that can decide the halting problem?
I'm no logician, but I believe that they would refer to this sort of thing as "model theory". I.e. you're basically taking proofs (sequences of logical statements) and studying different logical systems in which these statements make sense. For example, you could extend your theory/model to take as an axiom that there exists an algorithm to solve the halting problem (though this would be stupid since you can already prove within most theorems that the halting problem is impossible...i.e. you would have a self-contradictory axiomatic system).
> These mathematical object do not have to "exist" for them to be useful. I think there is a whole lot of new and interesting math that would be unlocked by dispensing with our logical blinders.
I 100% agree. Math is a tool that we invent to better understand the world and our thoughts (as well as do more). However, you'll probably have to track down a true logician if you were to go down that rabbit hole...
> The complex numbers come about by simply adding back the missing dimension
Mathematics makes so much more sense with complex numbers. Trigonometry a great example of this.
No. In fact, your claim is contradicted by your own link. As stated by Asaf Karagila in the comments:
> Continuity is a property of functions. You seem to ask why the rational numbers are not connected (or path connected).
But you are correct that you don't need real numbers to describe continuous functions. As you link points out, one is a property of spaces (or domains or whatever you want to call it) and the other is a property of function.
However, talking about continuous functions between complete spaces (basically "complete" is what makes the real numbers "real") is extremely natural and basically goes hand in hand with continuous functions. It really ties together a lot of the theory if you're talking about metric continuity.
Regardless, you also don't _lose_ anything by talking about real numbers. You can of course use it as a tool to develop a theory and then choose to apply the results to the rational numbers (or algebraic, etc.).
If one takes natural language as a means to definite sets, you quickly get a plethora of paradoxes, for example Russel's paradox("Takes the sets of all sets that don't contain themselves. Does that contain itself?"). So if one takes "natural language" as one's system of defining set, one has to assume it's inconsistent and any statement is provably true and false. Thus "Richard's Paradox" is in the same boat as all statements in our "system of natural language".
That said, I think the proof in the text falls apart in another way - it neglects the distinction made in Skolem's Paradox. The Löwenheim–Skolem [2] theorem show that any system definable with a finite alphabet has a countable model. This is only an apparent paradox because this model is only countable when "viewed" from outside the model, within the model, it is possible to have ostensibly uncountable sets. So ones could certainly haves a countable model of the real numbers while the real numbers themselves remained uncountable as "countable" and "uncountable" were defined in the countable model.
[1] https://en.wikipedia.org/wiki/Skolem%27s_paradox [2] The https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_...
Which is why I think if you resort to natural language to refute the consequences of a more rigorous treatment of the concept of number then there will be trouble. The whole paper attempts to refute things like Cantor through a weird recourse to French.
However I think it is possible to reduce real numbers as being a sort of subset of French purely through the same construct that Mr Cantor describes because that's the way descriptions work. If you define a real in some way in some form of symbolic language - I recall from GED that SSS might embody "three" and so does "trois". So I don't see why French can't encompass reals SSS can be considered exactly equivalent to trois.
I suspect I need to know and understand the formal, rigorous definition of "real" before I really give it some.
Nope, because he used the diagonalization technique to make sure the new text was not in the original set, which supposedly contained all texts.
Funnily enough: 0,1,2,3,4,5,6,7,8,9 are French words along with . and ,
So, how do we proceed to define reals in French?
How? The set of French texts is countable and the set of reals is uncountable.
The point of the article is that most reals are useless in practice; pi and e might be transcendental and the transcendental numbers are uncountable, but they are both computable, and the set of computable numbers is countable.
If his point is that the universe is finite and finite methods are a more correct basis for physical sciences, then I'm open to that even if I'm not particulary interested (theoretical math objects are perfectly interesting in their own right to me). But if there's more to it than that, I'd appreciate the help.
pi and e are computable; we even know a bunch of programs which will compute them (to arbitrary precision; Google for "spigot algorithms"). Computable numbers are countable, so we can identify them with the natural numbers, and there's no need for "reals". For example, we might think about the tapes of a binary universal turing machine: we can enumerate them (empty; 0; 1; 00; 01; etc.), and hence the tapes/programs are isomorphic to the natural numbers; the computable numbers are the results of running those programs (this is easier to imagine with a separate "monotone" tape for writing "output").
What about the rest of the "uncountably infinite transcendentals"? I would claim that such an argument is too hand-wavey in the form you've presented it. Can you write down a uniquely determined transcendental number which is uncomputable?
Such numbers can be defined; Chaitin's "omega" is an example. However, it's difficult to decide whether such numbers "exist" or not: we can assume that the physical world "exists", by definition; things which can't exist physically, but can be explored mathematically, like pi and e, can be said to exist, although it's a leap of faith; uncomputable numbers can't really be explored mathematically, or in any way that we know. Can we still say they "exist"?
Consider that the digits of omega: whatever formal system you use to study it, the digits you "discover" are nothing more than a scrambled representation of your formal system's axioms; since the axioms are assumed rather than proven, the "discovery" is actually a circular argument.
> Whitehead & Russell's Principia Mathematica which (and please correct me) used logic to construct the integers
It's easy to construct the integers "using logic". For example, Peano constructed the naturals like this (more or less):
The symbol '0' is a natural
The symbol 'S', followed by a natural, is a natural
We can likewise construct the integers like this:
A natural, followed by the symbol ':', followed by a natural, is an integer
It's not too hard to construct something logically. The problem is what assumptions you're willing to make. Whitehead and Russell wanted to prove everything using only the assumptions of set theory; that's why it took them hundreds of pages to prove seemingly trivial theorems about integers.
Goedel's incompleteness theorem(s) showed that no set of assumptions is complete and consistent; hence proving some result using set theory is no better than proving it with some other system. In particular, if it's easier to construct a theory of integers (like the one above) than it is to derive one from set theory (like Whitehead and Russell), we might as well take the easy path :)
The event set is non-empty (i.e. there are rational numbers between 0 and 1) but the probability of picking one at random is zero.
First of all, the set of values in the range [0,1] that can be represented by a computer is not at all the same as the set of rationals. If you're talking about fixed-point or floating-point data types, then there are only a finite number of bit patterns (corresponding to dyadic rationals), so obviously the probability of hitting one of them precisely is zero.
You may think I'm just being pedantic here, but I'm really not. The theorem you described is only interesting because there are an infinite number of rationals between zero and one, and yet the set still has measure zero. But if you're willing to say that any rational number is theoretically "representable" in a computer, then you're already assuming that we can go beyond the natively-available data types, and come up with our own representations -- e.g., a tuple of numerator and denominator. And in that case, we can also come up with representations of irrational numbers; for example, you could have a datatype that can finitely specify any algebraic number, such as sqrt(2) or the golden ratio. So the fact that a typical CPU happens to only be able to natively deal with rationals is irrelevant.
The beauty of the diagonalization argument described in this paper is that it applies to all possible discrete representations, no matter how weird or complex, without having to make any assumptions.
"probability of randomly picking a rational number from [0,1] is exactly 0."
If to consider that as a lemma only ...
You cannot and will never be able to prove that, right?
In order to draw a rational number, you must randomly select a number that has a repeating pattern in decimal. Imagine that for the sake of argument that we're in this "repeating pattern" and, amazingly, we've already drawn it 1000 times! What a roll we're on! In order for the number to be rational, how many more times must we draw this pattern? Infinitely many. What is the probability that in one of those infinite fair random draws, the repeating pattern gets broken? 1. It's just not possible for infinitely many fair draws to produce a repeating pattern; that would be proof that the process generating the number was in fact not random in the first place. (I can't be that sloppy if we're doing finitely many draws but I believe that's justifiable at infinity.)
Imagining through this process of drawing a random number I think makes this more intuitively obvious than imagining being presented with a completed number and trying to figure out if it's rational.
Proof: what else could it be? If it's not 0, there's a smaller number, contradicting your (intuitive) definition of epsilon.
> I think it's too bad that beginners are often shielded from controversies in foundations.
Mathematicians generally shouldn't worry about foundations, as it is the intention of foundations to stay hidden -- except in cases where the foundation requires a rewrite of much of math, as in the case of Brouwer's intuitionism, but constructive math is pretty advanced anyway. Foundations are usually the concern of logicians, but from what little I've seen in online discussions, it seems like many logicians aren't interested in philosophy, either, and that's a real shame.
> I ran across an alternate approach to calculus, which if I recall correctly, achieves the same basic results, but without the same notion of infinitely small slices and so on
There's constructive analysis[1], which recreates analysis within the framework of constructive math (by finite means etc.), and there's also non-standard calculus[2] (which I know nothing about) that makes treat infinitesimals as actual numbers, which may be the opposite of what you meant, but maybe not -- I saw something about there being constructive versions of non-standard analysis, too.
All possible questions (infinitely many) - no, that would be a non-terminating non-periodic binary, right. From the article:
> 2.4 Borel’s know-it-all number
> The idea of being able to list or enumerate all possible texts in a language is an extremely powerful one, and it was exploited by Borel in 1927 [Tasi ́c, 2001, Borel, 1950] in order to define a real number that can answer every possible yes/no question!
> You simply write this real in binary, and use the nth bit of its binary expansion to answer the nth question in French.
> Borel speaks about this real number ironically. He insinuates that it’s illegitimate, unnatural, artificial, and that it’s an “unreal” real number, one that there is no reason to believe in.
The catch, here is "selecting a number randomly" - that isn't constructively defined. And to me this looks kind of similar to the notion of "measurement" in quantum theory - not precisely defined either.
Also, any infinite program either passes through a finite number of instructions or never terminates. So any program which does not have a finite representation will never terminate.
[1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Example: consider a language where 0 means "if the input register is at most 0, halt with the answer "no", otherwise, decrement the input register and continue to the next instruction" and 1 means the same thing except that it gives the answer "yes" instead.
Then the fractional part of any real, expressed in binary, would be a program that takes an integer as input, and answers whether that digit of the number is 1. This seems like it would count as a program to me.
So, this would allow there to be uncountably many "programs", only, almost all of them would be impossible for us to refer to specifically.
Hey, this way you could define a uniform measure over programs. Hah.
Wait, is that how Solomonoff induction stuff works? (Of course, with a richer language than what I described)
page 249:
> I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent.
And then in the footnote:
> If we regard a symbol as literally printed on a square we may suppose that the square is 0 < x < 1, 0 < y < 1. The symbol is defined as a set of points in this square, viz. the set occupied by printer's ink. If these sets are restricted to be measurable, we can define the "distance" between two symbols as the cost of transforming one symbol into the other if the cost of moving unit area of printer's ink unit distance is unity, and there is an infinite supply of ink at x = 2. y = 0. With this topology the symbols form a conditionally compact space.
[1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
That's a valid point -- if you read it in a certain way, the Church-Turing hypothesis indeed states that continuous models are no more powerful than the discrete ones. In fact, we have every reason to believe it's true. See [1], and references [BCGH07], [GCB08] in that paper.
[1] - http://perso.ens-lyon.fr/yassine.hamoudi/wp-content/uploads/...
But yes, with those assumptions, it does not hold. It is not as much that the argument is circular, but that the only tech we know how to use (symbols) limits our expressiveness.
(Any countable set has a well-ordering, because a bijection with the natural number gives you one in an obvious way. The trouble is that you need well-orderings for all of them together. The unusual term "counted" emphasizes that we need the actual "countings" to do the job, whereas for me "well-ordered" is sufficiently commonplace that it doesn't shove in my face the requirement that each set come along with a specific choice of well-ordering.)
But in that case, why is is more probable to pick an irrational number?
What do you mean by "arbitrary?" Do you mean uncomputable? How does analysis require the existence of uncomputable reals?
>All numbers ever written are rationals and thus countable
It is also possible to "write" computable irrational numbers, more or less by definition.
I don't know what the other person was referring to, but from many important theorems of analysis you can prove the existence of uncomputable reals. For example, from the theorem that a continuous function on a bounded interval is uniformly continuous you can prove that there exist uncomputable reals. If we think that this theorem and many more like it are necessary for analysis, we must conclude that analysis requires the existence of uncomputable reals.
The above fact comes from the area of mathematical logic known as reverse mathematics. The idea is in the name: rather than proving theorems from axioms, we go in reverse. We take some theorem and we see what axioms we can derive from it (using a weak background theory). This gives us a sense of the logical strength of a theorem; the stronger the axioms we can prove from it the stronger the theorem.
An amazing fact is that most classical theorems of mathematics have their logical strength captured by one of five sets of axioms. The weakest are those which are outright provable from the weak background theory (briefly, the background theory, called RCA_0, says that you're allowed to do computable processes). The next is the theory WKL_0, formed from RCA_0 by adding an additional axiom, which goes by the name weak Kőnig's lemma. This axiom states that any infinite binary tree has a cofinal branch (it's a lemma in 'ordinary' mathematics but in reverse mathematics gets treated as an axiom). This is the theory which captures the logical strength of the theorem I mentioned in the first paragraph. From weak Kőnig's lemma we can prove the existence of uncomputable reals. We can construct a computable infinite binary tree so that any branch through it must be uncomputable. From such a branch one can build an uncomputable real, say by insisting that the nth bit in its binary expansion is 1 if and only if the branch went left at level n.
(The easiest way to build such a tree is to go through the halting problem. The basic idea is to construct a tree of attempts to solve the halting problem. It turns out this can be done in a computable way, and any branch through the tree will allow us to solve the halting problem and thus must be uncomputable. The key fact used is that while there's no computable procedure to check whether a Turing machine halts at some time, you just want to know whether it halts in n steps (for fixed n), then you can check that with a computer. The program is easy: simply simulate running the Turing machine for n steps and see whether it stops at some point.
To build our tree: list the Turing machine programs as p_0, p_1, p_2, ... (This listing can be done in a computable way.) We will associate level n+1 on the tree with p_n. Start with a single node for the root of the tree. Then, to build the (n+1)-st level of the tree, look at each node t on the nth level. Check, in a computable way, whether p_0, p_1, ..., p_(n-1) halt within n steps. If none of them halt, then t has a left and right child at the next level. If p_k does halt within n steps, then look below t to see whether you took the left or right path at level k to get to the node t. If you took the right path, then t gets no child nodes. Otherwise, if you took the left path whenever p_k halts within n steps, then t gets two child nodes. Intuitively speaking, at stage n we keep our options open and don't decide whether p_n halts. But if we later see that it does halt, then we retroactively fix any mistake by not going any further along paths where we guessed wrongly before.
For example, it could be that p_0 halts but it takes 1000 steps for this to happen. So while building the tree when you get to level 1000 you'll suddenly stop building any further the entire right half of the tree, since you finally learned that p_0 halts and that you wanted to go left at the root node all along.
This process for generating the tree is computable, so by definition it's a computable tree. It's infinite, because you can keep building the tree upward if you happened to have guessed correctly whether each Turing machine so far halts. However, no branch through this tree can be computable. This is because a branch goes right at level n if and only if p_n didn't halt within k steps for any k. That is, the branch goes right at level n if and only if p_n doesn't halt, so from a branch we can decide the halting problem.)
----
Probably the best reference for reverse mathematics is Stephen Simpson's book Subsystems of Second-order Arithmetic. The first chapter is freely available on his website. It nicely lays out the philosophy behind the project and the major results while deferring (most of) the technical details to the rest of the book. http://www.personal.psu.edu/t20/sosoa/chapter1.pdf
Besides that, the wikipedia page for reverse mathematics isn't awful, but neither is it very good. https://en.wikipedia.org/wiki/Reverse_mathematics
Well, his most famous paper, the one in he was first discovered the essence of what computation is (rather than merely asking what functions can be computed by a "definite procedure"), was named On Computable Numbers, and he uses the very problem of the real numbers as a segue into the more general topic of computation.
> Free choice can't be modeled formally by "Turing machines" because we possess a means for writing them all down. On the other hand, if I give you the trace of a Turing machine you have no (finite) means to predict it so "Turing machine traces" do provide the largeness you need. I don't really know how to handle the fact that someone might want to form a bijection between the two.
I don't think there is any such bijection (if only for the cardinality argument you mention), but that it turns out (thanks to halting), that lawful and lawless sequences are equally opaque: it is as impossible to determine (using finite means) whether two lawful sequences are equal as it is to determine whether two lawless sequences are, which is all that's required (I think) for the theory. Therefore the same idea that Brouwer had in mind does not really require lawless sequences (which, I think, he wouldn't have introduced if he'd known about halting).
> Turing showed that if you take working computationally very seriously that you will run into open-endedness and time-as-resource constraints very quickly. Programming is a long exercise in discovering just have very seriously you have to take both of those things (interfaces, abstraction on one side, resources, human patience on the other).
It's a bit more complicated, as Turing himself -- in his published conversations with Wittgenstein -- opposed intuitionism as a foundation, believing that math neither has nor requires one true formal foundation. After all, Formalism is also finitistic, and you can just as well use a program to prove a theorem about (classical) real numbers using finite means; there's no need to construct -- i.e. give specific meaning to -- each real number. That was Hilbert's point: it is enough to reason about mathematical proposition in a finitary manner, and there's no actual need to construct the objects in their domain of discourse with finitary means.
> Brouwer and intuitionism are subsequently having a bit of a resurgence in mechanized proving.
Yes, but I think the relationship is more complicated. Again, a mechanical prover can prove classical propositions -- by using deduction rules -- just as it can prove intuitionistic propositions. The resurgence with respect to mechanical provers, as far as I understand, has two reasons: 1. it is easier to create a tiny universal core for a mechanical prover based on intuitionsitic logic, and classical logic can then be built on top of that. 2. much of the research on the theory of functional programming rests on the desire (explicitly stated by Martin-Löf) to unify programming and constructive math. I personally find this approach misguided for various reasons (I'm not a mathematician or a logician, so I see this from a practicing programmer's perspective), but I can understand the appeal.
> there's something fun in trying to imagine just how profoundly computers may yet still impact our understanding of the world.
Oh, absolutely. Once Turing realized that computation is in a very strong sense a fundamental natural phenomenon, he understood the many implications (on logic, AI, biology and physics).
I also think that's enough.
I think when you mention that it's easier to build a mechanistic theorem prover on an intuitionistic foundation that it's a bit more "foundational" a problem than it seems. Theorem provers need (some kind of partial) equality on propositions and on proofs in order to function, but propositions are too rich to support finite equality. This backs you into a more intuitionistic approach.
Why do you say that? The finitary deduction rules of all logic systems provide both equivalence (<=>) and partial order (=> or |-) relations. Classical logic gives rise to a boolean algebra, while intuirionistic logic forms a Heyting algebra, of which boolean algebra is a special case. The latter is more general, but both are bounded lattices, and both are perfectly fine.
Would you mind producing such a phrase?
> What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure?
> What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore?
You may as well ask whether someone understanding a theorem has any bearing on its truth value. A well-formed sentence in a formal language has one and only one meaning regardless of whether a specific person understands it. That's the whole point of using a formal language. If meaning is actually somehow bound to its interpretation then communication of even the simplest of mathematics is totally impossible.
Well, I see your point, if we limit our phrases to only formal language, then you're right.
These sentences describe functions, not numbers.
> "One, if P=NP, zero otherwise".
This value is a constant. It doesn't change through time. We simply don't know what it is.
IMO, these kind of numbers are no more "real" than infinitesimals: https://en.wikipedia.org/wiki/Hyperreal_number
The way you defined that number makes it a perfectly valid element of the set R, as described by, say, the axiomatic definition here:
https://en.wikipedia.org/wiki/Real_number#Axiomatic_approach
Whether it's easy or hard or computationally intractable to compare it to other numbers, that's a totally different question unrelated to its definition.
Plus, you can actually empirically compute a finite set of initial digits (a specific Turing machine can be analyzed to see if it terminates or not), so you can compare this number with one that's constructed by flipping its digits, or with pi, etc.
In constructive mathematics, there is a perfectly well-defined set of real numbers. The usual diagonalization proof that this set is not a countable set applies.
Well, the fact that the number is not computable means that there will exist an index i, for which you will not be able to compute a_i (no matter how hard you try). In other words, you will not be able to analyze the Turing Machine i, i.e. it will not be possible to prove the termination or non-termination of the Turing Machine i.
So this specific digit will be a mystery forever, and you would not be able to compare it to anything.
[0] Specifically, the dual numbers: https://en.wikipedia.org/wiki/Dual_number
A constructivist would probably state the result more positive (and stronger, constructively): To every countable set M of real numbers, there is a real number not contained in M.
A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument.
What does make real numbers weird when working constructively is that you cannot conclude |x| > 0 from x != 0. This means that 1 / x need not exist even if x != 0, so the real numbers do not form a field in the classical sense.
If you don't trust me, maybe you'll trust wikipedia: https://en.wikipedia.org/wiki/Constructivism_(mathematics)#C....
Mayhap.
>A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument.
But in any case you misunderstand Cantor's argument and constructive mathematics.
mbid is correct; Cantor's diagonalization argument constructively proves the uncountability of the real numbers, see e.g. Bishop-Bridges' CONSTRUCTIVE ANALYSIS, Theorem 2.19, page 29.
I have a similar (and I believe to be equivalent) problems with infinitesimal as well. How does arbitrarily small but non-zero become infinitesimal? Since I have problem with infinitesimal, I find the differentiation of real numbers and rational numbers equally non-sensical.
So mathematician, take a pause, could you explain what is countable infinity? Since you never can finish counting (all the natural numbers), how does it make the set countable? What do we mean exactly by countable here?
Wikipedia refers to the idea of one-to-one correspondence. But since you can never exhaust the correspondence, what do we mean by one-to-one? Give me any unique real, I'll give you a unique natural number, and we can go on forever, so how does that not count as one-to-one correspondence?
Unlike mathematicians, physicists are fine with unresolved :)
PS: I guess countable can be defined as there is a definite way of ordering the set, which is true for natural numbers but questionable for real numbers. I still don't see how the ordering connects to the size of infinity and one to one correspondence. Even for the set of real numbers, I can have an algorithm continuously generate random numbers (discarding re-occurring ones so it will be a unique sequence) and prove there is an order of the set (non-exhaustively defined, same as the set of natural number). The ordering may not be describable though. But non-describable ordering is still an ordering, right? Just as a real number that cannot be exhaustively described is still a number. I don't have to describe it, I can hand-wave it just as the way mathematicians hand-waved the infinity.
So for example, the set of natural numbers is countably infinite and we know this because we can write a function that maps each natural number to exactly one natural number: the id function.
We can extend this and say that the set of even natural numbers is countably infinite because it has a mapping function of x => x / 2.
The same is true for all integers (natural numbers + negative numbers): x => if (x < 0) { x * -1 * 2 } else if (x == 0) { 0 } else { x * 2 + 1 }, i.e. if it's negative map it to an even number and if it is positive map it to an odd number, if it's zero map it to itself.
You can even write a function that maps all rational numbers to the natural numbers, since each rational number can be written as a fraction of two integers. (Figuring out the function is a fun exercise but it is also easy to google)
However, you can't write a function that maps any real number to a natural number. The easiest to understand proof of this is Cantor's Diagonal Argument[0], which is a proof by contradiction that shows that any attempted function must exclude some real numbers. Therefore, the real numbers are not countably infinite, and we call them uncountably infinite.
EDIT: In response to your edit, Cantor's Diagonal Argument basically shows that for any given function (and you have to define the function completely ahead of time - that's key) I can give you a real number that is not included in the domain of your function.
[0]: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
The computational techniques from Automatic Differentiation use these types of entities to calculate derivatives exactly without approximating infinite (limiting) processes.
Calculus can be done constructively without infinite limiting processes purely algebraically using these nilpotents. And from a geometric interpretation there is nothing nonsensical about a tangent line to a curve.
Also you don't differentiate numbers (real or rational), you can only differentiate functions.
Also the idea of a actual infinity is a poetic mathematical one. It doesn't have to fit reality. The issue is whether it is useful and to what extent.
Not what countable means. The meaning meant is the one about having a map from the set to the integers, where no two things of the set map to the same integer.
The correspondence is meant as either a full thing, or at least a well defined specification which could be applied to any of the things, if you want to get philosophical about ontology or something.
Also, the specification can't depend on things like, what reals have been given as input "previously".
Say that in this game, you have two obligations:
1: for any n,m I give, you must tell me what the mth binary digit of the real number associated with n is, in the mapping you are considering (or, if there is no real number associated with that natural number.).
2: For any finite collection of the binary digits of the real number I am choosing, you must tell me the first natural number such that the corresponding real number matches all the digits I specified.
With these rules, I can choose my real number (specifying more and more digits) such that for any natural number, I will be able to show that my real number doesn't correspond to that natural number, or any lower one.
Therefore, there is no natural number that corresponds to my number in the matching system you are providing.
(To win, I repeat this procedure:
Ask what the first natural not ruled out already by my specification of my number is. (Call that n)
Ask what the nth digits of the real associated with n is.
Inform you that the nth digit of my number turns out to have the other value for its nth digit, so no natural less than or equal to n corresponds to my number.
Repeat.
This will only ever tell you more about my number, and will not result in me changing my mind about any of the digits of my number, yet there is no natural number which won't ever be ruled out as potentially corresponding to my number.
Therefore, no natural corresponds to my number in your system.
So I win.)
Start counting the naturals: 1, 2, 3, ...
At future timelike infinity you'll reach infinity.
Now for the reals. Your goal is to step from 0 to 1, by way of 0.1, 0.01, and so forth.
0 0.0........
At future timelike infinity you still haven't stopped adding in zeroes to the right of the decimal point.
In the first case, at any finite time before \breve{i}^+ you will have counted out some finite natural number. In the second case, you will not yet have counted out your first nonzero real.
This survives across changes of positional counting systems, and almost certainly survives arbitrary choices of non-lossy notation, as long as you start with a finite representation of 0.
Yes, the counting process is non-terminating. But every item gets counted after only finite time.
In my view, every real number is well-defined and there's nothing controversial about the set of real numbers. If the infinite aspect of it causes some researchers to call it a "mathematical fantasy", so be it, so is literally every other mathematical model we use in our lives.
> I'd ask you if this set intersected with [0, 1] has a lower bound / 'inf' that's contained in it, and if so, did I just describe that lower bound with language?
The "indescribable numbers" are dense in [0,1], and so (if the set exists) the inf of the set of indescribable numbers which are between 0 and 1 is 0. Perfectly describable.
How so? The set of definable numbers in any formal langauage might not be clear concept. But you are making a stronger statement.
For any given language, like for instance ZFC, we can say that definable numbers are a countable subset. Hence measure zero.
How do you guarantee that you can compute the n-th decimal of the n-th number in the list? In fact, from what I understand, this paper[1] shows how to specify exactly a number can't be computed like that.
Then `floor(Ω.10^(n))-10.floor(Ω.10^n-1)` is also a number (a natural one) and actually it's the n-th decimal of Ω. It cannot be computed, but it still exist no matter what.
But well, now that we've proven that such sequence doesn't exist, we've proven that the given set is not countable !
Not the most elegant proof ever, but I think it works.
Also why is this unfortunate? Why does it matter if they do or do not "believe" it? Are they able to make useful predictions with their models? Are they able to better understand physics? If so, why worry about their personal beliefs?
If we want to be "true" and fully rational then we need to try to accurately represent our degree of knowledge about the world. Thus we shouldn't be making strong statements about things with an absence of evidence.
On the other hand, observations about Lorentz symmetry holding at distances on the order of the Planck scale put a wrench in a bunch of discrete spacetime theories. I don't really understand the math, though.
All this is somewhat tangential to the issue of real numbers. Real numbers are not necessary for continuity.
QM (and QFT) assume a background time, it is not an observable, even though it appears to commute with energy (e.g. energy is momentum in the time direction). So it's more tricky to understand how time emerges in a discrete Quantum Gravity, but I suspect there is an intrinsic proper time, defined by interactions with the 'vacuum' (minimal field states on the underlying lattice), which bootstraps a relational time defined over intervals between interactions.
Some of them extremely useful :)
You know of any continuum that doesn't include the real numbers? That will contradict the continuum hypothesis.
If true, then we can think of the continuity just as a convenient interface. All experimental questions can be answered by a simulation with a discrete state space.
(That is, presuming that you're speaking of the particle physics Standard Model, not something in cosmology.)
Either way, my point above was that this entire branch is not "mainstream math" by any means, AFAIK
I just wanted to clarify that intuitionistic and constructive mathematics don't have any problems with infinite constructions either. Finitism and ultrafinitism do, but they're not what's usually called "constructive mathematics".
There are at least three orthogonal axes which you can classify mathematical schools of thought in:
* Is the law of excluded middle accepted? ("Any statement is either true or not true.")
* Are infinite sets accepted? (They are not in finitism, but they are in constructive mathematics and of course in ordinary mathematics.)
* Can constructions implicitly refer to the result of what is being constructed? Is the powerclass of a set again a set? (Yes in ordinary mathematics and in constructive mathematics, no in predicative mathematics.)
See, I claim that this set is ill-defined, so I can't know its properties like whether or not it's dense, open, closed, Borel-measurable, etc. etc.
You have to tell me what its properties are, and I will come up with a concrete proof that the set in question is ill-defined.
EDIT: After I RTFA'd, this is actually the paradox in section 2.3 of the linked article
Yes, and if we think deeper about it, we'll find out that in mathematics we very often use functions in place for numbers, like it was the same thing. Simple example: √2. Even it form suggests that we apply function "square root" to number 2. Less obvious example: π. It's also a relation between diameter and circumference.
If we go even deeper, trying to understand what, for example, number "2" means, we'll come up to their definition through functions (or classes) of equivalence of sets cardinalities (cardinal numbers), or order (ordinal numbers), where sets are defined using ZFC, for example.
I met this discrepancy while naively trying to program mathematical logic in college. In mathematics you just "take" a number, while in programming you "create" or "instantiate" a number, and it has a ton of consequences.
>> "One, if P=NP, zero otherwise".
> This value is a constant. It doesn't change through time. We simply don't know what it is.
Not necessarily a constant, as it's not proven to be a constant yet. As an example of how it may turn out to be non-constant, check out Continuum hypothesis proof (https://en.wikipedia.org/wiki/Continuum_hypothesis) : solution is independent of our axiom set. In other words -- we can state that ℵ1=c, or we can say ℵ1!=c, and both statements will not contradict anything else. We'll just get two different models, with one more axiom each.
√ is a function. √2 is the result of applying √ to 2, which is a number. Since "how Giants scored last season" is a function, it can be applied to a value such as "2017-04-17", therefore "how Giants scored last season, and today is 2017-04-17" would be a number.
I don't follow your P=NP argument. Either P=NP or P!=NP. They can't both be simultaneously true. I also don't follow how the continuum hypothesis is relevant. = is not comparing the cardinalities of P and NP, it's asking whether they're the same set (i.e. all elements of P are in NP and vice versa). Again, either they're the same set or they're not. Even if there was a cardinality between that of N and that of R, I don't see how that would change how we compare sets for identity.
I don't have problem with calculus -- or I wouldn't be able to do physics. I am having problem with calculus based on infinity.
> Also the idea of an actual infinity is a poetic mathematical one. It doesn't have to fit reality. The issue is whether it is useful and to what extent.
Well said.
> Also you don't differentiate numbers (real or rational), you can only differentiate functions.
Of course I meant distinction.
There is no such things as «two successive real numbers».
As for implications that can't be falsified, for example ones that (to butcher Douglas Adams) "rather involve being on the other side of the event horizon," scientists can and do feel free to disregard those. Contradictory assumptions by scientists do not imply that one of them is "wrong" unless their theories imply contradictory observable phenomena. In which case there is probably a fruitful experiment to be done.
1. What does it mean to be "discrete on a macroscopic level"? (If a universe were discrete, would it not be discrete at any scale? When we use the term "discrete", are we talking about state space, or discrete spacetime, or what?)
2. What does it mean for a universe to "inherently [be] a natural number"? (Universes are not numbers, right? Is some sort of claim that the universe's state space is finite?)
3. What does have to do with whether a universe was "intelligently created"? (How can it possibly make sense that "intelligent creation" is an alternative to a discrete universe? The claims seem entirely unrelated.)
The "explanation" comment doesn't attempt to explain anything so I'm not sure why you call it an explanation. (Well, perhaps it explains that a conditional with a false antecedent is logically true, but most people here already know that, so pointing it out is not a great way to contribute to the discussion.)
This happens fairly often in mathematics, where similar-sounding terms are used to describe completely different concepts, or the same term sometimes means different things in context, or sometimes an Adjective Noun is neither described by Adjective nor by Noun.
That's not really ELI5, but remember learning derivatives in calculus? Just like you can't take the derivative of a function which isn't continuous, you can't use the Standard Model if spacetime isn't continuous.
Um... roughly the same. Is Robert Mugabe a king? Since we didn't give a clear and precise definition of "king" you can't really say.
For any way of doing the mapping, there is a real number that the mapping misses. Alternative statement: "there is no such mapping that doesn't miss any of the reals".
This is shown because, given a mapping, I can find a real that the mapping misses.
When one says "for all x, there exists a y such that P(x,y)", the y is allowed to depend on the x.
That's what this is.
Why wouldn't your objection apply to the proof that the halting problem is uncomputable ? The program that the halting checker can't check is defined in terms of the halting checker. Why is that allowed? Because that is what the statement is saying. For any purported halting checker, there exists a program it doesn't decide the halting of.
Similarly here, for any purported bijection between the integers and the reals, there is a real that the purported bijection misses.
I don't know if you are using the word "countable" in the standard way, so I don't know what you mean by that last sentence.
The general halting problem is uncomputable. It can only be simulated. However, any program is still assumed to be finitely described. Any discussion in finite domain (including arbitrarily big finite) cannot lead to conclusions or insight toward infinite.
> I don't know if you are using the word "countable" in the standard way, so I don't know what you mean by that last sentence.
In the context of infinity, words such as countable, bigger, order, etc. all lose its standard meaning. We don't really know what it means if we don't really know what infinity is. Mathematicians simply made a definition to countable here -- a finitely described mapping -- that is fine on its own, but completely useless. Since we can't draw any parallels from infinity to finite (including arbitrarily big), we can't really relate any definitions over the infinity to "standard" meaning of those words to the domain of finite.
https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#I...
Wikipedia says that the Cantor argument shows "no more" than that there is no bijection between the natural numbers and the real numbers. As far as I can tell, it also proves that there is no surjection from the natural numbers onto the reals in every system of constructive mathematics I know of, so I think this is slightly misleading.
What do you mean by "distinguishable"? In constructivism, a set A such that x = y or x != y for all x, y in A is sometimes called decidable. And yes, it is indeed not true that the real numbers are decidable. This would imply that there is an algorithm that decides whether two infinite sequences of ones and zeroes will differ at some point or agree indefinitely, which is pretty much equivalent to solving the halting problem. On the other hand, the natural numbers, integers, rational numbers and every finite algebraic extension of the rational numbers (for example Q[i], "rational imaginary numbers") is decidable.
Refer to my other reply, you asserted a requirement of predefined (describable) counting scheme here. Why that requirement has any relevance here (in the context of infinity)?
The proof that the adversary cannot name such an item is logically the same as a proof that every item gets counted. This is a fundamental logical truth, namely de Morgan's law for universal/existential quantifiers: (not exists x such that P(x)) is the same as (forall x, not P(x))
> Why that requirement has any relevance here
'A counting scheme' is an intuitive way of providing a 'one-to-one correspondence to the natural numbers,' which is used in the technical definition of countability.
I am leaving out any linguistic or Turing-computability aspects out of this, and people try to bring it back in, mixing computability with definability.
For instance, Chaitin's constant is a perfectly well-defined number, albeit uncomputable by construction: https://en.wikipedia.org/wiki/Chaitin%27s_constant
But that's the point - we cant produce such a definition for almost all reals.
I'm saying that ^ sentence makes no sense to me, I don't know how to parse it formally. If you start talking about the set of "definable" numbers (not computable, but specifically "definable"), I believe you're gonna run into paradoxes as it's an ill-defined concept, similar (in spirit) to "all integers described under 100 words". In fact, the linked article actually talks about it in 2.3.
> For any given language, like for instance ZFC, we can say that definable numbers are a countable subset. Hence measure zero.
If I can describe a set of objects, then we're all set as far as I'm concerned (mathematically speaking). Being able to efficiently construct individual elements of this set using Turing machines or other computational devices is an orthogonal problem.
Also, I don't think having only countable number of utterances in ZFC precludes you from having well-defined uncountable sets described in that system (quite obviously, for any set S take 2^S which is very well-defined).
Furthermore if we limit all mathematics to things that can in principle be done on a Turing machine, then this statement is trivially true because all possible Turing machines is a countable set.
Moving from Turing machines to a Turing-complete programming language, we could define a real number as an equivalence class of functions from positive integers to fractions such that for each function |f(n) - f(m)| <= 1/n + 1/m, and two such functions are equivalent if |f(n) - g(n)| <= 2/n for all positive n.
The question of whether a given function is actually a real number is in general undecidable. The question of whether two functions represent the same real number is also undecidable. However it is easy to create a set of functions that will definitely include all real numbers under this definition (and a few things that are not), but some of those real numbers will be included multiple times.
And the really important point about this is that suddenly "uncountable" doesn't mean "more". It just means that there is an undecidable question or three creating complexity in the way of generating the mapping.
Also, we can talk about definable numbers as long as we choose some specific system which we assume is consistent. So we are talking about numbers which are definable by predicates using the language of ZFC or Peano Axioms.
There is no need to invoke computability, just definability is sufficient. There are lots of definable numbers which are not computable(like Chaitins constant or the real number whose digits encode information about halting of Turing Machines).
But even with this more relaxed constraint, we still dont have enough definable numbers.
f(r) = if (r == 0) { 0 } { else f(p(r)) + 1 }
Given real number r, assume there exists a real number q such that q < r and there does not exist a real number x such that q < x < r. Let real number y = (q + r) / 2. It is trivial to show that q < y < r. Therefore we have a contradiction, and therefore there does not exist a real number q that meets our conditions for a "previous real number".
If you take issue with this, then I suggest you read up on the standard construction of the number systems from the naturals up to the reals. This is all very rigorously defined in terms of ZFC set theory.
Cantor's diagonal argument shows that any mapping from the natural numbers to the real numbers must necessarily miss some real numbers out. It takes some time to get your head around if you aren't used to mathematical proofs, but it's definitely worth looking it up and trying to work through it if you're interested in this subject.
> Start counting the naturals: 1, 2, 3, ...
> At future timelike infinity you'll reach infinity.
> Now for the reals. Your goal is to step from 0 to 1, by way of 0.1, 0.01, and so forth.
> 0 0.0........
> At future timelike infinity you still haven't stopped adding in zeroes to the right of the decimal point.
> In the first case, at any finite time before \breve{i}^+ you will have counted out some finite natural number. In the second case, you will not yet have counted out your first nonzero real.
The same reasoning applies for rationals, yet they can still be counted.
The definition of «can be counted» means there is a bijection between your set and the naturals. Such kind of bijection can easily be created for the rationals[1] and Cantor's diagonal argument[2] shows that you can't create such bijection for reals.
There is nothing really intuitive about this concept, but fortunately the proofs are pretty straigtforward which give a kind of «intuition» around this.
[1] https://en.wikipedia.org/wiki/Pairing_function#/media/File:D...
[2] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
It is only straightforward once you accepted infinity and all other definitions/description based on infinity.
If you, like me, cannot accept infinity, then all the proofs/descriptions that contain infinity become apparent non-sensical.
>> Start counting the naturals: 1, 2, 3, ... >> At future timelike infinity you'll reach infinity.
This highlights the flaw. You reach infinity with infinity. Nothing is really being said about infinity. But somehow if you accepted the understanding infinity here, the rest of thesis such as cantor's diagonal argument may seem to be natural, except you forget that you really didn't know what infinity is.
All property of infinity cannot be finitely described. So anything about infinity is built on top of infinity. Turtle all the way down (or up), and we don't really know what it is.
A real number with infinite precision is equally meaningless.
(Above are not directly related to your comments. I simply like to summarize my thought).
Now to your comment. You can start counting from 0 by 2s, you'll never hit 1, but that doesn't show 1 is not countable. It only shows that 1 is not countable in this particular counting scheme. Yes, you can devise a counting scheme that never hits some numbers, doesn't really contribute to either proof or insight.
I assume you are familiar with the counting scheme of rational numbers, and in that scheme, it can hit any number within any (finite) precisions. Just as infinity, a number with infinite precision is unclear. You certainly can define it, but the definition will have infinite built-in, and it is not clear what meaning does such definition adds.
Returning to my previous attempt, you could think of instead a successor function; for any finite natural number the immediately adjacent natural number can be found in finite time. For any real number, the immediately adjacent real number cannot be found in finite time because the step from one real number to the next is infinitesimally small.
All of these examples are "de-generalizations" of the mapping argument. Counting integers from 0 by 2s maps bijectively onto the natural numbers. The naturals map injectively and surjectively onto the reals; you exhaust all the naturals counting between 0.0 and 1.0, or 1.0 and 2.0, or even between 0.01 and 0.011.
"A real number with infinite precision is equally meaningless": uhm, integration of infinitesimals (dS, dV, ...) ?
Here you sneaked the concept of reals in. Remember reals are defined on top of infinity. You can't have reals if we are still debating what infinity is. There are infinite amount of numbers between 2.0 and 4.0, in the same sense there are infinite amount of numbers in the natural set.
Your successor function defines any finite natural number, it does not define infinity. In the rational counting scheme, we can reach any number within any finite precision. A real number that is defined on the base of infinity precision requires infinity time to reach with the same counting scheme -- the same way infinity requires infinity time to reach by 1, 2, 3, ... So if you allow infinity time, the same way you allowed infinity in your definition of real, then all real numbers can be reached (including infinity time) by counting -- not that provide any meaning.
Calculus is based on taking limit -- that is assuming a finite precision, albeit arbitrary. Infinitesimals are still finite, not infinite. Otherwise, you cannot divide them.
