[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 : 454 points
Date : 2021-07-15 15:03 UTC (1 days 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.
| ttctciyf wrote:
| This sounds a _little_ like Chaitin 's constant Omega (O),
| which is very roughly a number in [0, 1] which is the
| probability that a randomly chosen program (for a universal
| Turing machine, U) will halt.
|
| This has the interesting property that knowing the first n bits
| of O allows you to determine whether any program (for U) of
| length up to n will halt, in other words you could solve the
| halting problem for programs of length up to n.
|
| As Wikipedia puts it:
|
| > Because many outstanding problems in number theory, such as
| Goldbach's conjecture, are equivalent to solving the halting
| problem for special programs (which would basically search for
| counter-examples and halt if one is found), knowing enough bits
| of Chaitin's constant would also imply knowing the answer to
| these problems. But as the halting problem is not generally
| solvable, and therefore calculating any but the first few bits
| of Chaitin's constant is not possible, this just reduces hard
| problems to impossible ones, much like trying to build an
| oracle machine for the halting problem would be.
|
| - https://en.wikipedia.org/wiki/Chaitin%27s_constant
| 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.
| kd0amg wrote:
| > why is 2^68 0% of the "numbers that need to be
| checked"?
|
| The vast majority of natural numbers are larger than
| 2^68. Only 2^68 of them are less than 2^68, but
| infinitely many of them are greater.
| 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.
| HelloNurse wrote:
| Not every possible graph, just every "interesting" class
| of subgraph that can be extended or combined with others
| to obtain a coloring of any planar graph. These are a
| large but finite number; if a graph is planar it cannot
| have too many edges.
| 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?! :-)
| drdeca wrote:
| Whether the cardinality of the reals is aleph 1, aleph 2, or
| something larger, is independent of ZFC.
|
| In a model of ZFC in which the set of reals has cardinality
| greater than aleph_1 , I wouldn't be surprised if there is a
| subfield of the reals of cardinality aleph_1 , but I would be
| surprised if such a field was useful for things like that.
| Such a field would, of course, not be complete with respect
| to the usual metric on the rationals, so we wouldn't have the
| desired convergence properties. We wouldn't really be able to
| do infinite sums in it? (Well, perhaps some other sense of
| infinite summation could be done, but it wouldn't be the
| usual sense.)
|
| In addition, because such a subfield would only exist as an
| uncountable proper subfield in some models of ZFC, I find it
| hard to imagine that it would allow computations that
| wouldn't otherwise work? I suppose it could motivate some
| computations which would then also work regardless of what
| model of ZFC is being used / is true ?
| 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".
| TuringTest wrote:
| How are they more existent? They are both patterns of
| recognized concepts in human brains.
|
| Is it because more people understand rationals than
| reals? Ok, that would make rationals more existent, as
| they exist in more brains.
| 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.
| TuringTest wrote:
| No numbers exist, they are abstraction on human-created
| procedures. Even naturals, which are an abstraction over
| pointing to things and counting.
| 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.
| ProfHewitt wrote:
| The results in the article are based on 1st-order logic,
|
| which is inadequate for the foundations of mathematics.
|
| Mathematical abstractions need to be characterized up a
|
| unique isomorphism as in the theory Ordinals described in
|
| the following article: "Theory Ordinals can
| Replace ZFC in Computer Science"
| https://papers.ssrn.com/abstract=3457802
|
| Mathematical questions can be properly addressed only by
|
| using adequate foundations.
| 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.
| myWindoonn wrote:
| Hi, Lawvere pummelled your position into the ground a while
| ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your
| critique involves repeatedly crossing the boundary between the
| inside and outside of the system in question; Lawvere works
| entirely inside the system, and shows that the paradoxes of
| self-reference arise from our interpretations.
| https://arxiv.org/abs/math/0305282v1 explains with many
| examples.
|
| Hi downvoters: Use your words when somebody is wrong. Your
| downvotes aren't helpful here for finding the truth.
| sharpener wrote:
| Lawvere's paper appears to suggest that if I refute one
| diagonal argument then I refute them all. Would you consider
| that to be an accurate description?
| sharpener wrote:
| I'm not seeing this yet. Perhaps you could explain it to me
| in plain terms.
| curtisf wrote:
| This presents a confused understanding of Cantor's
| diagonalization argument.
|
| You are shrouding in complexity something that is
| straightforward. The complete proof of distinct infinite
| cardinalities can be stated succinctly and clearly in only a
| few lines, without referencing the reals at all. You don't need
| to vaguely refer to "four steps", you should precisely
| elaborate the steps of the proof you view as problematic.
|
| First, forget the reals. Let's establish that there are sets
| that are infinite yet uncountable.
|
| ----
|
| "Uncountable" means that there is no bijection with (a subset
| of) the natural numbers.
|
| An "infinite sequence of A's" means a function N - A. For
| convenience, I'll denote the set of infinite sequences of A's
| with `A**` -- this is not standard notation.
|
| Theorem: There is no bijection between N and {0, 1}**.
|
| Proof: Suppose for contradiction that there is a bijection f: N
| - {0,1}**.
|
| Define a function z(n) = 1 - f(n)(n).
|
| z is clearly well defined and is clearly a member of {0,1}**.
|
| Since f is a bijection and z is in the codomain of f, there is
| an element k of N such that f(k) = z.
|
| However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k).
|
| This is a contradiction. So, the assumption (that there exists
| a bijection f: N - {0,1}**) must be false.
|
| Q.E.D.: There does not exist a bijection between N and {0,
| 1}**.
|
| ----
|
| The linked paper claims that the above proof would work on a
| bijection of the form N - [N] or N - [Q] (where the [] indicate
| some suitable representation of the set as sequences of bits;
| again, not standard notation), but that is mistaken: crucially,
| the constructed function `z` must be a member of the codomain
| of `f`. The construction 1 - f(n)(n) does not necessarily lie
| in that set when the set only permits _certain_ bit-sequences!
|
| For example, consider an encoding [N] which is "one-hot"; the
| natural n is encoded as a function y(n) = 1 and otherwise y(k)
| = 0. Then there is an obvious bijection `f`: f(a, b) = 1 when
| a=b and otherwise 0. What is `z` for such an `f`? z(k) = 1 -
| f(k, k) = 1. So, `z` is not a member of [N].
|
| For a more involved example, consider an encoding of [NN] that
| is a unary-encoding of the first natural, followed by a single
| zero, followed by a unary encoding of the second natural, and
| followed by only 0s. (The rationals correspond to a subset of
| these). A standard bijection has the pairs appear in the order
| of their sum: (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2),
| ... It's an exercise left for the reader that z constructed on
| this set does not encode to a unary number, followed by a
| single zero, followed by a unary number, followed by only
| zeros.
|
| ----
|
| If you have an issue with cardinalities, I expect it can be
| found in the above proof and does not actually lie with the
| reals. But, for completion, to tie in the real numbers, it's
| necessary to show that {0,1}** is bijective with R, or with (0,
| 1). This falls out from the Cauchy-sequence definition of R.
| For a sequence y : {0,1}** the sequence z(k) = y(0) + 1/2*y(1)
| + 1/4*y(2) + 1/8*y(3) + ... + 1/2^k*y(k) is clearly a Cauchy
| sequence with a limit in the interval [0, 1]. It's also
| straightforward to check that every real number in the interval
| [0, 1] is the limit of one such Cauchy sequence.
| sharpener wrote:
| > Define a function z(n) = 1 - f(n)(n).
|
| I don't understand the notation f(n)(n). Is it related to
| f_{nn} in LaTeX notation? Your later text suggests maybe it
| was aiming at f(n,n) so I will assume that.
|
| I recognise a form of this argument and I might have tackled
| it in the supplementary materials I created that are
| referenced in the article. Let me know.
|
| > However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 -
| z(k).
|
| I'm assuming this was intended to be: z(k) = 1 - f(k). Yet
| f(k) = z, so z(k) = 1 - z(k).
|
| For some k, z(k) = 0.5. f(k) = 0.5. Seems Ok.
| drdeca wrote:
| For each natural number k, f(k) is itself a function, and
| f(k)(k) means the value of that function at k.
|
| Yes, you could basically think of it as f_{k,k} if you
| wanted to.
|
| No, this is __not__ meant to be 1 - f(k) . f(k) is a
| function (or a sequence, if you prefer), not a particular
| value in {0,1}, f(k)(k) is a particular value in {0,1}.
|
| 0.5 is not in the set {0,1}, and therefore if z(k)=0.5 then
| z is not in {0,1}* .
| myWindoonn wrote:
| For future readers: z cannot return 0.5. z can only return
| 0 or 1. This is because z is closed over a function which
| returns 0 or 1, and inverts it to return 1 or 0.
|
| This should remind folks of both Turing's Halting problem
| and Russell's paradox. z takes some f which claims to be a
| bijection (claims to Halt, claims to be a set of all sets)
| and finds a way to call f against a witness constructed
| from f.
| sharpener wrote:
| > Theorem: There is no bijection between N and {0, 1}*.
|
| So no bijection between \bb{N} in an unspecified number base
| and some binary strings that could represent integers? That's
| a nonstarter for me.
|
| Please read my article. Thanks.
| myWindoonn wrote:
| You misread their type. There is no bijection N -> (N ->
| 2); {0,1}* = 2* = N -> 2.
|
| Note that the given proof is a version of Lawvere's fixed-
| point theorem. The trick is noticing that for some x : N, f
| : N -> (N -> 2) can be applied onto it twice, giving f(x) :
| N -> 2 and f(x)(x) : 2.
|
| Note further that infinite binary strings don't just
| represent natural numbers. Indeed, every natural number has
| a _finite_ binary string, and that is the bijection that
| you 're imagining. The question is, which natural number is
| represented by 111...? This leads to the difference between
| the natural numbers, their one-point compactification, and
| Cantor space in terms of searchability. Escardo has an
| article on this:
| http://math.andrej.com/2007/09/28/seemingly-impossible-
| funct...
|
| Please read Lawvere's article. Thanks.
| candybar wrote:
| > Stage 4 of the CDA outline can be critiqued on several
| grounds. The first is that if we have all the numbers in [0,1]
| in our table a priori, then using the diagonal process to
| create a number that is not in the original set does precisely
| that: It creates a number that is not in [0,1]. So why does the
| constructed anti-diagonal number seem to have a form that puts
| it within [0,1]? Could it be that ignoring the zero ahead of
| the decimal point is a bit sneaky?
|
| You wrote all this and you don't seem to understand how proof
| by contradiction works?
|
| > If, instead, we construct the anti-diagonal number by
| counting down the table by positions before each digit
| selection we find that any anti-diagonal number constructed
| (from the rectangle) is now within the set we have counted
| through, and therefore not outside the counted set. This
| Stretched Diagonal counterargument remains true as d- [?],
| irrespective of any ordering of number representations in the
| table.
|
| This is not how anything works. You can't take a proof where
| they create an example that leads to contradictions and say,
| well, if you choose a different example, it doesn't lead to
| contradictions, so the proof doesn't work.
|
| Your "proof" in Appendix B is also just gibberish from a
| mathematical perspective. The infinity and cardinalities aren't
| numbers - this isn't a mathematically rigorous statement: lim(n
| -> inf) log(n) = inf = aleph_0 - it's nonsense. What you're
| saying here is that as n increases without bound, 2^n also
| increases without bound. That doesn't prove anything about the
| cardinality of infinite sets.
|
| Also, since you seem to accept that |R| is equivalent 2^|N|,
| it's also not hard to prove that 2^|S| > |S| for any S. 2^|S| <
| |S| is trivially untrue and if |S| = 2^|S], there must be at
| least one bijection F such that F: S => P(S) and inverse F^-1:
| P(S) => S
|
| Now define S' to be a subset of S such that s is in S if & only
| if it's in S, but not in F(s). Now, consider F^-1(S') - it must
| be in S, due to how it's defined. Let's consider whether it's
| also in S':
|
| 1. If F^-1(S') is not in S' (= F(F^-1(S')), by definition, it
| must be in S'
|
| 2. If F^-1(S') is in S', by definition it must not be in S'
|
| Since both these lead to contradictions, the assumption that
| there must be a bijection between P(S) and S mut be false.
|
| On the whole, you seem to be generally confused - R is not a
| real thing - it's a mathematical abstraction.
| 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.
| js8 wrote:
| I have a question, so assuming that we adopt the axiom(s) that
| cause real numbers to be cardinality Aleph_2 and not Aleph_1, is
| then there some intuitive explanation how does the set of size
| Aleph_1 looks like, and what it could be used for?
| tromp wrote:
| The explanation of Cohen's filter for making new reals reminds me
| of surreal numbers {L | R} but in this case every real is in
| either L or R. Still, I fail to see how that gives you more than
| restricting L and R to contain only rational numbers...
| 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
| TameAntelope wrote:
| I guess I was focusing on the word "easy", heh.
| mmmBacon wrote:
| You do this in sophomore level Real Analysis. So as far
| as pure math goes, easy.
| TameAntelope wrote:
| > sophomore level Real Analysis
|
| Hmm?
| rpearl wrote:
| We did this first semester freshman year at my school in
| a single lecture in a 100 level "concepts of mathematics"
| course. I get that there's a certain amount of "it's hard
| to wrap your head around infinity" but really this proof
| is pretty well trodden by students not far into learning
| mathematics.
| TameAntelope wrote:
| Which school?
| doctoboggan wrote:
| Watch the video, its actually quite easy to follow.
| 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).
| orangecat wrote:
| _(although in practice it 's suspected to be either aleph-1,
| which is what the Continuum Hypothesis states, or aleph-2)_
|
| There are some arguments that it's "really" much larger, as
| in greater than aleph-n for any finite n. See
| https://risingentropy.com/the-continuum-hypothesis-is-false/
| (incidentally an excellent blog if you're interested in these
| sorts of things).
| 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.
| philipswood wrote:
| Yes, the call for more experimentation to keep theorists
| honest.
| 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.
| ncmncm wrote:
| The mathematics of infinities are nothing if not
| counterintuitive.
| whoaisme wrote:
| Ken M is that you?
| 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.
| drdeca wrote:
| There is a way of mapping different ordinal numbers which are
| less than some large countable ordinal (idr how high up it
| goes. I suspect it isn't well defined at least past the church
| kleene ordinal, but I think it is much before that, but also I
| could be totally wrong) to different functions from integers to
| integers which increase at different rates.
|
| These methods include the Hardy hierarchy, and the fast growing
| hierarchy.
|
| (But regarding all infinities being equal, that's just
| incorrect, sorry.)
| 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.
| chasing wrote:
| There are exactly 1,837 real numbers and anyone who tells you any
| different is just trying to sell you something.
| 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.
| pdonis wrote:
| _> I like mathematical objects that can be written down
| with a finite number of symbols in a finite space._
|
| Which is fine, but I don't think it justifies the claim
| that there are only countably many real numbers. The only
| claim it justifies is that there are only a finite (not
| even countable, since "countable" implies infinitely many)
| set of numbers that you find useful.
| 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?
| LudwigNagasena wrote:
| In the usual sense. I don't see a problem. Just because
| you don't have a perfect knowledge of something, it
| doesn't mean that the thing isn't real.
|
| I am not sure where this idea even comes from? To be
| honest, this sounds completely ridiculous.
| pdonis wrote:
| These concerns don't apply to the claim that the set of
| real numbers is uncountable. Cantor's diagonal proof is
| constructive: given any countable set of real numbers, it
| tells you how to construct a real number that is not in
| the set. That is sufficient to show that the set of real
| numbers cannot be countable. Also, even though many real
| numbers cannot be written down with a finite set of
| symbols, Cantor's diagonal proof can be.
| btilly wrote:
| Yes, you can write down Cantor's diagonal proof. But if
| you're careful about it, you find that the diagonalized
| thing is not a real number. For example a program to list
| programs that can be proven (by some set of axioms) to
| create Cauchy sequences can be used to create a Cauchy
| sequence, but you can't _prove_ that that sequence is a
| Cauchy sequence without running into Godel 's
| incompleteness theorem.
| 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.
| myWindoonn wrote:
| Turing machines are countable. In some constructive settings,
| every real number is computable, as an axiom; those settings
| allow us to talk about the Turing machines which compute a
| particular real number.
| 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.
| pdonis wrote:
| _> We can thus assign natural numbers to real numbers by
| assigning numbers to their expressions in a natural or
| formal language_
|
| This doesn't work because not all real numbers _have_
| expressions in a natural or formal language. This is easily
| shown by an obvious variation on Cantor 's diagonal proof,
| applied to your lexicographically ordered list of
| expressions in any natural or formal language.
| skoodge wrote:
| Sure, that is why I wrote:
|
| > 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.
|
| I'm not disagreeing with your interpretation of Cantor's
| diagonal proof, I'm merely pointing out that this
| interpretation depends on a very specific philosophical
| view of mathematics, namely the platonist view that the
| real numbers _exist_ independently from their expressions
| in any natural or formal language and that it makes sense
| to say that there are real numbers that are not
| expressible.
|
| And yeah, nearly all working mathematicians will agree
| with this view and from their perspective the real
| numbers are uncountable, period, and you are right that
| what I sketched "doesn't work".
|
| But I think it's important to remember that there are or
| could be alternative philosophical views of mathematics
| that lead to a different interpretation, which will
| reject not the mathematical validity of Cantor's diagonal
| proof, but rather its _usefulness_ or _relevance_. After
| all, how can you convince someone that there are real
| numbers that are not expressible? By their very nature
| they cannot be practically used in any calculation, so
| how could you convince someone who is not convinced by
| this philosophical assumption of Cantor 's diagonal
| proof?
|
| In other words, Cantor's diagonal proof cannot _prove_
| that there are real numbers that are not expressible,
| because the proof only makes (philosophical) sense if you
| accept this viewpoint in the first place.
| chmod775 wrote:
| > 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.
|
| You could say the same about just real numbers, which can
| also be ordered from smallest to largest. This definitely
| not 'trivially' implies countability.
|
| Edit: I edited my post shortly after posting from "Humor
| me and count out the first two real numbers".
| skoodge wrote:
| EDIT: The parent first said (before being edited, with my
| original answer after the quote):
|
| > Humor me and count out the first two real numbers in
| English in lexicographical order.
|
| Probably "one" and "six" (then "ten" and "two", followed
| by all 4-letter expressions of real numbers), unless you
| can think of an English expression with a length of three
| letters or less that would occur before "one" and "six"
| lexicographically. If you consider "pi" or "e" to be
| descriptions of real numbers then clearly these would
| occur before "one" and "six".
|
| But of course you can also pick an arbitrary universal
| Turing machine or other suitable formalism, pick an
| encoding as bit strings and order expressions in such a
| formal language according to their bit strings. Ordering
| expressions in the English language is only the less
| formal counterpart.
|
| (If your point is that ordering expressions of real
| numbers in English is far from unambiguous without first
| agreeing on a dictionary of valid words and on rules of
| what can be considered an expression of a real number in
| more than one word then of course I would agree. But what
| I'm driving at is not that it's easy to unambiguously
| count out the real numbers in English, of course it's
| not, but rather that any kind of natural or formal
| language expressions, by being recursively enumerable,
| are "numerous" enough to be a countable set of
| expressions. To say that the real numbers are uncountable
| is to accept the view that there are real numbers that
| are not and can never be expressible in language, which
| is a view that only makes sense against the backdrop of a
| very specific philosophical framework. One that is
| definitely accepted more or less implicitly by most
| working mathematicians, but not the only possible one.
| And this philosophical framework cannot itself be
| justified or grounded by a mathematical argument such as
| Cantor's diagonal proof.)
|
| ---
|
| Reply to the parent after edit:
|
| > You could say the same about just real numbers, which
| can also be ordered from smallest to largest. This
| definitely not 'trivially' implies countability.
|
| No, what I meant was that by ordering expressions in the
| English language or other suitable formal languages first
| from smallest string to largest string and within these
| groups lexicographically, you can enumerate all the
| expressions in such a language, which makes them
| trivially countable.
|
| Of course this does not give you a 1:1 mapping from
| expressions in a language to real numbers, but it is
| meant to illustrate that the real numbers are not
| uncountable because they are 'too numerous' to be counted
| by the natural numbers, in the sense that a box is not
| large enough to hold a collection of things. They are
| uncountable because we accept the view that there can be
| real numbers that are not and cannot be expressible in
| language, which is a platonist view that is open to
| philosophical critique.
| chmod775 wrote:
| > Probably "one" and "six"
|
| You missed infinitely many numbers between those two. For
| example "one thousand" and "one dot/comma three".
|
| Once you've worked that all out, can you now tell me
| which natural number you assigned to "six" in your
| lexicographical order?
|
| Edit: Ah. Took me a moment to realize you are ordering by
| number of characters first.
|
| > They are uncountable because we accept the view that
| there can be real numbers that are not and cannot be
| expressible in language, which is a platonist view that
| is open to philosophical critique.
|
| So similar to R \ Q? Or the same?
| skoodge wrote:
| Oh, I see what the issue is. I wrote "smallest to largest
| and lexicographically", meaning first from smallest to
| largest (as measured by the length of the string) and
| then within each group lexicographically, which is the
| usual way of giving an enumeration of such expressions as
| far as I know. Of course you cannot enumerate these
| expressions if you expect a solely lexicographical
| ordering. In any case, English was just an example, you
| can basically pick any Turing-complete language that is
| recursively enumerable and count its expressions by
| considering its bit string encodings as natural numbers.
|
| Edit: This is also why the computable numbers are
| countable, but not computably enumerable (because
| figuring out which expressions correspond to real numbers
| is equivalent to the halting problem).
| chmod775 wrote:
| You've convinced me that R without all numbers that are
| not expressible in typical languages is countable at
| least.
|
| Though I'm not convinced that numbers that are not
| expressible don't exist. I could for instance say "the
| length of this line", which may very well have a length
| that is not expressible in a language that uses a finite
| set of symbols (hah, that's why your expressions are
| countable, of course!).
|
| Consider a language however that instead of numbers
| simply uses sounds of the appropriate length, or draws
| lines of proportional length (assuming of course you
| could do this precisely).
|
| With that language you could express every real number,
| and you could express numbers that turing machines* or
| English can't.
|
| *Unless programmed in that language.
| skoodge wrote:
| That's an interesting thought experiment, though I'm not
| sure how using "sounds of the appropriate length" or
| "lines of proportional length" would get you more than
| the rational numbers, which are already countable and
| thus fully captured by any Turing-complete language. To
| say that there are inexpressible real numbers is to say
| that there are numbers that are not rational but which
| can never be practically used or accessed either, at
| which point they become kind of like an invisible and
| unnoticeable unicorn: it is certainly possible to believe
| in its existence, but such a belief is quite different
| from the belief in the existence of practically useful
| real numbers such as pi.
|
| I am not trying to convince anyone that inexpressible
| real number do or do not exist, but I think it's worth
| noting that these issues quickly cross over into the
| realm of philosophy, where it's not possible to justify a
| particular conviction by appealing to firm mathematical
| or practical reasons. Nothing wrong with that, of course.
|
| Personally, I'm content with what is expressible in
| language and I consider mathematical concepts going
| beyond this boundary of expressivity as inessential to my
| own personal use, though I can certainly see that these
| mathematical calculi can be of interest to mathematicians
| on their own.
| btilly wrote:
| Your "easily shown" is only easily shown if you're
| sloppy.
|
| If you're careful, it can't be shown at all.
|
| As I already pointed out, if classical mathematics is
| consistent, then constructivism must be as well.
| Therefore if you think that you've found a logical flaw
| in constructivism, the mistake must be in your own
| thinking.
| 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.
| CamperBob2 wrote:
| Not a mathematician, so this probably has an obvious
| answer, but who says that "size" is a necessary universal
| property of a set? It doesn't seem any more rational to
| speak of size as a required property of a set than it
| would be to treat color or weight that way. Some sets
| have those attributes, but not all.
|
| It seems perfectly reasonable to say that the set of real
| numbers is one of those sets that doesn't have a "size"
| property.
| dwohnitmok wrote:
| Size is a hand-wavy way of saying it. What we're really
| asking is given two sets A and B, is there a function
| from A to B such that no two elements from A are mapped
| to a single element in B?
|
| It turns out if you use ZFC (in particular choice) then
| one direction must hold. Either such a function exists
| from A to B or from B to A. This means that we can order
| all sets using the existence of these functions, and so
| in that sense size is a "universal property."
| 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.
| HotHotLava wrote:
| The illustration in the article doesn't start with the whole
| set of all real numbers, but with just "a" set containing an
| uncountable number of reals, so there is no contradiction in
| that sense.
|
| I'm assuming there's some unmentioned technical condition on
| which sets you are allowed to choose in order for the
| procedure to work, otherwise the argument would indeed seem
| to lead to a contradiction when choosing the set of all real
| numbers.
| 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.
| logicchains wrote:
| >The ultrafilter construction gives one such model.
|
| It's worth noting that this construction relies on the
| axiom of choice, so exists in ZFC but not ZF. Generally a
| lot of counter-intuitive constructions disappear when
| eliminating the axiom of choice (such as the Banach-
| Tarski paradox and non-continuous functions).
| kmill wrote:
| > non-continuous functions
|
| I think the step function doesn't depend on choice. Say
| f(x) = 0 if x < 0 and f(x) = 1 if x >= 0. Also, suppose
| we define the reals through Dedekind cuts. We can define
| f(x) by checking whether 0 is an element of x as a cut.
| We can prove f is discontinuous in the usual way.
|
| What I had heard is that Brouwer proved, using some kind
| of constructive/intuitionistic logic, that every function
| is continuous, but ZF is still based in classical logic.
| I believe the step function is not definable
| constructively.
| R0b0t1 wrote:
| Can you explain what use these have? If natural numbers
| are (n, n, n, ...) then you have just made a new type of
| number not comparable to natural numbers.
| kmill wrote:
| A theoretical use is that it shows that the axioms of the
| natural numbers (the Peano axioms) aren't enough to pin
| down what we think the natural numbers should be -- there
| are these crazy non-standard natural numbers out there!
|
| In context of the discussion, this non-standard model of
| the natural numbers gives some intuition about what
| happens if the consistency of ZFC is independent of ZFC
| and you add in the axiom that ZFC is inconsistent: your
| natural numbers will have to be something similarly
| weird.
|
| > you have just made a new type of number not comparable
| to natural numbers
|
| But they _are_ comparable. The everyday natural numbers
| are embedded in this new system, which is what these
| (n,n,n,...) elements represent. One way to interpret what
| we 've done here is to add in infinities to the number
| system so that all the normal operations still work, and
| there's even a total ordering on them!
|
| Using the real numbers instead of the naturals, you get
| the so-called nonstandard real numbers, which is the
| number system used in nonstandard analysis. Nonstandard
| analysis is a way to do analysis without epsilon-delta
| proofs. Nonstandard reals include infinitesimals and
| infinities, similar to nonstandard naturals having
| infinities. There are even textbooks on the subject -- I
| haven't read them, but they claim it makes analysis
| easier.
|
| The last thing that comes to mind is that nonstandard
| numbers of this exact type show up when you study certain
| infinite-dimensional number systems and calculate the
| points (like in the end of my comment).
| kmill wrote:
| > calculate the points (like in the end of my comment)
|
| Oh, I forgot I commented more than once today on HN. I
| was referring to this one:
| https://news.ycombinator.com/item?id=27851188
| 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.
| skissane wrote:
| > in that it yields only models that have elements that
| are larger than every written numeral.
|
| Are these like hyperintegers (or should I say
| hypernaturals), as in the hyperrreal numbers used in non-
| standard analysis?
| 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?
| l33t2328 wrote:
| I don't believe a consequence of the axioms discussed is
| that there exist natural numbers with no "written form." Do
| you have a proof or citation?
| 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.
| skybrian wrote:
| On any storage system you will eventually run out of
| memory, so there will always be a maximum integer that
| you can write down with what you have, and we can only
| write down a vanishingly small subset of the natural
| numbers.
|
| Of course, this isn't what mean when they talk about
| "writing down" a number, but I've long thought that
| assuming the existence of natural numbers that you can't
| write down is poetically apt.
|
| In some sense, the set of natural numbers is "too big" to
| be about everyday finite numbers alone and it seems
| fitting to acknowledge that our usual axioms can't
| exclude weirdo large finite numbers that are simply too
| big to ever reach.
| 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?
| thaumasiotes wrote:
| Do they exist? I thought there was an independence
| theorem for the specific values of almost all busy beaver
| numbers.
| bryan0 wrote:
| Yes they are independent of ZFC but they still exist.
| From the original article talking about CH which is also
| independent:
|
| > This independence is sometimes interpreted to mean that
| these questions have no answer, but most set theorists
| see that as a profound misconception. They believe the
| continuum has a precise size; we just need new tools of
| logic to figure out what that is. These tools will come
| in the form of new axioms.
|
| I believe the same applies for BBs. They have precise
| values outside of ZFC but we still cannot ever know them
| because they are incomputable (??)
| thaumasiotes wrote:
| > but we still cannot ever know them because they are
| incomputable (??)
|
| That doesn't mean you can't know them. We know BB(2). It
| means there is no single algorithm which is capable of
| yielding them all. But there could, theoretically, be an
| algorithm for BB(10), a different algorithm for BB(11),
| etc.
|
| In fact, those individualized algorithms don't exist
| either.
| rssoconnor wrote:
| They exist in that it is easy to prove "for ALL x there
| EXISTS y such that (there EXISTS a Turing machine with at
| most x states M such that (there EXISTS some n such that
| M prints y 1's and halts after n steps) AND (for ALL
| Turing machines with at most x states M, if (there EXISTS
| some n such that M halts after n steps) then (M prints no
| more than y 1's after n steps))". I expect you can prove
| this in systems as weak as Primitive Recursive
| Arithemetic.
|
| It is true though that various (decidable) proof systems
| are unable to prove that the Busy Beaver function has any
| specific value beyond a certain point. However, where
| that cut-off is varies from proof system to proof system,
| with stronger proof systems being able to prove more an
| more values of the Busy Beaver function.
|
| Maybe you find it weird that we can prove (Exists x. P x)
| without being able to prove P n for any particular
| numeral n? Welcome to the strange world of classical
| (i.e. non-constructive) mathematics.
| thaumasiotes wrote:
| > It is true though that various (decidable) proof
| systems are unable to prove that the Busy Beaver function
| has any specific value beyond a certain point.
|
| Isn't the result stronger than that though? The value of
| BB(30) might be X. Or it might be Y. Neither value would
| cause any problems.
|
| Thus, "the value" doesn't exist. There is no value that
| is the value of BB(30).
| 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.
| rssoconnor wrote:
| It's not "okay" because such a system proves that various
| particular Turing machines halt when, in fact, those
| machines do not halt. See
| https://news.ycombinator.com/item?id=27847719.
|
| But to be a bit more specific, !Con(ZFC) says that the
| Turing machine that searches for a contradiction in ZFC
| does indeed halt. However (in all likelihood) such a
| machine does not actually halt, in the sense that it does
| not halt in 1 step, and it does not halt in 2 steps, and it
| does not halt in 3 steps, etc., and indeed (in all
| likelihood) for each numeral n, ZFC even proves that the
| machine does not halt in n steps.
|
| (Now there is a small possibility that maybe such a machine
| does halt in some particular number of steps. If it does
| actually halt, that means it has found a proof that ZFC is
| inconsistent. But this scenario is even worse, because it
| means that ZFC itself is not only unsound, but
| inconsistent, (and hence ZFC+!Con(ZFC) is also
| inconsistent). In particular ZFC+!Con(ZFC) being
| inconsistent means it proves that every Turing machine
| halts, which is even more wrong in general, even if it
| happens to be right about this particular machine.)
| a1369209993 wrote:
| > such a system proves that various particular Turing
| machines halt when, [ _]in fact[_ ], those machines do
| not halt.
|
| Er, no. The _fact_ is that there _is no_ fact of the
| matter as to whether those particular Turing machines
| either a: do not halt at all, or b: halt after a
| (colloquially) infinite number of steps. (A implication
| of there being no fact of the matter is that,
| empirically, we can 't tell the difference by running
| them, but we can't tell the difference for a machine that
| halts in 2^(2^(2^256)) steps (or not at all) either, so
| that's not very interesting on it's own.)
|
| (As you note, we don't actually _know_ that (for example)
| a Turing machines looking for contradictions in ZFC is
| one of those particular machines; indeed I 'm not sure
| offhand if we actually know of _any_ specific example of
| such a machine. But that 's presumably not the issue
| here.)
| rssoconnor wrote:
| ZFC+!Con(ZFC) either wrongly proves that the machine that
| searches for an inconsistency in ZFC halts, or it wrongly
| proves that `while(true)` halts. Either way ZFC+!Con(ZFC)
| is wrong about something.
| graycat wrote:
| The Banach-Tarski paradox is fine with me: Not all subsets
| of the real line or R^n for the set of real numbers R and
| positive integer n are measurable. Yes, the usual example
| of a non-measurable set uses the axiom of choice. The sets
| in the Banach-Tarski paradox are not measurable -- okay.
|
| Of course the natural numbers can be put into 1-1
| correspondence with the rationals -- how to show that is
| the classic Cantor diagonal argument.
|
| At a tea before a seminar, I asked Max Zorn what Paul Cohen
| had just proved. Zorn didn't explain it and instead just
| loaned me his copy of Cohen's paper -- I lost it in a move!
| If Zorn wasn't strongly interested in Cohen's proof, then
| neither should I be.
|
| For any set of axioms, there will be statements we can
| neither prove nor disprove. Surprising, interesting, got
| it.
|
| Zermelo-Fraenkel set theory with the axiom of choice seem
| fine to me -- now back to the real work!
| hutzlibu wrote:
| "the claim that the set of natural numbers has the same
| size as that of the rational numbers"
|
| Where can I read more about that? Because, both are
| infinite, but there still should be more rational numbers,
| than natural numbers?
| jari_mustonen wrote:
| You can count rational numbers and everything countable
| is the size of infinity as natural numbers.
|
| Google "counting rational numbers" and "different sizes
| of infinity" to learn more.
| [deleted]
| TheCondor wrote:
| The proof is when you can create a bijective function
| between the sets then they have the same cardinality. The
| "zip" function can do this between integers and
| rationals.
| quisnam wrote:
| Many entry-level real analysis courses will cover
| cardinality after introducing sets and functions. There's
| also a short article on Wikipedia. [0]
|
| Your intuition about there being more rational numbers
| might be based on viewing the rationals as a proper
| superset of the natural numbers. You might similarly
| consider that there are more natural numbers than even
| natural numbers. However, by "renaming" every even
| number, and that shouldn't change how many there are, to
| half its value, we obtain the natural numbers. Formally,
| there exists a bijection between N and 2N, as between N
| and Q, and this is what mathematicians mean when they say
| that sets have the same size, or cardinality.
|
| [0]: https://en.wikipedia.org/wiki/Cardinality
| Someone wrote:
| To add, for hutzlibu and others like them: as soon as
| infinite sets (or sequences. See
| https://plus.maths.org/content/when-things-get-weird-
| infinit...) are involved math gets counter-intuitive.
|
| In this case, at most one of these two a priori quite
| reasonable statements can be true:
|
| - if set B is a strict superset of A, B is larger than A.
|
| - if you can map the times in A to the items in B in 1:1
| fashion, A and B have the same size.
|
| Giving up the first is deemed less problematic than
| giving up the second (probably because that means giving
| up comparing sizes of infinite sets at all, but I'm not
| familiar enough with that to be sure about that)
| thaumasiotes wrote:
| > 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).
|
| Isn't this a straightforward implication of nonstandard
| analysis?
| 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!
| dwohnitmok wrote:
| Indeed, that article is correct. More accurately I should be
| calling this position mathematical realism (although the
| lines between the two can get a bit blurry).
| IngoBlechschmid wrote:
| Indeed! And in fact, there are set theorists who argue that the
| traditional dream solution to the continuum hypothesis,
| adopting new axioms, is doomed to fail, and that we should
| instead embrace all models of set theory, all possible
| universes of mathematics.
|
| I tried to write an introduction to this "set-theoretic
| multiverse philosophy" which is accessible to the HN crowd
| here:
|
| https://iblech.gitlab.io/bb/multiverse.html
| 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 :).
| IshKebab wrote:
| Isn't that what an axiom _is_ though? Something you have to
| define as true? The way you 've described it, Platonism
| makes no sense. Maybe there's a missing part of the
| explanation...
| bonoboTP wrote:
| Platonists think you can define them wrong if you're
| careless.
|
| Imagine having a spreadsheet with the population of each
| country. I can go and enter 1 billion for the US, and the
| spreadsheet will happily recalculate all the cells about,
| say, GDP per capita etc. based on my incorrectly modified
| input. Clearly just because I've set the US population
| value in my spreadsheet to 1 billion the actual
| population did not change. There _is_ a real population
| count and if we don 't use the correct one then all our
| output will be garbage too: garbage in, garbage out.
|
| Mathematics is like this spreadsheet, its input are the
| axioms and the outputs are various interesting theorems.
| Feed in wrong axioms and you get wrong theorems.
|
| Platonists believe in a realm of ideas, that math talks
| about something real, just like the spreadsheet talks
| about real human populations. Even though within the
| spreadsheet everything remains fine and consistent if I
| tweak the US population. It just doesn't correspond any
| more to reality.
|
| I myself am not a mathematical Platonist, I more of an
| engineer/practical person and see math as a survival tool
| of a bunch of primates on a rock floating in space, not
| something that taps into anything mystical.
|
| But the Platonist worldview also seems coherent.
| dwohnitmok wrote:
| bonoboTP gives a nice high-level description, I give a
| slightly more ranty description here:
| https://news.ycombinator.com/item?id=27857728.
|
| Basically it seems like no matter what axioms you have,
| there's a bright line as to whether they accurately
| describe the natural numbers as we observe them in our
| universe, as that has physical ramifications. That bright
| line seems like "whether these axioms are true in our
| universe" and that seems to lend an objective standard by
| which we can measure our axioms.
| zajio1am wrote:
| > this entire article is implicitly assuming a Platonist
| philosophical foundation
|
| Is mathematical platonism still significant position between
| mathematicians? I thought it is outdated since Lobachevsky.
| dwohnitmok wrote:
| It is a significant position among mathematicans and
| logicians who study the foundations of mathematics.
|
| It is probably not how most non-foundations mathematicians
| think of mathematics (especially larger infinities).
| zenon wrote:
| In this survey, most "Philosophers of mathematics" endorsed
| Platonism: https://philpapers.org/surveys/results.pl?affil=Ta
| rget+facul...
| saithound wrote:
| edit: I did not pay enough attention, so what I wrote is
| wrong, see the comment below
|
| In the survey you linked, it looks like 45.7% of the
| surveyed philosophers of mathematics endorse Platonism.
| That's a lot, but not "most", by any measure.
| oehtXRwMkIs wrote:
| You're looking at the result for aesthetic value not
| Platonism.
|
| And by the measure of "most" meaning majority it would
| still be most.
| saithound wrote:
| Note that a view can be a majority position even if it is
| extremely outdated. This often happens when the outdated
| position is much easier to explain than the more nuanced
| alternatives. E.g. when surveyed, evangelical preachers often
| endorse Arianism, despite it being considered outdated since
| 325AD.
| dwohnitmok wrote:
| Even though I'm personally not much of a realist, I feel
| like it's worth explaining why it's so popular when
| studying foundations of mathematics, because outdated is
| selling it short and it's actually a fairly nuanced
| position. The basic question is are mathematicians
| fundamentally discovering mathematics (Platonism) or
| creating mathematics (non-Platonism)?
|
| The first step is that it seems like natural numbers are
| "real" and "tangible" in some sense. So for example, even
| though we can have modular arithmetic that would say maybe
| 2 + 5 = 2 under addition mod 5, it clearly feels
| "artificial" compared to 2 + 5 = 7. More concretely there
| seems to be some universal idea that seems to underly the
| fact that if you have three stones and add another stone
| you get four stones, or if you have three bottles and add
| another bottle you get four bottles. "three", "one", and
| "four" might not exist in the same as "bottle" or "stone"
| exist, but clearly they seem to exist and are "true" in
| some sense (it is clearly incorrect to say if you have
| three bottles and add another bottle you still have three
| bottles).
|
| Indeed, to even talk about mathematics it seems like you
| need some intuitive grasp of natural numbers that precedes
| mathematical axioms, or at least be able to understand at a
| deep level that if you have n things and you add another
| thing, then you have n + 1 things, and that any axioms that
| violate this are more "artificial" than axioms which don't
| violate this. More generally, if you have axioms that
| create results which violate the rules of "normal" natural
| numbers, it seems reasonable to say that those axioms are
| "artificial" and not "real" in some sense. And so one
| interpretation of mathematicians' jobs, at least when
| tightly scoped to natural numbers, is to find those axioms
| of the natural numbers that reflect our natural numbers
| really work in "our universe" as opposed to a hypothetical
| other universe. And that approach seems to presuppose that
| natural numbers exist, at least in our universe, in some
| objective some that we are "discovering" with our axioms,
| rather than "creating" ex nihilo.
|
| Indeed being able to say the term "normal natural numbers"
| and have even lay, non-mathematicians understand what that
| means (as opposed to "weird natural numbers" such as
| modular arithmetic) seems to suggest a certain
| objectiveness to the natural numbers.
|
| Or to put it another way, the abstract notion of "counting"
| seems to exist objectively and outside of our formal
| mathematics theories, and our formal theory of natural
| number is really trying to describe "counting" rather than
| create the notion of "counting" from scratch.
|
| Now if you accept that "counting" as an abstract idea
| exists in some sense that makes it possible to say either
| "yes that is an accurate description of counting" or "no
| that is not an accurate description of counting," then
| Godel's incompleteness theorems become quite interesting,
| namely that every useful theory of the natural numbers will
| have additional axioms that are independent of the ones
| already included in that theory. The non-realist looks at
| the incompleteness theorems and says, "Well yeah those new
| axioms just create different 'natural numbers' no biggie."
| The realist says, "That seems totally at odds with the fact
| that even though hypothetically you could have multiple
| notions of 'natural number,' there is only one notion of
| 'natural number' that holds true in our current universe
| and agrees with our similarly abstract notion of 'counting'
| and not a hypothetical other universe!"
|
| And if you accept that for the natural numbers... well a
| lot of things have ramifications for the natural numbers.
| One classic example, as mentioned elsewhere in this HN
| discussion, is the busy beaver function, a function whose
| input is the number of instructions in a given Turing
| machine and whose output is the maximum number of steps the
| machine could possibly take for any input before it must be
| non-terminating on that input (basically an end run around
| the halting problem).
|
| Any set of axioms (including ZFC) that includes the notion
| of arithmetic makes a statement on what it think a finite
| number of busy beaver values are (and only a finite number,
| again the halting problem prevents us from knowing more).
| And yet it seems like _every_ value of the busy beaver
| function has some objective truth value in our universe! I
| can just run the Turing machine and find out! And that
| seems like an objective yardstick that we can use to
| determine whether a given axiom system is "true" or not in
| our universe (granted it's not one of very much utility
| because you are waiting to see if a machine runs forever,
| but still something that seems to have obvious physical
| ramifications).
| zajio1am wrote:
| > The basic question is are mathematicians fundamentally
| discovering mathematics (Platonism) or creating
| mathematics (non-Platonism)?
|
| My main issue with mathematical platonics is not whether
| we are discovering or creating mathematic (which seems to
| me as semantically empty question), but whether existence
| of matematical object is an absolute property, or a
| property relative to a specific model/structure, and
| whether some models are metaphysically exceptional, or
| all models are metaphusically equal, only some are more
| convenient to use, so they are more worth studying.
|
| Consider some poly-platonist, who thinks that both
| natural-number-structure and non-standard-number
| structure (and both models of ZFC+CH and models of
| ZFC+non-CH) exist and are "real" and "tangible", and we
| discover internal relations in these structures as
| mathematical knowledge.
|
| > Or to put it another way, the abstract notion of
| "counting" seems to exist objectively and outside of our
| formal mathematics theories, and our formal theory of
| natural number is really trying to describe "counting"
| rather than create the notion of "counting" from scratch.
|
| I can say that we all have clear informal concept of what
| are natural numbers, just limitations of logic prevent us
| to formalize that.
|
| But i cannot see how such argument can be extended to set
| theory, where are plenty of arbitrary choices how to
| axiomatize that (e.g. ZFC vs. New Foundations).
| dwohnitmok wrote:
| To keep my Platonist hat on... Well if you accept that
| there is an objective truth to the natural numbers, the
| set theory axioms you choose will have ramifications for
| the natural numbers. (Elsewhere in these threads a
| commentator brings up that Not(Con(ZFC)) will tell you a
| Turing machine terminates when in our universe it
| doesn't)
|
| Put another way there will always be a purely
| arithmetical statement of the natural numbers that is
| independent of your set theory axioms. What is the truth
| value of that statement? If you think you have a clear
| and absolute conception of the natural numbers it seems
| like you should believe that an arithmetical statement
| has an objective truth value, and if that's true, then
| that seems like your objective benchmark to decide on how
| to accept a new axiom (does it prove or refute this true
| arithmetical statement?). There's your absoluteness.
| a1369209993 wrote:
| I thought it was outdated since Epimenides. It requires the
| axiom of the excluded middle, which is about as false as
| axioms can possibly be, on account of having concrete
| counterexamples. (eg "This proposition is false.")
| drdeca wrote:
| Intuitionistic logic, which is what you get from not
| assuming lem, still reaches a contradiction if you permit
| that as a valid proposition. So, doing away with LEM isn't
| sufficient. You could use a logic that explicitly has more
| values though.
| kkylin wrote:
| Those with a bit more math background may enjoy Cohen's own
| perspective on the discovery of forcing:
| https://projecteuclid.org/journals/rocky-mountain-journal-of...
|
| (Not technical as these things go, but helps to have a little
| knowledge of logic / set theory and some amount of "mathematical
| maturity.")
| zeven7 wrote:
| What online class should I take to learn more about this topic in
| particular?
| 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.
| panic wrote:
| _> Can there be an "infinitely large integer?"_
|
| Check out _p_ -adic numbers (https://math.uchicago.edu/~tghyde/
| Hyde%20--%20Introduction%2...), which are related to the
| two's-complement representation of signed integers. For
| example, in the 10-adic numbers, ...9999 + 1 = 0.
| 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}?
| [deleted]
| DangitBobby wrote:
| > then there would be a well-defined sorting of the reals
| between 0 and 1 based on their integer representation
|
| Why is that?
| alanbernstein wrote:
| Because the integers are ordered?
| DangitBobby wrote:
| I took well-defined to mean "if it exists, we know what
| it is." So really I guess what I want to know is why it
| matters that we can't actually calculate the mapping.
| 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.
| perfunctory wrote:
| > simply write it's trailing digits in reverse order
|
| so how do you map say pi/4? Which digit do you start with?
| phkahler wrote:
| That would be:
|
| ...61893587
|
| We start writing the digits right to left an pi/4 is about
| 0.78539816...
| perfunctory wrote:
| So you found a flaw in Cantor's diagonal argument?
|
| https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
| drdeca wrote:
| They are just saying "but what if we replace the set of
| integers with a larger set". I think they are also
| defining this larger set in a base 10 specific way.
|
| I think they basically mean the 10-adic numbers, which,
| unlike the p-adics for p a prime number, uh, I forget
| exactly what goes wrong, but I suspect it has like, zero
| divisors or something like that.
| 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?
| pwdisswordfish8 wrote:
| What does 1/3 map to?
| 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-16 23:02 UTC)