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.
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.
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.
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.
> 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.
A surjection seems silly: doesn't that imply that some reals would be indistinguishable? Or can you indeed not prove that more than the natural number of reals are distinguishable in constructive mathematics?
Honestly, the result hinted at in the wikipedia article caught me by surprise as well: There are some flavors of constructive mathematics (notably CZF), that are still consistent if you also add the statement "There is a subset A of the natural numbers such that there is a surjection from A onto the real numbers". Note that this does not imply that you can prove this in CZF, it only means that you cannot disprove it. See http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf prop. 8.2 if you're interested.
Wikipedia says that the Cantor argument shows "no more" than that there is no bijection between the natural numbers and the real numbers. As far as I can tell, it also proves that there is no surjection from the natural numbers onto the reals in every system of constructive mathematics I know of, so I think this is slightly misleading.
What do you mean by "distinguishable"? In constructivism, a set A such that x = y or x != y for all x, y in A is sometimes called decidable. And yes, it is indeed not true that the real numbers are decidable. This would imply that there is an algorithm that decides whether two infinite sequences of ones and zeroes will differ at some point or agree indefinitely, which is pretty much equivalent to solving the halting problem.
On the other hand, the natural numbers, integers, rational numbers and every finite algebraic extension of the rational numbers (for example Q[i], "rational imaginary numbers") is decidable.
Furthermore if we limit all mathematics to things that can in principle be done on a Turing machine, then this statement is trivially true because all possible Turing machines is a countable set.
Moving from Turing machines to a Turing-complete programming language, we could define a real number as an equivalence class of functions from positive integers to fractions such that for each function |f(n) - f(m)| <= 1/n + 1/m, and two such functions are equivalent if |f(n) - g(n)| <= 2/n for all positive n.
The question of whether a given function is actually a real number is in general undecidable. The question of whether two functions represent the same real number is also undecidable. However it is easy to create a set of functions that will definitely include all real numbers under this definition (and a few things that are not), but some of those real numbers will be included multiple times.
And the really important point about this is that suddenly "uncountable" doesn't mean "more". It just means that there is an undecidable question or three creating complexity in the way of generating the mapping.
>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.
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.
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.
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).
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.
What is your definition of "previous real number"? If you define p(r) such that p(r) < r and there does not exist any real number x such that p(r) < x < r, then it is easy to show that p(r) cannot exist using a proof by contradiction.
Given real number r, assume there exists a real number q such that q < r and there does not exist a real number x such that q < x < r. Let real number y = (q + r) / 2. It is trivial to show that q < y < r. Therefore we have a contradiction, and therefore there does not exist a real number q that meets our conditions for a "previous real number".
If you take issue with this, then I suggest you read up on the standard construction of the number systems from the naturals up to the reals. This is all very rigorously defined in terms of ZFC set theory.
Your definition of f is circular: to calculate f(r) we need to know p(r), which in turn depends on f(r).
Cantor's diagonal argument shows that any mapping from the natural numbers to the real numbers must necessarily miss some real numbers out. It takes some time to get your head around if you aren't used to mathematical proofs, but it's definitely worth looking it up and trying to work through it if you're interested in this subject.
Suppose there exists an r' such that for some real number r, p(r)=r', where p(r) gives the real number that precedes r.
What does that mean? Does it mean there are no numbers between r and r'? Because that's what I think predecessor means, even though it's trivial to prove that there are numbers between r' and r. For example, (r'+r)/2, the average of r and r', is between the two numbers. And there are also numbers between r and (r'+r)/2, and between r' and (r'+r)/2.
So there can't possibly be a real that is the predecessor to another real, because there are always more real numbers between any two reals.
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.
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.
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.
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)?
The reason that the real number being defined can be defined in terms of the function is because, that is the situation being considered in the statement.
For any way of doing the mapping, there is a real number that the mapping misses. Alternative statement: "there is no such mapping that doesn't miss any of the reals".
This is shown because, given a mapping, I can find a real that the mapping misses.
When one says "for all x, there exists a y such that P(x,y)", the y is allowed to depend on the x.
That's what this is.
Why wouldn't your objection apply to the proof that the halting problem is uncomputable ? The program that the halting checker can't check is defined in terms of the halting checker. Why is that allowed? Because that is what the statement is saying. For any purported halting checker, there exists a program it doesn't decide the halting of.
Similarly here, for any purported bijection between the integers and the reals, there is a real that the purported bijection misses.
I don't know if you are using the word "countable" in the standard way, so I don't know what you mean by that last sentence.
Given any finitely described real numbers, there will be a finitely described mapping map it to a unique natural number. But if you use real numbers that can never finish describing, we have to use a mapping that cannot be finished in describing. That is not the same as "there is no such mapping that doesn't miss any of the reals". If all mappings that cannot be finitely described are excluded, what will be the reason? And why that reason cannot be applied to exclude some real numbers (that cannot be finitely described) as numbers? I understand that is what it is, but being what it is seems meaningless.
The general halting problem is uncomputable. It can only be simulated. However, any program is still assumed to be finitely described. Any discussion in finite domain (including arbitrarily big finite) cannot lead to conclusions or insight toward infinite.
> I don't know if you are using the word "countable" in the standard way, so I don't know what you mean by that last sentence.
In the context of infinity, words such as countable, bigger, order, etc. all lose its standard meaning. We don't really know what it means if we don't really know what infinity is. Mathematicians simply made a definition to countable here -- a finitely described mapping -- that is fine on its own, but completely useless. Since we can't draw any parallels from infinity to finite (including arbitrarily big), we can't really relate any definitions over the infinity to "standard" meaning of those words to the domain of finite.
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.
> 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.
> but fortunately the proofs are pretty straigtforward which give a kind of «intuition» around this.
It is only straightforward once you accepted infinity and all other definitions/description based on infinity.
If you, like me, cannot accept infinity, then all the proofs/descriptions that contain infinity become apparent non-sensical.
>> Start counting the naturals: 1, 2, 3, ...
>> At future timelike infinity you'll reach infinity.
This highlights the flaw. You reach infinity with infinity. Nothing is really being said about infinity. But somehow if you accepted the understanding infinity here, the rest of thesis such as cantor's diagonal argument may seem to be natural, except you forget that you really didn't know what infinity is.
All property of infinity cannot be finitely described. So anything about infinity is built on top of infinity. Turtle all the way down (or up), and we don't really know what it is.
The mathematical concept of infinity generally derives from the axiom of infinity in Zermelo-Fraenkel set theory, which asserts the existence of the inductive set (which is the basis for the construction of the natural numbers). Specifically, it states that there exists a set N such that the empty set is in N, and for all x in N, x union {x} is also in N. This is an axiom, so it cannot be proven to be right or wrong. You can either accept this axiom, or attempt to create your own system of mathematics that does not require the axiom of infinity.
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.
Counting integers from 0 by 2s and never hitting 1 (or 3 or 5 ...) still results in a finite number of natural numbers counted in finite time, skipping a finite number of natural numbers at each step. How many reals do you have to skip between 0.0 and 2.0 and between 2.0 and 4.0 ?
Returning to my previous attempt, you could think of instead a successor function; for any finite natural number the immediately adjacent natural number can be found in finite time. For any real number, the immediately adjacent real number cannot be found in finite time because the step from one real number to the next is infinitesimally small.
All of these examples are "de-generalizations" of the mapping argument. Counting integers from 0 by 2s maps bijectively onto the natural numbers.
The naturals map injectively and surjectively onto the reals; you exhaust all the naturals counting between 0.0 and 1.0, or 1.0 and 2.0, or even between 0.01 and 0.011.
"A real number with infinite precision is equally meaningless": uhm, integration of infinitesimals (dS, dV, ...) ?
> How many reals do you have to skip between 0.0 and 2.0 and between 2.0 and 4.0 ?
Here you sneaked the concept of reals in. Remember reals are defined on top of infinity. You can't have reals if we are still debating what infinity is. There are infinite amount of numbers between 2.0 and 4.0, in the same sense there are infinite amount of numbers in the natural set.
Your successor function defines any finite natural number, it does not define infinity. In the rational counting scheme, we can reach any number within any finite precision. A real number that is defined on the base of infinity precision requires infinity time to reach with the same counting scheme -- the same way infinity requires infinity time to reach by 1, 2, 3, ... So if you allow infinity time, the same way you allowed infinity in your definition of real, then all real numbers can be reached (including infinity time) by counting -- not that provide any meaning.
Calculus is based on taking limit -- that is assuming a finite precision, albeit arbitrary. Infinitesimals are still finite, not infinite. Otherwise, you cannot divide them.
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.
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)?
If I start at 0 and successively add 1, do you agree that I eventually hit any positive integer you could pick after a finite number of steps? Does that not prove to you that I hit every positive integers? Which one do I not hit?
You will only eventually hit any given integer after finite steps. It does not prove you will hit every positive integer. You'll miss those that one never can finish giving you -- for example, I'll start with digit 1, and I'll infinitely adding 1 behind it (never finishing). It is an infinite natural number that you can't hit within any finite number of steps.
The game itself is certainly not the proof that is required. The proof in question is a proof that the game cannot be won by the adversary. By no means do you need to play all possible rounds of the game to conclude this.
The discussion really helps me understand the problem. Real numbers are infinity in disguise. Because infinity is not really defined, real numbers are not really defined. Just saying infinity is not finite does not make much sense (in the sense of adding anything helpful). Any real number that you can finitely describe can be included in a finitely described counting scheme. Let's use the counting schemes of rational numbers, I'll hit arbitrary numbers to arbitrary precisions. Taking a limit, it is not clear that I miss any numbers (including pi). To defeat this scheme, the adversary has to keep adding digits to his real number, as well as keep shrinking his allowed precision infinitely. Now both the number (that is being infinitely being described) and my counting process is infinite, we didn't and can't prove anything. There is simply no conclusions to be drawn.
> you didn't really prove every item gets counted in finite time
The proof that the adversary cannot name such an item is logically the same as a proof that every item gets counted. This is a fundamental logical truth, namely de Morgan's law for universal/existential quantifiers: (not exists x such that P(x)) is the same as (forall x, not P(x))
> Why that requirement has any relevance here
'A counting scheme' is an intuitive way of providing a 'one-to-one correspondence to the natural numbers,' which is used in the technical definition of countability.
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?
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.
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.