[whatshisface]

"So, in Borel’s view, most reals, with probability one, are mathematical fantasies, because there is no way to specify them uniquely." (Paraphrasing, because there are only countably many possible math papers that might describe a number.)

I think Borel has confused names with things. The fact that we can only write down only countably many expressions for numbers doesn't mean that there are numbers that we may never write expressions for - only that in a single symbolic system we can't have expressions for all of them at once.

Besides, if you confuse extant with useful you might end up believing that some random large integers aren't "there!"

[xyzzyz]

only that in a single symbolic system we can't have expressions for all of them at once.

I don't think that's true. There are only countably many different symbolic systems[1], and as we can only express countably many numbers in each, we don't leave the realm of countable.

[1] - A "symbolic system" must at least come with a procedure to tell whether a sequence is a part of it, and, unless you disbelieve the Church-Turing thesis, there are only countably many procedures.

[j2kun]

Doesn't this (and by extension, Curch-Turing) rely on the assumption that the universe is discrete? Provided it were not, and one were able to harness infinite precision, one could presumably make a new symbolic system based on it.

Not saying I believe it, just teasing out assumptions. If one is arguing whether the universe is continuous and using the Church-Turing thesis as justification for something, there's a danger of circular reasoning.

Also, I think the parent commenter is getting more at naming vs existence rather than naming versus "could be named in the future." Is the argument boiling down to that something does not exist (is not "real") if it cannot be named?

[MrMoenty]

You are right, this reasoning depends on only allowing formal systems with finitely many symbols. Turing himself actually gave justification for this in a beautiful footnote in his 1936 paper [1]:

page 249:

> I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent.

And then in the footnote:

> If we regard a symbol as literally printed on a square we may suppose that the square is 0 < x < 1, 0 < y < 1. The symbol is defined as a set of points in this square, viz. the set occupied by printer's ink. If these sets are restricted to be measurable, we can define the "distance" between two symbols as the cost of transforming one symbol into the other if the cost of moving unit area of printer's ink unit distance is unity, and there is an infinite supply of ink at x = 2. y = 0. With this topology the symbols form a conditionally compact space.

[1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[xyzzyz]

Doesn't this (and by extension, Curch-Turing) rely on the assumption that the universe is discrete? Provided it were not, and one were able to harness infinite precision, one could presumably make a new symbolic system based on it.

That's a valid point -- if you read it in a certain way, the Church-Turing hypothesis indeed states that continuous models are no more powerful than the discrete ones. In fact, we have every reason to believe it's true. See [1], and references [BCGH07], [GCB08] in that paper.

[1] - http://perso.ens-lyon.fr/yassine.hamoudi/wp-content/uploads/...

[nightcracker]

The Church-Turing hypothesis only applies to functions that apply on discrete data. If the data itself is also continuous it does not apply.

[marcosdumay]

Physics would have something to say about infinite precision.

But yes, with those assumptions, it does not hold. It is not as much that the argument is circular, but that the only tech we know how to use (symbols) limits our expressiveness.

[Retra]

The universe doesn't have to be discrete. Only our capacity to understand it rationally and form consistent linguistic models of it.

[enugu]

I think you (and some other commenters) are responding to something different - potential vs actual infinity - not being able to write down all natural numbers, but we can potentially write any number(with some assumptions like an infinite universe).

Whereas the point being made is different and needs some math background which is the work of Cantor. Countable can include all natural numbers that you count until infinity, and the reals are uncountable in that they exceed even this.

The proof of this fact(Reals are uncountable), has the same idea involved in Turing machines halting problem and also Godel's theorem. The general version is the power set of a set(set of subsets of a set) cant be put in one to one correspondence with original set. If you assume such a correspondence, then (<guess the clever trick>) leads to a contradiction.

Reals are sequences of naturals which include sequences of 1's and 0's which can be interpreted as subsets of naturals(a sequence represents the subset of indexes which get assigned the value 1). So reals are bigger than the power set of naturals.

Also, the infinite countable union of countable sets is countable. The number of grid points(integer coordinates) on a plane is the same as the number of grid points on a line. You can set up a zig-zag correspondence. A salesman can visit all grid points on a plane in infinte time. This is used to prove rationals are countable. So even countably infinitely different symbolic systems doesnt help.

[btilly]

The proof of the reals being uncountable depends on the idea that one can build a number that depends on being able to make an infinite number of choices, each of which depends on the absolute truth or falseness of a statement.

But what happens if we open it up to have statements be true, false, or currently unknown? That is we develop a system of mathematics that could be in principle done inside of a Turing machine?

Then Cantor's diagonalization argument falls apart because of all of those "currently unknown" options. See https://news.ycombinator.com/item?id=13843725 for a previous explanation that I gave of this.

[mbid]

Mathematician here. If you mean to say that you cannot constructively prove "the real numbers are not countable", then you're wrong. As a rule of thumb, you can usually prove negative statements constructively as you would prove them classically.

A constructivist would probably state the result more positive (and stronger, constructively): To every countable set M of real numbers, there is a real number not contained in M.

[gertef]

"the real numbers are not countable" is a different statement from "the real numbers are constructible"

[btilly]

Yeah, I'm a trained mathematician as well.

A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument.

[mbid]

I don't understand this. For a constructivist, "¬A" means "from A, falsity is derivable". You can derive falsity from the statement "there is a countable enumeration of the real numbers". A diagonal function given such an enumeration is constructively definable, and it is also constructively true that it is not equal to any of the enumerated ones (because 0 != 1 is true constructively). Thus, the diagonal is not enumerated all real numbers, but it also is by assumption, thus falsity.

What does make real numbers weird when working constructively is that you cannot conclude |x| > 0 from x != 0. This means that 1 / x need not exist even if x != 0, so the real numbers do not form a field in the classical sense.

If you don't trust me, maybe you'll trust wikipedia: https://en.wikipedia.org/wiki/Constructivism_(mathematics)#C....

[mietek]

> The interpretation of Cantor's result will depend upon one's view of mathematics. To constructivists, the argument shows no more than that there is no bijection between the natural numbers and T.

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

[TezlaKoil]

> I'm a trained mathematician as well.

Mayhap.

>A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument.

But in any case you misunderstand Cantor's argument and constructive mathematics.

mbid is correct; Cantor's diagonalization argument constructively proves the uncountability of the real numbers, see e.g. Bishop-Bridges' CONSTRUCTIVE ANALYSIS, Theorem 2.19, page 29.

[Smaug123]

Are you happy with the stronger "there is no surjection from any set to its power set"?

[hzhou321]

I am not a mathematician (physicist). I think the concept of infinity is a con that mathematicians have pulled on us (as there isn't an easy reality to map on to). I can understand arbitrarily big set; however, I never managed to make the jump from arbitrarily finite to infinity. Mathematicians made that jump and glossed over, then continue to show the difference between countable infinity and infinity beyond. Since I never could make that jump, it all sounds nonsense to me.

I have a similar (and I believe to be equivalent) problems with infinitesimal as well. How does arbitrarily small but non-zero become infinitesimal? Since I have problem with infinitesimal, I find the differentiation of real numbers and rational numbers equally non-sensical.

So mathematician, take a pause, could you explain what is countable infinity? Since you never can finish counting (all the natural numbers), how does it make the set countable? What do we mean exactly by countable here?

Wikipedia refers to the idea of one-to-one correspondence. But since you can never exhaust the correspondence, what do we mean by one-to-one? Give me any unique real, I'll give you a unique natural number, and we can go on forever, so how does that not count as one-to-one correspondence?

Unlike mathematicians, physicists are fine with unresolved :)

PS: I guess countable can be defined as there is a definite way of ordering the set, which is true for natural numbers but questionable for real numbers. I still don't see how the ordering connects to the size of infinity and one to one correspondence. Even for the set of real numbers, I can have an algorithm continuously generate random numbers (discarding re-occurring ones so it will be a unique sequence) and prove there is an order of the set (non-exhaustively defined, same as the set of natural number). The ordering may not be describable though. But non-describable ordering is still an ordering, right? Just as a real number that cannot be exhaustively described is still a number. I don't have to describe it, I can hand-wave it just as the way mathematicians hand-waved the infinity.

[jonreem]

A set being "countably infinite" only means that you can write a function that maps each distinct entry in the set to exactly one natural number (0, 1, 2, etc.) without duplicates. That's it.

So for example, the set of natural numbers is countably infinite and we know this because we can write a function that maps each natural number to exactly one natural number: the id function.

We can extend this and say that the set of even natural numbers is countably infinite because it has a mapping function of x => x / 2.

The same is true for all integers (natural numbers + negative numbers): x => if (x < 0) { x * -1 * 2 } else if (x == 0) { 0 } else { x * 2 + 1 }, i.e. if it's negative map it to an even number and if it is positive map it to an odd number, if it's zero map it to itself.

You can even write a function that maps all rational numbers to the natural numbers, since each rational number can be written as a fraction of two integers. (Figuring out the function is a fun exercise but it is also easy to google)

However, you can't write a function that maps any real number to a natural number. The easiest to understand proof of this is Cantor's Diagonal Argument[0], which is a proof by contradiction that shows that any attempted function must exclude some real numbers. Therefore, the real numbers are not countably infinite, and we call them uncountably infinite.

EDIT: In response to your edit, Cantor's Diagonal Argument basically shows that for any given function (and you have to define the function completely ahead of time - that's key) I can give you a real number that is not included in the domain of your function.

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

[hzhou321]

Why a pre-definable function matters here? We have allowed a real number (that cannot be exhaustively described) in, so why a real function (that you cannot exhaustively define) has to be excluded? Isn't it unfair that I am only allowed to use a finitely definable function while you can choose a non-pre-finitely-describable real number? Isn't that a loop proof -- that the set of real numbers is uncountable simply because it is defined to be uncountable, and it is larger infinity than that of natural numbers simply it is defined to be bigger (as what bigger means in the context of infinity is otherwise undefined).

[bjourne]

Here is how you do it. Have a function p(r) which evaluates to the previous real number. Then your mapping function is:

    f(r) = if (r == 0) { 0 } { else f(p(r)) + 1 }

If your objection is "You can't determine what the previous real number is." Then my counter-objection is "Please prove that you can't." Which I don't think is possible without first assuming reals are uncountable.

[hardboiled]

Reals are not equivalently as unrealizable or dubious as infinitesimals. Infintesimals can be constructively specified as nilpotent/nilsquare entities, numerical entities which when squared equal 0 but where those entities themselves aren't reducible to 0. All of this can be done in a constructive manner avoiding any use of infinity or classical logic that depends upon indirect proofs (ie excluded middle). John Bell's 'Primer of Infinitesimal Analysis' has good details.

The computational techniques from Automatic Differentiation use these types of entities to calculate derivatives exactly without approximating infinite (limiting) processes.

Calculus can be done constructively without infinite limiting processes purely algebraically using these nilpotents. And from a geometric interpretation there is nothing nonsensical about a tangent line to a curve.

Also you don't differentiate numbers (real or rational), you can only differentiate functions.

Also the idea of a actual infinity is a poetic mathematical one. It doesn't have to fit reality. The issue is whether it is useful and to what extent.

[hzhou321]

Seems I agree with you (or you agree with mine) :)

I don't have problem with calculus -- or I wouldn't be able to do physics. I am having problem with calculus based on infinity.

> Also the idea of an actual infinity is a poetic mathematical one. It doesn't have to fit reality. The issue is whether it is useful and to what extent.

Well said.

> Also you don't differentiate numbers (real or rational), you can only differentiate functions.

Of course I meant distinction.

[drdeca]

> Since you never can finish counting

Not what countable means. The meaning meant is the one about having a map from the set to the integers, where no two things of the set map to the same integer.

The correspondence is meant as either a full thing, or at least a well defined specification which could be applied to any of the things, if you want to get philosophical about ontology or something.

Also, the specification can't depend on things like, what reals have been given as input "previously".

Say that in this game, you have two obligations:

1: for any n,m I give, you must tell me what the mth binary digit of the real number associated with n is, in the mapping you are considering (or, if there is no real number associated with that natural number.).

2: For any finite collection of the binary digits of the real number I am choosing, you must tell me the first natural number such that the corresponding real number matches all the digits I specified.

With these rules, I can choose my real number (specifying more and more digits) such that for any natural number, I will be able to show that my real number doesn't correspond to that natural number, or any lower one.

Therefore, there is no natural number that corresponds to my number in the matching system you are providing.

(To win, I repeat this procedure:

Ask what the first natural not ruled out already by my specification of my number is. (Call that n)

Ask what the nth digits of the real associated with n is.

Inform you that the nth digit of my number turns out to have the other value for its nth digit, so no natural less than or equal to n corresponds to my number.

Repeat.

This will only ever tell you more about my number, and will not result in me changing my mind about any of the digits of my number, yet there is no natural number which won't ever be ruled out as potentially corresponding to my number.

Therefore, no natural corresponds to my number in your system.

So I win.)

[hzhou321]

Why should you get to choose your real number -- specifying more and more digits -- implies an un-exhaustive process, while I am not allowed to do the same? An unfair game will have unfair winners, how would it mean anything? If we both are allowed an un-exhaustive process of specifying what we have, this goes back to the counting game. As we never can finish, how does it make countable (or not)?

[raattgift]

I'll try to physicalize countability.

Start counting the naturals: 1, 2, 3, ...

At future timelike infinity you'll reach infinity.

Now for the reals. Your goal is to step from 0 to 1, by way of 0.1, 0.01, and so forth.

0 0.0........

At future timelike infinity you still haven't stopped adding in zeroes to the right of the decimal point.

In the first case, at any finite time before \breve{i}^+ you will have counted out some finite natural number. In the second case, you will not yet have counted out your first nonzero real.

This survives across changes of positional counting systems, and almost certainly survives arbitrary choices of non-lossy notation, as long as you start with a finite representation of 0.

[stymaar]

> I'll try to physicalize countability.

> Start counting the naturals: 1, 2, 3, ...

> At future timelike infinity you'll reach infinity.

> Now for the reals. Your goal is to step from 0 to 1, by way of 0.1, 0.01, and so forth.

> 0 0.0........

> At future timelike infinity you still haven't stopped adding in zeroes to the right of the decimal point.

> In the first case, at any finite time before \breve{i}^+ you will have counted out some finite natural number. In the second case, you will not yet have counted out your first nonzero real.

The same reasoning applies for rationals, yet they can still be counted.

The definition of «can be counted» means there is a bijection between your set and the naturals. Such kind of bijection can easily be created for the rationals[1] and Cantor's diagonal argument[2] shows that you can't create such bijection for reals.

There is nothing really intuitive about this concept, but fortunately the proofs are pretty straigtforward which give a kind of «intuition» around this.

[1] https://en.wikipedia.org/wiki/Pairing_function#/media/File:D...

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

[hzhou321]

Infinite defined as not finite is meaningless. For example, infinity is not really a number in a conventional sense. What it is is not clear other than it is not finite.

A real number with infinite precision is equally meaningless.

(Above are not directly related to your comments. I simply like to summarize my thought).

Now to your comment. You can start counting from 0 by 2s, you'll never hit 1, but that doesn't show 1 is not countable. It only shows that 1 is not countable in this particular counting scheme. Yes, you can devise a counting scheme that never hits some numbers, doesn't really contribute to either proof or insight.

I assume you are familiar with the counting scheme of rational numbers, and in that scheme, it can hit any number within any (finite) precisions. Just as infinity, a number with infinite precision is unclear. You certainly can define it, but the definition will have infinite built-in, and it is not clear what meaning does such definition adds.

[cvoss]

I find it helpful to think of countability in terms of the following game: You have a set of items in mind. You propose a (non-terminating) scheme for listing all the items in the set. An adversary attempts to name any item X, hoping your scheme misses it. However, you then show your scheme does, in fact, get to X after a _finite_ amount of time. The set is said to be countable if you prove that your adversary cannot win this game.

Yes, the counting process is non-terminating. But every item gets counted after only finite time.

[hzhou321]

Since it is non-terminating, you didn't really prove every item gets counted after finite time, did you?

Refer to my other reply, you asserted a requirement of predefined (describable) counting scheme here. Why that requirement has any relevance here (in the context of infinity)?

[smsm42]

That sounds like, if you use ternary logic (true, false and CU), then the relationship between sizes of N and R is different. Intuitively, that sounds kinda wrong - why sizes of N and R and their relationship would depend on which kind of logic model you're using to reason about them? If you could build a 1-1 mapping between N and R somehow employing your logic system (which is equivalent to saying they have the same size then shouldn't it be possible to build the same without using your special logic? At least intuitively it sounds so, what am I missing?

[enugu]

Yes, when you restrict to computable numbers, then there are countably many reals. Countable in classical sense. You wont have an computable enumeration, again of because of diagonalization.

[Smaug123]

Nitpick: the infinite countable union of countable well-ordered sets is countable. This statement is immune to the failure of Choice.

[gjm11]

The formulation I prefer: a countable union of counted sets is countable.

(Any countable set has a well-ordering, because a bijection with the natural number gives you one in an obvious way. The trouble is that you need well-orderings for all of them together. The unusual term "counted" emphasizes that we need the actual "countings" to do the job, whereas for me "well-ordered" is sufficiently commonplace that it doesn't shove in my face the requirement that each set come along with a specific choice of well-ordering.)

[Smaug123]

In my mind, "well-ordered" is fully distinct from "well-orderable" :) but "counted" is unambiguous, you're right.

[enugu]

As Lang used to say the Axiom Of Choice is obvious, 'I just pick the elements'. Just kidding, thanks for this interesting logical point.

[xigency]

What about a continuum of symbolic logic systems?

[TheOtherHobbes]

How do you find the edges?

[surement]

> The fact that we can only write down only countably many expressions for numbers doesn't mean that there are numbers that we may never write expressions for

Yes it does: there are countably many numbers we can define, and the reals are uncountable, therefore there are uncountably many numbers that cannot be defined.

[btilly]

Whether or not it does is a matter of which philosophy you choose.

A Platonist may believe that those numbers exist in an abstract space we cannot reach. A Formalist simply defines "existence" in such a way that this is true without worrying about whether they really exist. And a Constructivist denies the existence of things that cannot actually be written down, at least in theory.

[Smaug123]

This may be clearer to the parent commenter if expressed as "there are only countably many strings drawn from the Unicode alphabet, so if we fix a coding scheme such that a string expresses at most one number in that scheme, then there are only countably many numbers we could have defined. If you try and get around this by saying that the coding scheme is arbitrary so the symbol L can be made to stand for any real, then you have dodged the question of how you specify that coding scheme; there are only countably many coding schemes which can be expressed by strings of Unicode once a coding scheme is fixed, and in particular there are only countably many coding schemes expressible in English".

[upquark]

"Real numbers that cannot be defined with language" is not a well-defined set though. Just like "integers that cannot be described in less than 100 words" is not well-defined (I could reach a contradiction by pointing to the "smallest integer that cannot be described in less than 100 words").

[FabHK]

True, but the argument that one set is larger still works.

[upquark]

Wait, you're agreeing with me that the set in question is ill-defined, but still somehow comparable to other sets? I am not sure I follow. My statement is that you cannot meaningfully talk about "all the numbers that cannot be described with language". If you could, I'd ask you if this set intersected with [0, 1] has a lower bound / 'inf' that's contained in it, and if so, did I just describe that lower bound with language? I'm sure some sort of paradox similar to the one with integers can be constructed here...

In my view, every real number is well-defined and there's nothing controversial about the set of real numbers. If the infinite aspect of it causes some researchers to call it a "mathematical fantasy", so be it, so is literally every other mathematical model we use in our lives.

[Smaug123]

Your example is faulty.

> I'd ask you if this set intersected with [0, 1] has a lower bound / 'inf' that's contained in it, and if so, did I just describe that lower bound with language?

The "indescribable numbers" are dense in [0,1], and so (if the set exists) the inf of the set of indescribable numbers which are between 0 and 1 is 0. Perfectly describable.

[upquark]

My example is incomplete, not faulty. I left it as a question (does the inf belong to the set?). If the answer is yes, we reached a contradiction. If the answer is no, we have to continue further zooming in to this interval (or some other construction along those lines).

See, I claim that this set is ill-defined, so I can't know its properties like whether or not it's dense, open, closed, Borel-measurable, etc. etc.

You have to tell me what its properties are, and I will come up with a concrete proof that the set in question is ill-defined.

EDIT: After I RTFA'd, this is actually the paradox in section 2.3 of the linked article

[enugu]

> In my view, every real number is well-defined...

How so? The set of definable numbers in any formal langauage might not be clear concept. But you are making a stronger statement.

For any given language, like for instance ZFC, we can say that definable numbers are a countable subset. Hence measure zero.

[upquark]

Then we mean different things by define. I am saying the set R (with all its elements) is an uncontroversial, well-defined construction within ZFC.

I am leaving out any linguistic or Turing-computability aspects out of this, and people try to bring it back in, mixing computability with definability.

For instance, Chaitin's constant is a perfectly well-defined number, albeit uncomputable by construction: https://en.wikipedia.org/wiki/Chaitin%27s_constant

[FabHK]

There are more people on earth than, say, kings. That's true, even though I can't enumerate all non-kings, and even if the set of non-kings is somehow ill-defined.

[upquark]

Still not sure I follow. Set of non-kings is not ill-defined, not in the same way as set of numbers non-describable by any formal system is.

[Smaug123]

A sentence which fails to specify a real uniquely… fails to specify a real uniquely. Borel's talking about numbers which can be defined uniquely: that is, picked out, identified. Your Berry-paradox description doesn't identify an integer.

[zodiac]

But if we assume that we can say a sentence either specifies a real number uniquely or does not, the Berry paradox number is uniquely specified.

[robinhouston]

A rather more technical – but very interesting – take on this question is [0], which opens:

> One occasionally hears the argument — let us call it the math-tea argument, for perhaps it is heard at a good math tea — that there must be real numbers that we cannot describe or define, because there are are only countably many definitions, but uncountably many reals. Does it withstand scrutiny?

then explains in detail why it does not withstand scrutiny.

[0] https://arxiv.org/abs/1105.4597

[JacksonGariety]

Why do you suppose there is a difference between things and the names we give them? What sort of basis is there for that?

EDIT: How do you know that a large number is "there" if you can't count to it? What would it mean for a large number to "be there."

Being-there is something special. ;-)

[mcherm]

Consider the set of all real numbers which you can actually specify IN ANY FASHION AT ALL, so that the person writing a paper about it and the person reading the paper are talking about the same number. This includes easy ones like "3" or "Square root of Pi". It includes oddballs like Chaitin's constant -- the probability that a randomly constructed program will not get stuck in an infinite loop (for some particular choice of computer and programming language) -- which is so ornery a number that we cannot (even in THEORY) figure out a single digit of it (other than its being between 0 and 1).

Consider that great big set. It's still countable. The thing that makes "real numbers" bigger than integers, the "extra" that real numbers have must be very, very peculiar.

[GregBuchholz]

>Chaitin's constant -- <snip> -- which is so ornery a number that we cannot (even in THEORY) figure out a single digit of it (other than its being between 0 and 1).

You might be interested in:

https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf

"A Chaitin Omega number is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random(its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly noncomputable. The aim of this paper is to describe a procedure, that combines Java programming and mathematical proofs, to compute the exact values of the first 64 bits of a Chaitin Omega: 0000001000000100000110001000011010001111110010111011101000010000"

[tromp]

Unfortunately, that is not a Chaitin Omega, since the notion of program length in that paper is flawed. In particular, it counts a 0 or a 1 provided as binary data in the program as adding 7 bits of length to the program. Later papers by Calude fix this problem, while reducing the number of computed bits to 43.

[stymaar]

> Consider that great big set. It's still countable.

You didn't prove that statement, and actually Cantor's diagonal arguments [1] proves you wrong:

Consider the set of «all real numbers which you can actually specify IN ANY FASHION AT ALL». If you can count it, you can order them in a certain fashion: n0, n1, n2, n3 … It's easy to specify a number X which is not part of this set (which is in contradiction with the definition of this set, and demonstrates ad absurdum that this set is not countable). To build such X, consider the n-th decimal of the n-th number: if it's zero, the n-th decimal of X is 1, otherwise the n-th decimal is 0. Then by construction, X is different from any number of this set, which mean X is not a part of the set. □

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

[moefh]

I don't think that argument works.

How do you guarantee that you can compute the n-th decimal of the n-th number in the list? In fact, from what I understand, this paper[1] shows how to specify exactly a number can't be computed like that.

[1] https://arxiv.org/pdf/1003.0480.pdf

[stymaar]

Why do you need to compute the n-th decimal of a number for this proof to work ? let Ω be a Chaitin Omega number it's decimal are non-computable, yet for every x, Ω + x is a perfectly valid number.

Then `floor(Ω.10^(n))-10.floor(Ω.10^n-1)` is also a number (a natural one) and actually it's the n-th decimal of Ω. It cannot be computed, but it still exist no matter what.

[gertef]

The number you are paraphrasing cannot be precisely identified in finite time.

[stymaar]

Oh, you're right. For that I would need to explicit the construction of the sequence n0, n1, … but that's impossible : if I can find such sequence, my proof holds but at the same time such sequence shows that the set is countable => contradiction, hence there is no such sequence.

But well, now that we've proven that such sequence doesn't exist, we've proven that the given set is not countable !

Not the most elegant proof ever, but I think it works.

[stymaar]

Actually it doesn't: what if the given sequence exists but cannot be expressed with words ? (This is exactly the same thing than «a real number that can't ne expressed with words» which is what I'm trying to demonstrate not to exist. I'm going nowhere)

[deepsun]

What about phrases that specify some numbers on Thursdays, and another numbers when Moon is in second quarter?

What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure?

What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore?

I just making counter-examples to Jules Richard paradox formulation, showing that it's not properly formalized, but rather expressed in vague language, so cannot be considered strict mathematics.

[E6300]

> What about phrases that specify some numbers on Thursdays, and another numbers when Moon is in second quarter?

Would you mind producing such a phrase?

> What about phrases that some people agree specifies a number, while other people think it's another number, and yet another people just aren't sure?

> What about phrases that specify one and the same number for a specific person, but once that person reached age of 40, then he/she is not sure anymore?

You may as well ask whether someone understanding a theorem has any bearing on its truth value. A well-formed sentence in a formal language has one and only one meaning regardless of whether a specific person understands it. That's the whole point of using a formal language. If meaning is actually somehow bound to its interpretation then communication of even the simplest of mathematics is totally impossible.

[deepsun]

> Would you mind producing such a phrase? Sure: "Current quarter of the Moon". Or "How Giants scored last season". Or "One, if P=NP, zero otherwise".

Well, I see your point, if we limit our phrases to only formal language, then you're right.

[E6300]

> "Current quarter of the Moon". Or "How Giants scored last season"

These sentences describe functions, not numbers.

> "One, if P=NP, zero otherwise".

This value is a constant. It doesn't change through time. We simply don't know what it is.

[deepsun]

> These sentences describe functions, not numbers.

Yes, and if we think deeper about it, we'll find out that in mathematics we very often use functions in place for numbers, like it was the same thing. Simple example: √2. Even it form suggests that we apply function "square root" to number 2. Less obvious example: π. It's also a relation between diameter and circumference.

If we go even deeper, trying to understand what, for example, number "2" means, we'll come up to their definition through functions (or classes) of equivalence of sets cardinalities (cardinal numbers), or order (ordinal numbers), where sets are defined using ZFC, for example.

I met this discrepancy while naively trying to program mathematical logic in college. In mathematics you just "take" a number, while in programming you "create" or "instantiate" a number, and it has a ton of consequences.

>> "One, if P=NP, zero otherwise".

> This value is a constant. It doesn't change through time. We simply don't know what it is.

Not necessarily a constant, as it's not proven to be a constant yet. As an example of how it may turn out to be non-constant, check out Continuum hypothesis proof (https://en.wikipedia.org/wiki/Continuum_hypothesis) : solution is independent of our axiom set. In other words -- we can state that ℵ1=c, or we can say ℵ1!=c, and both statements will not contradict anything else. We'll just get two different models, with one more axiom each.

[psyc]

The fact that we can only write down only countably many expressions for numbers doesn't mean that there are numbers that we may never write expressions for

In all seriousness, I don't know that we know for sure that the former doesn't in fact exactly mean the latter.

[protonfish]

Numbers are not physical things, they are symbols that are part of a system that has changed significantly over years. We can make a metaphorical link between a number and a measurement of our universe, but that does not mean that numbers are part of the physical world.

[cgh]

They may not be part of our physical world but that does not mean they don't exist independently:

https://plato.stanford.edu/entries/platonism-mathematics/#Ex...

[petercerno]

Think about a real number with digits: 0.a_1 a_2 a_3 ... in which a_i encodes whether Turing Machine with index i (or program i) halts or not. Since Halting problem is not computable, we will never be able to compute the digits of this real number. Never in our universe.

[IngoBlechschmid]

In the usual setting in which we do mathematics, this is a well-defined real number. That it's hard to determine its digits (even impossible when restricted to use an algorithm) is of no relevance.

However, you might be interested in the effective topos. This is an alternate mathematical universe in which one can't define construct this real number. It has a number of curious properties:

* The statement "1 + 1 = 2" is true in that topos, just like it is in the ordinary topos.

* The statement "any number is either prime or not prime" is true in that topos, just like it is in the ordinary topos, however its truth is not trivial.

* The statement "any real number is either equal to zero or not equal to zero" is false in that topos.

* The statement "any function is computable" is true in that topos (and wildly false in the standard topos).

* The statement "any function is continuous" is true in that topos (and wildly false in the standard topos).

Details are in this set of slides:

https://rawgit.com/iblech/mathezirkel-kurs/master/superturin...

Questions are welcome!

[upquark]

Yes but you defined the number just fine, right? "Compute" is a separate issue from "define", you can't compute a lot of things. Is this going in the intuitionistic logic direction?

[eatitraw]

Even though you defined the number, you can't really do usual stuff with it: e.g. you can't compare it to other numbers.

IMO, these kind of numbers are no more "real" than infinitesimals: https://en.wikipedia.org/wiki/Hyperreal_number

[upquark]

Oh it's definitely more real, as in it belongs to R and not to any of its extensions. You guys realize that the definition of R is non-controversial in modern math, right? There are fringe theories like constructivist logic and other groups that reject all infinite constructions, but this is not the consensus view among practicing mathematicians...

The way you defined that number makes it a perfectly valid element of the set R, as described by, say, the axiomatic definition here:

https://en.wikipedia.org/wiki/Real_number#Axiomatic_approach

Whether it's easy or hard or computationally intractable to compare it to other numbers, that's a totally different question unrelated to its definition.

Plus, you can actually empirically compute a finite set of initial digits (a specific Turing machine can be analyzed to see if it terminates or not), so you can compare this number with one that's constructed by flipping its digits, or with pi, etc.

[IngoBlechschmid]

In constructive mathematics, we don't reject "all infinite constructions". The only axiom which we don't generally assume is the axiom which says "any statement is either true or not true". (Note that we also do not use the counterfactual axiom "there is a statement which is neither true nor false". In fact, we're just agnostic on some truth values.)

In constructive mathematics, there is a perfectly well-defined set of real numbers. The usual diagonalization proof that this set is not a countable set applies.

[upquark]

I said "and other groups that reject all infinite constructions". Some schools of thought within that general intuitionist/constructivist/etc branch of mathematical logic do reject all infinite constructions: https://en.wikipedia.org/wiki/Finitism

Either way, my point above was that this entire branch is not "mainstream math" by any means, AFAIK

[petercerno]

> Plus, you can actually empirically compute a finite set of initial digits (a specific Turing machine can be analyzed to see if it terminates or not).

Well, the fact that the number is not computable means that there will exist an index i, for which you will not be able to compute a_i (no matter how hard you try). In other words, you will not be able to analyze the Turing Machine i, i.e. it will not be possible to prove the termination or non-termination of the Turing Machine i.

So this specific digit will be a mystery forever, and you would not be able to compare it to anything.

[sjolsen]

>The fact that we can only write down only countably many expressions for numbers doesn't mean that there are numbers that we may never write expressions for

It depends, as they say, on what the definition of is is. What does it mean for a number to exist if it cannot be described? What does it mean for a construction to exist if it cannot be constructed?

>if you confuse extant with useful you might end up believing that some random large integers aren't "there!"

The question isn't whether it's useful to claim the existence of uncomputable reals; the question is whether it's meaningful. A construction needn't be useful to be meaningful, but surely it must be meaningful to be useful.

[nine_k]

The standard delta-epsilon type of reasoning crucially depends on existence of arbitrary reals. Many geometry proofs / lines of reasoning crucially depend on the ability to position a point on a line at an arbitrary distance from another point.

All numbers ever written are rationals and thus countable. But those endless irrational numbers make a lot of ways of reasoning simpler, or possible at all.

[sjolsen]

>The standard delta-epsilon type of reasoning crucially depends on existence of arbitrary reals.

What do you mean by "arbitrary?" Do you mean uncomputable? How does analysis require the existence of uncomputable reals?

>All numbers ever written are rationals and thus countable

It is also possible to "write" computable irrational numbers, more or less by definition.

[zerodagger]

>How does analysis require the existence of uncomputable reals?

I don't know what the other person was referring to, but from many important theorems of analysis you can prove the existence of uncomputable reals. For example, from the theorem that a continuous function on a bounded interval is uniformly continuous you can prove that there exist uncomputable reals. If we think that this theorem and many more like it are necessary for analysis, we must conclude that analysis requires the existence of uncomputable reals.

The above fact comes from the area of mathematical logic known as reverse mathematics. The idea is in the name: rather than proving theorems from axioms, we go in reverse. We take some theorem and we see what axioms we can derive from it (using a weak background theory). This gives us a sense of the logical strength of a theorem; the stronger the axioms we can prove from it the stronger the theorem.

An amazing fact is that most classical theorems of mathematics have their logical strength captured by one of five sets of axioms. The weakest are those which are outright provable from the weak background theory (briefly, the background theory, called RCA_0, says that you're allowed to do computable processes). The next is the theory WKL_0, formed from RCA_0 by adding an additional axiom, which goes by the name weak Kőnig's lemma. This axiom states that any infinite binary tree has a cofinal branch (it's a lemma in 'ordinary' mathematics but in reverse mathematics gets treated as an axiom). This is the theory which captures the logical strength of the theorem I mentioned in the first paragraph. From weak Kőnig's lemma we can prove the existence of uncomputable reals. We can construct a computable infinite binary tree so that any branch through it must be uncomputable. From such a branch one can build an uncomputable real, say by insisting that the nth bit in its binary expansion is 1 if and only if the branch went left at level n.

(The easiest way to build such a tree is to go through the halting problem. The basic idea is to construct a tree of attempts to solve the halting problem. It turns out this can be done in a computable way, and any branch through the tree will allow us to solve the halting problem and thus must be uncomputable. The key fact used is that while there's no computable procedure to check whether a Turing machine halts at some time, you just want to know whether it halts in n steps (for fixed n), then you can check that with a computer. The program is easy: simply simulate running the Turing machine for n steps and see whether it stops at some point.

To build our tree: list the Turing machine programs as p_0, p_1, p_2, ... (This listing can be done in a computable way.) We will associate level n+1 on the tree with p_n. Start with a single node for the root of the tree. Then, to build the (n+1)-st level of the tree, look at each node t on the nth level. Check, in a computable way, whether p_0, p_1, ..., p_(n-1) halt within n steps. If none of them halt, then t has a left and right child at the next level. If p_k does halt within n steps, then look below t to see whether you took the left or right path at level k to get to the node t. If you took the right path, then t gets no child nodes. Otherwise, if you took the left path whenever p_k halts within n steps, then t gets two child nodes. Intuitively speaking, at stage n we keep our options open and don't decide whether p_n halts. But if we later see that it does halt, then we retroactively fix any mistake by not going any further along paths where we guessed wrongly before.

For example, it could be that p_0 halts but it takes 1000 steps for this to happen. So while building the tree when you get to level 1000 you'll suddenly stop building any further the entire right half of the tree, since you finally learned that p_0 halts and that you wanted to go left at the root node all along.

This process for generating the tree is computable, so by definition it's a computable tree. It's infinite, because you can keep building the tree upward if you happened to have guessed correctly whether each Turing machine so far halts. However, no branch through this tree can be computable. This is because a branch goes right at level n if and only if p_n didn't halt within k steps for any k. That is, the branch goes right at level n if and only if p_n doesn't halt, so from a branch we can decide the halting problem.)

----

Probably the best reference for reverse mathematics is Stephen Simpson's book Subsystems of Second-order Arithmetic. The first chapter is freely available on his website. It nicely lays out the philosophy behind the project and the major results while deferring (most of) the technical details to the rest of the book. http://www.personal.psu.edu/t20/sosoa/chapter1.pdf

Besides that, the wikipedia page for reverse mathematics isn't awful, but neither is it very good. https://en.wikipedia.org/wiki/Reverse_mathematics

[bo1024]

You might be reading too much into the phrase "mathematical fantasies". This is not saying Borel claims they literally do not exist. More that they are not "accessible" or "usable".

[mannykannot]

"So, in Borel’s view, most reals, with probability one, are mathematical fantasies, because there is no way to specify them uniquely."

If that were so, might it not offer a way to an "explanation" for the Banach-Tarski paradox that even the likes of I could imagine I understood? - that duplicate volume you constructed is made from the same reals, specified differently!

Not that that would be an argument for the proposition quoted.

I was going to say that I am not a mathematician, but that would be redundant.

[eli_gottlieb]

Banach-Tarski isn't a paradox. It's just what happens when you build geometric "shapes" out of nonmeasurable sets. In actual, real-world geometry, we almost always assume the set of points inside the shape/construction we care about is measurable, and that any geometric operations we perform must preserve measure.

[mannykannot]

Thanks - I have seen it mentioned in many places (often with "paradox" appended, e.g. [1]), but never with such a succinct commentary as you have given here.

[1] http://mathworld.wolfram.com/Banach-TarskiParadox.html

[rgossiaux]

>Besides, if you confuse extant with useful you might end up believing that some random large integers aren't "there!"

In addition to the points already made about the "all at once" claim, every integer (every rational number, even) can be given a finite description (just write it down).

[mannykannot]

"So, in Borel’s view, most reals, with probability one, are mathematical fantasies, because there is no way to specify them uniquely."

So I guess that probability has to be a rational number?

[LfLxfxxLxfxx]

yep, like many other faux paradoxes, it stems from mixing language and meta-language

[stcredzero]

I think Borel has confused names with things.

Pedantic positivist?

[TheOtherHobbes]

Or simply a pragmatist.

Reals are a useful sensory abstraction. Countability is another sensory abstraction, although for most people it's a rather less useful one.

There's no particular obligation for sensory abstractions to be logically watertight - if only because logic is an abstraction itself.