How many real numbers exist? New proof moves closer to an answer(quantamagazine.org)

501 pointsby theafh5 lat temu344 comments

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

https://www.quantamagazine.org/how-many-numbers-exist-infinity-proof-moves-math-closer-to-an-answer-20210715/

354 comments

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

rssoconnor5 lat temu

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

Someone5 lat temu

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

graycat5 lat temu

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!

rssoconnor5 lat temu

ZFC+¬Con(ZFC) proves "ZFC+¬Con(ZFC) is inconsistent".

So if were the case that ZFC+¬Con(ZFC) was sound then what it proves would be true, and "ZFC+¬Con(ZFC) is inconsistent" would be true. But that would mean ZFC+¬Con(ZFC) is actually inconsistent, and thus ZFC+¬Con(ZFC) would actually be unsound after all.

rssoconnor5 lat temu

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

a13692099935 lat temu

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

rssoconnor5 lat temu

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.

ummonk5 lat temu

Why is it wrong to say that the machine halts?

rssoconnor5 lat temu

ZFC+¬Con(ZFC) definitely proves that the machine that searches for an inconsistency in ZFC halts. That is a direct consequnce of ¬Con(ZFC). Keep in mind that by "proves" I'm only saying that there exists a logical deduction from the axioms. I'm not saying that it is true or false. Remember that logical deductions are "truth preserving", but we can only conclude that the conclusions are true if the axioms at the start are all true.

So again, we have a proof in some sketchy axiom system that the machine that searches for an inconsistency in ZFC halts. The question is whether that conclusion is a true statement or not, whether that machine actually does or does not halt. You can start up that program on your laptop while we consider it. Maybe it will halt during our discussion. I also want to point out that whether that conclusion is a true statement or not has no bearing on whether the deduction system was sound to begin with. Unsound systems can prove true statement, simply by accident rather than by design.

Case (1) that machine doesn't really halt, then ZFC+¬Con(ZFC) proves an untrue statement, and we thus the system is unsound.

Case (2) that machine does really halt. Then this particular conclusion wasn't untrue, but we have another problem. We can take the output of that machine, decode it, and we have a proof of an inconsistency in ZFC. Again this is just a deduction, it doesn't mean that math is wrong or the world ends. Just that the ZFC axiom system is so unsound that it is inconsistent, and it has some untrue axioms. Nevertheless we can use such a proof and derive a proof that ZFC prove `while(true)` halts, and in turn transform that into a proof in ZFC+¬Con(ZFC) that `while(true)` halts. And it is definitely the case that `while(true)` doesn't halt. So in this case we have found a different but still untrue statement that ZFC+¬Con(ZFC) proves. Our conclusion is the same: ZFC+¬Con(ZFC) is unsound.

So in either case `ZFC+¬Con(ZFC)` proves some machine halts that doesn't. I haven't concluded which of the two machines it is wrong about though I have my personal suspicions, but it is definitely wrong about one of them.

a13692099935 lat temu

> if the axioms at the start are all true.

Axioms are true by definition; that's what "axiom" means. (They might also be false, but (if and) only if your system is inconsistent.)

> Case (1) that machine doesn't really halt

This is not a state of affairs: all you know at any given time is that the machine hasn't halted yet (after some specific finite number of steps), or that it has aquired some termination-precluding invariant like a infinite loop (which you can detect only strictly less than all of).

rssoconnor5 lat temu

Axioms are most certainly not true by definition.

Regardless, the particular technical definition of truth I'm using is Tarski's definition of truth[1]. We don't have to agree whether Tarski's definition is "correct", and I'm happy to qualify my use of the word "truth" here, but I'm referring to a specific technical definition here.

[1] https://en.wikipedia.org/wiki/Semantic_theory_of_truth#Tarsk...

[deleted]5 lat temu

hutzlibu5 lat temu

"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?

quisnam5 lat temu

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

Someone5 lat temu

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)

gwf5 lat temu

  for a in range(1, Infinity):
      for b in range(a):
          print(a-b, "/" , b+1)

Will print out:

      1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, ...

Hence, we've just mapped all rationals (with duplicates) to a single linear list. Since any linear list can always be mapped to the naturals (1, 2, 3, ...), they have the same cardinality.

QED

TheCondor5 lat temu

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.

jari_mustonen5 lat temu

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]5 lat temu

tgflynn5 lat temu

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

kmill5 lat temu

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.

Tainnor5 lat temu

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

Isn't that just true for models of a first-order axiomatisation of the natural numbers? As far as I know, if you write down the Peano axioms in second order logic (as is required), you do get the natural numbers uniquely, and applying the successor function over and over again does exhaust all the natural numbers eventually.

The reason why you get non-standard models of arithmetic in first-order logic is the Löwenheim-Skolem theorem, but that isn't available for second-order logic.

kmill5 lat temu

Yeah, my understanding is that second-order arithmetic picks out the usual natural numbers, but it is a much stronger system since you can additionally quantify over subsets of naturals in your formulas.

The context of the comment is ZFC and its concept of the natural numbers (and what I had in mind in particular was what is its minimal infinite inductive set?). ZFC is a first-order theory, so "model" means model of a first-order theory.

> The reason why you get non-standard models of arithmetic in first-order logic is the Löwenheim-Skolem theorem

The ultrafilter construction I described is a way around the compactness theorem, in that it constructs new models semantically rather than syntactically. Ultrafilters are also a good way to prove the compactness theorem. But in any case, it's essentially the first half of the upwards Löwenheim-Skolem theorem before applying the downwards Löwenheim-Skolem theorem -- I think the significance of that theorem is that you can get models of any infinite cardinality you want, rather than just a strictly larger one. (Though I'm no logician.)

logicchains5 lat temu

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

kmill5 lat temu

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

logicchains5 lat temu

>suppose we define the reals through Dedekind cuts

You can't define the classical reals this way in a constructive setting, only the computable reals.

kmill5 lat temu

Ok, but I'm not sure what your point is. Throwing out only the axiom of choice (which is the difference between ZFC and ZF) does not make things constructive. If you're thinking of Diaconescu's theorem, it's that choice implies the law of the excluded middle, but the converse is certainly not true.

I was objecting to this:

> Generally a lot of counter-intuitive constructions disappear when eliminating the axiom of choice (such as [...] non-continuous functions).

R0b0t15 lat temu

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.

kmill5 lat temu

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

kmill5 lat temu

> 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

rssoconnor5 lat temu

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.

skissane5 lat temu

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

im3w1l5 lat temu

This sounds a little bit like an argument against systems with an infinite number of axioms to me. Or maybe it's fine but only under certain conditions?

hypersoar5 lat temu

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.

gooberwonder5 lat temu

45,000,000,001?

agalunar5 lat temu

Look around you!

munk-a5 lat temu

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?

dwohnitmok5 lat temu

> 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?"

l33t23285 lat temu

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?

rssoconnor5 lat temu

For this entire argument I will be operating under the assumption that ¬Con(ZFC) is independent of ZFC.

ZFC+¬Con(ZFC) proves "there EXISTS a natural number x such that x is an encoding of a proof in ZFC of 0=1".

Now suppose there is actually a numeral n, i.e. a specific written term written using symbols, e.g. (+,*,1), such that ZFC+¬Con(ZFC) proves that "n is an encoding of a proof in ZFC of 0=1". We can mechanically decode such a n and check if it is indeed a proof that that ZFC proves "0=1" or not.

There are two possibilities: (a) the check is successful and thus we have found proof of a contradiction in ZFC. But if ZFC is inconsistent, then it proves everything. In particular ZFC proves ¬Con(ZFC), which violates our assumption that ¬Con(ZFC) is independent of ZFC.

Alternatively (b) our check fails and n does not encode a proof in ZFC of 0=1. But that statement "n does not encode a proof in ZFC of 0=1" is a true Delta_0 statement, and we can prove by induction that ZFC proves every true Delta_0 statement. Thus we can prove that ZFC proves "n does not encode a proof 0=1", and hence ZFC+¬Con(ZFC) proves "n does not encode a proof 0=1". But now we have found a statement Q such that ZFC+¬Con(ZFC) proves both Q and also ¬Q. This means that ZFC+¬Con(ZFC) is inconsistent. But if ZFC+¬Con(ZFC) is inconsistent, by the deduction theorem, ZFC proves ¬¬Con(ZFC), or equivalently ZFC proves Con(ZFC). This contradicts our assumption that ¬Con(ZFC) is independent of ZFC (it also implies that ZFC is inconsistent).

Thus we are left with the conclusion that there is no such numeral n. However it is still the case that ZFC+¬Con(ZFC) proves "there EXISTS a natural number x such that x is an encoding of a proof in ZFC of 0=1", and the only way this can be the case is any such x is a "natural number" which has no numeral that denotes it.

chongli5 lat temu

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.

skybrian5 lat temu

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.

lupire5 lat temu

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

pavpanchekha5 lat temu

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.

ummonk5 lat temu

"But of course it's sound to assume many silly things. But why assume those things?"

This goes to the parent comment's point about real numbers though. It's silly to assume unwritable real numbers. Why do we do so?

dwohnitmok5 lat temu

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

ummonk5 lat temu

As you allude, it's rather ridiculous to make certain philosophical commitments but only apply them to natural numbers. I think ordinary finitism will do fine though, no need to go to ultrafinitism.

rssoconnor5 lat temu

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.

bryan05 lat temu

But isn’t this what the busy beaver numbers are? Numbers that we cannot write for arbitrary n but they do exist?

rssoconnor5 lat temu

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.

thaumasiotes5 lat temu

Do they exist? I thought there was an independence theorem for the specific values of almost all busy beaver numbers.

rssoconnor5 lat temu

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.

thaumasiotes5 lat temu

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

rssoconnor5 lat temu

Yes, what you are saying is indeed the case in the sense that if BB(30)=n for some particular numeral n is independent of whatever proof system we are focusing on, for the sake of argument let's say ZFC, (though 30 feels a a bit on the low side for ZFC), then we can consistently add BB(30)=n or BB(30)≠n as axioms to the system, the same way to can for any other independent statement. And there will be arbitrary large values of n that are independent, so we could add BB(30)=n or we could add BB(30)=m or so forth for any numerals i so long as BB(30)=i is independent of ZFC (or whatever axiom system we are considering).

But! that does not mean that all these systems are sound, for if you add the incorrect value as an axiom, specifically if you add anything but the smallest value 'm' such that BB(30)=m is independent of ZFC, then you are in a similar situation to adding ¬Con(ZFC) whereby you only have non-standard models.

They way this works is that, suppose BB(30)=m for some particular m is independent of ZFC, but BB(30) is not actually equal to m. What we will find is that there is some Turing machine M and some non-standard natural number q such that, while M doesn't actually halt in reality, according to some non-standard model it does halt in 'q' number of steps, and, in this model, when it does halt, it leaves 'm' 1's on the output tape.

That said, your comment did push me towards the limits of my comfort zone, so it might be helpful to double check what I'm saying. I don't see how it could be any other way though.

rssoconnor5 lat temu

To elaborate a little further on why BB(30) does have a true value.

If BB(30) truly equals some particular numeral m, then there actually does exist a Turing machine M that has no more than 30 states and does halt with m 1's on its tape. Not only does this machine really exist, but the fact that it halts in this state is true Delta_0 statement, and thus it is trivially provable, you don't even need induction. It is provable in Robinson Arithmetic, it is provable in Peano Arithmetic, and it is provable in ZFC. Thus we have that RA proves "BB(30) ≥ m" and PA proves "BB(30) ≥ m" and ZFC proves "BB(30) ≥ m", etc.

By transitivity each of these systems also proves "BB(30) ≥ m₀" for every numeral m₀ less than m. But if m₁ is a numeral larger than m, it is no longer the case that RA proves "BB(30) ≥ m₁" and PA doesn't prove "BB(30) ≥ m₁" and (assuming ZFC is sound) ZFC doesn't prove "BB(30) ≥ m₁"

Thus we "can tell" what the true value of BB(30) is because it is the greatest value in which RA (or PA or (presumably) ZFC) proves "BB(30) ≥ m" for the numeral m denoting that value. Equivalently the value of BB(30) is the least value m for which RA, PA, or any other sound system, does not prove "BB(30) ≠ m".

We "can tell" this value even if we might not be able prove it in PA, or ZFC, or "ZFC + there exists a Mahlo cardinal". Indeed each different proof system likely can extend the range of BB values that are provable.

If you add an axiom "BB(30) = m" for some particular numeral m as an axiom to ZFC and it is the wrong value of m, you will either get an inconsistent system if "m" is too small, or you will get an unsound system if "m" is too large. In case "m" is to large, the unsound system will wrongly prove that certain Turing machines halt that do not actually halt. Specifically it will falsely prove that the Turing machine that searches for (a Turing machine with no more than 30 states that halts with "m" 1's on it tape) will halt, when such a machine does not actually halt.

bryan05 lat temu

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 (??)

thaumasiotes5 lat temu

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

bryan05 lat temu

Yes I was referring to calculating BB(n) for arbitrary n. But certainly these numbers exist even if they’re independent of ZFC (?)

ummonk5 lat temu

Why is that wrong? If you actually ran a Turing machine for a number of steps that is beyond any number that can be written, maybe it would halt.

rssoconnor5 lat temu

By number that cannot be written, I don't mean cannot be written due to lack of paper; I mean a value that there is no notation for.

You cannot run a machine for "that many" steps because such a value is unreachable by steps. Non-standard models have a set of values that begin with a copy of the actual natural numbers, followed by some ordered set of copies of the integers in the sense that any values "beyond" the initial natural numbers have an infinite number of successors and an infinite number of predecessors, like integers do. By counting in steps it is not possible to move from a value in the initial natural number fragment to one of these non-standard values, because there are an infinite number of values in between them that you would be required to step through.

ummonk5 lat temu

> By number that cannot be written, I don't mean cannot be written due to lack of paper; I mean a value that there is no notation for.

That's true for most real numbers in ordinary mathematics too, so if you accept the existence of those numbers, no reason why you can't do the same for the natural numbers in these non-standard models.

> You cannot run a machine for "that many" steps because such a value is unreachable by steps. Non-standard models have a set of values that begin with a copy of the actual natural numbers, followed by some ordered set of copies of the integers in the sense that any values "beyond" the initial natural numbers have an infinite number of successors and an infinite number of predecessors, like integers do. By counting in steps it is not possible to move from a value in the initial natural number fragment to one of these non-standard values, because there are an infinite number of values in between them that you would be required to step through.

Yes...

dogecoinbase5 lat temu

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

dwohnitmok5 lat temu

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.

pavpanchekha5 lat temu

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.

thaumasiotes5 lat temu

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

ummonk5 lat temu

'because it asserts the existence of natural numbers that have no "written form"'

I mean, mainstream axiomatic systems assert the existence of real numbers that have no written form (after all, only countably many entities can have a written form), so how is this any different?

BoiledCabbage5 lat temu

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.

jerf5 lat temu

"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?

avz5 lat temu

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

jerf5 lat temu

Thank you. I accept this.

BoiledCabbage5 lat temu

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.

finnh5 lat temu

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.

dwohnitmok5 lat temu

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.

CamperBob25 lat temu

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.

dwohnitmok5 lat temu

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

[deleted]5 lat temu

glial5 lat temu

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.

jerf5 lat temu

Yes, thank you, that was a typo.

scotty795 lat temu

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

mdoms5 lat temu

This is covered in the article.

Layke11235 lat temu

HotHotLava5 lat temu

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.

cevi5 lat temu

This assumption is correct - the quanta article left out quite a bit of detail about how forcing actually works, while trying to give some hint of the philosophy behind it.

As it turns out, you can still apply the forcing technique even if you start with the whole set of all real numbers. What happens in this case is a bit surprising: since there's no legitimate way to add new real numbers that weren't there previously, the forcing procedure cheats by pretending that real numbers have nonstandardly long decimal expansions.

To make the way it cheats a bit more concrete, we start by first imagining that there are "nonstandard integers" n which are bigger than all of the "true" integers from our starting model. Once we assume that these integers exist, we have to commit ourselves to providing answers to questions like, "what is the nth digit of pi?", "what is the n+1th digit of pi?", and so on in a consistent way. By answering these questions, we embed all of the original real numbers from our starting universe into the new universe. But the point is that now that we have all of these extra digits to play with, all of the original real numbers only fill up a tiny subset of the potential "real" numbers in the new universe, and we can happily go back to forcing new ones in.

Of course, adding nonstandard integers to our universe is quite a violent change, so we also have to worry about whether we've accidentally screwed up the way that the ordinals work in the process (for instance, the "first infinite ordinal" in the new universe now contains all of the nonstandard integers we added), and we need to worry about this again when we get around to forcing the new reals in. So a whole lot of technical details need to be ironed out carefully, using a few clever combinatorial arguments, to make the whole charade come together.

All of this cheating happens under the hood in a way that is not obvious at all when you first go through the technical details of the forcing construction. I only learned about the full perspective from Joel David Hamkins's "naturalistic account of forcing".

cwzwarich5 lat temu

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.

myhf5 lat temu

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

intuitionist5 lat temu

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.

pavpanchekha5 lat temu

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.

ProfHewitt5 lat temu

Note that forcing and the independence results are only for 1st-order logic.

They do not work for theories that characterize mathematical

abstractions such as the Ordinals and Natural Numbers up to a

unique isomorphism.

See the following video:

https://www.youtube.com/watch?v=AJP1VL7shiI

scrubs5 lat temu

@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!

pdonis5 lat temu

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.

01GOD5 lat temu

dwohnitmok5 lat temu

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.

IngoBlechschmid5 lat temu

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

ummonk5 lat temu

Yeah, I tend to lean towards the side of realism (and constructivism), explicitly for the reasons exemplified by your rock / bottle analogy downthread.

But even from that perspective, I found the article's discussion of "true" / "false" rather weird, since it seemed to be taking certain positions (namely regarding the continuum hypothesis) for granted even though those positions don't seem to be grounded in any material fact.

It's as if people are conjuring up imaginary fictional entities and then asserting certain attributes about those entities as obvious and objective.

red_trumpet5 lat temu

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!

dwohnitmok5 lat temu

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

zajio1am5 lat temu

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

saithound5 lat temu

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.

dwohnitmok5 lat temu

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

zajio1am5 lat temu

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

dwohnitmok5 lat temu

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.

zenon5 lat temu

In this survey, most "Philosophers of mathematics" endorsed Platonism: https://philpapers.org/surveys/results.pl?affil=Target+facul...

saithound5 lat temu

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.

oehtXRwMkIs5 lat temu

You're looking at the result for aesthetic value not Platonism.

And by the measure of "most" meaning majority it would still be most.

dwohnitmok5 lat temu

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

a13692099935 lat temu

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

drdeca5 lat temu

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.

kachnuv_ocasek5 lat temu

Thanks for the clarification. I was indeed a bit confused by some of the implicit assumptions as an intuitionist myself.

goldenkey5 lat temu

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.

dwohnitmok5 lat temu

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

IshKebab5 lat temu

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

bonoboTP5 lat temu

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.

dwohnitmok5 lat temu

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.

joe_the_user5 lat temu

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.

kibwen5 lat temu

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

daxfohl5 lat temu

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.

ttctciyf5 lat temu

This sounds a little like Chaitin's constant Omega (Ω), 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 Ω 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

Rinum5 lat temu

I think you'll like this - https://youtu.be/HeQX2HjkcNo

sharpener5 lat temu

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.

myWindoonn5 lat temu

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.

ProfHewitt5 lat temu

Lawvere's work is elegant! However, Lawvere missed the

crucial importance of Russell's orders on propositions in

blocking the construction of monster propositions using

recursive definitions. Orders on propositions block

construction of I'mFalse, I'mNotSelfapplicable,

I'mUnprovable, and MyTheoremsAreEnumerable.

See the following video for more information:

https://www.youtube.com/watch?v=AJP1VL7shiI

for the following article:

https://papers.ssrn.com/abstract=3603021

sharpener5 lat temu

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?

sharpener5 lat temu

I'm not seeing this yet. Perhaps you could explain it to me in plain terms.

myWindoonn5 lat temu

Pick any Cartesian closed category. Says Lawvere:

If there exists t : Y -> Y such that t;y != y for all y : 1 -> Y then for no A does there exist a surjection A -> (A -> Y).

(He actually says something much stronger.) Note that the first half of this is saying "if there exists t such that t has no fixed points..."

Let our category be Set, the category of sets and functions; it is well-known to be Cartesian closed. Let A be the set of natural numbers and let Y be the Booleans. Then Lawvere is saying that there is no surjection N -> (N -> 2), and thus definitely no bijection, because there is a function 2 -> 2 with no fixed points: the negation function which swaps true and false has no fixed point.

It does not get much plainer without actually reading Lawvere and/or Yanofsky directly, sorry. I hope that this helps explain how inescapable this sort of theorem is.

candybar5 lat temu

> Stage 4 of the CDA outline can be critiqued on several grounds. The ﬁrst 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.

curtisf5 lat temu

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 ℕ → 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 ℕ and {0, 1}**.

Proof: Suppose for contradiction that there is a bijection f: ℕ → {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 ℕ 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: ℕ ↔ {0,1}**) must be false.

Q.E.D.: There does not exist a bijection between ℕ and {0, 1}**.

----

The linked paper claims that the above proof would work on a bijection of the form ℕ ↔ [ℕ] or ℕ ↔ [ℚ] (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 [ℕ] 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 [ℕ].

For a more involved example, consider an encoding of [ℕℕ] 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 ℝ, or with (0, 1). This falls out from the Cauchy-sequence definition of ℝ. 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.

sharpener5 lat temu

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

myWindoonn5 lat temu

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.

drdeca5 lat temu

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

sharpener5 lat temu

> Theorem: There is no bijection between ℕ 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.

myWindoonn5 lat temu

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. Escardó has an article on this: http://math.andrej.com/2007/09/28/seemingly-impossible-funct...

Please read Lawvere's article. Thanks.

sharpener5 lat temu

For the sake of HN archival history...

The executive summary of my paper is that provably there are fatal inconsistencies in Cantor's Diagonal Argument (CDA).

They take a few forms:

(1) Application of basic classical analysis tools reveals that the contradiction sought by CDA does not hold if those tools are used.

E.g. Assume we have the table of all unique infinite length binary strings {0,1}* (where * represents the supremum of the natural numbers, e.g. the first ordinal infinity in set theoretic language).

Assume that those strings represent the fractional part of binary represetations of real numbers in the continuum interval [0,1].

Assume they start big endian, so for some string s, the value v(k) of some bit at the k-th position of s is v(k) = s(k)/2^k, for k = 1,2,3....

Let f: \N x \N -> {0,1}, be a function that accesses bits in the binary strings viewed as a matrix M(i,j).

Create the binary number z as z(k) = 1 - f(k,k).

Now deploy basic analysis.

Note that k -> \infty implies v(k) -> 0.

So no matter what the value of z(k) is, k -> \infty implies |z - f(k)| -> 0, for some suitable k.

Let f be the limit of f(k) as k -> \infty.

Then in the limit k -> \infty the number z = f, and (for all practical purposes) the diagonal z coincides with a binary number in the table f within a countable limit.

This is independent of any ordering of the table rows of M(i,j).

So the contradiction of CDA does not hold convincingly when these basic tools of analysis are used.

(2) Corollary: Platonists would need to prove that infinite digit existence somehow invalidates basic analysis in order to cling to CDA. Moreover, they would have to prove that "higher" infinite digit existence does not invalidate useful concepts of numbers and limits at all.

As far as I know, no one has done that yet.

(3) Using the same basic tools of analysis, key arguments about powersets having cardinalities that are "higher" infinities do not go through, and moreover aspects of "higher" cardinal arithmetic, as presently defined, can be shown to be self-inconsistent.

Therefore: A) When the tools of basic classical analysis are so useful, why would any pragmatic user of mathematics throw them out at some key point within CDA (and CDA only) to endorse a notion of "uncountability" that creates manifold inconsistencies further on?

B) Why should any pragmatic mathematician allow the extra unconvincing machinery of higher infinities into maths?

In the absence of decent answers to those questions I am compelled towards the recommendation is that mathematicians should throw CDA out.

Edit: formatting.

myWindoonn5 lat temu

You're presupposing the topology of the Cantor space; how do you know that Cantor space {0,1}* corresponds to real numbers? You're also supposing that an infinite matrix is actually some sort of infinite-plus-one matrix in a handwaved fashion. Limits don't work in the discrete setting; you must invent and justify them.

Pick a k. Note that z(k) is not in rows 0 through k of M, by finite diagonalization. Now, suppose that you try taking k to "infinity" again. z(k) keeps up at every step, by primitive recursion, and M is always missing at least one entry. By what justification do you suppose that M somehow outruns v at "infinity"?

I need you to remember how to be a human for just a moment. Reread your words, "the recommendation is that mathematicians should ..." and consider the precise moral justification by which you make this recommendation. Note that your attempt at the passive voice failed to shift the moral burden, because the given proof is unconvincing (and quite unrigorous). Please consider a dram of humility and give Yanofsky's paper a serious read. It's good.

Also, if you want a better idea of such an infinite Boolean matrix, consider reading about Chu spaces: http://chu.stanford.edu/

civilized5 lat temu

Your argument has some gaps. Here are the two basic problems:

1. f(k) is not defined in your notation, only f(k,k) is. My guess is that f(k) is supposed to represent the real number defined by the k^th row of the table.

2. Whatever f(k) is supposed to be in your notation, you have not shown that it has a limit as k approaches infinity, let alone that z = f.

In fact, f(k) cannot possibly have a limit f. If it did, then by the definition of limit, all but finitely many numbers in [0,1] would have to be within epsilon of f, for any epsilon > 0. We could then show that all but finitely many numbers in [0,1] have the exact same first trillion digits of their decimal expansion. Obviously this is absurd.

This is what always happens with Cantor diagonal argument critiques. The critique invariably ignores the logically rigorous argument of the CDA itself, sets up its own new version or extension of the diagonalization construction, and then makes whatever false assumptions are needed for the new construction reach a conclusion contrary to the CDA.

It's like walking into a sturdy bridge with a few pebbles in your pocket, arranging the pebbles into a flimsy tower, knocking the tower over and declaring that you've destroyed the bridge.

ncmncm5 lat temu

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

90minuteAPI5 lat temu

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.

ncmncm5 lat temu

The mathematics of infinities are nothing if not counterintuitive.

rkagerer5 lat temu

"Does this skirt make my butt look too big?"

"Too big for what?"

Yeah let me know how that works out.

philipswood5 lat temu

Yes, the call for more experimentation to keep theorists honest.

whoaisme5 lat temu

Ken M is that you?

123pie1235 lat temu

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

svachalek5 lat temu

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.

phkahler5 lat temu

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.

panic5 lat temu

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

plus5 lat temu

> 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]5 lat temu

DangitBobby5 lat temu

> then there would be a well-defined sorting of the reals between 0 and 1 based on their integer representation

Why is that?

alanbernstein5 lat temu

Because the integers are ordered?

DangitBobby5 lat temu

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.

plus5 lat temu

Any finite number of randomly chosen integers can be sorted in increasing order. The quantities invented for the proposed mapping do not share this property, and thus cannot possibly be integers.

DangitBobby5 lat temu

Again, you don't know how to compute the function which creates the mapping, so you don't know the results, so you don't know how to sort the results. I don't follow the logic which claims your inability to compute something is now an intrinsic property to the resulting set. I do understand that sortability is a property intrinsic to integers.

alanbernstein5 lat temu

I think the point is that the example with irrational numbers guarantees that this mapping/sort can't be done.

red_trumpet5 lat temu

> 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 -π/2 < x < π/2, and then scale and shift the interval to 0 < x < 1.

plus5 lat temu

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.

gowld5 lat temu

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

perfunctory5 lat temu

> simply write it's trailing digits in reverse order

so how do you map say pi/4? Which digit do you start with?

phkahler5 lat temu

That would be:

...61893587

We start writing the digits right to left an pi/4 is about 0.78539816...

perfunctory5 lat temu

So you found a flaw in Cantor's diagonal argument?

https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

drdeca5 lat temu

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.

question0005 lat temu

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

victorbojica5 lat temu

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

...

bonzini5 lat temu

You can't, this is Cantor's diagonal counterexample.

pwdisswordfish85 lat temu

What does ⅓ map to?

mmmBacon5 lat temu

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.

Sharlin5 lat temu

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

orangecat5 lat temu

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

keymone5 lat temu

unrelated: how do we know there are no alephs between 0 and 1?

elcomet5 lat temu

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.

Sharlin5 lat temu

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.

TameAntelope5 lat temu

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.

twelfthnight5 lat temu

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

TameAntelope5 lat temu

I guess I was focusing on the word "easy", heh.

mmmBacon5 lat temu

You do this in sophomore level Real Analysis. So as far as pure math goes, easy.

TameAntelope5 lat temu

> sophomore level Real Analysis

Hmm?

rpearl5 lat temu

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.

ummonk5 lat temu

I was homeschooled, so I was shown this in middle school hah. I think math camps and the like also tend to teach it before college.

TameAntelope5 lat temu

Which school?

rpearl5 lat temu

Carnegie Mellon

doctoboggan5 lat temu

Watch the video, its actually quite easy to follow.

bmitc5 lat temu

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.

bmitc5 lat temu

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

ruggeri5 lat temu

I should finish reading the linked article. But I have a quick initial question.

Proofs in ZFC can be enumerated by a machine. In theory, we could devise a machine that (1) will certainly eventually halt iff ZFC is inconsistent (proves two contradictory statements), or (2) will never halt iff ZFC is consistent.

(Caveats: naturally, if ZFC is consistent, we'll never learn whether we should just keep waiting for the machine to find a contradiction. And our machine will require unbounded storage space.)

Can we build a corresponding device that would have different behaviors depending on whether the continuum hypothesis is "true" (whatever that means)? I suppose the computational model would be Turing machine as above.

kkylin5 lat temu

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

devit5 lat temu

In addition to adding the continuum axiom or its negation, there's also the approach of restricting oneself to computable sets and thus only having countable infinities.

ProfHewitt5 lat temu

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.

ProfHewitt5 lat temu

PS. There are no ordinals of intermediate cardinality between ω<sub>0</sub> and ω<sub>1</sub>.

renanbg5 lat temu

I find this very much fascinating, although I can't understand it. I hope I can, eventually, fully appreciate "higher math" questioning like this one, and would be really grateful if someone could point me what to study, as an "amateur mathematician" with only background on engineering calculus.

btilly5 lat temu

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.

scapp5 lat temu

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^ω, 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

btilly5 lat temu

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.

pdonis5 lat temu

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

papandada5 lat temu

Every integer can be written down with a finite number of symbols....right?

LudwigNagasena5 lat temu

What’s the problem with it being “artificial”? Is your problem purely linguistic? You just dislike the word “exists” being used in this context?

btilly5 lat temu

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?

pdonis5 lat temu

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.

ummonk5 lat temu

You're assuming you've been able to construct all those real numbers in the first place, using arbitrary imaginary cauchy sequences (i.e. cauchy sequences that cannot be constructed but rather rely on some magic axiom of infinite choice).

papandada5 lat temu

Such an interesting criticism. All of this thread has been enlightening. I sat through traditional undergrad analysis and set theory classes and never imagined there was another option, other than things bothering me for decades since in my subconscious.

btilly5 lat temu

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 Gödel's incompleteness theorem.

LudwigNagasena5 lat temu

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.

[deleted]5 lat temu

ummonk5 lat temu

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

Huh? It's trivial to create an injection R -> N, by encoding each computational algorithm - whether valid or invalid - as a number.

reggieband5 lat temu

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.

ummonk5 lat temu

Constructivism (including the kind that precludes uncountable infinities) is not inherently more shocking than classical mathematics. It only seems surprising because classical mathematics has become the default formalism.

chmod7755 lat temu

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

ummonk5 lat temu

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

I can give you a function that will never output the same natural number on any two real numbers unless those two real numbers are equal.

My function outputs the binary value of the Unicode encoding of the description of the number that you provide.

Go ahead, name me a pair of real numbers for which my rule doesn't work.

chmod7755 lat temu

The thread already went down that line of argument, you can take this comment as an response to yours: https://news.ycombinator.com/item?id=27851171

btilly5 lat temu

And, as I pointed out there, that comment remains wrong.

See https://news.ycombinator.com/item?id=27859355 for why.

ummonk5 lat temu

Upthread you said: "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."

That is false - you're actually unable to name these numbers for which the rule doesn't work. Instead you're just insisting we accept on faith the existence of these unnamable numbers.

myWindoonn5 lat temu

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.

skoodge5 lat temu

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.

pdonis5 lat temu

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

skoodge5 lat temu

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.

chmod7755 lat temu

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

skoodge5 lat temu

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.

chmod7755 lat temu

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

skoodge5 lat temu

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

chmod7755 lat temu

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.

skoodge5 lat temu

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.

chmod7755 lat temu

> 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

Consider the canonical form of Pi. You can't express it accurately in English, but you can have a distance of Pi length in the physical world, so you could express Pi by that distance.

Now we can refer to Pi in English because it is tied to a concept which we can describe and because we can assign a name to it.

If I picked two arbitrary points in the physical realm, then due to the distribution of real numbers there's a good chance you wouldn't be able to express the distance accurately in a language that uses a finite set of symbols/sounds to express numbers.

I'm convinced such 'numbers' exist however, Pi exists after all, and it happens to be just one we assigned a name to because it is of note.

blacklion5 lat temu

Numbers exist only in our heads. They are results of formal symbol manipulations.

What does "to exist" mean for number which can not be written down as some formula (in broad sense of this word) in formal language?

btilly5 lat temu

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.

ummonk5 lat temu

If you're claiming the existence of entities that you are unable to identify or express, you're veering into religion and faith.

papandada5 lat temu

I have found my people. Thank you.

klysm5 lat temu

Does constructivism rule out uncountability because induction is always indexable?

btilly5 lat temu

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.

tromp5 lat temu

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

js85 lat temu

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?

pachico5 lat temu

I thought this was already solved decades ago by Mr. Show:

https://m.youtube.com/watch?v=RkP_OGDCLY0

Sorry, I couldn't resist.

arduinomancer5 lat temu

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?

miloignis5 lat temu

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!

arduinomancer5 lat temu

Makes sense, thanks

ceh1235 lat temu

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

pavpanchekha5 lat temu

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.

tpetrina5 lat temu

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.

pfortuny5 lat temu

Then you cannot guarantee that when you change the first digit of the second number, what you get is not the first number.

erdos4d5 lat temu

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.

xvilka5 lat temu

There is a good video about that on Numberfile[1]

[1] https://www.youtube.com/watch?v=5TkIe60y2GI

MiddleEndian5 lat temu

https://www.smbc-comics.com/comic/the-largest-number-2

Tangentially related comic

dwater5 lat temu

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.

zeven75 lat temu

What online class should I take to learn more about this topic in particular?

privatdozent5 lat temu

Another great piece from Quanta. Such an important institution

chasing5 lat temu

There are exactly 1,837 real numbers and anyone who tells you any different is just trying to sell you something.

jaywalk5 lat temu

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

helen___keller5 lat temu

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

sillysaurusx5 lat temu

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

svat5 lat temu

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

sillysaurusx5 lat temu

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.

schoen5 lat temu

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 2¹⁰⁰ 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.)

kevinventullo5 lat temu

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_conjecture

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___keller5 lat temu

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.

Sharlin5 lat temu

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.

acchow5 lat temu

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

HelloNurse5 lat temu

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.

bordercases5 lat temu

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.

ivanbakel5 lat temu

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

sillysaurusx5 lat temu

https://math.stackexchange.com/questions/514/conjectures-tha... was excellent. Thank you.

> 𝑛^17+9 and (𝑛+1)^17+9 are relatively prime

> The first counterexample is 𝑛=8424432925592889329288197322308900672459420460792433

I think this helped me appreciate the difficulty of being satisfied with the Collatz conjecture.

helen___keller5 lat temu

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.

Ivoirians5 lat temu

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.

schoen5 lat temu

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?

Ivoirians5 lat temu

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

sillysaurusx5 lat temu

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

Ivoirians5 lat temu

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

kd0amg5 lat temu

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

hvocode5 lat temu

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.

myWindoonn5 lat temu

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.

big_curses5 lat temu

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.

Sharlin5 lat temu

> 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

stonemetal125 lat temu

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.

thehappypm5 lat temu

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.

quickthrower25 lat temu

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!

gorgoiler5 lat temu

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?

lupire5 lat temu

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.

mmastrac5 lat temu

I'd love to see James Burke tackle this line.

sillysaurusx5 lat temu

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_gibbins5 lat temu

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.

fighterpilot5 lat temu

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

l33t23285 lat temu

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.

hawkice5 lat temu

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?

bmitc5 lat temu

> I see no reason to suspect this is the case

Isn’t history enough reason?

erichahn5 lat temu

No history actually tells you that only 1% of produced maths is useful. You only see the good stuff not the ugly stuff.

bmitc5 lat temu

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.

l33t23285 lat temu

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.

jonnycomputer5 lat temu

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.

dfdz5 lat temu

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_5 lat temu

bmitc5 lat temu

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.

thom5 lat temu

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

magicalist5 lat temu

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.

bmitc5 lat temu

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.

lupire5 lat temu

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.

thom5 lat temu

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?

drdeca5 lat temu

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

scapp5 lat temu

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.

bmitc5 lat temu

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

dabitude5 lat temu

Are real numbers uniformly spaced? Or are there clusters?

hawkice5 lat temu

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.

orbital2235 lat temu

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

helen___keller5 lat temu

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.

knodi1235 lat temu

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.

fighterpilot5 lat temu

For the same reason that integers have the same cardinality as only odd numbers. You can create a 1:1 mapping between them.

bmitc5 lat temu

Not just one-to-one (injective) but also onto (surjective). :)

Y_Y5 lat temu

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.

ssivark5 lat temu

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?! :-)

drdeca5 lat temu

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 ?

pjfin1235 lat temu

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.

lupire5 lat temu

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

Hamlet425 lat temu

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

db48x5 lat temu

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.

l33t23285 lat temu

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

pantulis5 lat temu

Because this advances math. Same could be said for lambda-calculus and yet here we are with FP.

[deleted]5 lat temu

shockeychap5 lat temu

Why spend time on it? To borrow from George Mallory: Because it’s there.

soperj5 lat temu

This is kind of the equivalent of asking why does your life matter?

01GOD5 lat temu

question0005 lat temu

(2)

morpheos1375 lat temu

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.

kmeisthax5 lat temu

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.

Rerarom5 lat temu

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

croes5 lat temu

You are confusing numbers with natural numbers.

"A number is a mathematical object used to count, measure, and label."

morpheos1375 lat temu

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.

HelloNurse5 lat temu

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.

TuringTest5 lat temu

> 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

HelloNurse5 lat temu

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.

TuringTest5 lat temu

No numbers exist, they are abstraction on human-created procedures. Even naturals, which are an abstraction over pointing to things and counting.

gowld5 lat temu

They are "more existent" ("less fictional"), not "more in cardinality".

TuringTest5 lat temu

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.

TuringTest5 lat temu

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.

croes5 lat temu

I don't need to, I can measure and label with real numbers. That's enough for being a number.

gowld5 lat temu

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.

morpheos1375 lat temu

technically you will use an infintesimally small real number approaching 0%...

Decker875 lat temu

Honest question, what is the usefulness of proving such an obvious thing?

pelorat5 lat temu

The existence of addition implies that the answer is infinity. Too simple an explanation for mathematicians obviously.

Sharlin5 lat temu

The whole point of the article is that we don't know which infinity it is.

throwawayboise5 lat temu

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.

howderek5 lat temu

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

jostmey5 lat temu

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

ceh1235 lat temu

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

omnicognate5 lat temu

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.

jmgao5 lat temu

gotostatement5 lat temu

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

mikepurvis5 lat temu

Veritasium did a really good video on this recently, based around Hilbert's Hotel:

https://www.youtube.com/watch?v=OxGsU8oIWjY

chaoticmass5 lat temu

https://www.youtube.com/watch?v=SrU9YDoXE88

I really like how VSauce covers this topic as well.

dexwiz5 lat temu

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.

zeugmasyllepsis5 lat temu

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

drdeca5 lat temu

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

IncRnd5 lat temu

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.

gowld5 lat temu

No, it doesn't. Then have the same number, as can be plainly seen by lining them up and counting the elements in order.