Live data from Hacker News

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

quantamagazine.org

291–300 of 359 posts

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

#291

Earlier quoted context omitted.

That would be: ...61893587 We start writing the digits right to left an pi/4 is about 0.78539816...

So you found a flaw in Cantor's diagonal argument? https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

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.

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

#292
post #204
post #193

Earlier quoted context omitted.

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…

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

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.

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

#293

Earlier quoted context omitted.

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…

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

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

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

#294
post #205

Earlier quoted context omitted.

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

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

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.

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

#295

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

> Stage 4 of the CDA outline can be critiqued on several grounds. The first is that if we have all the numbers in [0,1] in our table a priori, then using the diagonal process to create a number that is not in the original set does precisely that: It creates a number that is not in [0,1]. So why does the constructed anti-diagonal number seem to have a form that puts it within [0,1]? Could it be that ignoring the zero ahead of the decimal point is a bit sneaky?

You wrote all this and you don't seem to understand how proof by contradiction works?

> If, instead, we construct the anti-diagonal number by counting down the table by positions before each digit selection we find that any anti-diagonal number constructed (from the rectangle) is now within the set we have counted through, and therefore not outside the counted set. This Stretched Diagonal counterargument remains true as d→ ∞, irrespective of any ordering of number representations in the table.

This is not how anything works. You can't take a proof where they create an example that leads to contradictions and say, well, if you choose a different example, it doesn't lead to contradictions, so the proof doesn't work.

Your "proof" in Appendix B is also just gibberish from a mathematical perspective. The infinity and cardinalities aren't numbers - this isn't a mathematically rigorous statement: lim(n -> inf) log(n) = inf = aleph_0 - it's nonsense. What you're saying here is that as n increases without bound, 2^n also increases without bound. That doesn't prove anything about the cardinality of infinite sets.

Also, since you seem to accept that |R| is equivalent 2^|N|, it's also not hard to prove that 2^|S| > |S| for any S. 2^|S| 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.

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

#296

Earlier quoted context omitted.

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

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

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)

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

#297

Earlier quoted context omitted.

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.

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

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

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

#298

Earlier quoted context omitted.

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

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…

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.

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

#299

Earlier quoted context omitted.

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

Because the integers are ordered?

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.

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

#300

Earlier quoted context omitted.

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

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

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.

Post reply on HN