[HN Gopher] How many real numbers exist? New proof moves closer ...
___________________________________________________________________
How many real numbers exist? New proof moves closer to an answer
Author : theafh
Score : 293 points
Date : 2021-07-15 15:03 UTC (7 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| daxfohl wrote:
| A related thing that occurred to me the other day: there's some
| number in [0, 1] that encodes every state of every possible
| Turing machine (the number of Turing machines is countable, the
| duration of its run is countable, and the states at each step are
| countable, so you can diagonalize that and make a real number out
| of it). I'm pretty sure you can take that further and show that
| all possible mathematical proofs, including the Godel unsolvable
| ones (I think...they're just proofs that are infinitely long but
| countably so), can also be encoded in a single real number. That
| makes it feel like the reals are pretty big.
| Rinum wrote:
| I think you'll like this - https://youtu.be/HeQX2HjkcNo
| bmitc wrote:
| If people are interested in this stuff, there's a great course
| called _Paradox and Infinity_ going on right now on edX. You've
| missed the first two homework assignments, but there's still time
| to get going in the course.
|
| The course is based on or supported by the book _On the Brink of
| Paradox_.
| bmitc wrote:
| Some links:
|
| https://www.edx.org/course/paradox-and-infinity
|
| https://ocw.mit.edu/courses/linguistics-and-philosophy/24-11...
|
| https://www.amazon.com/Brink-Paradox-Highlights-Intersection...
| jaywalk wrote:
| I'm not trying to be flippant, although it may come off that way:
| why does any of this matter?
| gorgoiler wrote:
| We don't know but looking into the past hints at the future.
|
| Cantor, Hilbert and Godel gave us Church who gave us Turing.
| Turing and Flowers gave us the machines as well as the theory.
| All of them put together gave us type systems and types are how
| you formally prove that your 747 software is free of, if not
| all bugs, then at least certain large classes of error.
|
| There is a clear line of connections from Cantor (1890s) to
| jumbo jet fly-by-wire (1990s.)
|
| Countability of sets and Cantor's diagonal argument -- the
| subject of the first part of this article -- are some of the
| first topics teenagers learn about in high school CS (if you're
| lucky and on a very modern course) or CS101 (if you're at a
| University.) Types _are_ sets.
|
| Who knows what today's mathematics will bring us in the year
| 2121?
| mmastrac wrote:
| I'd love to see James Burke tackle this line.
| lupire wrote:
| Eh, this argument kind of falls apart with higher infinities,
| where the numbers you are studying are bigger than the power
| set of all interactions among all particles in all possible
| universes.
| [deleted]
| shockeychap wrote:
| Why spend time on it? To borrow from George Mallory: Because
| it's there.
| pjfin123 wrote:
| I understand the diagnol proof but not a lot of the rest. If
| you assume only computable numbers exist though a lot of this
| seems to really not matter.
| lupire wrote:
| Even if only computable numbers exist, it's inconvenient, to
| do math on them in bulk, so it helps to have a set of
| virtual/potential numbers (misleadingly named the "real"
| numbers, even though almost all of them (100%) will never be
| realized in any way).
| helen___keller wrote:
| Others have addressed why it matters (or doesn't matter) when
| viewed from outside mathematics. But within mathematics,
| unsolved problems usually matter for two reasons:
|
| (1) When lots of really smart people spend lots of time trying
| to solve something, and fail to do so, it becomes even more
| interesting for other smart people. A well-known example is the
| Collatz Conjecture[0] which, by most accounts is a meaningless
| problem, but endlessly fascinates many for its renowned
| difficulty.
|
| (2) In mathematics, you often stumble upon problems that are
| equivalent to other problems. If X is difficult to solve so you
| give up and go work on Y, only to find out that Y as a problem
| is basically the same to X, or they have some other intimate
| relationship, and it makes X that much more tantalizing. A
| common example for computer scientists is the whole class of NP
| complete problems[1] for which we don't know if there exists a
| polytime algorithm to decide. Every time we discover a new
| problem that lives in the realm of NP-complete, the P vs NP
| problem gets a little more tantalizing.
|
| [0] https://en.wikipedia.org/wiki/Collatz_conjecture
|
| [1] https://en.wikipedia.org/wiki/NP-completeness
| sillysaurusx wrote:
| This is an excellent answer. I have a mostly unrelated
| question. In the case of the Collatz conjecture, it seems all
| but proved:
|
| > If the conjecture is false, it can only be because there is
| some starting number which gives rise to a sequence that does
| not contain 1. Such a sequence would either enter a repeating
| cycle that excludes 1, or increase without bound. No such
| sequence has been found.
|
| There are lots of histograms and empirical data supporting
| the conjecture.
|
| My question is, why is this empirical data not "good enough"
| for mathematicians? As something closer to a physicist, I do
| wonder what the fascination is with trying to prove
| conclusively that 3n+1 xor n/2 will eventually encounter 1.
| It seems a bit like trying to prove conclusively that the
| gravitational constant is so-and-so, when it seems the best
| you can do is to measure it as precisely as possible:
|
| > Jeffrey Lagarias stated in 2010 that the Collatz conjecture
| "is an extraordinarily difficult problem, completely out of
| reach of present day mathematics."
|
| As someone who loved mathematics but was never much good at
| it, what's the fascination here? (I'm only trying to
| understand the motivations of people smarter than I am.)
| stonemetal12 wrote:
| It is simple empirical data isn't proof. It is as if you
| were testing primes 2 yes, 3 yes, 4 no. Here is empirical
| data that only 2 primes exist. Should we believe it?
|
| Sure for Collatz we have tested more than 3 numbers but we
| can't guaranty it is true until we test all infinity of
| them, or have a proof that doesn't rely on empirical data.
| To do otherwise would be to look like a fool when someone
| got around to testing N+1 and it no longer being true.
| Ivoirians wrote:
| They've verified that the Collatz conjecture holds for all
| numbers up to ~2^68, but that's precisely 0% of all the
| numbers that need to be checked.
|
| But more importantly, the goal of (pure) mathematics isn't
| to declare truths. If you had a machine from God himself
| that outputted True or False for theorems you put in, that
| wouldn't demotivate (pure) mathematicians from doing the
| work they're doing. Understanding the reason things are the
| way they are (and being able to share those understandings)
| is the purpose of math. I'd be willing to wager that almost
| every mathematician would rather have a proof that Collatz
| holds for all numbers divisible by 17 rather than a
| definitive yes/no answer to whether it's true or not,
| because the former would lend much more illumination to the
| secrets behind the problem, and would lead to new, more
| interesting mathematical methods and disciplines. The
| latter would be a fun fact to share at parties.
| schoen wrote:
| Though note that that True/False machine could also
| quickly lead to the discovery of actual proofs, for
| example by making it extremely efficient to search for
| counterexamples. "The Collatz conjecture is true for all
| n <= some_huge_number." Also perhaps by making it
| extremely efficient to search for correct proofs in a
| lexicographically ordered list of proofs. "The shortest
| valid proof of the Collatz conjecture in the list of all
| proofs in my formalism is before proof number
| some_huge_number."
|
| Although I think the basic version of the machine is
| "just" the first Turing jump oracle
|
| https://en.wikipedia.org/wiki/Turing_jump
|
| -- it depends on how you formalize the inputs to the
| machine, right? -- so maybe mathematicians would still be
| busy afterward. :-) Maybe the machine is an oracle with
| _infinite_ Turing degree?
| Ivoirians wrote:
| This is true, a universal oracle would probably lead to
| some chaos in the world's computer science departments. I
| wonder how many mathematicians would switch over to help
| formalize and solve their fields, and how many would
| stick to their pencils and paper :P
| sillysaurusx wrote:
| > They've verified that the Collatz conjecture holds for
| all numbers up to ~2^68, but that's precisely 0% of all
| the numbers that need to be checked.
|
| This is the crux of what has me looking like a fool to
| every mathematician in the thread, but I don't mind: why
| is 2^68 0% of the "numbers that need to be checked"? From
| a physicist standpoint, you can do a lot with numbers
| from 0 to 2^68. After all, 64-bit floats are quite
| useful. Is there 0% value in proving the Collatz
| conjecture for all possible numbers one might want to use
| in a normal programming language without big number
| libraries?
|
| I know the question must sound pretty crude, but it's
| also a source of mystery. Mathematicians are so obsessed
| with exactness. Is there no room for empirical analysis
| in number theory?
|
| In other words, number theory relies on certain
| assumptions. What if one of your assumptions is "a number
| system from 0 to 2^64"? Why is there no value in that?
| Ivoirians wrote:
| >Why is there no value in that?
|
| Because it's uninteresting. The point of pure math is not
| to be "useful", it's to be interesting. The Collatz
| Conjecture is (as yet) a completely useless result. Like
| I said, if God himself came down and told the world "The
| Collatz Conjecture is true", all we'd get is a useless
| piece of trivia. "The Collatz Conjecture is true for the
| first 2^68 natural numbers" is even more worthless than
| that. Maybe it'd be useful if we had an application for
| it, but for context, many pure mathematicians are quite
| derisive at the idea that their work should have
| practical applications.
|
| Here's a digression, a simple math problem. If you take a
| checkerboard and remove two opposite corner squares, can
| you tile the remaining 62 squares with 31 dominoes?
|
| You can probably write a program that can exhaustively
| churn through all the possible arrangements of dominoes
| in a checkerboard, and it'll spit out the answer (it's
| "no"). But is that interesting? No. This is a boring
| fact, "if you take a checkerboard and remove the two
| opposite corners you can't tile the remaining squares
| with 31 dominoes". No one cares about that.
|
| But, here's a proof that this is true. If you look at the
| colors of each square on a checkerboard, there are 32
| black squares and 32 white squares. When you remove the
| two opposite corner squares, you're removing two squares
| of the same color. So you have 30 black squares and 32
| white squares left (or the converse). Meanwhile, every
| domino takes up one black square and one white square. So
| no matter how you place 31 dominoes, they should cover 31
| black squares and 31 white squares. Therefore, we've
| proven the tiling is impossible.
|
| That's somewhat interesting. You have an easily
| understandable argument for why the fact is true, and you
| have an application of a method (here, invariants) for
| looking at other math problems. Plus, it's kinda fun and
| satisfying and "elegant" to solve a problem like this.
| The proof is much, much more interesting than knowing the
| answer to the problem. Hopefully this helps convey that.
| big_curses wrote:
| I'll give a perspective, although my specific knowledge of
| math is not very deep at all, I've thought a lot about
| concepts and abstractions.
|
| I think the difference here is that math is much more
| abstract than physics. The concepts backing math are built
| off of very low level abstractions about the world. For
| math, over a long period of time more and more
| relationships and rules were deduced from what had already
| been induced from reality. And if you CAN deduce, you
| should likely, as it provides a proof for some idea or
| concept that induction never could (but only if your
| previous inductions and deductions were accurate).
|
| Physics on the other hand, cannot deduce as readily. It is
| primarily based in the realm of gathering more and more
| data from the world and observing physical relationships
| firsthand. This cannot be done in abstract math because
| abstract math does not exist in reality. There is nothing
| to observe, it is mostly abstractions based on lower level
| observations in reality. For example, you can measure the
| effects of gravity firsthand, but you cannot measure
| infinity, a mathematical abstraction. Infinity does not
| exist in reality. It is simply a useful abstraction for
| things that are too large or small for us to meaningfully
| measure.
| Sharlin wrote:
| > There are lots of histograms and empirical data
| supporting the conjecture.
|
| There's a very interesting implicit question there: _why
| should counterexamples be small?_ [1][2] Certainly,
| counterexamples to many conjectures about infinite sets can
| be found with a brute-force search, even if the problem is
| merely semidecidable. But isn 't that simply an example of
| selection bias?
|
| There is a certain subjective beauty in having
| counterexamples like 9 or 341 or even 23338590792. But is
| that just anthropocentrism? After all, no matter how many
| cases we check, we have made absolutely no progress in
| exhausting the whole set of natural numbers! We can never
| reach even reasonably easily constructable numbers like
| 3|||3 (using Knuth arrow notation [3]), and still almost
| all[4] natural numbers are bigger than that.
|
| In physics, there's an (often implicitly made) assumption
| that more evidence in support of a hypothesis makes it more
| likely that the hypothesis is supported by any future
| evidence as well. But why should we be able to make that
| assumption? We do, because it seems to work, but why should
| it still work tomorrow? This is, of course, the famous
| philosophical problem of induction [5]. But math is
| basically what happens when you _explicitly reject
| inductive reasoning_ and then start to explore the space of
| things that can still be reached, using purely deductive
| reasoning!
|
| [1] https://math.stackexchange.com/questions/449886/the-
| largest-...
|
| [2]
| https://math.stackexchange.com/questions/111440/examples-
| of-...
|
| [3] https://en.wikipedia.org/wiki/Knuth%27s_up-
| arrow_notation
|
| [4] https://en.wikipedia.org/wiki/Almost_all
|
| [5] https://en.wikipedia.org/wiki/Problem_of_induction
| ivanbakel wrote:
| >My question is, why is this empirical data not "good
| enough" for mathematicians?
|
| There are two reasons: firstly, because mathematics is not
| an empirical discipline (well, unless you're a number
| theorist...), so it is possible to be certain of
| mathematical truth, unlike the inherent uncertainty of
| physical truth; secondly, because every finite bound on the
| natural numbers may as well be 0 when compared to the
| numbers that remain.
|
| There is simply no way to take any empirical measurements
| of the natural numbers (or the reals) that would let you
| estimate anything "for all numbers", since the proportion
| of numbers you failed to sample is infinite.
|
| You may be interested in reading the answers to this
| question:
| https://math.stackexchange.com/questions/514/conjectures-
| tha... which describes some problems which seemed true "up
| to some large number", but later turned out to be false.
| sillysaurusx wrote:
| https://math.stackexchange.com/questions/514/conjectures-
| tha... was excellent. Thank you.
|
| > n^17+9 and (n+1)^17+9 are relatively prime
|
| > The first counterexample is
| n=8424432925592889329288197322308900672459420460792433
|
| I think this helped me appreciate the difficulty of being
| satisfied with the Collatz conjecture.
| helen___keller wrote:
| Well, firstly there are "important numbers" much bigger
| than the range we've empirically tested, so our empirical
| results aren't actually good enough. If there was some deep
| relationship with number theory, maybe it just happens that
| a number in this range is the first to break the pattern,
| which could be a deep and beautiful result.
|
| But also, it's just the nature of mathematics, proving what
| is true is just as important (if not more so) than knowing
| what is true.
|
| From a practical perspective, doing mathematics, you often
| don't _really_ grok why something is true until you prove
| it.
|
| From a philosophical perspective, there's not much in the
| universe we can know for sure (as you mention with the
| gravitational constant), but a mathematical proof we know
| for sure. That's the beauty of it.
|
| if X is true and the implication (X => Y) is true, then it
| must be that Y is true. By definition of a logical
| implication.
|
| Add in a whole bunch of axioms and suddenly you can take
| these simple logical atoms and build them into a field that
| spans the working tools of every engineer and beautiful
| arcane subjects like set theory. And every single thing we
| prove, we know to be true, as we build it from logical
| atoms that can be traced back to definitions and axioms.
|
| It "could be" that for certain types of matter or at
| certain distances, the gravitational constant changes. It
| cannot be that there exists a bijection between the natural
| numbers and the real numbers under ZFC. Cantor's
| diagonalization argument *proves* it.
| myWindoonn wrote:
| Some theoretical physicist (Aaronson?) once quipped
| something like, "If physicists had discovered P vs. NP,
| then they'd have said P != NP and given a Nobel for it. And
| then if it turned out P = NP, then they'd give another
| Nobel."
|
| Another, more important reason is that we know that the
| Collatz Conjecture is a single slice of a Turing-complete
| question about dynamical systems. Trying to find a complete
| proof expands our knowledge about the bridge between
| dynamical systems and the natural numbers. Such
| explorations were essential to founding modern physics in
| terms of dynamics and conservation laws.
| hvocode wrote:
| I think others addressed the "why proof not empirical data"
| question well, but one additional point. A logical proof is
| only as solid as its weakest component. In mathematics any
| result that has been proven may be used in a component of
| another proof. If you have a result that is based on
| empirical evidence, then every result proven based on that
| also inherits that empirical evidence as part of its
| foundation. The reason we don't do this is that if, by some
| weird chance, the original result that used empirical data
| instead of proof is shown to be false, then every result
| built upon it is invalidated and needs to be revisited.
| That would be a mess. Sticking to requiring formal proofs
| at least reduces that possibility - although it is still
| entirely possible for a proof to have a subtle mistake as
| well, which would have a similar cascading effect on
| results built upon it.
| svat wrote:
| No amount of empirical data is ever "good enough" for the
| mathematical standard of proof. (It may be enough for
| mathematicians to "believe" something in some informal
| sense, but not enough to consider it "proved".) You can see
| some examples at the answers to these questions; maybe at
| least one of them will be interesting to you:
|
| - https://math.stackexchange.com/questions/514/conjectures-
| tha...
|
| - https://math.stackexchange.com/questions/111440/examples-
| of-... (and maybe
| https://mathoverflow.net/questions/11517/computer-algebra-
| er... )
|
| - https://mathoverflow.net/questions/15444/examples-of-
| eventua...
|
| (There are over a hundred examples at those questions; I
| guess this counts as a lot of empirical data that empirical
| data is not enough! However, sometimes empirical data _can_
| be enough for a mathematical proof; for instance if you
| know somehow that a polynomial f is of degree less than n
| and you have shown that f(x)=g(x) at n distinct points, you
| can indeed conclude that f=g and so on -- see the "Proofs
| by Example?" section of the first "Proof Machines" chapter
| of the book "A=B" available online
| https://www2.math.upenn.edu/~wilf/AeqB.html .)
| sillysaurusx wrote:
| That was another question in the back of my mind --
| famously, the four color theorem was proved by computers
| through exhaustive analysis (checking every possibility).
| At the time, it was controversial as a "proof" since it
| didn't really take the usual form of a proof.
|
| I've often wondered "Why can't we do something like that,
| but for all instances of things like the Collatz
| conjecture?" Of course, it's computationally infeasible.
| But that raises the question: Suppose the four-color
| theorem was only able to prove 95% of cases rather than
| 100%. Isn't it at least sort of valuable to do so? Or is
| that last 5% all the difference?
|
| I suppose what bugs me about math is, physicists are
| proved wrong all the time. Mathematicians are rarely
| proved mistaken, because they construct assumptions that
| you can't disagree with. There's no chance for empirical
| data to falsify one's assertions.
|
| But that's an odd kind of debate, and not too productive.
| I just can't help but wonder about stuff like this.
| bordercases wrote:
| You're adhering to certain misconceptions for no good
| reason. An exhaustive check of all the cases in the model
| that supports the four-color conjecture _is_ the
| "empirical" (here, meaning experimental) data required to
| falsify conjectures. And even physicists don't deny the
| value of falsification in narrowing down models to truth.
| But I think they are much more loose in what they are
| willing to stipulate as true if it means advancing other
| conclusions.
|
| Furthermore mathematicians do accept certain kinds of
| probabilistic arguments, but they need to take a form of
| proving that an object will be guaranteed to have a
| certain property as a parameter on the object approaches
| a statistical limit. So partial evidence can sometimes
| point to the possible truth of a mathematical conjecture,
| but you are still burdened with the requirement of
| deductive demonstration if you desire logical certainty.
|
| The tautological notion you take of math is a half-truth.
| On the one hand, models in math seek to be sound over the
| objects they specify. This is opposed to physics where
| deliberate simplifications must be made to make your
| idealizations of a system manageable or relevant. At the
| same time, no mathematical system is complete. So there
| will be truths that require other axiomatizations to
| access via proof. This is one source of mathematical
| creativity requiring judgment beyond following
| tautologies.
| Sharlin wrote:
| Math is simply not a science, not in the sense of
| "natural science". Math research does not follow the
| scientific method, it is not an iterative effort to
| construct (wrong, but useful) models of some external
| universe like science does. Math is a thing of its own,
| and it's best just to not compare it to physics or
| biology or gender studies or whatever.
| acchow wrote:
| "famously, the four color theorem was proved by computers
| through exhaustive analysis (checking every possibility)"
|
| This is impossible. The plane can be arbitrarily large
| with an arbitrary number of regions. It can be
| exhaustively checked for n number of regions up to a
| certain n. But not for arbitrary n.
| schoen wrote:
| The four-color theorem had the preliminary challenge of
| creating a method to identify all the relevant cases.
| That also required a mathematical theory. (I don't
| actually understand how it was done!)
|
| If you didn't have that, you would have an infinite
| search for possible maps that violate the conjecture,
| because you wouldn't be able to divide them into a finite
| number of equivalence classes, or enumerate a finite
| number of possible counterexamples, or whatever.
|
| For Collatz, I don't think we have any lemma that gives a
| path to saying "a counterexample must be one of these
| 2100 integers" or the like. So without such a thing,
| checking every possibility would mean checking _every
| integer_. (Well, there are definitely lemmas that make it
| unnecessary to check large numbers of integers, so I
| should say instead that checking every possibility would
| still mean checking an infinite number of cases.)
| kevinventullo wrote:
| As an interesting example where we did have a finite
| bound that was still out of reach to computationally
| exhaust, see the Weak Goldbach Conjecture:
|
| https://en.m.wikipedia.org/wiki/Goldbach%27s_weak_conject
| ure
|
| It was known to have at most finitely many counter-
| examples by the 1930's, and by the 1950's it was known
| that the largest counter-example had to be < 3^3^15. In
| 2002 that was lowered to about 10^1346. Still well out of
| reach of any computer!
|
| Only in 2012 was an unconditional proof given.
| helen___keller wrote:
| It can be valuable, but it's not as valuable as covering
| all cases.
|
| If I could prove collatz for 99% of numbers it would be
| great.
|
| If i could additionally prove which 99% converge, let's
| say all numbers not divisible by 100, it would be
| enormous because even showing this much is likely to be a
| stepping stone to a full proof (what property is it about
| the number 100 that excludes all non-divisors from
| diverging?)
|
| > I suppose what bugs me about math is, physicists are
| proved wrong all the time. Mathematicians are rarely
| proved mistaken, because they construct assumptions that
| you can't disagree with. There's no chance for empirical
| data to falsify one's assertions.
|
| Right, and that's the whole point and beauty of it.
| thehappypm wrote:
| I mean, at its simplest, the Collatz conjecture is a type of
| random walk, with the sequence either exponentially growing
| or exponentially shrinking, basically at random. It's
| statistically impossible that that any random walk will
| continue one direction forever, and once it randomly decays
| to 1 you're done.
| quickthrower2 wrote:
| Loops are the other option you'd need to prove don't exist.
|
| I think I can see why trying to solve this problem is
| popular. It almost feels like it should be easy to solve
| but it just quite isn't!
| sillysaurusx wrote:
| It took many years to understand that!
|
| It's not a flippant question at all.
|
| The answer is, it doesn't matter. And that's the joy of it.
|
| It wasn't until I got into ML that I learned the value of doing
| unimportant work. When you're free to think about
| inconsequential matters very seriously, you end up discovering
| so many useful things. It was how I independently rediscovered
| what is apparently called the Discrete Hartley Transform.
|
| You have a vague notion that what you're doing might be
| important, but it's not the focus. It matters because it's fun
| in a way that nothing else can be.
|
| Of course, the more serious folk won't admit it's fun. It's
| serious work. And they're not wrong; nobody's fooling around.
| Our time is every bit as precious as an executive's.
|
| But their goal is to change the world. Ours -- or mine, at
| least -- is to know the truth of a thing that most people don't
| know.
| mr_gibbins wrote:
| I agree entirely. Industrially, I work a role within an IT
| team. My work is, I hope, useful and strives towards a
| purpose - my employer's purpose/business model.
|
| Do I 'go home' - leave my home office - and think about it?
| No. Do I muse on how to solve a work-related issue when I'm
| showering? Also no. Will I forget almost everything about
| this job as or when I move onto the next? Definitely yes.
|
| But academically, I'm interested, and actively publish albeit
| modest, low-impact research, in relational databases. I love
| the set-based approach to all matters SQL and after many
| years in the field still fool around trying to embellish,
| attack, improve and invent the core ideas.
|
| Why bother? Even if I come up with some magical new
| improvement to RDBMSs, it doesn't matter. If I fork MySQL and
| try out my ideas, no one cares. I'll never get the traction
| or the FOSS community support, I'll spend more time playing
| politics and managing collaborators than I'd like (zero) and
| I enjoy the independent thought that my interests bring.
|
| So my academic work is pointless. But it's meaningful to me.
| And I think that's what matters. I don't understand one-tenth
| of the ideas in this article, but that doesn't matter. What
| matters is that it's interesting to _somebody_.
| fighterpilot wrote:
| > it doesn't matter
|
| It doesn't matter _yet_. Applications of pure math happen
| downstream decades or centuries later. It 's hard to predict
| the impact.
| l33t2328 wrote:
| I don't like this framing because it implies any piece of
| pure math becoming useful is just a matter of time, and I
| see no reason to suspect this is the case.
| hawkice wrote:
| I think it's more about being open minded to strange
| uses. Maybe 3% of strange pure math ends up being used
| for something bigger? But since nobody knows what it'll
| be, it's good to be curious about all sorts of nonsense.
| Riemannian geometry was OBVIOUSLY absurd useless pure
| math sophistry, but then it turned out we lived in it. I
| think a lot of the work on modular forms and elliptic
| curves has come across that way too, despite the crypto
| intersection. The general idea is that, even if it's been
| a century or two, it's too soon to tell if something is
| useless, that's solid. And formalization of infinity has
| been useful in some practical exploration of proof
| systems used by humans. It might be the future of
| programming, who knows?
| bmitc wrote:
| > I see no reason to suspect this is the case
|
| Isn't history enough reason?
| jonnycomputer wrote:
| I've read lots of math papers that were a complete waste
| of time because they were banal. The only "innovation"
| was to use different words to describe the same thing.
| New mathematics is actually pretty damn hard I suspect.
| erichahn wrote:
| No history actually tells you that only 1% of produced
| maths is useful. You only see the good stuff not the ugly
| stuff.
| bmitc wrote:
| I don't know why people are throwing around percentages
| so much in these replies. Percentage of what? Plus, the
| body of work of mathematics continues to grow all the
| time.
|
| The core of the original comment that started this chain
| was:
|
| > Applications of pure math happen downstream decades or
| centuries later.
|
| My argument was that history shows that a surprising
| amount of mathematics does eventually trickle down into
| applications. I don't think anyone is arguing all of
| mathematics eventually sees an application.
|
| Again, my point was that history does indeed seem to show
| that "applications of pure math happen downstream decades
| or centuries later". As the original commenter said, it's
| hard to predict what will be the next thing to be
| applied.
| l33t2328 wrote:
| In addition to what the other commenter said, it's
| important to understand the scale. Cutting edge research
| 600 years ago was solving cubic equations. Today, cutting
| edge research requires potentially years of advanced
| study to understand the objects involved.
|
| There are more mathematicians alive today than at any
| point in human history, and their work has become
| specialized to a tremendous degree. Gone are the days
| where one mathematician could do substantial new work in
| a dozen diverse areas.
|
| So, in short, the fact that historically lots of pure
| math has not found use, the specialized nature of modern
| research math, the volume of work being out out, and an
| irreverence for applications(again, this is _pure_ math)
| leads me to be doubtful that even a moderate amount of
| modern pure math research will ever be useful in any
| practical sense.
| dfdz wrote:
| To follow up on this comment, I think that math should be
| viewed as a giant tree structure or pyramid
|
| At the bottom are all sorts of applications of linear
| algebra and optimization (calculus) are related to machine
| learning, deep learning (AI), physics, engineering etc.
|
| One level up there are all sorts of ideas in algebra and
| mathematical analysis that are leading to new ideas in
| linear algebra and optimization (calculus)
|
| Going one level higher, there are ideas in mathematical
| logic and set theory that are improving our understanding
| our algebra and analysis.
|
| If you look at a specific result at the very top of the
| pyramid as ask why does it matter? It is difficult to give
| a good answer. Clearly we want to base of the pyramid, but
| do we need to keep building it up? Should we stop at a
| certain level?
| just_one_time_ wrote:
| Lololol. U gay.
| Hamlet42 wrote:
| Some math problems seem uselees when first encountered until
| they become useful some dacades later. An example of this is
| knot theory and medicine[1]
|
| [1] https://science.sciencemag.org/content/255/5043/403
| db48x wrote:
| Also certain of the more recondite aspects of number theory
| that deal with prime numbers: completely useless right up
| until RSA was invented; now we use them to protect every
| webpage we view, every email we send, and every financial
| transaction we make.
| Y_Y wrote:
| I think you'd have to say exactly what you mean by "matter".
|
| At one point in my life I felt like the continuum hypothesis
| was the most important question in the world. Now I'm mostly
| concerned about finite material issues, e.g. my health. I think
| a good argument can be made why either of them matter much more
| than the other.
| soperj wrote:
| This is kind of the equivalent of asking why does your life
| matter?
| l33t2328 wrote:
| It's interesting, and fun.
|
| Most modern pure math is done completely independent of and
| without regard to applications(if it were, it would be 'applied
| math').
| bmitc wrote:
| We know that the cardinality of the natural numbers is less
| than the cardinality of the real numbers. The Continuum
| Hypothesis, which is a long unsolved problem, states that there
| are no sets with cardinality between the two. The posted
| article states that this new result strengthens the case
| against the hypothesis, that is that's it's probably false.
|
| All of this is nuanced but is important to mathematics and
| philosophy.
| thom wrote:
| Why does "the set containing the natural numbers and a
| sandwich" not have cardinality between the two?
| knodi123 wrote:
| Because cardinality of finite sets is intuitive, but
| cardinality of infinite sets is less intuitive and totally
| different. The natural numbers plus a sandwich is mixing
| the two together in a single argument, which doesn't really
| track.
| bmitc wrote:
| The non-sandwich analogy is called Hilbert's hotel.
|
| Saying that two sets have the same cardinality is
| equivalent to them having a bijection between them.
|
| So the claim is that the natural numbers and the natural
| numbers plus a sandwich have the same cardinality. This can
| be proved by the bijection: 0 -> sandwich
| 1 -> 0 2 -> 1 3 -> 2 .
| . . n -> n-1 . .
| .
|
| There is actually more though! If you had an infinite but
| countable amount of sandwiches (that is a sandwich for
| every natural number), that plus the natural numbers still
| has the same cardinality as just the natural numbers.
| There, the bijection is 0 -> sandwich_0
| 1 -> 0 2 -> sandwich_1 3 -> 1 4 ->
| sandwich_2 5 -> 2 . .
| .
|
| No natural number or sandwich is left out by this mapping.
| thom wrote:
| Because everyone gave me such good and well meaning
| answers perhaps you'll permit me a follow up.
|
| As I understand it we can say the cardinality of the
| reals is 2^aleph_0. Why is it cheating to create a
| bijection thusly: 0 -> 0 1 ->
| 1/(2^aleph_0) 2 -> 2/(2^aleph_0)
|
| etc?
| dabitude wrote:
| Are real numbers uniformly spaced? Or are there clusters?
| bmitc wrote:
| I am not entirely sure what you wrote or are asking, but
| if you're interested in this stuff, come take the course
| (or read the book) I mentioned here:
|
| https://news.ycombinator.com/item?id=27846666
| scapp wrote:
| Problem 1: 1/(2^aleph_0) isn't a real number. The real
| numbers don't contain infinitesimals. It's possible to
| formalize a number that behaves like 1/(2^aleph_0) "ought
| to" (surreals would be one possible approach), but the
| result won't be a real number.
|
| Problem 2: There's no natural number that maps to (say)
| 1. Even if you do allow 1/(2^aleph_0), there's no finite
| number n that would make n/(2^aleph_0) = 1. With any
| reasonable definitions of the operations involved here,
| n/(2^aleph_0) would always be infinitesimal, so it would
| never equal a non-infinitesimal.
|
| Problem 3: You're still skipping over infinitely many
| numbers. If 1/(2^aleph_0) is a number (and again, this
| requires going beyond the real numbers) and 1.5 is a
| number, then 1.5 * 1/(2^aleph_0) = 1.5/(2^aleph_0) is
| also a number, but no natural number gets mapped to that.
| drdeca wrote:
| 1/(2^{\aleph_0}) isn't something that has a clear
| meaning.
|
| 2^{\aleph_0} is a cardinal number, which isn't really a
| number in the sense of "an element of a field" or
| something like that. Dividing by it isn't a well defined
| thing.
|
| And, you certainly can't just multiply any real number
| (or, any real number between 0 and 1) by 2^{\aleph_0} and
| get a different integer as a result.
|
| (Now, if you work in the surreal numbers, you can define
| things like n/(2^{\aleph_0}) (identifying cardinals with
| the first ordinal of that cardinality), but these would
| not be real numbers. They would all be infinitesimal ,
| smaller than 1/k for all positive integers k, and yet
| bigger than 0. Similarly in the surreal numbers, you
| could multiply real numbers between 0 and 1 by
| 2^{\aleph_0}, but you would get surreal numbers which are
| larger than every integer (in fact, larger than any
| countable ordinal))
|
| Summary: What you wrote doesn't define a mapping from the
| integers to the real numbers . (It can be interpreted as
| defining a map from integers to something else though.)
| lupire wrote:
| Don't stop there! Let's have a countably infinite variety
| of sandwiches, with a countably infinite number of
| sandwiches of each variety.
|
| Still enough natural numbers to eat them all, one per.
|
| But still not enough sandwiches to feed all the (so-
| called) real numbers one sandwich each!
|
| But if sandwiches grew on trees, and we had an infinite
| branching tree with two branches at each branching point,
| and every branch has a (pair of) sub-branches, then
| natural numbers could not eat all the sandwiches, and the
| sandwiches could feel all the (so-called) real numbers.
| fighterpilot wrote:
| For the same reason that integers have the same cardinality
| as only odd numbers. You can create a 1:1 mapping between
| them.
| bmitc wrote:
| Not just one-to-one (injective) but also onto
| (surjective). :)
| orbital223 wrote:
| The cardinality of infinite sets is unintuitive. We can
| create a one to one correspondence between the
| Naturals+Sandwich set and the Naturals set (for example,
| assign sandwich to 0, 0 to 1, 1 to 2, 2 to 3, etc). That
| means they have the same cardinality.
|
| It's even possible to add an infinite number of elements to
| an infinite set and retain the same cardinality (the
| Integers set has the same cardinality as the Naturals set).
| hawkice wrote:
| Because it's the same size. I can show it's the same size
| because I can just change the labels on the sets (label
| change of elements doesn't change group size) and go back
| and forth. In this case, 0 is the sandwich, and all the
| nonnegative numbers get relabelled down by one. Going back,
| sandwiches become 0 and you add one to nonnegative numbers.
| So they've got to be the same size, if I can go back and
| forth and everything just gets a new label and I don't miss
| anything.
| helen___keller wrote:
| You can create a bijection between that set and the set of
| natural numbers, defined by the function f:
|
| 0 <-> sandwich
|
| 1 <-> 0
|
| ...
|
| n+1 <-> n
|
| By definition, if you can biject two sets, they have the
| same cardinality.
| magicalist wrote:
| One way to say two sets of things are of equal size is if
| we can pair up all the elements of one set with all the
| elements of the other.
|
| If we're ok with extending that to sets of infinite things
| (we can still pair elements of each set, we'd just never be
| able to finish listing all the pairs), then we can say that
| the natural numbers and "the set containing the natural
| numbers and a sandwich" are of equal size because we could
| pair 1 from the first set with the sandwich from the second
| set, pair 2 from the first set with 1 from the second set,
| 3 from the first set with 2 from the second set, etc etc.
|
| There's no element of either set without a match in the
| other set, so they have the same cardinality as the natural
| numbers, with or without the sandwich.
| pantulis wrote:
| Because this advances math. Same could be said for lambda-
| calculus and yet here we are with FP.
| ssivark wrote:
| Let me venture a possible application, since there are already
| many responses celebrating pure mathematics.
|
| As far as we understand, the natural numbers are not sufficient
| for modeling physical phenomena. The reals/complex while
| immensely useful also occasionally turn out to be "too
| complicated" to give theoretical guarantees/proofs of models
| working well. On the practical side, that means that these
| models/algorithms can't be guaranteed to not give junk results,
| while working on the domain of real numbers.
|
| Now, purely speculatively, since the naturals/rationals are
| aleph0 in size and the reals are aleph2, that means there
| likely exists a set of numbers of size aleph1 sitting in
| between the two. What if we could use that set of numbers to
| construct our physical models? Could we somehow guarantee
| better behavior... Eg: in quantum mechanics, or field theory,
| or chaos, etc?! :-)
| morpheos137 wrote:
| It depends on what you define as a number. For example reals and
| complex have different properties from integers. Is there a
| mathematical reason why both are considered numbers? You can
| count (with) integers but not with reals. Thus one appears to be
| a number while the other appears to be a measure.
| Rerarom wrote:
| "Number" is not a mathematical term.
|
| "Natural number", "real number", "complex number" are.
|
| The fact that they all contain the string "number" is
| completely irrelevant.
| kmeisthax wrote:
| The essential property of anything mathematicians tack the word
| "number" onto _isn 't_ the fact that there's always a "next"
| number to count with. And it's very useful to do math with
| reals, otherwise we wouldn't be able to talk about things like
| the circumference of a circle, because you need an irrational,
| transcendental (not the root of a finite rational polynomial)
| constant.
|
| Generally speaking, a good chunk of the number systems
| mathematicians worked with involve taking some existing number
| system (tracing back to the natural numbers), finding some
| operation that takes you outside that system, and then building
| a new system to cover that hole. A system that has no such
| holes given a particular operation is said to "close over" that
| operation. So, integers close over subtraction; rationals close
| over division, and complex numbers close over exponentiation.
| Since all of these systems ultimately derived from operations
| over the natural numbers, it makes sense to also call them
| numbers, even though they might lack certain symmetries or
| properties of simpler number systems.
|
| Also, the word "measure" is already taken by a different
| concept.
| croes wrote:
| You are confusing numbers with natural numbers.
|
| "A number is a mathematical object used to count, measure, and
| label."
| morpheos137 wrote:
| You can't count reals or complex numbers. Real numbers by
| definition describe objects with infinite precision. In the
| real world infinite precision cannot exist therefore real
| numbers are the limit of an arbitrary precision measuring
| process not real themselves.
|
| Meanwhile natural numbers like "two" most certainly do exist
| as a quantitative attribute of a set.
|
| Show me how you can count with reals.
| croes wrote:
| I don't need to, I can measure and label with real numbers.
| That's enough for being a number.
| gowld wrote:
| You'll only ever use 0% of the real numbers for that.
| Unless you say that you count with "the reals", You don't
| need and won't use "the reals" for measurement and
| labelling, 100% of which are indescribable.
| morpheos137 wrote:
| technically you will use an infintesimally small real
| number approaching 0%...
| TuringTest wrote:
| At the end of the day, a number is a _reification_ (or
| thing-a-fication, watching a process as a separate entity)
| of the processes of _mapping_ and _ordering_. You may begin
| with a very simple use of those processes, which get you
| the natural numbers. But you may use them in more creative
| ways, which will get you other different classes of
| numbers. Mathematician love to explore all the implications
| of using basic processes and combining already defined
| numbers to create new kinds, never seen before.
|
| For example, if you start with number '1' and apply
| operator _successor_ (or "adding one more"), you get the
| *natural numbers*, which are a mapping from the size of
| sets to strings of operators {'1', 'successor(1)',
| 'successor(successor(1))', ... }. You can use this process
| to define an order: number A is smaller than B if you can
| repeatedly apply _successor_ to A and generate B in a
| finite time. (Not the best definition, I know, but bear
| with me for a second).
|
| If you reverse the _successor_ operator, you get the
| _predecessor_, which can be used to dismount large numbers
| and make them smaller. If you apply _predecessor_ to '1',
| you get 'predecessor(1)' which doesn't match any of the
| *natural* numbers as defined in the paragraph above.
| However, this new number is useful because you can map it
| to a collection without elements, allowing you to count a
| set of size 'zero'. This set doesn't exist, but it has a
| well defined size thanks to the process explained above.
| (You may as well apply _predecessor_ to 'zero' and count
| *negative numbers*, which allow you to create a mapping
| with debt, and thus count _I owe you_ amounts that don't
| exist in the physical world either).
|
| Now as for real and complex numbers, they can't count
| physical objects as you said because at some point you
| can't measure smaller and smaller magnitudes (though you
| _can_ create orders with them, even if it doesn 't directly
| involve the _successor_ operator). But mathematicians use
| them to count the size of _infinite sets_, which being
| immaterial never lose precision; you just know you can
| repeat their defining processes once and again, showing
| that there exist a mapping between any step in the process
| and the instance of the real or complex number that
| correspond to its size.
| HelloNurse wrote:
| In practical terms, "counting and measuring" means well-
| behaved arithmetic operations like addition, subtraction,
| multiplication, division, roots etc. (and often specific
| algebraic structures like rings, fields etc.)
|
| Rational and real numbers represent the most intuitive
| concept of quantity with different cardinality; natural
| numbers are more basic in theory but a restricted special
| case in most application (they can only count "countable"
| objects and they aren't dense); complex numbers compensate
| unnatural weirdness with important applications; then there
| are other very number-like niches (e.g. p-adic numbers,
| quaternions, algebraic extension fields...) and number-
| based arbitrary constructions (multidimensional vector
| spaces, matrices and tensors...).
|
| > Show me how you can count with reals.
|
| Like you count with natural numbers, plus many other
| possibilities because there are more numbers to count with.
| The same applies to rational numbers (which exist more than
| real numbers), complex numbers, etc.
| TuringTest wrote:
| > The same applies to rational numbers (which exist more
| than real numbers)
|
| Wait, did you say there are more rationals than reals?
| Isn't that the other way around?
|
| I don't know if that's a slip of the tongue or I'm
| missing something in my recall of basic math lessons
| gowld wrote:
| They are "more existent" ("less fictional"), not "more in
| cardinality".
| HelloNurse wrote:
| Real numbers do not exist: they are convenient, but there
| is a high risk of crossing over from reality-relevant
| math to nonsense because of infinite calculations.
|
| Real numbers are of course more numerous than rational
| numbers, just like unicorn horns are more numerous than
| horse horns, but it's an entirely different question.
| Decker87 wrote:
| Honest question, what is the usefulness of proving such an
| obvious thing?
| question000 wrote:
| The only thing this proves is that mathematics is a soft science,
| where concepts like "number" and "infinite" are subjective.
|
| There are obviously infinite numbers, if you think there's a
| finite number of numbers, take that number and add one to that.
| QED
| dang wrote:
| " _Please don 't post shallow dismissals, especially of other
| people's work. A good critical comment teaches us something._"
|
| https://news.ycombinator.com/newsguidelines.html
| question000 wrote:
| I can't believe you called this shallow and didn't even
| include an explanation as to why, ironic. There's nothing
| shallow about this at all, it goes to the heart of this fake
| intellectualism on this site.
| dang wrote:
| It's shallow because (a) contentless denunciations of "soft
| science" are cliche; (b) reducing serious mathematical work
| to "obvious" is the worst sort of dismissal.
|
| Please don't post like this to HN. We're trying for higher-
| quality discussion.
|
| https://news.ycombinator.com/newsguidelines.html
| question000 wrote:
| Seriously fuck off, everyday I read the same bullshit
| like this and it never gets removed. Read your own
| comments! This is laughable.
|
| Some things are obvious, and I'm allowed to say that to
| these self-proclaimed mathematicians.
| creddit wrote:
| 1) Mathematics is in no way a science.
|
| 2) I think you didn't read the article at all.
| question000 wrote:
| Yeah of course I didn't read the article. It's literally was
| the same as an article saying "Cows are green! If you're
| smart enough it becomes math!" I can't feed the clickbait
| machine.
| kibwen wrote:
| _> Woodin named the axiom (*), pronounced "star," because it was
| "like a bright source -- a source of structure, a source of
| light," he told me._
|
| There are only two hard problems in mathematics: infinity and
| naming things.
| sharpener wrote:
| The mileage of others may vary, but it has been my experience
| that there is no cogent solid proof of uncountability that can
| withstand concerted critique.[0]
|
| Being charitable one might argue that the meanings of terminology
| had been lost in translation over time and that perhaps Cantor
| was trying to create non-standard analysis, but then the diagonal
| argument seems to represent nothing more than the truism that
| finite numbers are smaller than transfinite ones.
|
| Hence I worry about people who are still worrying about this
| issue, and I worry for the future of science and AI in particular
| if folks can't get clear of it.
|
| [0]
| https://www.researchgate.net/publication/328568169_The_Case_...
|
| Yes, I'm that guy who wrote that.
| xvilka wrote:
| There is a good video about that on Numberfile[1]
|
| [1] https://www.youtube.com/watch?v=5TkIe60y2GI
| joe_the_user wrote:
| _For 50 years, mathematicians have believed that the total number
| of real numbers is unknowable._
|
| It's an established result that the Continuum Hypothesis is
| independent of Zermelo-Fraenkel axioms of set theory. No proof is
| going change that.
|
| So whatever has been proved here doesn't change that. It will
| take a second to get the reference but Raymond Smullyan says
| essentially that "we're not looking for a proof or disproof of
| CH, we're looking for an assumption that can be shown to be
| natural enough that we can take it as an axiom".
|
| Just sayin' since the (subheading) writer seems to be playing
| fast and loose with the concepts involved. Edit: article goes on
| to give rigorous explanation but still starting "no one knew"
| confuses what's going on.
| mmmBacon wrote:
| Maybe I misunderstood the article but if the set of real numbers
| is finite then it should be countable. But I can easily prove
| that the set of real numbers or any subset of real numbers is not
| countable. Been a really long time since I've thought about this
| but wondering what I'm missing.
| TameAntelope wrote:
| How can you easily prove that the set of real numbers is not
| countable? I don't think it's as easy as you claim, but I'm
| kind of a dummy so it's quite probably I'm wrong.
| twelfthnight wrote:
| Here's some background on the proof [1]. Here's a video
| explaining it little better [2].
|
| [1]
| https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
| [2] https://www.youtube.com/watch?v=elvOZm0d4H0
| Sharlin wrote:
| No, what the article is talking about is the question whether
| or not the cardinality of real numbers is the _smallest
| uncountable infinity_ or some other, larger uncountable
| infinity. The only _countable_ infinity is aleph-0, the
| cardinality of natural numbers, and Cantor showed that aleph-0
| is too small to hold all reals. So reals must be uncountable,
| but there is an infinite hierarchy of uncountable infinities,
| and it is not known which one is the cardinality of reals
| (although in practice it 's suspected to be either aleph-1,
| which is what the Continuum Hypothesis states, or aleph-2).
| keymone wrote:
| unrelated: how do we know there are no alephs between 0 and
| 1?
| elcomet wrote:
| That's the definition of aleph-1.
|
| The continuum hypothesis is that 2^aleph-0 (number of sets
| of integers or number of reals) = aleph-1.
| Sharlin wrote:
| If you assume Axiom of Choice, you can define cardinalities
| in terms of ordinal numbers (an extension of naturals that
| generalizes the notion of "counting", or "indexing"). And
| ordinal numbers are well-ordered, ie. every element has a
| unique "successor" element.
| jostmey wrote:
| > "Not all infinities are equal"
|
| In other words, there are different categories of infinite, and
| it might be inappropriate to represent infinity with just one
| symbol! This article is about how many types of infinity might
| exist.
|
| I was taught there is countably and uncountably infinite.
| Integers are countably infinite because the number of integers
| between any two numbers if finite. Real numbers are uncountably
| infinite because there are infinite numbers between any two real
| numbers.
| ceh123 wrote:
| >I was taught there is countably and uncountably infinite.
| Integers are countably infinite because the number of integers
| between any two numbers if finite. Real numbers are uncountably
| infinite because there are infinite numbers between any two
| real numbers.
|
| So this isn't exactly right, although I suppose the argument
| for integers isn't exactly wrong. When we get to the rational
| numbers however, they are countable but there are an infinite
| number of rational numbers between any two rationals in the
| typical way of thinking about "between" numbers. Based on your
| argument above, this would mean that rationals are uncountable.
|
| A better way to think about this is that the set of natural
| numbers is the first (and smallest) infinite set you can
| construct. This is the set of all counting numbers so we call
| it countable.
|
| We then say two sets are the same size (cardinality) if you can
| create a one-to-one mapping between the two that covers both
| sets (a bijection). This way you exactly pair one element of
| one set with one element of another. You can do this with the
| natural numbers and integers by just alternating positive and
| negative (so 0 -> 0, 1 -> 1, 2 -> -1, 3 -> 2, etc.). All the
| sets that you can do this sort of mapping with the natural
| numbers are considered countable.
|
| You can't do this sort of mapping from the natural numbers to
| the reals (see cantor's diagonalization argument) so since you
| can't "count" the reals, the set is "uncountable."
| omnicognate wrote:
| The article isn't about how many types - or rather
| cardinalities (sizes) - of infinity exist, it's about which of
| those cardinalities describes the real numbers.
|
| "Countably" infinite sets have cardinality Aleph_0, the
| "smallest infinite size". There is an infinity of "larger
| infinite sizes", all of which are "uncountable", so to refer to
| a set as "uncountably infinite" doesn't pin down which
| particular cardinality it has.
|
| The article is about what specific cardinality the set of real
| numbers has, and in particular whether it's Aleph_1 or Aleph_2
| as it seems less likely to be any of the infinite other
| possibilities.
| jmgao wrote:
| > I was taught there is countably and uncountably infinite.
| Integers are countably infinite because the number of integers
| between any two numbers if finite. Real numbers are uncountably
| infinite because there are infinite numbers between any two
| real numbers.
|
| This is unsound: a set is countable if there's a mapping that
| assigns an integer to each element of that set. There are an
| infinite number of rational numbers between any pair of
| rational numbers, but you can pretty easily construct a mapping
| between integers and rationals. Imagine representing a rational
| x/y as a point on the plane, and draw a square spiral around
| the origin. Every rational number lays on that spiral, and
| there's a unique "shortest arc-length of the spiral from the
| origin" for each rational.
| gotostatement wrote:
| I guess you could rephrase OP's argument in a sound way as: a
| set is countable if there's a way to order it such that
| between every two numbers there are finitely many numbers
| chaoticmass wrote:
| https://www.youtube.com/watch?v=SrU9YDoXE88
|
| I really like how VSauce covers this topic as well.
| mikepurvis wrote:
| Veritasium did a really good video on this recently, based
| around Hilbert's Hotel:
|
| https://www.youtube.com/watch?v=OxGsU8oIWjY
| ncmncm wrote:
| > _How many real numbers exist?_
|
| You might be tempted to say "lots". And you would be right, as
| far as that goes.
|
| But that doesn't satisfy a _real_ mathematician. The question
| that immediately arises is whether "lots" is "enough". And that
| leads the better sort of mathematician inevitably to: "enough for
| what?" That is what mathematicians are deep in the middle of
| exploring, now.
|
| For example, when you are asked, "Does this skirt make my butt
| look too big?", you obviously must not say "yes", but you just as
| obviously cannot, with an entirely clear conscience, say "no",
| either. But for anyone with an intact survival instinct, the
| counter-question, "too big for what?" should spring immediately
| to mind. And it's a good one, but it depends intimately on the
| true size of the set of real numbers. So, this is not an idle
| pursuit.
| rkagerer wrote:
| _" Does this skirt make my butt look too big?"
|
| "Too big for what?"_
|
| Yeah let me know how that works out.
| 90minuteAPI wrote:
| Answering "Does this skirt make my butt look too big?" with
| something that "depends intimately on the true size of the set
| of real numbers" seems to be among the worst strategies.
| dexwiz wrote:
| I'm no mathematician, but I have always found it strange
| infinities are talked about as physical states (towers of tall
| towers, etc), and not functions.
|
| Integer number counting is essentially a successor function; take
| N, add 1, output N+1. One input, one output.
|
| Real number counting is a bit more loose. To find the numbers
| between .1 and .2, you find all fractionals of a given size,
| normally 1/10. So we get .10, .11, .12, etc. This function gives
| more outputs than inputs, thus an increase in cardinality.
| Forcing just seems like changing the function to increase the
| cardinality.
|
| In my mind, all infinities are equal, it's how you generate them
| that matters.
| zeugmasyllepsis wrote:
| > Real number counting is a bit more loose. To find the numbers
| between .1 and .2, you find all fractionals of a given size,
| normally 1/10.
|
| Unfortunately the fractionals method does not work, since there
| are numbers (in fact, uncountably infinitely many!) irrational
| numbers which cannot be expressed as fractions, which are
| nonetheless real numbers (such as the square root of two and
| pi).
| IncRnd wrote:
| I'm not a mathematician, either, but I believe your comment
| shows why not all infinities are equal.
|
| When you attempt to enumerate .1, .2, .3, .4, etc. you get an
| infinite count of numbers. However, when you perform that same
| operation on .05, .15, .2, .25, and so on, you will get "twice
| as many numbers" as the first time around.
|
| In this way, the second infinite sequence has "twice as many
| numbers" as the first infinite sequence.
| gowld wrote:
| No, it doesn't. Then have the same number, as can be plainly
| seen by lining them up and counting the elements in order.
| arduinomancer wrote:
| I don't get for Cantor's diagonalization proof, why do we need to
| use the diagonal digits to form the new number?
|
| Would the proof work the same if we instead used the first digit
| of every number in the list?
| pfortuny wrote:
| Then you cannot guarantee that when you change the first digit
| of the second number, what you get is not the first number.
| ceh123 wrote:
| To give a concrete example for you, lets start with the finite
| set:
|
| {0.22, 0.32, 0.33}
|
| We now construct a new number in this way:
|
| First digit of the first number is 2, so we take 3 which is
| different as our first digit.
|
| First digit of the second number is 3 so we take 2 as our
| second number. Now we have 0.32
|
| First digit of the third number is 3 so we take 0 as our third
| number.
|
| We've constructed the number: 0.320 = 0.32 which is in the set
| already. So this construction method doesn't guarantee that
| it's a new number, only that it's different from the first.
|
| With Cantor's Diagonalization argument we guarantee it's
| different from the first number since it's different in the
| first digit, then we guarantee it's different from the second
| since it's different in the second digit, etc. etc. it's
| different from all the numbers in our list.
|
| To take the same set above as an example, we end up creating a
| number like: 0.318 which is definitely different from the
| numbers in the set
| miloignis wrote:
| There are only 10 possible first digits of the new number, so
| you can't choose a number that will differ from all other
| numbers in the first digit. If you do it diagonally, you'll
| always have 9 other options to choose from, since you just have
| to make it different from that one number!
| arduinomancer wrote:
| Makes sense, thanks
| tpetrina wrote:
| That wouldn't work because n-th digit differing from 1st digit
| of n-th number doesn't guarantee that the new number isn't
| accounted for already.
| erdos4d wrote:
| You need the diagonal because you are making a new number in
| (0,1) that can't be in the list by just choosing the nth digit
| of said number different than the nth digit of the diagonal.
| pavpanchekha wrote:
| To fill in some details:
|
| Two real numbers are different if in the same place they have
| different digits. [1] So the idea is to take your infinite,
| hypothetical list of all real numbers A[] and make a new real
| number X, where for all i, there's some digit where A[i] and X
| differ. Easiest way is to make X differ from A[i] at digit i.
|
| [1] There's a subtlety here about repeating nines at the end of
| a number, but it is inessential.
| privatdozent wrote:
| Another great piece from Quanta. Such an important institution
| btilly wrote:
| As a constructivist I'll be over in the corner that says that
| there are only a countable number of real numbers, and the
| unimaginable number of unimaginable infinities that classical
| mathematics insiste exists is all made up nonsense. That, in
| fact, things that can't ever be named, even in principle, don't
| actually exist.
|
| What is interesting is that as shocking as constructivism may be,
| there is no logical flaw in it. If classical mathematics is
| consistent, then so is constructivism. And "there exists" is a
| whole lot more meaningful in constructivism.
| papandada wrote:
| I have found my people. Thank you.
| reggieband wrote:
| I'd like to subscribe to this newsletter.
|
| Mathematicians using sets to argue about the size of
| uncountably infinite Reals feels like the old joke of
| philosophers arguing over how many angels can fit on the head
| of a pin. I often wonder if we've used set theory (and
| formalisms of math based on logic) to substitute one
| metaphysical theory for another equivalent one.
|
| I can understand the frustration of mathematicians of the past
| being told they have to ensure their theories align with some
| spiritual mythology. But it sort of feels like I'm being forced
| to accept some kind of metaphysical truth in the name of
| ensuring the calculus of infinitesimals is grounded in logic.
| scapp wrote:
| You sound like you need to read this [0] answer to the question
| "Are real numbers countable in constructive mathematics?".
|
| > You are using the word "constructive" in an unusual way. It
| is true that, in ZFC, the set of computable real numbers is
| countable, but that is not directly a statement about
| constructive mathematics.
|
| > Not every school of constructive mathematics identifies real
| numbers with algorithms; that's a characteristic of the
| "Russian" school as I understand it. In other schools of
| constructivism that I am more familiar with, real numbers are
| coded by elements of 2^o, or by a certain type of Dedekind cut
| on the rationals. In such schools it is not universally assumed
| that every real number is associated with a finite algorithm.
|
| > Even in the Russian school, they would not say that the set
| of real numbers is countable. Because, if you identify real
| numbers with algorithms, there is no computable enumeration of
| computable reals that lists all computable reals, and so the
| translation of "the real numbers are countable" into this
| setting is false.
|
| > That phenomenon also occurs in classical computable analysis.
| The subsystem RCA0 of second-order arithmetic has a model in
| which every real number is computable. But this subsystem still
| proves that there is no surjection N -> R.
|
| ---
|
| It's worth noting that another answer to that question (Andrej
| Bauer's) gives a constructive proof that the real numbers are
| uncountable using with the axiom of countable choice. The
| question of whether it's provable without the axiom of
| countable choice is open (though see this [1] fairly recent
| paper on a proof for MacNeille reals).
|
| [0] https://mathoverflow.net/questions/30643/are-real-numbers-
| co...
|
| [1] https://arxiv.org/abs/1902.07366
| btilly wrote:
| Yes, there are multiple constructivist approaches possible.
| However since my objection to classical approaches is that I
| want "X exists" to be meaningful, I like mathematical objects
| that can be written down with a finite number of symbols in a
| finite space. Which means that I'm only interested in a
| countable universe of possible mathematical things.
|
| If you say "exists" about anything else, I'll understand you
| - I do have advanced degrees in math. But I'll think that
| you're using the word "exists" in a deeply artificial way.
| LudwigNagasena wrote:
| What's the problem with it being "artificial"? Is your
| problem purely linguistic? You just dislike the word
| "exists" being used in this context?
| btilly wrote:
| The problem is that exists comes to mean something
| technical that doesn't match common usage.
|
| Let's take my favorite example.
|
| In graph theory, a minor of a graph is a graph you can
| get by removing vertices, removing edges, or by replacing
| an edge-vertex-edge triple with a single edge. Many
| categories of graphs are closed under the act of taking
| minors. For example planar graphs, graphs you can draw on
| the plane with no crossings, are.
|
| The category of planar graphs is entirely described by
| the fact that any graph that isn't planar must have
| either K5 or K3,3 as minors. That is, a graph with 5
| vertices, all connected. Or a graph with 2 groups of 3
| vertices, that all connect to each other. Therefore we
| call those two graphs the "forbidden minors" for planar
| graphs.
|
| The Robertson-Seymour theorem says that any category of
| graphs which is closed under graph minors has a similar
| description. There is a finite list of forbidden minors
| which, if none are minors of a given graph, then that
| graph is in the category.
|
| Since there is a polynomial time algorithm to detect
| whether a given graph is a minor of another, this
| immediately means any category of graphs closed under
| taking minors must have a polynomial time algorithm to
| test for membership. Just test each forbidden minor.
|
| So far this is straightforward, but here is where things
| get weird.
|
| The first catch is that the Robertson-Seymour theorem is
| non-constructive. That is, it says that the list exists
| and is finite. But it does not bound the number. It does
| not give us a way to find those minors. It does not give
| us any way to determine whether we have a complete list.
| For example we know of thousands of minimal forbidden
| minors for graphs that can be drawn on a torus, and do
| not know if our list is complete.
|
| The second catch is that we know that none of those
| things are possible to do. That is, there are collections
| of categories of such graphs such that we can prove that
| no algorithm can bound the number, no algorithm can
| search for those examples, and no algorithm can verify
| that a list of forbidden minors is complete.
|
| In what sense does a finite thing that is unfindable,
| unverifiable, and of unknowable size actually exist? And,
| if you think that it exists, in what sense is something
| of unboundable size actually finite?
| chmod775 wrote:
| > there are only a countable number of real numbers
|
| Then you should be able to come up with a function that assigns
| a natural number uniquely to each real number.
|
| Of course if you tried that I could immediately name you a real
| number, or a pair of them, for which your rule doesn't work.
| skoodge wrote:
| That depends on what you mean by "assigns uniquely", "rule"
| and "doesn't work", which is why this question is deeply
| entangled with philosophical issues that cannot be settled
| purely mathematically.
|
| It is obvious that all expressions in the English language
| can be ordered from smallest to largest and
| lexicographically, which makes these expressions trivially
| countable. We can thus assign natural numbers to real numbers
| by assigning numbers to their expressions in a natural or
| formal language, which will of course include infinitely many
| expressions that are just nonsense descriptions and
| infinitely many expressions that map to the same real number.
| These expressions will also include any possible expressions
| of Cantor's or other diagonalized numbers. In such a sense
| then, we can trivially "count" the real numbers unless we
| hold the philosophical view that there are real numbers that
| are not expressible. This is where it becomes a question of
| philosophy of mathematics, not mathematics proper.
|
| You can of course object that what you meant by "assigns
| uniquely" is an _unambiguous 1:1 mapping_ and that including
| any number of nonsense descriptions misses the point. In that
| case giving a "rule doesn't work" because the diagonalized
| number always escapes the proposed system of counting the
| numbers, but only because the diagonalized number is allowed
| to 'parasitically' depend on the totality of the system, but
| is excluded from the system (or else it would diagonalize
| itself and become ambiguous at that particular decimal
| place). This particular viewpoint is tied to a particular
| philosophical position, however, and not all positions in the
| philosophy of mathematics will agree with it.
|
| This all might seem trivial or even nonsensical (as
| philosophy of mathematics so often appears), but I merely
| want to point out that the 'uncountability' of the real
| numbers is not a consequence of the set of the natural
| numbers being 'too small' to hold all the real numbers,
| because they are 'large enough' to assign numbers to all
| possible descriptions all real numbers that will ever be
| expressed in language. Uncountability is a consequence of a
| view that restricts Cantor's diagonalized number from the set
| of the countable number _but still considers this
| diagonalized number to be a real number_ (which again is only
| unambiguously defined if it is not allowed to diagonalize
| itself). There are however other possible philosophical
| viewpoints which either include the diagonalized number in
| the set of countable numbers (at the cost of including
| ambiguous or paradoxical numbers) or reject the view that
| Cantor 's diagonalized number should be considered to be a
| real number in the first place.
|
| tl;dr: Yeah, you can always name a real number for which a
| particular counting rule does not work, but only as long as
| there is agreement regarding the philosophical underpinnings.
| Most mathematicians can probably be considered platonists and
| from their standpoint the real numbers are obviously
| uncountable, but that is by no means true for all positions
| in the philosophy of mathematics.
| klysm wrote:
| Does constructivism rule out uncountability because induction
| is always indexable?
| btilly wrote:
| There are different schools of constructivism. But if you
| insist on only dealing with mathematical objects that admit
| of finite descriptions with finite symbols, there is a
| surjection from a countable set onto the entire universe of
| possible mathematical objects.
|
| That said, an _enumeration_ of all mathematical objects is
| not possible. That 's because we may not be able to resolve
| the question of whether 2 descriptions of a mathematical
| object actually refer to the same object or not.
| pavpanchekha wrote:
| Great article. Since it looks like a lot of folks are interested
| in this article, some extra background.
|
| First, what is forcing? The article actually has a great
| description of ultrapowers (a key part of the construction) but
| it goes by a little fast, so you might like Tim Chow's "A
| beginner's guide to forcing" [1] which does a good job not only
| laying out the mathematical details at a high level, but also
| really clearly explaining the philosophy of how you prove
| something independent of the axioms. I found it very
| illuminating.
|
| Second, the article has some interesting notes on how
| mathematicians go about what axioms to select and which not to.
| Penelope Maddy's "Believing the Axioms" [2] is the classic on
| this topic (it has two parts). It is focused on set theory, so it
| has a nice description of Martin's axiom and the arguments for
| and against. It was nice to read because it is a deeply technical
| argument (set theory is hard!) but at the same time there is no
| "right answer"--all of these axioms, after all, are independent
| of ZFC, and it's "ok" to add any of them. The arguments are
| sometimes aesthetic ("rules" versus "surprises"), sometimes
| pragmatic (what they can and cannot prove), and sometimes involve
| deep values of what the universe should be like (should higher
| cardinalities be like lower ones? weirder? simpler?).
|
| It might all seem abstract, but if your day job is programming,
| imagine an argument over how to architect a large and complex
| system. Perhaps both architectures are possible, but which one is
| "right"? What arguments would you deploy? Set theorists are also
| building a large and complex system (the universe of sets) and
| are having arguments over how it should be built, which things it
| should make easy and which hard, which technologies should be
| supported natively (forcing?) and which should not.
|
| [1] http://timothychow.net/forcing.pdf [2]
| https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf
| BoiledCabbage wrote:
| Why does forcing work? To me it seems flawed (which obviously
| means I don't understand it fully).
|
| For diagonalization argument: 1) Assume every real can be
| assigned a natural number. 2) Do a bunch of steps that
| essentially find a new real that differs from any real you have
| listed from step 1. 3) Conclude that either your steps are
| flawed, or your initial assumption is wrong 4). Because your
| steps aren't flawed then your initial assumption (that every
| real can map to a natural number) is flawed.
|
| That all makes sense to me. Forcing seems broken though: 1)
| Capture of list/set of all real numbers 2) Do a bunch of steps
| that essentially find a new real that differs from any real you
| have listed from step 1. 3) Conclude that either your steps are
| flawed, or your initial assumption is wrong 4). Because your
| steps aren't flawed then your initial assumption (that you can
| produce a list of every real number) is flawed.
|
| Now you're left in an odd situation. Didn't you just conclude
| that it's impossible to have a set of all real numbers? Which
| isn't what you're trying to prove at all.
| cwzwarich wrote:
| In a forcing-based consistency proof of a proposition P, you
| start with a model of ZFC (or a sufficiently large subset of
| ZFC, depending on the exact formalism being used),
| approximate a witness to P (e.g. a bijection between a set of
| reals and aleph_2) within the starting model, and then apply
| the forcing machinery to construct a new model of ZFC where P
| holds. Unlike the diagonalization argument, it's inherently
| metamathematical.
| jerf wrote:
| "Didn't you just conclude that it's impossible to have a set
| of all real numbers?"
|
| Cantor's diagonalization proof proves that it's impossible to
| list all the real numbers with a list of size aleph-0, which
| is the cardinality of the set of natural numbers.
|
| The forcing proof is an attempt to prove you also can't do it
| with the a list of the size aleph-1, which is the size of the
| power set of aleph-0. It purports to prove that you need a
| list of size aleph-2, which is the size of the powerset of
| aleph-1.
|
| You can kind of think of this not so much as whether "Can
| Crysis run?" ("can you have a set of all real numbers?") but
| "Can Crysis run _on this machine_? " Do the real numbers need
| aleph-1 "resources", or aleph-2 "resources" to list?
| glial wrote:
| I think this is a typo:
|
| > aleph-0, which is the cardinality of the set of real
| numbers.
|
| aleph-0 is the cardinality of the set of natural numbers,
| and (as you say) is not the cardinality of the real
| numbers.
| jerf wrote:
| Yes, thank you, that was a typo.
| BoiledCabbage wrote:
| Thanks for the reply. Question though. in Cantor's argument
| we explicitly mapped the reals to aleph-0 so it makes sense
| that our conclusion decides that mapping to aleph-0 is too
| small so it's size must be larger.
|
| Where in the forcing process do we even "use" aleph-1? If
| we used aleph-1 then it could see the parallels and the
| argument would make sense - but all I see in the forcing
| process is "start with a set of all reals". Nothing about
| trying to map them to aleph-1. Maybe it's implicit, but
| couldn't I have just changed step 1 to instead be "start
| with a list of size aleph-90, then use forcing to prove
| that the reals are larger than aleph-90." In Cantor's
| argument it feels like we "used" the natural numbers. Here
| it seems more like we said take an arbitrary number of them
| and see this one isn't in it. But that arbitrary number of
| them (aleph-1) could've been any arbitrary number of them
| because we never really used any property of the set being
| aleph-1 vs aleph-90.
| finnh wrote:
| Great question, I have no answer.
|
| The article explained forcing in such a way as to simply
| restate what I thought we already knew: given a real,
| there is no "next" real. (ie, there are a non-countable-
| infinite number of reals between any two reals).
|
| I don't see the newness that forcing brings to this.
| [deleted]
| dwohnitmok wrote:
| Forcing is about a completely different question.
|
| The question is not where there are reals between reals,
| it's a question of the size of sets. In particular is
| there a set strictly larger than the natural numbers, but
| strictly smaller than the reals? Forcing allows us to
| construct such a set in ZFC.
| scotty79 wrote:
| That's weird. I thought that it was proven that existence
| of sets larger than aleph-0 but smaller than the number of
| real numbers is undecidable and you can add it (or negation
| of it) as additional axiom to math.
|
| https://en.wikipedia.org/wiki/Cardinality_of_the_continuum
|
| "The continuum hypothesis, which asserts that there are no
| sets whose cardinality is strictly between aleph-0 and
| c=aleph-1. The truth or falsity of this hypothesis is
| undecidable and cannot be proven within the widely used ZFC
| system of axioms."
| mdoms wrote:
| This is covered in the article.
| Layke1123 wrote:
| Cantor's diagonalization proof was never a proof to begin
| with. You can't construct a number that isn't on an
| infinite list of all numbers because you can't list all the
| numbers, otherwise you'd eventually find your number. It's
| honestly kind of ridiculous that this proof hasn't been
| subjected to more rigor than just handwaving away the
| problems.
| avz wrote:
| > aleph-1, which is the size of the power set of aleph-0
|
| In ZFC, aleph-1 is not the size of the powerset of aleph-0.
| Instead, aleph-1 is the next larger cardinal number after
| aleph-0. The size of the powerset of aleph-0 is called
| continuum or beth-1. In ZFC, we can show that the size of
| the set of real numbers equals continuum, but it is not
| possible to relate continuum to a specific aleph-k (though
| some can be ruled out using Easton's theorem).
|
| Now, the statement that aleph-1 is the size of the powerset
| of aleph-0 is known as the Continuum Hypothesis (CH) and is
| independent of the axioms of ZFC. Therefore, your claim
| that aleph-1 is the size of the powerset of aleph-0 cannot
| be made in ZFC. The statement can be made in ZFC+CH, but
| then the question which aleph-k is the size of the real
| numbers has a straightforward answer: aleph-1.
| jerf wrote:
| Thank you. I accept this.
| myhf wrote:
| > 2) Do a bunch of steps
|
| It's not just a bunch of steps. It's an infinite number of
| steps. It requires the axiom of choice.
| intuitionist wrote:
| Maddy's work is great and worth reading (even as an
| antirealist!), but it's worth keeping in mind that debates
| about foundations are basically irrelevant to the working lives
| of the large majority of mathematicians. If you're studying,
| say, extremal graph theory or the Langlands program or low-
| dimensional topology, the cardinality of the continuum is
| simply not relevant.
| pavpanchekha wrote:
| Yes, I actually have a kind-of related blog post:
|
| https://pavpanchekha.com/blog/proof-system-os.html
|
| I tried to restrict my post to just set theory because this
| philosophical point is often hard for people to grasp.
| rssoconnor wrote:
| > but at the same time there is no "right answer"--all of these
| axioms, after all, are independent of ZFC, and it's "ok" to add
| any of them.
|
| Minor quible: Just because a potential axiom is independent of
| ZF(C) doesn't make it necessarily "okay" to add. Potential
| axioms can be unsound, for example if they prove new / untrue
| Sigma_1 statements. As an example, even in the likely
| circumstance that !Con(ZFC) is independent of ZFC, it wouldn't
| be "okay" to add !Con(ZFC). While the resulting system would be
| consistent, and does have models, the resulting system is
| unsound (in the sense of Tarski) because it asserts the
| existence of natural numbers that have no "written form" (i.e.
| the existance of natural numbers that are larger than any term
| you can write to denote a natural number).
|
| That said, Martin's axiom, like the CH (or the axiom of
| choice), does not have any arithmetic consequences, and thus
| doesn't fall into this category of problematic axioms.
| pavpanchekha wrote:
| You're absolutely right. ZFC + !Con(ZFC) is a weird set of
| axioms, and no mathematician really studies it. I skipped
| this point, because we weren't really discussing such axioms,
| but it's an important point that there are different levels
| of mathematical / philosophical commitments, and realism and
| PA are way stronger commitments than the ones people have
| about cardinalities.
| tgflynn wrote:
| > he resulting system is unsound (in the sense of Tarski)
| because it asserts the existence of natural numbers that have
| no "written form" (i.e. the existance of natural numbers that
| are larger than any term you can write to denote a natural
| number).
|
| Isn't that basically the definition of the natural numbers,
| ie. if you write down any natural number (say n) I can always
| construct a natural number that is larger than it (like n+1)
| ?
| kmill wrote:
| This surprisingly doesn't mean repeatedly adding 1 will
| exhaust all natural numbers -- there are models for the
| natural numbers with elements that can't be reached this
| way!
|
| The ultrafilter construction gives one such model. You take
| the set of all sequences of natural numbers (n1, n2, n3,
| ...) then use an ultrafilter to decide which of these
| sequences are considered to be equal. The usual operations
| of natural numbers are defined term-by-term. You can think
| of the usual natural numbers as being the sequences
| (0,0,0,...), (1,1,1,...), (2,2,2,...) and so on. However,
| there are many additional numbers in this system, like
| (0,1,2,...) that are strictly greater than all the usual
| numbers, and these cannot be reached by repeatedly adding
| one. (The reason (0,1,2,...) is greater than (n,n,n,...) is
| that if we do the comparison term-by-term we get
| (false,false,...,false,true,true,true,...), and the
| ultrafilter will decide the comparison is true because it
| is true for all but finitely many terms. Ultrafilters are
| devices to consistently turn infinite sequences of trues
| and falses into a single decision, but every ultrafilter
| will make a true decision in the case there are only
| finitely many falses.)
|
| Counter-intuitively, proofs by induction still work for
| this system... speaking with no authority here, maybe an
| intuition is that it's doing a hypercomputation.
| rssoconnor wrote:
| Dropping down to Peano Arithmetic for a moment. We can
| consider adding a new constant 'c' for a natural number to
| the language along with the following infinite list of
| axioms about this remarkable constant:
|
| - 0 < c
|
| - 1 < c
|
| - 2 < c
|
| - 3 < c
|
| ...
|
| Adding all these axioms is consistent. I.e. you can do
| induction upto 'c', whatever it is. Why is it consistent?
| Because if there was a contradiction, the proof of such a
| contradiction would be finite, and hence can only use a
| finite number of these new axioms (this is a so-call
| compactness argument). But clearly any finite subset of
| this list of axioms is consistent because it has a model
| where c is just defined to be 1 more than the largest
| numeral appearing in that list.
|
| But all those infinite number of axioms taken together
| creates an unsound system because it claims that 'c'
| denotes a natural number that is larger than every written
| numeral.
|
| Heading back to ZFC land, it turns out that (assuming
| !Con(ZFC) is independent of ZFC) adding !Con(ZFC) to ZFC
| similarly is similarly unsound in that it yields only
| models that have elements that are larger than every
| written numeral.
| hypersoar wrote:
| You can find a natural number that is bigger than any one
| natural number, but you can't write _one_ down that 's
| bigger than _every_ natural number in the ZFC sense.
| gooberwonder wrote:
| 45,000,000,001?
| dwohnitmok wrote:
| > that's bigger than every natural number in the ZFC
| sense.
|
| I'm not sure what you mean by this.
|
| Even for nonstandard models of the natural numbers there
| will never be a single number larger than all other
| numbers, since that violate the Peano axioms.
|
| Did you mean by "in the ZFC sense" "the standard model?"
| munk-a wrote:
| Do you mean that given finite resources (like time and
| matter) we would be unable to express the number? Or are
| you talking about a sort of recursive thing where writing
| down a number which is a sum of all natural numbers up to
| and including itself is impossible since that number is
| bigger each time you look at it?
| chongli wrote:
| If you can write down the natural number n, you can write
| down n+1.
|
| Of course, you can't write down the entire set of natural
| numbers but _that_ is not a natural number.
| lupire wrote:
| why is that "unsound"? what's wrong with an unwritable
| natural? Almost all reals are unwritable.
| rssoconnor wrote:
| Mostly because it implies that some Turing machines halt
| that actually do not halt. That is unless you are willing
| to accept that a Turing machine can halt in some number of
| steps that is beyond any number that can be written. And I
| don't mean can't be written in the sense that we don't have
| enough paper. Just cannot be written in principle at all by
| our notation for numbers.
| bryan0 wrote:
| But isn't this what the busy beaver numbers are? Numbers
| that we cannot write for arbitrary n but they do exist?
| rssoconnor wrote:
| I think this is a great question.
|
| The difference here is that with busy beaver numbers,
| e.g. BB(101) we can, presumably, write their values with
| our notation; it's just that we often cannot prove that
| any particular value written in our notation does indeed
| denote the value for that function. So if we write
| 100000...0000 with an unholy number of 0s there, it might
| be the value of BB(101), in particular we might not be
| able to prove that it isn't.
|
| On the other hand, for a non-standard number, c, it is
| definitely the case that 100000...0000 is not c, because,
| whatever c is, it is strictly greater than 100000...0000,
| or any other number we can write down.
|
| And thus when it comes to proofs about the termination of
| Turing machines that do not actually terminate, the
| unsound system is claiming that some machine terminates,
| but it doesn't terminate in 1 step, nor 2 steps, nor 3
| steps, nor ... nor 100000...0000 steps, nor 100000...0001
| steps, nor 100000...0002 steps, nor .... However,
| regarding the BB(101), the (presumably) sound systems we
| use such as PA, or ZFC, do not claim that BB(101) isn't
| 100000...0000. They just may not be able to prove
| anything one way or the other.
| dogecoinbase wrote:
| Soundness in this sense (sigma_1 soundness) is defined by
| equivalency to the standard model (specifically, all
| sentences provable in the system must be provable in the
| standard model).
| dwohnitmok wrote:
| It is defined by equivalency to _a_ standard model.
| Whether there is a single standard model is a
| philosophical question (which granted most, but not all,
| set theorists tend to agree with). Hence sigma_1
| soundness is from a purely mathematical point of view a
| relative statement.
| pavpanchekha wrote:
| I wonder what you mean by "what's wrong with an unwritable
| natural"... It is sound to assume one! And it doesn't make
| any true mathematical facts false. But of course it's sound
| to assume many silly things. But why assume those things?
|
| The reality is that mathematicians didn't first come up
| with the Peano axioms and then study the interesting
| consequences of them. Both as a matter of history and also
| as a matter of why most mathematicians do math,
| mathematicians first came up with numbers, and only later
| came up with axioms that allow them to do rigorous
| reasoning about them. The same is actually true of almost
| all math--real numbers were invented to do rigorous
| reasoning about calculus, which by that point had been
| around for a century plus; set theory likewise.
|
| In other words, if the goal is to come up with any old
| consistent set of axioms, you can assume an unwritable
| natural number, that's fine, go ahead. But if your goal is
| to study natural numbers--which, like, I have a lot of
| experience with natural numbers in my day to day life, I'm
| pretty sure I could write all of them if I had enough time
| and space and so on--then you want to study natural
| numbers, not some other weird things where there are
| unwritable weird things.
| dwohnitmok wrote:
| This is not unsound in the usual sense of "logical
| soundness" (which applies to logical systems such as first-
| order logic, rather than specific theories in the system
| such as ZFC).
|
| This is unsound in that it runs counter to certain
| philosophical commitments, namely that there should be some
| tangible, physical realization of all the natural numbers
| (although if you really go far in that direction you end up
| with ultrafinitism, which most set theorists would find
| unpalatable, so the philosophical implications of all this
| are rather tricky).
| Someone wrote:
| > _because it asserts the existence of natural numbers that
| have no "written form"_
|
| I don't see why that should imply it wouldn't be "okay" to
| add !Con(ZFC).
|
| It may be highly counterintuitive, but the history of
| mathematics is full of counterintuitive results that nowadays
| are accepted as true in mainstream mathematics.
|
| Well-known examples are the existence of irrational numbers,
| the claim that the set of natural numbers has the same size
| as that of the rational numbers, the existence of hyperbolic
| geometry, and the Banach-Tarski paradox.
| scrubs wrote:
| @pavpanchekha: thank you indeed for this great post and great
| references. I took ML and ran into CH, Ultrafilters but never
| really got my head around it. Reading with interest!
| 01GOD wrote:
| Hmmm...somebody named "chow" faking something...why is that not
| surprising?
| pdonis wrote:
| Thanks for these references! The Chow paper is the first one
| I've read that makes me feel like I understand forcing and
| Cohen's proof.
| dwohnitmok wrote:
| Man there's a lot of juicy stuff in this article (Woodin's
| Ultimate L program gets briefly alluded to at the end of the
| article).
|
| I just want to point out, because the HN crowd seems to generally
| not be mathematical Platonists, that this entire article is
| implicitly assuming a Platonist philosophical foundation. This
| may cause confusion for lay readers who are not mathematical
| Platonists.
|
| In other words the article assumes that mathematical objects have
| an objective existence: they either exist or they do not. Hence
| every single logical axiom has a truth value. You do not get to
| arbitrarily choose what logical axioms you want. If you do, you
| can end up choosing the "wrong one." Therefore it is an important
| question to understand whether the Continuum Hypothesis is true
| or not, even if it's independent of ZFC (and hence requires
| ultimately philosophical rather than mathematical arguments).
|
| If you aren't a Platonist and instead view logical axioms as
| having no inherent truth value, but rather foundations that you
| can pick and choose from as necessary (where in one case you may
| choose to use an axiom and in another you may choose its
| negation), then all that might sound very strange to you. In that
| case, you should mentally substitute every instance of "true" or
| "false" in the article with "agrees or disagrees with the meta
| model used to examine the semantics of a logical theory." In
| particular, whenever we talk about a formal treatment of the
| semantics (i.e. model) of a theory, whether that be something
| like ZFC or a programming language, we must always make those
| statements relative to a meta-model.
|
| For example if we talk about the formal semantics of a language
| like C, we must first posit a meta-model which already contains
| notions of things like "integer" and "natural number" which can
| be used to give meaning to statements such as "performed an
| operation n times." If you're not a Platonist then you probably
| believe that there are multiple possible meta-models you could
| use.
| red_trumpet wrote:
| Thanks for that perspective! Searching around I found this
| article https://plato.stanford.edu/entries/platonism-
| mathematics/#Tr... which even distinguishes mathematical
| Platonism and truth-value realism. Interesting stuff!
| kachnuv_ocasek wrote:
| Thanks for the clarification. I was indeed a bit confused by
| some of the implicit assumptions as an intuitionist myself.
| goldenkey wrote:
| Individually, or independently, axioms have no truth value. But
| when you put together a system of multiple axioms, they can
| contradict eachother. I see no problem with the question of
| whether the continuum hypothesis is true, given ZFC as a
| precondition. All we are asking is if the axiom contradicts
| ZFC. Axiom independence is very similar to operator commutation
| in quantum mechanics.
| dwohnitmok wrote:
| The Continuum Hypothesis and its negation are both proven to
| be consistent with ZFC (this is what the article is talking
| about RE forcing and Godel's proof of the consistency of CH).
| There is no contradiction to assume one or the other
| alongside ZFC. The article is really talking about Platonic
| truth when it talks about something being true or false.
|
| > Individually, or independently, axioms have no truth value.
|
| Indeed, you are not a Platonist :).
| phkahler wrote:
| You can map all the real numbers to the interval 0 <= x < 1. To
| map one of those reals to an integer, simply write it's trailing
| digits in reverse order on the left side of the decimal point.
| You may then drop any leading zeros.
|
| 0.0 => 0
|
| 0.1 => 1
|
| 0.2 => 2
|
| ...
|
| 0.14159 => 95141
|
| The argument against this is that there are real numbers with an
| infinite number of digits, which will not have a specific integer
| associated with them. Or do they? Can there be an "infinitely
| large integer?" or are there just infinitely many of them? I
| think this question gets to the core of the problem.
| plus wrote:
| > The argument against this is that there are real numbers with
| an infinite number of digits, which will not have a specific
| integer associated with them. Or do they?
|
| If it was possible to construct your mapping, then there would
| be a well-defined sorting of the reals between 0 and 1 based on
| their integer representation (e.g. we could sort the set {0.05,
| 0.1, 0.2} => {50, 1, 2} to [0.1, 0.2, 0.05] => [1, 2, 50]).
|
| How would you sort the list {0.5, 1 / sqrt(2), pi - 3}?
| question000 wrote:
| "Can there be an infinitely large integer"
|
| No there can't there's always a larger integer. Anyone who
| claims otherwise is just making stuff up. It's just mind
| blowing to me that anyone think otherwise, it's like asking
| what the final digit of pi is, you'd get laughed out of any
| college class for insisting there might be one, rightly so.
| red_trumpet wrote:
| > You can map all the real numbers to the interval 0 <= x < 1.
|
| Even easier use a well-established function such as arctan to
| map the reals bijectively to the interval -p/2 < x < p/2, and
| then scale and shift the interval to 0 < x < 1.
| plus wrote:
| This allows you to map the real range (0, 1) to (-infinity,
| infinity). It does not allow you to map the integers to the
| reals.
| victorbojica wrote:
| But if you assign them randomly, then it should work
|
| 1->5.85916
|
| 2->8.7599
|
| ...
|
| Or even randomize the order for the integers
|
| 5->7.52256951
|
| 77->848.455
|
| ...
| bonzini wrote:
| You can't, this is Cantor's diagonal counterexample.
| gowld wrote:
| > Can there be an "infinitely large integer?"
|
| What could that even mean? Aren't integers all defined as
| Succ^n(x) for a finite n and a base x?
| pelorat wrote:
| The existence of addition implies that the answer is infinity.
| Too simple an explanation for mathematicians obviously.
| Sharlin wrote:
| The whole point of the article is that we don't know _which_
| infinity it is.
| howderek wrote:
| They know it is infinite. They want to understand the
| cardinality. Any two sets (including infinite sets) A, B have
| the same cardinality if there exists a bijection from A|->B
| throwawayboise wrote:
| I didn't read the paper, and have only an undergraduate math
| background, but it seems to me that for sufficiently large n, n
| + 1 = n. Vague justifications related to limits.
| 123pie123 wrote:
| I've always been brought up to realise that math(s) is not real.
| It's more of a (extremely) good system to model stuff, say like a
| map isn't real, but just a representation
|
| so this proof is pushing the system of this math(s) system
| svachalek wrote:
| The deeper physics goes, the more apparent it is that our
| perception of reality is a good model for what is happening at
| our scale in the universe and the forces that are dominant at
| that scale. Our intuition breaks down at larger and smaller
| scales, but the math still works. So in some sense, math is the
| truest access we have to reality.
| 01GOD wrote:
| I suspect the op was trolling the hackernews community to
| intentionally cause a big mathsturbatory circlejerk.
|
| Golf clap on how amazingly effective that was.
| MiddleEndian wrote:
| https://www.smbc-comics.com/comic/the-largest-number-2
|
| Tangentially related comic
| dwater wrote:
| I have a degree in math but the first thing this headline made
| me thing of was still the "24 is the highest number" sketch
| from Mr. Show:
|
| https://www.youtube.com/watch?v=RkP_OGDCLY0
|
| Theoretical mathematics is often absurd, maybe that's why I
| like the sketch so much.
___________________________________________________________________
(page generated 2021-07-15 23:00 UTC)