6 ms·
As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or
by CJefferson 10y ago
As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ.
Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities.
* How many natural numbers are there? Countable
* How many rational numbers are there? Countable
* How many numbers are solution to a polynomial? Countable
* How many numbers are the output of any turing machine (including programs that run forever, producing an infinite decimal)? Countable
* How many numbers are the answer to any maths problem anyone can write down (where the problem has at most a countable number of answers)? Countable.
If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have, is countable, why do we need the other uncountables?
- kirrent 10y agoHow many real numbers are there?
- chriswarbo 10y ago> How many real numbers are there? 2^ℵ₀ Which I just managed to encode using a finite number of symbols :)
- baddox 10y agoThis is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the reals: https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number It is pretty fascinating to think about: that almost all real numbers are not computable ("almost all" of course meaning "all but a countable set"). And yet you almost certainly will never run into a noncomputable real except in computer science when you're specifically defining one to illustrate something about computability (like Chaitin's constant).
- IsaacL 10y agoAre there any good books on this topic?
- andybak 10y agoYes. An uncountable number are in the Library of Babel. (actually - I'm guessing there's actually a countable number in the Library of Babel but it didn't read quite so amusingly that way. In any case - all the ones I flicked through were trash.) Edit - The Library of Babel is actually finite isn't it? Fixed alphabet and fixed book length? It's a while since I read it.
- disconcision 10y agothe number of possible distinct books is finite but it's unknown if the library itself is finite. iirc it ended with the narrator speculating that, although the books themselves are devoid of meaning, perhaps the overall structure of the library is ordered, i.e. the same finite pattern of books repeats endlessly in infinite space.
- sn41 10y agoThe Library of Babel is finite if the books are unique. Interestingly, Borges does mention that one of the books in the library must be an index of the other books. This is similar to the notion of a universal computably enumerable language. However, I doubt that Borges' claim is accurate. If the set of programs is finite, then I think there cannot be a comprehensive index of all programs. A finite set is a regular language, and there is no universal regular language in the set of regular languages.
- philipov 10y agoI recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem. [0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/1400077974 https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...
- im3w1l 10y ago> As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Is a hammer true or false? I don't know, but it's good for hitting nails.
- kmm 10y agoYeah, a hammer is definitely useful, but I think the point he's trying to make is that the notion of uncountable sets isn't very useful outside of things like set theory.
- zodiac 10y agoHow many sets of natural numbers are there? An uncountable number. Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.
- pherq 10y agoIn this case, what you "throw out" are uncomputable (or non-recursive, depending on terminology you like) sets; i.e. sets for which the membership function is not decidable. Yes, there are an uncountable number of these sets, but they can't be defined in any useful way.
- baddox 10y agoIndeed, if you consider a real number to just be a decimal representation formed by concatenating all the natural numbers in a set (not at all a rigourous construction of the reals, but hopefully sufficient for this argument), the equivalence is clear.
- zodiac 10y agoI've always found dedekinds construction (where sqrt 2 is represented by the set of rationals {x in Q : x^2 < 2}) to be a nice natural place where powersets of countable infinite sets come up (in addition to being a great way to construct R)
- pherq 10y agoI tend to prefer considering the sets to encode bitstrings (encode a set as sum(2 ^ -x for x in X)), but yes the equivalence between computable sets and computable numbers is straightforward.
- zodiac 10y agoFor sure - as I understand it in most formulations you throw out lots of sets but keep all the finite sets of natural numbers, the set of even numbers, the set of prime numbers etc One thing I never found satisfactory is that any axiom system like this has to define things in terms of decidability etc, so it's "more verbose" (or less axiomlike) than ZFC
- rw 10y agoYou could have answered all of your questions with "finitely many", because, after all, we can each only perform a finite number of actions in the world. In general, the infinite hierarchy of infinite sets "exists" because we can define it.
- sn41 10y agoOne of the great theorems in logic is the Lowenheim-Skolem theorem [1], which says that if a countable first-order model has an infinite model, then there is a countably infinite model. For example, there is a countably infinite model for the theory of reals. I have heard that Skolem [2] used this theorem as a basis for his belief that uncountable sets can be avoided, and countably infinite sets suffice. [1] https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_... [2] http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.html http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.h...
- joatmon-snoo 10y agothe solution to any problem any could ever have That's a pretty tall claim to make. Once upon a time people thought irrationals and transcendentals like pi and e didn't even exist. It wasn't until the past century that people realized abstract algebra and its ilk had practical applications. The same goes for chaos theory and fractals as well. Admittedly it's hard for me to envision a world where notions of countability will ever have real-world uses, but I also consider calling it "a fun maths game" rather reductionist, and frankly, poor taste (especially if you're going to say something like "intrinsic truth or falsity"). Give him three pence, since he must make gain out of what he learns.
- CJefferson 10y agoThe reason I say "the solution to any problem anyone could ever make" is a maths argument! If you can write down a problem as a finite string, then the set of all problems must be countable.
- heinrichhartman 10y agoGood luck developing analysis with only countable infinities. Limits will take you out of the realm of countable spaces. Most of your derivatives and integrals won't exists, if you force them to take values in countable sets.
- CJefferson 10y agoWhy not, can you give an example. Most of the "common" derivatives and integrals I can think of would work just fine, unless I'm missing something obvious?
- kutkloon7 10y agoNo, for example the integral sqrt(1 - x^2) from x = 0 to x = 1. Or any other integral over a circle/sphere for that matter.
- CJefferson 10y agoNothing wrong with that, it's still a computable number -- I'm not suggesting doing away with all real numbers, just the non-computable ones. I don't claim to have thought through every detail, but having now gone and done some reading, this seems fine in the world of constructivism, which only requires computable numbers (and therefore only countable infinities of numbers)
- twic 10y agoAre the computable numbers continuous? If not, is that a problem for analysis? If so, can you construct some computable analogue of continuity which is sufficient?
- heinrichhartman 10y ago- Every real number can be represented as a limit of rational numbers, which are uncountable. - So for every countable subset you can find a (Cauchy) sequence of rationals that does not converge. Hence, you loose one of the most important tools in Analyisis (Cauchy criterium for convergence). You can still work with the remaining set, but formulating and proving theorems, is going to be much harder. - If integrals over f and g exists, then the integral over f * g does not need to exists. - E.g. Integrals over bounded regions will not always exists. - Theorem of Montonic convergence fails - Function spaces will not be complete (L2). A nice theory of constructible "periods" has been developed by Kontsevich and Zagier (http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf) but it relies heavily on the existing body of Analysis being available.
- heinrichhartman 10y agoAre you aware of the concept of periods ? This is a quite fascinating, countable, ring of numbers, that captures all of the above: Kontsevich and Zagier introduce and develop this concept quite far: http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf
- CJefferson 10y agoNo, but this looks interesting. Thanks for the reference!
- wolfgke 10y agoJust to give a little bit more attention to this link: Wikipedia link to one of the authors: > https://en.wikipedia.org/wiki/Maxim_Kontsevich https://en.wikipedia.org/wiki/Maxim_Kontsevich Proof that one of the authors really is no other "M. Kontsevich" (I openly admit that I wanted to be sure since I associate Maxim Kontsevich mostly with other mathematical areas): > http://www.ihes.fr/~maxim/publicationsanglais.html http://www.ihes.fr/~maxim/publicationsanglais.html
- ArkyBeagle 10y agoEuler held that infinities in general were nothing more than a way of reasoning about limits.
- yequalsx 10y agoThe are uncountably many polynomial over the reals. There are uncountably many functions from N to N. The premise of your question is incorrect.
- waqf 10y agoOP never claimed there were countably many functions from N to N, only that there are countably many Turing machines which is true. By "polynomials" OP doesn't mean polynomials over the reals but over, for example, the rationals – the point is that there's a countable subset of R that's algebraically closed.
- yequalsx 10y agoI know those things. OP does not claim that the set of functions from N to N is uncountable. One gives up things if only countable things are considered. For instance those things that I mentioned.
- waqf 10y agoOh, I see, you're addressing the "we don't need uncountable sets" statement by giving examples of intuitively obvious things which are uncountable. But I think OP's claim is that we don't "need" those things because we could do mathematics with the set of Turing machines instead of the set of functions, etc.
- yequalsx 10y agoYes, but can Turing machines do enough mathematics? The second order Peano Axioms are categorical and the first order axioms are not. The Incompleteness Theorem tells us that there are statements that are true in the standard model of N that are not provable by a Turing Machine.
- lmm 10y agoNo mathematical object exists exactly in the real world. E.g. you will never see a physically perfect square. The whole point of mathematics is that it's a simplified model of reality that's easier to work with for some purposes, and that's as true of uncountable infinities as it is of anything else in maths.
- imh 10y agoBetter yet, just consider all deduction as "a fun language game," rather than having any intrinsic truth or falsity. If you assume a whole bunch of stuff and the axiom of choice, you can get these interesting things over here. If you assume that same bunch of stuff but not the axiom of choice, you get this other interesting stuff over there. Which assumptions to use at any given time just depend on what you're trying to do. If I'm trying to count my sheep, I just need enough axioms to get me addition of natural numbers. If I'm trying to model some mechanical trajectory, maybe I ought to grab some reals. Got circles? Adding imaginary numbers to the reals makes that easy, even though imaginary numbers are totally "fake." Using sentences that might not make sense? Maybe avoiding the excluded middle is a good idea.
- paulddraper 10y ago> If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have is countable This is trivially true, since there are only countable (finite) expressions and problems. > why do we need the other uncountables? You can't do calculus without reals. http://math.stackexchange.com/questions/1880741/why-cant-calculus-be-done-on-the-rational-numbers http://math.stackexchange.com/questions/1880741/why-cant-cal... And calculus is pretty important (e.g. for any branch of physics ever).