How many real numbers exist? New proof moves closer to an answer • Hacker News Board

Re: How many real numbers exist? New proof moves closer to an answer

#41

Post by glial » Thu, Jul 15, 2021, 4:36 PM UTC

jerf wrote: post #38

BoiledCabbage wrote: post #28

Earlier quoted context omitted.

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…

"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 pro…

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.

Re: How many real numbers exist? New proof moves closer to an answer

#42

Post by bmitc » Thu, Jul 15, 2021, 4:36 PM UTC

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.

Re: How many real numbers exist? New proof moves closer to an answer

#43

Post by gorgoiler » Thu, Jul 15, 2021, 4:37 PM UTC

jaywalk wrote: post #8

I'm not trying to be flippant, although it may come off that way: why does any of this matter?

We don’t know but looking into the past hints at the future.

Cantor, Hilbert and Gödel 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?

Re: How many real numbers exist? New proof moves closer to an answer

#44

Post by knodi123 » Thu, Jul 15, 2021, 4:39 PM UTC

thom wrote: post #27

bmitc wrote: post #20

Earlier quoted context omitted.

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 philoso…

Why does “the set containing the natural numbers and a sandwich” not have cardinality between the two?

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.

Re: How many real numbers exist? New proof moves closer to an answer

#45

Post by BoiledCabbage » Thu, Jul 15, 2021, 4:42 PM UTC

jerf wrote: post #38

BoiledCabbage wrote: post #28

Earlier quoted context omitted.

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…

"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 pro…

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.

Re: How many real numbers exist? New proof moves closer to an answer

#46

Post by omnicognate » Thu, Jul 15, 2021, 4:42 PM UTC

jostmey wrote: post #17

> "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 infini…

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.

Re: How many real numbers exist? New proof moves closer to an answer

#47

Post by bmitc » Thu, Jul 15, 2021, 4:42 PM UTC

thom wrote: post #27

bmitc wrote: post #20

Earlier quoted context omitted.

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 philoso…

Why does “the set containing the natural numbers and a sandwich” not have cardinality between the two?

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.

Re: How many real numbers exist? New proof moves closer to an answer

#48

Post by ivanbakel » Thu, Jul 15, 2021, 4:43 PM UTC

sillysaurusx wrote: post #39

helen___keller wrote: post #30

Earlier quoted context omitted.

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 p…

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 hist…

>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.

Re: How many real numbers exist? New proof moves closer to an answer

#49

Post by orbital223 » Thu, Jul 15, 2021, 4:44 PM UTC

thom wrote: post #27

bmitc wrote: post #20

Earlier quoted context omitted.

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 philoso…

Why does “the set containing the natural numbers and a sandwich” not have cardinality between the two?

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).

Re: How many real numbers exist? New proof moves closer to an answer

#50

Post by ceh123 » Thu, Jul 15, 2021, 4:44 PM UTC

arduinomancer wrote: post #2

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?

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