Cantor diagonalisation
cs.virginia.edu
cs.virginia.edu
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.
That assumption is unnecessary. Cantor's theorem works just as well for finite sets: it's simply the statement that 2ⁿ > n.
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.
http://math.stackexchange.com/questions/409658/can-every-rea...
1 = 0.9999999999..... for example
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!
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.
If countable means "put into a one to one correspondence with" then the reals are not countable because there are pairs of reals that can be proven to be real whose equality or inequality can't be proven. So in such cases you can overcount, or undercount, but you can never exactly pick each real only once.
But the set of possible constructions can be enumerated. We may not know which actually are real numbers, and which pairs are equal. But we can list all of the possibilities. So there is a countable list of things that contains them all..multiple times..along with other stuff.
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.
What's the last number you've written after two minutes? Is it the last digit of pi?
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.
* 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.
It's a rather limited edge-case in mathematics, it's misleading to simply assert that "everything is countable."
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.
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.
It seems you didn't need to redefine the reals as programs to make this argument--the reals are classically defined as Cauchy sequences of rationals and (if the argument were valid) you could make the same claim using these sequences instead of programs.
I don't think the actual philosophical question is whether the reals are countable, it's whether the reals "exist". You can't define the reals such that they're countable because if you did, they wouldn't be the same structure.
The difference between the classical version and the constructive version that I wrote down is in what kind of rules you can use to construct a Cauchy sequence. My version is something that can be written down in a Turing machine. The classical version is that rules are anything that can follow a set of axiomatic rules - and includes rules that we cannot, even in principle, think of trying to evaluate.
Therefore in the classical version, you can create a rule that depends on being able to evaluate every other rule - including rules similar to itself. That is exactly what Cantor's argument does. In the constructive version you can only create rules using operations that we can guarantee will finish. Which doesn't include verifying the incalculable truth or falsity of arbitrary other rules.
Moving on, though, existence is critical. The key philosophical difference that drove the debate was pure existence proofs. Is proof by contradiction a valid method of reasoning with infinite sets? In particular, can you establish the existence of something by proving a contradiction if it does not exist? In what sense does the thing proven to exist actually exist? What if we prove that it exists but have no way to find it? What it we prove that it exists, have no way to find it, and no way to verify that we have found it?
These are not hypothetical questions. See the https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... for a class of graph theory problems, all of which have polynomial time algorithms to solve. But we have no way to find those solutions. And in some cases it is impossible for us to verify whether a purported solution is a solution even if we were handed it.
So..do you believe in the existence of things in an infinite set that are impossible to find and impossible to verify?
Do you believe in the existence of things that are provably impossible to construct?
http://www.scottaaronson.com/blog/?p=2725
I think the current record is 1919 states, so if you run a certain Turing Machine for BB(1919) steps and it doesn't halt then you know that ZFC is consistent. Godelian considerations might make it reasonable to say that integers BB(1919) or larger don't exist.
I get skeptical of integers so large that you need weird Turing Machines to enumerate their digits whose halting proof is independent of set theory, but I don't yet disbelieve in their existence.
That said I'm quite able to quote and do mathematics that depends on axioms that I do not accept. I can be quite the formalist when it is convenient. But I privately think of it as formal bullshit. And don't like seeing people who haven't accepted it beaten over the head until they do.
I am fully aware of the constructionist approach to mathematics.
But your argument goes somewhat like this:
The reals are real
In computer programs however, we can only do so much
Every computer program represents a real number
For every bounded amount of bits, there is only a countable set of computer programs
Therefore, the reals are countable.
This is not how math works. You extrapolate from a bounded set that is countable to the collection of all those bounded sets - and then claim because every one set is bounded, the collection must be bounded as well - and therefore countable.
Let me make a similar argument just to show how silly your argument is. Here we go: 1. Every set of integers with only one element is finite. Call it a trivial set, for example: {1}
2. Every finite union of such trivial sets is finite
3. Every finite union of such a finite union of trivial sets is finite
4. and so on - after many iterations, your finite set will look pretty big to the human eye - almost as if it was the set of integers.
5. Therefore, the set of integers must be finite.
Sounds pretty silly, right? Thats what you've done for a different property of a different set.
That is nonsense. This is why arguing with illiterates about math is so annoying. They think they can write non-stringent arguments and then claim they have "somewhat proof". In math, there is no such thing as "somewhat proof". You are either right or you are wrong. The reals are the reals by definition. You can not make them countable.
What you can make countable is sets of numbers that you work with. Sure. You wont ever create a computer that has access to all the reals, PRECISELY because it operates from a position of countable-ness (even quantum computers). But thats not what I care about when I talk math.
The real numbers are not accessible to in a "reality" way. They lie fully in the realm of arcane mathematics. Like many other things do. You would never claim that the hyper-exponentiation operator had anything to do with reality, and it doesn't. Neither do the reals. You're just confused about them because they appear so prominently in middle school mathematics.
Accept it and move on.
Mathematics is the realm of absolute truth. Everything we have proven is de facto true. You can make an argument that we are doing the "wrong kind of mathematics". And that may actually be true. But it doesn't change anything about our discipline. If you want to get philosophical and create a new Mathematics discipline based on different arbitrary rules (axioms), you are free to do so. But you will have to prove a lot of very mundane things and go through centuries of early day fuckups and its very likely that you will soon seek to merge with the already established mathematics.
Call it math2.0. I'll play with it. If its interesting, why not. But don't expect your new math to be more interesting than the one we've got.
But let's move on to the critical point. You said this:
The real numbers are not accessible to in a "reality" way. They lie fully in the realm of arcane mathematics. Like many other things do.
You are lecturing me on the nature of the nature of existence of things which cannot be described or verified by any process that can be carried out or imagined by any process that can exist in our universe. In a discussion about whether we should accept any existence for such things. And are failing to address the point that assuming axioms that lead to the conclusion of existence is an entirely unprovable assumption!
Do you see the obvious problem here?
Beyond that, you say: "all real numbers that you're likely to hear of" - this is a fallacy twice over.
First, since my lifetime is finite, it's easy to count all the real numbers that I will hear in my life. But I don't think that's the argument you want to make.
Second, there are people who professionally construct unlikely real numbers; just because you choose to ignore those numbers doesn't mean that your countable sequence of all real numbers can. There's a difference between "things that cannot be written down" and "things you can't write down".
Whether or not such numbers are well-defined at all is a point of philosophy. What does it mean to declare the truth of statements that cannot be verified either way?
That's why this is a philosophical question that is foundational for mathematics.
First you said the reals are countable, now you're saying they don't exist at all?
What does it mean for something to "exist"? I can construct these sets from the axioms of ZFC, and under ZFC I can show your proof doesn't work.
Philosophy only enters into it when you are considering which axioms to take.
I agree that by the time you start assuming ZFC, you're well past the realm of philosophy. The flip side of it is that in a discussion of philosophy you shouldn't make assertions based on axioms that have not yet been agreed on.
In any constructivist axiom system, the usual constructions of the real numbers do not define anything sensible. If you try to make sense of Cauchy sequences from a constructivist point of view, then you'll necessarily wind up with a definition that is very much like the one that I gave.
So you get the result that I stated. From a constructivist point of view, the usual "constructions" of the real numbers are nonsense and construct nothing, while the definition that I gave constructs something that can be reasonably called the real numbers. According to classical mathematics, both sets of constructions are well-defined, and the one that I gave is both complicated and different than the usual reals.
Which version you accept depends on your philosophical beliefs. Seeing what a different philosophical belief will lead to is very hard the first time you do it. But if you believe that it makes no sense to talk about the "truth" of unverifiable statements, you won't wind up debating the finer points of whether to accept C in ZFC...
Any particular theory, capturing some aspect of the reals, can be given a countable model. Those "constructed reals" are countable, but they miss out almost all of the reals.
Think about it this way: a theory is like an interface, a theory of the reals provides an API to access the reals. The API is necessarily limited; not least because there are only countably many ways we can combine the operations.
Now consider a mock implementation of that interface: rather than passing around reals, we invent some (countable) dummy objects to use instead. Since the API is limited, we can always come up with a mock implementation which cannot be distinguished from the real implementation using that API/theory.
That doesn't mean that the reals are countable. It does mean that uncountability is an implementation convenience; regardless of what result we're after, we could get it using countable objects, but we might have to spend a lot of effort "out smarting" the algorithms we're using (i.e. coming up with our "mock" set).
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?
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!
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) and hopefully illustrates the problem with your enumeration of the reals.
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 :)
I did understand before how flipping changed the numbers into 0.5, 0.25, etc., but had missed that this process would only create rational, thereby missing the irrationals altogether. There's enough food for thought for me now. :-)
Pi looks somewhat like this: 3.1415... "and so on". Let's ditch the 3.
0.1415... and so on. flipped over equals:
...5141
Easy enough, right? But pi had infinite decimals. Infinite decimals on the left side means what? You tell me :)
Infinity is not an element in the real numbers. All the irrationals, when flipped over, get absorbed into infinity - and infinity itself has no decimal representation. For people who are not in math, saying "and so on" is fine. But you can't do math on "and so on". "And so on" is a handwaving way of saying that you lack the mathematical language to describe whats going on. Which is fine, for casuals.
I had assumed from the middle school itself that the set {1, 2, 3, ...} includes infinity, and I still am questioning if this not being is just a matter of definition or it has to be that way. More below:
We say that the size of the set {1, 2, 3, 4} is 4, in which scenario, the number 4 happens to be an element in the set. Likewise for {1, 2, 3, 4, ..., 100000}. Now we say that the size of the set {1, 2, 3, 4, ...} is infinity, but infinity is not an element of that set.
It seems what I am missing is the formal definition of this "..." or "and so on". If these two were not allowed in any of the proofs, how would you word Cantor's Diagonalisation and other theorems in mathematics that currently involve these. (Or alternatively, what is the formal definition of "...")
PS: I do understand limits and calculus but perhaps from an engineering perspective, not for pure mathematics where I have these confusions.
Thanks! :-)
The definition of the number 2 is by axiom. The peano axioms state this:
1. There is a number. We call it 0
2. For every number n, there is a successor S(n). The successor of 0 is called 1
3. Let m and n be numbers. m=n is equivalent to S(n)=S(m). This means that if two numbers are the same, they have the same successor
4. For every number n, S(n) is not 0. This means that 0 is the first such number
This completely describes the natural numbers. If you want to say that 0 is not part of the natural numbers, just write down the same things and say that 1 is the first number, and construct 0 later. For some funky reason, this doesn't actually matter. Although you'd think that difference between 0 and 1 is pretty big.
Nowhere in this does infinity appear. Infinity does, in fact, not belong to the natural numbers. Infinity as a NUMBER is only defined much later in mathematical literature. As a concept, it just means "big". When we talk about infinity in terms of the reals it just means "if we construct a series of numbers that get succeedingly bigger and they are not bounded, then they 'tend toward infinity'". But infinity is not a thing. Its just a name for "this shit gets big brutha".
The problem is that I can't give you a formal definition for "and so on", because it can mean many things.
I will give you a formal definition for a number instead.
Pretend again that we look at the number .111111111...
and now we flip it around. We look at the number ...111111.0
What this means is the following. This number is the sum over all the exponents of 10. The number is obviously identical to 1 + 10 + 100 + ... = 10^0+10^1+10^2+...
We still get the and so on. Now we need to find language that seeks to eliminate the notion of "and so on". Keep in mind that this number is not part of the real numbers, because it would be identical to infinity.
We prove this in the following way:
Our number is obviously bigger than 1, because it is 1+10+...
It is obviously bigger than 10, because it is 1+10+...
Now, we perform something devious. An argument by induction. This happens in the first week of math education and it is precisely when we leave the realm of "all the things we can write down".
We prove that for every n, the number ...1111.0 is bigger than 10^n.
1. We already know this for n=1, because 1+10+... is bigger than 10^1 = 10.
2. For n>1, 10^(n-1)+10^(n) is clearly bigger than just 10^(n), and our number contains all the exponents of 10.
(^Up there is a tautological proof. You already know this, I just write it down "semi formally". Proving a fact about natural numbers by induction is always somewhat tautological because the mechanism that makes induction possible IS the natural numbers themselves.)
Now we know that for every exponent of ten, our number is bigger than that. This means that for every natural number that we can possibly think of, our number is bigger than that. Therefore, the number we are looking at is not part of the natural numbers and by extension, not part of the real numbers.
This is because every natural number has a successor and by definition, the successor is bigger than the number itself. But our number is bigger than all the numbers already. In order for it to be a natural number, it would have to have a successor, which would be bigger than itself. But our number is bigger than all the numbers. This sounds a bit clunky. I could write it down mathematically, but that would just confuse you, probably.
Now I'm just being wordy. The proof was over long ago.
edit: Writing this down mathematically goes like this: Let b=...1111 and n be an arbitrary natural number. b>n => n is not successor of b => b is not in N. (You see that I had to reduce the argument to something I already knew - the successor axiom - in order to wrap it up).
I've shown that your number is bigger than all the possible number on the real line and if its not on the real line, it is not part of the real numbers.
Now you would ordinarily say that it is infinite. And that's kind of true, but you can only say that once you understand that infinity is just a concept, not a number in the way you understand numbers.
tl;dr: Infinity is not part of any of the ordinary sets of numbers (natural numbers N, integers Z, rationals Q, reals R, complex C, ... - yes, there are more of these)
Is infinity the result of adding 1 to a number in the set? If infinity-1 is in the set. Is infinity-1 in there? If infinity-2 is. ... This gets you a set {1,2,3,...,infinity-2, infinity-1, infinity, infinity+1, ...}
But you can do the same with foo and get the set {1,2,3,...,foo-2, foo-1, foo, foo+1, ...}. So if infinity is in {1,2,3,...}, the same should be true for foo or anything else. This obviously doesn't make sense, so {1,2,3,...} is defined to be the smallest possible set containing 1 and n+1 for each n in the set.
Step 2 fails because you can't create a 1-1 correspondence between the real numbers between zero and one, and the integers. That is what you are trying to prove. I'm too tired to figure out if your proof is valid or not, but your conclusion is correct.
Make up your mind.
decimal: Not base 10, but fractional, those with a decimal point binary: Not just 0 or 1, but base 2.
0.01 is a binary positive decimal number which is 0.25 in base 10.
These are also merely countable...
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.