8 ms·
Cantor diagonalisation
- joveian 10y agoI've long had a question that might be a variation of the third concern listed: couldn't diagonalisation just show that considering all real numbers to be an infinite sequence of digits is a flawed representation? Not necessarily that they don't exist somehow or that they are necessarily countable, just the diagonalization argument seems flawed to me. Edit: Actually maybe this is just the first concern mentioned :/. Edit2: Maybe clearer explanation: you can produce an infinite sequence of digits from many real numbers, but it doesn't seem to me to be valid to consider that infinite sequence to actually be the real number.
- nine_k 10y agoPlease describe the flaw, and give.an example of it.
- sillysaurus3 10y agoThe logic embedded in Supertasks and the Banach-Tarski Paradox has always seemed strange. It's not flawed, but it's so counterintuitive that it can seem like evidence that something in the logic of infinities must be wrong. https://www.youtube.com/watch?v=ffUnNaQTfZE https://www.youtube.com/watch?v=ffUnNaQTfZE https://www.youtube.com/watch?v=s86-Z-CbaHA https://www.youtube.com/watch?v=s86-Z-CbaHA
- Smaug123 10y agoBanach-Tarski isn't so much evidence that infinity or Choice is wrong, as evidence that the reals aren't a particularly good model of the real world.
- _rpd 10y agoCan every real number be represented by a (possibly infinite) decimal? ... http://math.stackexchange.com/questions/409658/can-every-real-number-be-represented-by-a-possibly-infinite-decimal http://math.stackexchange.com/questions/409658/can-every-rea...
- 77pt77 10y agoThe answer is yes but it's not a unique representation. 1 = 0.9999999999..... for example
- btilly 10y agoYou are looking in the wrong place for the key philosophical issue, but didn't land on it. When we talk about "an infinite sequence of digits", what are we talking about? Are we talking about ACTUALLY having an infinite sequence of digits in front of us? Or are we talking about having a RULE that will in theory produce them? Platonists believe that they actually exist in a reality beyond human conceptual limits. (Maybe in the mind of God?) Formalists side step the question by making everything an abstract symbol manipulation game. (Though the rules of the game are chosen to result in something matching platonic intuition.) And Constructivists take the rule approach, and not just that, but a rule that we can write down and actually evaluate. Cantor's diagonalization argument obviously works according to Platonists. Formalists choose their rules to make it work as well. But Constructivists, well, it doesn't work there! Why not? Well when you get down to it, how do you define a rule and how do you prove that it works? Well, a "rule" can be thought of as just a computer program. And now we have the problem that, thanks to the Halting Problem, it is impossible in general for one computer program to predict what another program will do! You can, of course, attempt to write Cantor's number down. You can implement the rule that he describes using a theorem prover to filter a list of all programs to just the ones that we can prove are numbers. We can write a perfectly well-defined program that produces Cantor's number. BUT THERE IS NO CONTRADICTION? Why not? Because THAT program is one that the theorem prover CAN'T prove works! (In fact the theorem prover will prove what it is doing, and prove that if it always works, then its set of axioms is consistent. And now you're up against Gödel's Incompleteness Theorem!) The result is that in the two most popular philosophies of math, Cantor's argument works. But in the third, it doesn't, it can't, and the reals are countable. There the complications of diagonalization are simply another illustrations of the challenges of self-reference, and not the assertion that more numbers exist than can be written down!
- mabbo 10y ago> But in the third, it doesn't, it can't, and the reals are countable Isn't that a bit of an overreach? It seems that in Constructivism, Cantor's diagonalization doesn't work as a proof. But that doesn't mean that the reals are countable, just that this proof isn't valid.
- yongjik 10y agoTLDR: It is a rather nontrivial result that each real number can be represented by an infinite sequence of digits, although not uniquely (as other comments said). However, to understand that, we need to answer several questions: * What is a real number, after all? How do we even define it? * When we have a sequence of digits like 0.12345678..., and when we say this sequence represents a number X, what exactly does that mean? * (...which leads to): What is a sequence? What does it mean for an infinite sequence to converge? So, it's definitely not "Duh, it's obvious": some work is needed to understand all this. I recommend reading the first several chapters of any good book on analysis.
- sillysaurus3 10y agoIf you write the first digit of pi after one minute, then the second digit after 30 seconds, then the third after 15 seconds, then the fourth after 7.5 seconds, and so on... What's the last number you've written after two minutes? Is it the last digit of pi?
- Smaug123 10y agoHuh? There isn't a last number you've written after two minutes. You've written them all, but there's no terminating one.
- MichaelBurge 10y agoSure, that's the story the government tells everyone. It sounds plausible enough, but is it the whole story? * Apply Downward Lowenheim-Skolem to get a countable model of set theory * Construct the reals using whichever technique you want. * Since the base set theory is countable, so is the set of constructed reals. The same technique can give you countably many groups, countably many rings, countably many points in the plane, etc. Everything is countable.
- openasocket 10y agoYou're referring to https://en.wikipedia.org/wiki/Skolem%27s_paradox https://en.wikipedia.org/wiki/Skolem%27s_paradox ? It's a rather limited edge-case in mathematics, it's misleading to simply assert that "everything is countable."
- danharaj 10y agoCountable in the external logic, but the internal logic still proves that there are uncountably many reals.
- wayn3 10y agoit is very much not possible to construct the real numbers in such a way that they are countable. (the set of real numbers is the object that "happens" when you fill the "holes" in the set of rational numbers). cantors diagonalization argument is proof of that. you can't pull some silly trick to make them countable. there are many properties of R that are countable, but that doesn't make R itself countable.
- btilly 10y agoThe truth of your statement depends on what philosophy of mathematics you accept. Which itself is not something that can ever be settled by pure reason. Here is a definition of the reals to consider. A real number is a computer program which implements a function f from positive integers N to the rationals such that |f(n) - f(m)| < 1/n + 1/m. This is a reasonable definition of real numbers, and all real numbers that you're likely to hear of are real numbers under this definition. But now consider. There are a finite number of symbols that we build programs out of. Therefore for every N, there are a finite number of possible computer programs of length N. Only some of which represent real numbers under this definition. Therefore there is a countable sequence which contains all real numbers in it! What is the key philosophical difference between this system of mathematics and the usual one? Quite simply this. Classical mathematics asserts the existence of things that cannot be written down or calculated by humans. This system of mathematics denies the existence of things which we cannot write down. Now about a hundred years ago there was a major debate between these two philosophical camps. In the end the classical school won simply because most mathematicians don't care about philosophy, and classical mathematics is easier to work with. But the purportedly inescapable logical conclusions that you're taught about are not actually as inescapable as you've been lead to believe.
- danharaj 10y agoI think this blog post will delight anyone who liked this submission: http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/ http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theo...
- danbruc 10y agoI am already struggling right at the beginning. If we open a book on set theory, we will find a proof of Cantor’s theorem which shows explicitly that for every map e : A → P(A) there is a subset of A outside its image, namely S = { x ∈ A ∣ x ∉ e(x) } What about e(x) = { x }? In that case S would be the empty set, wouldn't it? Does map imply some additional properties in this case? Am I misunderstanding the statement and it does not try to imply that S is non-empty for every e?
- Smaug123 10y agoCantor's theorem is better stated as "Let X be infinite. If f: powerset(X) to X, then f is not injective.". This is completely uncontroversial, and its proof is by diagonalisation in a context where it really does intuitively "just work". Set X to the naturals, and prove that the reals are equipotent with the powerset of N, to obtain "the reals are uncountable".
- _rpd 10y ago> This is completely uncontroversial I think it is still intuitively surprising that some infinite sets somehow have more elements than other infinite sets. The powerset operator is very special because it can create this difference.
- Smaug123 10y agoI suppose I really meant "why should one expect that f might be injective anyway?" Once you're no longer in the context of a set like N which is very familiar, there's just no obvious reason for the theorem to be false.
- deleted 10y ago[deleted]
- pwdisswordfish 10y ago> Let X be infinite. That assumption is unnecessary. Cantor's theorem works just as well for finite sets: it's simply the statement that 2ⁿ > n.
- Smaug123 10y agoTrue, thanks. I thought the proof I knew of Cantor only worked for infinite sets, and that a separate proof was required for the finite case; but actually the same proof works for both.
- bladecatcher 10y agoA most merry and illustrated explanation of the diagonal argument: http://www.coopertoons.com/education/diagonal/diagonalargument.html http://www.coopertoons.com/education/diagonal/diagonalargume...
- kmill 10y agoHere's an argument I've found sometimes works better for people who can't see what the diagonal from the list is supposed to do, or if they think it's rather arbitrary. It's essentially the same argument, just written differently. Definitions: 2 is the set {0,1}. N is the set of natural numbers {0,1,2,...}. An infinite sequence of 0's and 1's c_0,c_1,c_2,... can be thought of as a function c : N -> 2 (that is, the values in a sequence are a function of their position: c_i = c(i)). A set X is countably infinite if there is an invertible function f : N -> X (which, in other words, is a sequence f_0,f_1,f_2,... where each element of X appears exactly once). Let's write A -> B for the set of functions from A to B, rather than the usual B^A. Suppose for sake of contradiction (N -> 2) is countably infinite, so there is an invertible function f : N -> (N -> 2). Let F : (N -> 2) -> N be the inverse, so I can save having to type f^-1. Let g : N -> 2 be defined by g(n) = 1 - f(n)(n). Then, g(F(g)) = 1 - f(F(g))(F(g)) = 1 - g(F(g)), so g(F(g)) must be 1/2, contradicting the fact that it ought to be 0 or 1 instead.
- alok-g 10y agoGenuinely asking: Consider decimal numbers between 0 and 1 in binary. Here's how I am going to synthesize this set. Step 1: Take non-decimal binary numbers and consider them to be padded with an infinite of zeros at the left. ...0000000 ...0000001 ...0000010 ...0000011 ...0000100 ...0000101 ...0000110 .......... Do we agree that this will contain all the non-decimal non-negative binary numbers? In particular, is the following number in the above set? ...111111 (all ones, not zero-padding on the left). If not, why not. And if not, this seems to be a matter of definition to me. If yes, move on. Step 2: Place a decimal at the end of each line above and flip left and right. 0.0000000... 0.1000000... 0.0100000... 0.1100000... 0.0010000... ............ Do we agree that this contains all the decimal positive binary numbers between zero and one: [0, 1). Let's now apply diagonalisation on this. It says that the number 0.11111111... will not be present in the above set. Perhaps someone can see my confusion and enlighten me. :-) Thanks!
- BuuQu9hu 10y agoThe number ...1 in your first notation is actually -1, using 2-adic interpretation. The number 0.1... is actually 1, which lies outside your expected range. Maybe another base will help. In base 3: 0.0... 0.10... 0.20... 0.010... Once again, a naive diagonalization yields 0.1... but this time at least we have not extended past 1. Is there a way to avoid that convergence? Sure, we can change the 0 digit to either 1 or 2 randomly, or based on some pattern or enumeration, instead of just 1. So now we can take many diagonals, and they all look like: 0.121212... 0.122122... 0.121121... 0.22212221... ... Augh! What happened? Our diagonalization appears to have revealed an infinity of missed reals! This is similar to the construction of the Cantor set (https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set) and hopefully illustrates the problem with your enumeration of the reals.
- alok-g 10y agoThanks. This was helpful. I am not sure that I fully get it, but I think I do. :-)
- wayn3 10y agoThe confusion in your argument is rather simple. You construct the set of INTEGERS in a binary representation. Then you flip them over to the other side,in an operation that you yourself do not fully understand. The first number that you flip (0.1) turns into 0.5 decimal The second number that you flip (0.01) turns into 0.25 decimal The third is 0.75 0.125 and so on. You are creating a subset of the rational numbers, which is obviously countable. It is countable because you constructed it to be countable. You constructed something that was countable and then tried to prove that it is countable. Happens all the time :)
- t0mek 10y agoThis theorem blew my mind on the Set Theory 101. A particularly interesting implication is that we can't say anything about the vast majority of the real numbers. Anything we say or write, all texts created by the humanity now and in the future creates a countable set. Since the real numbers are not countable, we can't assign them with the definitions.
- sdenton4 10y agoFor some added fun: algebraic numbers are the set of all numbers which are roots of rational polynomials. You know, things like sqrt 2, along with all the rationals themselves. Algebraic numbers comprise the vast majority of real numbers we ever have a reason to actually use. These are also merely countable...
- petters 10y agot0mek noted that all possible definitions of a number are countable. That would include all algebraic numbers.
- effie 10y ago> we can't say anything about the vast majority of the real numbers. It depends on which majority is at question. For that majority that is irrational, we can say any member can be approximated arbitrarily closely by a rational number.
- erodommoc 10y agoThis seems to come up over and over again, and it always comes down to what assumptions you start with. If you accept all of the axioms and methods, the proof holds. If you don't, it doesn't. Articles like this one, aimed at an audience that already assumes that its techniques are valid, are never going to convince a non-mathematical audience that doesn't know what the basic assumptions are, because that's not their goal.