Another chaos theory post is in progress. But while I was working on it, a couple of
comments arrived on some old posts. In general, I’d reply on those posts if I thought
it was worth it. But the two comments are interesting not because they actually lend
anything to the discussion to which they are attached, but because they are perfect
demonstrations of two of the most common forms of crackpottery – what I call the
“Education? I don’t need no stinkin’ education” school, and the “I’m so smart that I don’t
even need to read your arguments” school.
Let’s start with the willful ignorance. This is the kind of crackpottery
that frankly bugs me most. As an American, I’m used to the fact that our
culture distrusts intelligence and education. Politicians in America use
“intellectual” as a insult. Mentioning that someone attended one of the best
schools in America is commonly used as a criticism. That’s where this one, by
a guy who calls himself “Vorlath”, comes from. Enough introduction, here
it is:
I can’t believe there are still people who believe in Cantor’s
theory. It’s complete silliness and makes the people who believe in
superstition look like the smart ones by comparison. Cantor was well known to
treat infinity as a finite number and that’s all he’s doing with his theory.
It doesn’t mean anything.
That argument reduces, roughly, to “I have no idea what Cantor’s argument was,
but I don’t like it, and therefore it’s wrong”.
Cantor didn’t treat infinity like a finite number. What he did was study the
structure of numbers, and realize that “infinity” isn’t a simple thing. You can show
that there are “infinities” that are larger than other “infinities”. In fact, it’s
pretty inescapable.
The rough sketch is: take any set, S. You can create another set, called the power set of S
(usually written 2S), which consists of the set of all subsets of S. So if S is
the empty set, then 2S has one value: the set containing the empty set. If S
is the set { a, b }, then 2S = { {}, {a}, {b}, {a,b} }. The power set of any set S is
always larger than S. So – take the set of all natural numbers. How big is it? Well,
it’s infinite. How big is its powerset? It’s also infinite. But every powerset must be
bigger than the original set – so the powerset of the natural numbers must be larger
than the natural numbers. How can that be? It can be, because there are different kinds
of infinities.
Some of that actually has an effect in reality. I can create a perfect one
to one mapping between the natural numbers, and the set of all rational
numbers. They’re the same size. But I can’t do that for real numbers. My
mapping for the rationals won’t include π, unless I cheat and specifically add it
to the list. It won’t include square roots. No matter what I do, I can’t devise any
method for creating a one-to-one correspondence between the natural numbers and the real
numbers. That is what Cantor’s work really showed.
Intuitively, it seems wrong that there are degrees of infinity, that there
are bigger infinities and smaller infinities. The argument from Vorlath is, basically,
that the fact that it’s not intuitive means that it must be wrong. Vorlath has
no need to know what Cantor really said, or what it really means. Without knowing that,
he just knows it’s wrong, because it’s obviously silly.
Moving on, we come to the genius who doesn’t need to know an argument in
order to disprove it. This is an amazingly common form of argument. I see it
mostly in the form of Cantor disproofs, where it takes the form “Here’s a
one-to-one mapping between the natural numbers and the reals”. The mappings
are always wrong. But what makes the argument particularly annoying is that
the mappings are trivially wrong: Cantor’s diagonalization shows that
given any one-to-one mapping between the naturals and the reals, the
mapping will miss some real numbers. In every case where I’ve seen
one of these arguments, their enumerated mapping fails because Cantor’s
diagonalization shows how to produce a counterexample for it. You can’t disprove
Cantor’s diagonalization without showing that something is wrong with the
diagonalization proof – but these anti-Cantor geniuses constantly think that
they can disprove Cantor without actually addressing the proof.
This comment though, has nothing to do with Cantor. It’s on
the subject of iterative compression. Here
it is:
Your talking linear maths not non-linear with non-linear representation you
can compress repeatedly because the input a is different to the output b which
you can then consider B in linear form ready to become non-linear C I know it
can be done as I have the non-linear twin bifurcation maths needed and have
tested it already on random digit data and yes you can unpack this information
too. not to worry I’m am just getting ready to produce the compressor myself
and no I’m not a Christian. There of course for a given data set will be
limits as to how compressed you can make the data but this will not be
relative to linear laws of data compression.
This is, basically, the same thing as the Cantor disproofs. The argument
against iterative compression is pretty simple: compression is intrinsically
limited – because most strings are non-compressible. It doesn’t
matter how clever you are.
The argument is incredibly simple. Imagine that you want to compress all
strings of 128 bits. You’re not very ambitious: you only want to compress them
by one bit – to reduce all of those strings of 128 bits to 127
bits.
You can’t do it.
There are 2128 strings of 128 bits, and 2127 strings
of 127 bits. That means that either: (1) you can’t compress half of the strings,
or (2) on average, every 127 bit string is the compressed form of two
128 bit strings. In case 1, you’ve admitted defeat: you can’t compress half of
the strings at all. In case 2, you’re screwed, because compression is
only valuable if it’s reversible – that is, when you compress a string, you
expect to be able to get the original uncompressed string back; but if
there are multiple input strings that can be mapped to the same compressed
string, then your decompressor can only, at best, return a set of
strings saying “The uncompressed string is one of these”.
The more you compress, the worse it gets. Want to compress things by half?
Then you’re talking about compressing 2N strings into
2n/2 values – giving you 2n/2 possible uncompressed
values for each compressed string.
The way that this relates to iterative compression is that an iterative
compression system is no different than any other. Sure, you can devise
iterative compression systems – they’re commonly known as “lousy compressors”.
What they do is take some specific set of input strings, and compress them a
little bit. Then you run them again, and they compress a little bit more. Then
you run them again, and they compress a little bit more. Until eventually,
they stop working. And, at best, you’ve compressed your input as much as you
could have in a single pass with a non-iterative compression system.
The unavoidable fact is that the set of inputs is larger than the set of
outputs, and that means that compression is inevitably limited. The reason
that compression works in practice is because our input strings are
highly structured – and in this case, structure is another word for
“redundancy”. We can compress text because text is far from random – it
has redundant structure that we can remove. (For example, in the format
that I’m using to write this post, each letter takes 8 bits. But I’m using
a character set of about 64 characters. So really, even ignoring all of
the redundancy of english, I’m using 8 bits per character when I could
be using only 6. Fully 1/4 of the length of this document is completely
redundant. And that doesn’t even cover the fact that I use words like “that” all
the time – 41 times so far in this document, and each one takes 32 bits.)
The problem with compression has nothing to do with linearity
versus non-linearity. It doesn’t matter how clever you are. If you can’t
explain just how you’re going to compress 2N strings into
2N-1 strings without losing any information, then you
lose: it can’t work. You haven’t addressed the problem.
I think these are essentially the same argument system: only one is self-deluded. One says: I don’t understand the argument, so it’s wrong. The other says: I pretend to understand the argument, so it’s wrong. Note that 2 reduces to 1.
Counterintuitive is my favorite word. It means: I understand this, but you’re not going to.
Mostly OT, but I recall back in my BBS days there was a short-lived compression scheme called UC2 (if I recall correctly) that basically just took advantage of the inefficiencies in the commonly-used compression formats of the day, and just iteratively LZ’d (probably LZ’d — I don’t actually know the details) a couple extra times to squeeze out another 10% or so above the commodity formats. They got away with it by having a rip-roaring fast implementation, so the extra passes (and their accompanying diminishing returns) didn’t make it a non-starter from a performance perspective.
Hrm, I wanted to muse about some pie-in-the-sky ideas this post gave me, but it occurs to me it is probably too closely related to my job, and I should stay mum. Ah well…
Typo: “lousy” should be “lossy”.
Ultra-Compression:
Take a digital file. Sort all the ones to the front, zeros to the back. Zeros are just zero: throw them away. Count up the ones.
Take resultant number, represent in binary. This is your compressed file.
Note that this system can be used recursively.
Decompression algorithm is still pending.
@Alex: No, I am pretty sure Mark meant “lousy”. “Lossy” is something completely different, and is typically not iterative. JPEG anyone?
There are people who try to disprove Cantor? The world never ceases to amaze me.
The nicest compression crackpot argument I’ve heard of is the following: Okay, so you can’t compress every string, but you could just take run your compression algorithm anyway. If it outputs something shorter, you take that output; if it doesn’t, you take the original string.
Of course this also can’t give you anything useful, but at least it’s more creative than the usual nonsense.
@1:
I disagree with your definition of counter-intuitive.
Most of us develop a set of basic ideas about how things work based on our experiences. Many of those ideas are common to just about anyone who grows up as a human being on planet earth. A typical example: If you lift something up and then let go of it, it
will fall down.
When we’re educated, we learn some more abstract ideas – but we rapidly develop a basic understanding of them, usually by relating them to our concrete experiences.
Intuition is that basic understanding that we develop by relating our concrete experience to abstract ideas. Some of it is obvious and correct. We can get commutativity by knowing
that if I pick one apple and you have two, then we have the same number of apples as if I picked two and you picked one.
The problem with intuition is that our concrete understandings of abstract ideas frequently aren’t correct. We may not have learned all of the details of the abstract idea
before we formed our intuition. Or we may have learned them, but the way that we concretized our understanding into intuition left some out.
In the case of things involving numbers, most people never get beyond the very basic idea of numbers. Almost everyone develops their intuition about numbers based on a very incomplete understanding. And that leads to things like the huge number of Cantor crackpots: It’s just obvious that you can’t say infinity one is bigger than infinity two. Our basic understanding of what comparing things means doesn’t allow us to compare infinities.
BTW, I just want to mention that a number of statements that Mark made in this and the other post are accurate from a theoretical standpoint, they are only “mostly” accurate from a practical standpoint. Most practical lossless compression format is going to involve transmitting some preliminary data — usually a Huffman tree of sorts — and because of the way that preliminary data is encoded and the fact that the compression method (generally) doesn’t take this data into account when figuring out how to compress the rest of the data, you typically are still going to wind up with a “compressible string” as the output of the majority of practical compression formats.
Which is why if you ZIP something, and then ZIP the ZIP file, you might get a modest improvement, even though ZIP is not a “lousy” compression format.
Not that this contradicts the point of anything Mark is saying! 🙂
Mark:
I was, of course, being deliberately glib. Counterintuitive indeed conveys the nuances you ascribe to it. But it is often used (not here) as an arrogant hammer.
@3:
No, not a typo. I meant “lousy”. What I was trying to get at is that the way that a compression system works is basically by recognizing redundancies in input data. If you eliminate all of the computable redundancies, you’ve got a maximally compressed format. Most compression systems try to capture all computable redundancies in a single pass. A good compression system is one which does a good job and identifying and eliminating all redundancies in the input data.
For iterative compression to work, it has to mean that the first compression pass didn’t eliminate all of the redundancies that it was capable of recognizing. Instead, it left behind redundancies that it could recognize, which it would then eliminate in another pass. The worse the compression system, the more likely it would be to benefit from multiple passes. A really good compression system would work in a single pass.
A less good system might be able to get something out of a second pass. A not-very-good system might be able to get something out of a third pass. But the better the compressor, the sooner it can’t get any more out of the file.
To be concrete: there’s a compression system called huffman coding. In the simplest version of huffman coding, you find the most common character in your file, and you represent it using a very short format. For things less common, you use longer formats; the least common things, you just leave alone.
It’s possible to imagine an input file where the first pass of a huffman coding compressor merged pairs of characters in a single byte – and that that single byte would be one of the most common “characters” in a second pass. So you could benefit from repeating the huffman coding compression twice. But the amount of compression that you’d get from that second pass would be very small. And the odds of things falling out so that you could get any benefit from a third pass are vanishingly small.
In fact, in practice, simple Huffman coding for most texts isn’t a particularly great compression system. If you take a better compression system, like the modern LZW compressors that most of us use, the odds of seeing any significant improvement from a second pass are virtually zero.
If I understand the concept of an indescribable number properly, even though there are more Reals than Rationals we will never encounter more than aleph-null of the Reals, simply because they cannot be expressed.
If this is true, then I don’t know if it would somewhat pacify or further confuse those who think that Cantor was mistaken. Perhaps if they knew that we cannot, technically, ever, in any way, write down or measure more than aleph-null of the Reals they would feel like their intuitive grasp of numbers makes more sense.
@6:
Are you kidding? There are still tons and tons of people trying to disprove Cantor. I probably get an anti-Cantor flame at least twice a month, and I’m just a lowly math-blogger. Math journals still get multiple submissions a year containing attempted refutations of Cantor!
I think the fundamental trait of crackpots (the “zeroth” hallmark) is a deep inability to understand that their own knowledge has limits. In other words, if they cannot understand XYZ, then XYZ must be a hoax. They are unable to believe that there are things beyond their comprehension.
It’s sort of a form of arrogance, because they think they know all there is to know.
Just nit picking, but algebraic numbers are countable. A mapping including square roots is totally legitimate.
Huh??? What does being or not being a Christian have anything do do with that?
I wonder if your commenter is confusing digital and analog compression schemes.
After all, if I convert all the numbers from 1 to 1,000,000 to logs, I can fit them all into a range from 0 – 60. (Hey! I am an engineer, these are converted to dB!) I can take that 0 – 60, take the log of that (handling the zero as a special case) and reduce the range still further…
Of course, anybody can *compress* data that way, the trick is to *de-compress* it losslessly and not lose precision.
I bet your commenter is an Audio Engineer who designs companders. 8^)
“because there are different kinds of infinities”
Only during construction of another set and only as long as that set stay dependent on the original.
Look, you have set A and are constructing set B based on set A. So if you treat A as a finite set, you can make something that appears larger. Unfortunately, this is the fallacy of composition. What applies to the elements does not automatically translate to the whole. That’s the flaw with the whole one-to-one mapping theory and how you apply it.
What you have is where the elements of set B are dependent on the elements of set A. You say so yourself.
“If S is the set { a, b }, then 2S = { {}, {a}, {b}, {a,b} }. The power set of any set S is always larger than S.”
What you don’t say is that this is true only while 2S is dependent on S when the sets are infinite. If you remove the relationship, then both sets are equal size.
Consider the following.
Set A is base2 while Set B is base 3. For any given amount of digits (this is our dependency), base 3 will always be able to represent numbers that the same amount of digits in base 2 cannot represent. Is base 3 “larger” than base 2? Yes, as long as we’re comparing finite digits. But no if we treat each set as independent. That’s Cantor’s flaw right there. He’s using the finite digits to say that the whole has a certain property. That’s the fallacy of composition.
As I said, you can have dependent sets that appear to be smaller or larger DURING CONSTRUCTION. This is what you’re saying when you say the power set is larger. Depends on POV whether you’re seeing it as a dependent or independent set.
Take the set of reals up to 0.5. This is half the “size” of the set of reals. Has to be. But up to 0.5, we have an infinite amount of reals as well. Contradiction. Cantor’s contradiction.
Cantor’s argument does nothing except compare different bases and uses the digit level to produce a contradiction as I explained above. The dependency is the digits, so the two axis can never be independent. Even in infinity, the two axis will be different sizes (just like 0-0.5 is smaller than 0-1.0 when it’s a subset) until you can treat both axis (or sets) as independent. Then you can remap them.
By forcing this inequality at the digit level (where one axis will be longer than the other), Cantor constructs his diagonal. Then he states that both axis must be infinite when taken independently, yet we can create a new element. Well, no shit Sherlock. I can create a new element outside of 0-0.5 at the element level too, but it doesn’t mean jack to the whole of the set.
Cantor’s argument is flawed and so is his first proof which is even more ridiculous.
Cantor uses the digits to create a finite relationship that is different from the relationship between infinite sets. It’s a bogus contradiction and you know it.
An infinity of them, indeed.
re: 17
Hooray! I’m so looking forward to this thread!
@17:
So…Many…Mistakes….
Fundamentally, you do not understand the difference between measure and cardinality. Looking at the interval [0,1], then yes, the measure of [0,0.5] is half the measure of [0,1]. However, the cardinality, the ‘number of elements’ in each set is ‘c’. They are equal.
But I don’t think you WANT to be right. Because being right would mean that you have to change your current position. When your ego is more powerful than your desire to know the truth, you have abandoned science.
@Vorlath:
You have a good point about Cantor’s cardinalities, namely that they are not the same as a notion of set “size” according to which, for instance, the set of reals up to 0.5 is half the “size” of the set of reals. These two sets would be of different “size”, while they have the same Cantor cardinality.
Your mistake is to assume that Cantor thought the two were equivalent. He didn’t; neither do textbooks that teach Cantor cardinality and the diagonalization argument. Mathematicians do discuss your kind of “size”, but usually call it measure, and defining measures in general ways is tricky: see e.g. Wikipedia on the Lebesgue measure.
I will try the impossible:
@17: You are apparently confusing the concepts of *cardinality* (generalisation of “numbers of elements in a set”) with that of *measure* (generalisation of “geometric size of a set”).
It is true that (using standard measure) [0,0.5] has half the *measure* of [0,1], but they have the same *cardinality*. Consider the mapping that takes an element of [0,0.5] and sends it to [0,1] by multiplying it by 2. This map is obviously both one-to-one and onto*, so for each element in [0,0.5] there is a unique element in [0,1]. Thus, they have the same *cardinality*. It really isn’t that hard.
*(I hate it when I can’t expect people to understand what ‘bijective’ means.)
It takes either a whole heap of ignorance, or a steaming heap of something else, to believe the ideas in #17.
You do not need to understand a theorem’s claimed proof in order to invalidate it. A correct counterexample suffices.
Similarly, you do not need to actually read through a crank’s alleged counterexample to know it is false. Knowing the correct proof suffices.
For a few years, I believed there was one famous professional mathematician who was an utter crackpot regarding Cantor’s theorem. The William Dilworth of Dilworth v Dudley, who sued Dudley for libel over being called a “crank” in Dudley’s Mathematical Cranks and lost (see the dismissal by Judge Richard Posner) turns out is not the famed Robert Dilworth of lattice theory fame. The crank Dilworth managed to publish his gibberish in a nothing journal.
See also Hodge’s article in The Bulletin of Symbolic Logic on the anti-Cantor papers he dealt with as an editor over the years.
@24: “You do not need to understand a theorem’s claimed proof in order to invalidate it. A correct counterexample suffices.”
True, but it would be nice if those giving incorrect counterexamples would look at this particular proof, given that it can be used to show why their incorrect counterexample does not work.
The problem is that these crackpots are incapable of understanding what Cantor’s theorem actually says, let alone actually reading the proof and applying it to their alleged counterexamples. Vorlath simply makes no sense whatsoever, although some readers do try to parse a sentence here and there and then explain his mistake. That is misunderstanding what he has written, which is ultimately just mathematical word salad. There’s no way in, no way out.
Old timers will recall James Harris on sci.math. Same crankery, different theorem.
Then that’s exactly what I’m saying. Cantor is mistaking measure (the finite digits) to create his diagonal.
Ketil, your multiplying by 2 is exactly my point. The Y axis in Cantor’s diagonal can be scaled to match the X axis by using base 2 (the same as the X axis). But Cantor’s mapping when picking digits doesn’t allow it because the two axis are dependent on each other (his own personal custom mapping).
I do know what bijective means. Also, I’m not arguing that any sets have the same or different cardinality. I’m only arguing that Cantor’s argument is wrong.
Also, [0,0.5] does not have the same cardinality as [0,1.0] when the first set is a subset of the other. This is true because all elements of the first set can be found in the second, but not vice versa. Only when the first is not a subset of the other and taken as independent sets are their cardinality the same.
I know people here won’t like what I’ve just said, but it’s true. As I said earlier, if I map base 2 to base 3 via digits, then base 3 does not have the same cardinality. Once you remove the dependency on digits, then they DO have the same cardinality. If you want to call one measure, then fine. It’s all relative to the mapping in use at the time. This is what Cantor is doing. His axis are dependent via digits and is what causes the apparent (but wrongful) difference in cardinality. Until he uses independent sets for both axis, then his argument is flawed.
Note that if you dislike my use of cardinality, then you see the problem with Cantor’s argument. He too is using measure instead of cardinality when building his diagonal.
@24:
That depends.
You need to be able to provide a counter-example to a proof. But you often can’t tell whether a particular counter-example is valid unless you understand the proof that it purports to be a counter-example ofany enumeration, it will be missing reals. Without understanding what Cantor’s proof does, you can’t create a counter-example to it. Before anyone can take an enumeration of the reals seriously, you need to show why the diagonalization doesn’t work for your enumeration.
I’ve gotten *dozens* of these things from cranks, and every single time, they give me an enumeration of the reals, which can be disproven using the diagonalization.
@26. Yes. I agree. I feel victim to it, now I will step back.
When someone produces a bijection from NR, and produces the concurrent flaw in Cantor’s proof, I will discard a century of topology. Until then, I need to let this go.
That was supposed to read ‘a bijection from N to R’ but my fancy ascii symbols got HTML’d away.
And two sets which are bijectable have the same cardinality. By definition. If you don’t like the definition of the term, make up a new term. Just because you want two sets cardinality to be different, that doesn’t make it so.
#27: It is not true that if A is a proper subset of B then A and B do not have the same cardinality. You are misapplying your intuition about finite sets to infinite ones.
@27: Or you are just using a faulty definition of cardinality. The correct definition is that two sets have the same cardinality if there exists a bijection between them.
[0,0.5] is indeed a proper subset of [0,1], but that doesn’t stop there from being the obvious bijection f(x) = 2x between them.
@27 said:
Actually, they have the same cardinality whether they are considered together or independently. This may be the source of your confusion. The fact that “all elements of the first set can be found in the second, but not vice versa” does not mean that two sets have different cardinality. For example, consider the set of all natural numbers except 37 and the set of all natural numbers. Their cardinality is the same. What you say is true of finite sets, but it is not true of infinite sets. Two sets have the same cardinality if and only if there is a bijection between them.
In your bizarro-math, do the set of even naturals and the set of odd naturals have the same cardinality or not?
Pelli, you are missing the point. Your argument and mine are the same. What you just said, apply it to Cantor’s argument.
The vertical axis in Cantor’s grid is a subset of the horizontal axis (because the X axis is compressed using base 2). By your own admission, they have the same cardinality. But Cantor uses the dependent aspect of the digits to create a false illusion that he can create a new element.
Suppose you have the set [0,1.0] and I DON’T create a new set. All I do is create a new division. I just put in a separator in the ORIGINAL set at 0.5 (before or after doesn’t matter). You can’t tell me that all elements before the division can be mapped to the whole set. It’s impossible (the elements before the division can only map to themselves leaving the rest of the set without a mapping). This is what Cantor is doing. When you have dependent sets, you have an equivalent situation. Apologies if I can’t explain this concept as clearly as I would like.
Apologies for the double post. What everyone is saying about the cardinality between [0,0.5] and [0,1.0] is EXACTLY MY POINT as to the flaw found in Cantor’s argument. You’re all correct on this point (so no need to repeat that they have the same cardinality), but none of you are seeing the implications.
@27: Start off with this diagonalisation that shows there is no bijection between the natural numbers and the set of sequences with elements 0 or 1: Suppose there is a bijection f between the natural numbers and the set of sequences. Then create this sequence: Let the kth element in the sequence be the opposite of the kth element of f(k). This sequence cannot be f(m) for any m, since if it is then it differs from itself in the mth position.
Do you wish to claim this proof is false, or just that a similar argument won’t apply to the reals?
I don’t completely understand your argument. I’m guessing you might have misunderstood the vertical axis. It consists of discrete points numbered 1, 2, 3, etc. It is not a continuum.
That’s just utter nonsense! Infinite sets don’t bevahe like finite sets and you can’t draw conclusions about infinite sets using rules that only apply to finite sets. You are wrong: all elements of the second set can indeed be found in the first set. Any element from [0,1.0] can be divied by 2 to yield a unique element of [0,0.5]. In fact, any subset of the real numbers can be directly mapped onto any other subset of the reals. For example, the set [0,1.0] has a bijection to the set [1.0,∞). Any element in the first set has a unique corresponding element in the second set defined by x→1/x and vice versa. There are no elements that don’t map. The set of reals has no “holes” in it.
“You can’t tell me that all elements before the division can be mapped to the whole set.”
Yes I can. Map x to 2x. Then every point in [0,0.5] gets mapped to exactly one point in [0,1]. Check out Hilbert’s hotel. Do you agree there is a bijection between the set of positive integers and the set of positive even integers?
Mathmatics is a purely human exercise. We humans completely define the exercise. The definition we use for “sets being the same size” is “there exists a one-to-one onto mapping (bijection) between the two sets.” I like that definition because it works for both finite and infinite sets.
Now, maybe you reject that definition. Maybe your rejection of that definition leads to an exercise that is at least as enjoyable for you as the common definition is to the rest of us. It’s my impression that’s how non-Euclidean geometry came about. But unless you have done some work to flesh out the system that your definition leads to, don’t come around to people who use mathematics on a daily basis and tell them, “you’re wrong, I’m right, and you all are so stupid to be using that stupid definition for describing equally sized sets.”
Okay, I guess you mean “the reals between 0 and 0.5.”
Because you say so? Puuuhhleeeze. I am not convinced. I doubt many others reading this blog are convinced, either. In order to talk about “size” with regard to infinite numbers, you have to define “size.” Produce a definition, and see what it leads to.
Agreed, assuming again that you really mean “reals between 0 and 0.5”
What? You haven’t even established what you mean by “size,” yet. Produce a definition, preferably one that will work with both finite and infinite sets, do the work of seeing what happens with your definition, and present that to us before making bald assertions.
Cantor uses the same base (base 10, I believe) to produce a real that is not in any given list of reals. The thing that allows him to do that is that each real is infinitely long, so both axes are infinitely long. The only way the two axes could be a different size is that the horizontal axis is countably infinite (aleph 0) and the vertical axis is not countably infinite (aleph 1). Oh, wait…that was what Cantor was trying to show, and which you are saying is wrong.
Okay, it looks like I misunderstood what Vorlath said. It’s still wrong for most of the reasons I said.
What I find striking about Vorlath’s argument here is that he’s arguing that Cantor is wrong for concluding that there are differently sized infinities, when that’s plainly ridiculous. But at the same time, his argument about that relies on creating differently sized infinities.
How is that a refutation of Cantor?
Vorlath’s own article and comments might show a little clearer where things are going wrong.
@Vorlath: What are, in your opinion, the cardinalities of the following sets? And what are the cardinalities as per Cantor’s arguments?
1. The natural numbers {0, 1, 2, …}
2. The even natural numbers {0, 2, 4, …}
3. The odd natural numbers {1, 3, 5, …}
4. The non-negative reals [0, infty)
5. The reals on a “small” interval: [0, 1]
6. The reals on a “large” interval: [0, 10^6]
Pelli: “Yes I can. Map x to 2x.”
That would make the subset into an independent set. Cantor is not using an independent set as you’re showing (which would be cool if he had). If you do what you claim to Cantor’s axis, then you lose the ability to create a diagonal where this number is not found in the list.
And to everyone else saying you can map [0,0.5] to [0,1.0], please stop and reread what I’ve said. I agree with all of you. In fact, you’re all making my point for me. What you think I’m doing wrong is exactly what Cantor is doing wrong and is in fact what I’ve been unsuccessfully trying to explain.
Mark: Finally, someone who is getting close. Brilliant! It’s the first time I’ve seen someone move closer to what I’m trying to explain.
Two different infinities, quite right. But I’m saying that the USE of different infinities is flawed by Cantor, and that he DECLARES them the same. In other words, Cantor is declaring that the two axis are infinite “size” (sorry if that’s the wrong term). But his grid uses a relationship that created an uneven mapping digit-wise (aka FINITE relationship) much like mapping base 2 to base 3 via digits. See where I’m getting at? That’s the flaw. That’s what’s wrong with Cantor’s diagonal argument. He’s mapping via digits instead of by element and we all know you can’t do that. He thinks he’s mapping by element but he is not.
If you can’t map by digit between base 2 and base 3, why should we believe it between base 2 (X axis) and an enumeration (akin to base 1 if there were such a thing) (Y axis)?
A more thoughtful post: when I learn a new concept I sometimes get caught up on a part that I seem to have “disproved”. I then seek an explanation why my proof is wrong, which helps me to understand the concept in general. If, for some reason, I can’t find a disproof, it is sufficient to know that almost all mathematicians accept the concept and that many other theories depend on it. I have the humility to say “I don’t understand why my proof is wrong, but I understand that other people do, and that is good enough for me.”
Ultimately I need to be able to be understand my mistake, but as a new learner, which Vorlath seems to be in this subject, I need to be take certain things as true to proceed.
Vorlath’s claim that Cantor’s arguments are invalid doesn’t stand in some void. He’s claiming that countless mathematicians, engineers, computer scientists, and whoever else are all deluded – and that, despite claiming that the disproof is simple – only he has discovered it. He’s further claiming that the tenets of topology, computability, and many other theories are in jeapardy. And he has the audacity to make this extraordinarily sweeping statement with the triteness of “BTW, I’ve just disproved Cantor’s theory with the above image” (taken from his website).
Vorlath, have the humility to understand that everyone else understands why you are wrong, even if you don’t (yet).
@32: I wouldn’t say he’s using a “faulty” definition of cardinality; he’s certainly using a non-Cantorian definition, but perhaps in the end his definition of cardinality for infinite sets ultimately makes more sense than the standard Cantorian definition. I doubt it, though.
More fundamentally, it appears that the biggest complaint from Vorlath is about Cantor’s use of the decimal expansion of reals to generate the diagonalized counterexample. I personally feel there are surmountable technical issues with the standard presentation (relating to the equivalence between pairs of digit sequences like 0.4999999… and 0.5), but as I said, they are surmountable.
Stepping away from reals, Cantor’s proof is very suitable for showing that there isn’t a surjection from S to 2S for any set S (including N). For suppose there is such a surjection f:S->2S. Take the subset K of S such that n in K if and only if n not in f(n). Then K is not equal to f(i) for any i in S, because i is in exactly one of K or f(i). This contradicts the premise that f was a surjection, so no such surjection can exist.
With a proof that the relation |A| ≤ |B|, defined as “There exists a surjection from B to A”, is a well-defined ordering relation, that is sufficient to prove that there is a never-ending chain of infinitites, even without showing a bijection from 2N and R.
Vorlath, I don’t quite follow your arguments. I’d like to know what you think about my proof in 36 that there is no bijection between the set of natural numbers and the set of infinite binary strings? Is it correct or not? If not, then which sentence is wrong?
IMO Vorlath is not satisfied with the fact that the vertical axis corresponds to *enumeration* of reals, while the horizontal axis corresponds to *digits* of reals, i.e., the meaning and perhaps the “sizes” (“scales”?) of the two axes are not the same. However, I do not understand how does this “incomparability of axes” invalidates Cantor’s diagonal argument that the set of real numbers is not countable.
@27 “… Also, I’m not arguing that any sets have the same or different cardinality.
[one sentence passes]
Also, [0,0.5] does not have the same cardinality as [0,1.0] when the first set is a subset of the other. …”
Now, obviously you don’t see how you’re wrong about the mathematics, but do you at least see how you contradict yourself?
Anyway, I dare say this thread has been a wonderful example and confirmation of everything Mark wrote in his post. Good job, Vorlath!
Each row in the grid is an infinite bit sequence in a countably infinite set of bit sequences. The bits in each sequence are enumerated just as the sequences in the set are (if stacked to make a grid, your X axis is enumerated just as your Y axis is). The individual columns in your grid are irrelevant to the point. There is no “map by digit between base 2 and base 1.” Any “base” in itself is simply a map between a sequence and a number. The diagonal counterexample is simply a demonstration that there will necessarily be sequences (and therefore real numbers) excluded by the set even though it is infinite.
@Blaise: “This contradicts the premise that f was a surjection, so no such surjection can exist.”
You’re talking about the power set. I can tackle that at a later time if you wish. But it comes down to having a dependent set. Apply a new transformation (ie. make the sets independent) and the contradiction disappears.
@Pelli: Your statement is only true with dependent sets. When you use the stated relationship, you are modifying the properties of the original set to create a new set. So it’s expected that you will get a “contradiction” between the two sets. Remove the relationship between elements and the contradiction disappears.
@Radoslav: The different scales on a finite level is what allows the new number to be created. However, this property disappears on infinite sets rendering the diagonal impossible to construct.
It’s like setting up a vertical axis on base 2 and a horizontal axis on base 3. I can list all the base 2 elements, create a diagonal and set all digits to 3. No matter how many digits you take, this diagonal will always be different than what is found in the list.
Some people think this argument is flawed because only base 2 digits are used in Cantor’s argument, but this is not so. He uses the row itself as a digit much like cutting notches on a stick. The difference in bases is a finite property that occurs digit-wise, but does not hold true when you take the entire sets into consideration independently of the base (element by element).
@Ketil: ”
“Also, I’m not arguing that any sets have the same or different cardinality.”
“Also, [0,0.5] does not have the same cardinality as [0,1.0] when the first set is a subset of the other. …”
Now, obviously you don’t see how you’re wrong about the mathematics, but do you at least see how you contradict yourself?”
I should have been clearer and you’re right that it is a contradiction as I have written it. Sorry about that. My first statement was in relation to reals and naturals. I don’t want to debate here whether or not they have the same cardinality. My second statement was not related to the first. It relates to what Cantor is doing incorrectly.
@pjb:
“There is no “map by digit between base 2 and base 1.””
There is. You will have log(x) base 2 digits for x base 1 rows. That’s a relationship that happens at the finite digit level and is required to build the diagonal, but is not valid when you take the whole set into consideration (fallacy of composition). IOW, these are two different mappings and is where the bogus contradiction stems.
@Everyone: What Cantor has proven is that B = [0,0.5] has a different cardinality than A = [0,1.0] ONLY while set B is based on A. In other words, the elements before 0.5 are identical in both sets. They are mapped one to one. Doesn’t matter if you can map them differently. That’s not the issue here. Cantor is using a DEPENDENT mapping. As long as that dependent mapping exists, the two sets have different cardinality until the two sets are made independent (where one would apply a transformation, scaling or whatever else).
In Cantor’s argument, the finite digits are what creates the dependency between the two axis. Reals don’t even enter the scenario.
Also, I’m willing to be wrong, but I haven’t seen anything that contradicts my argument. In fact, everyone agrees with what I’m saying aside from the implications. If I can be shown how I’m seeing the implication wrongly, then I’ll gladly admit it.
“Also, I’m willing to be wrong”
That’s great – but you have a long way to go before what you say can be considered close enough to be wrong – it’s “not even wrong” now.
Cantor’s argument basically says this: no matter how you careful you are when you arrange all the numbers in [0,1] into a countable list, you fail, because a cleverly simple (perhaps that’s the part that confuses you) argument shows that missed at least one. No different bases, no “dependent” and “independent” sets.
Why don’t you spend your time trying to square the circle?
You keep harping on “dependent” sets and such. But set theory has no notion of dependent sets the way you’re using the term; and the implications that you’re drawing from the “dependent set” notion are just plain wrong.
The set [0..0.5] has the same size as the set [0..1]. Both sets already exist, by definition. You’re not creating the set [0..1] by pointing out that there’s a one-to-one relationship between [0..0.5] and [0..1] – you’re just defining a relationship. No matter how you chose to define a relation, it doesn’t change the set that it maps to. Whether you map [0..1] to [0..0.5] with the relation { (x, x/3) }, or [0..2] to [0..0.5] via the relation { (x, x/4) }, the set [0..0.5] remains exactly the same, with the same cardinality, the same members, etc.
You’re relying on the idea that relations construct sets, which is wrong. You’re using that error to create a weird version of dependent sets which is worse than wrong – it’s just completely invalid. According to your theory, you can’t define the cardinality of any infinite set, because it varies depending on which relation you’re using on that set. In fact, your notion means that a given set doesn’t even have identity operations unless you know the relation that defined it – and two sets with the same values are not if they’re defined using different relations.
That’s worse than wrong. That makes the entirety of set theory pretty much entirely useless.
Vorlath, it might help to provide some precise definitions of the terms you’re using, because certain of the words fundamental to your argument are either not standard mathematical words, or seemingly not used in the standard way. Here’s a short list to start with:
dependent mapping;
independent (and dependent) sets;
cardinality.
Without precise definitions of your terms, you’ll end up just talking past everyone.
@51 “@Pelli: Your statement is only true with dependent sets. When you use the stated relationship, you are modifying the properties of the original set to create a new set. So it’s expected that you will get a “contradiction” between the two sets. Remove the relationship between elements and the contradiction disappears.”
I am proving no bijection exists by contradiction: Suppose there is one. Then I can exhibit an element not included in your bijection, so it wasn’t a bijection after all. Hence there cannot be a bijection. Which exact sentence here is wrong?
It is true that my exhibited element will depend on what supposed bijection you are giving be, but that isn’t a problem at all. I don’t really see what you mean by “dependence” here. Are you getting confused by the fact that the bijection is “specified”? Well, that’s how proof by contradiction works.
By dependent set, I mean using a set that exists based on a relationship to another set. A specific mapping that not only determines the “transformation” or criteria, but also how many elements are found in the other set. (Exact one to one mapping does not count as it changes nothing).
Independent sets are sets that are free to be mapped to each other in any way you like, especially allowing someone to map them one to one. If you see things like “Set K only contains n where n is not in f(n)”, that is NOT an independent set as set K cannot exist independent of f(n) as long as the quoted relationship exists. That set K could theoretically exist on its own is irrelevant as that is not the issue. The issue is removing any relationships so as to enable one to one mapping.
Cardinality is if you can map all elements of one set to another and only applies to independent sets because otherwise, you would already have a pre-imposed mapping and are not free to map them one to one.
@Mark:
Of course it does. Your power set is constructed from another set, is it not? It has a mapping, right? Try removing this initial relationship and remap them.
I agree. This is my point. It’s been remapped from it’s initial relationship. The original mapping has thus been discarded (or modified). Cantor does not discard the original mapping, but imposes one that is not one to one.
That’s irrelevant because Cantor isn’t using it that way. I know you can do this or that. But Cantor is doing ONE very specific thing. He is CREATING a new set based on another. Or if you prefer to treat all sets as pre-existing, then he is using ONE very specific mapping that is intentionally not one to one.
So he is doing the equivalent of mapping [0..0.5] of subset B to [0..0.5] of set A. Doesn’t matter that other mappings exists. Big deal. I know that. Everyone here knows that. In fact, this is my argument. Without this particular mapping, Cantor’s argument falls apart.
Not my theory, Cantor’s. What you said is exactly the reasoning Cantor uses to say that the cardinalities are different. He uses one very specific mapping to show how cardinalities are different. I agree with you that the “theory” is nonsense.
Two sets with the same values are not what? Identical? They can be, even if defined via different relations. That’s not the issue though. It’s the imposing of a relation that is not one to one and then asking people to show a counter-example while retaining this skewed mapping. It’s astonishing how many people ask for this bogus counter-example.
@Pelli:
I know, but there is no contradiction. It only looks like one. The kth element uses base 2 digits while f(k) uses what is essentially base 1 like notches on a stick. Comparing different bases SHOULD result in one axis being able to represent more elements than the other when comparing finite digits. But the infinite case does not hold without using the fallacy of composition.
As I’ve said plenty of times, comparing bases via digits does not mean that cardinality of base 3 is greater than the cardinality of base 2.
If your “proof” held, then you would also prove that base 3 has higher cardinality than base 2 because this example is equivalent to your setup.
@56:
If I understand you correctly, there are three bits to dependence of sets, a set A, a set B, and a surjection f from A to B (such that y in B implies an x in A such that f(x) = y), so that B “exists”/depends on A and f for it’s existence.
In that case, Cantor is saying that N and R are fundamentally independent, because no such surjection f can exist between N and R.
You are right in that the proof relies on a formulation similar to “Set K contains n if and only if n is not in f(n)”. You may not find that OK. But another way of looking at it is that Cantor is trying to create a function in a much bigger domain. He is saying “There exists a function K from RN to R such that K(f) is not in f(N)”, (where “RN” is the set of all functions from N to R) and then attempting to prove this by showing how to construct such a function. He’s not claiming that K is an injection or surjection or even unique. Just that at least one function K exists with that property. Clearly, for a given f in RN, K(f) depends on f, but that’s sort of standard with any function.
A bijection F between R and N implies that no such function K exists, for if it did then K(F) would have to be in F(N), since F(N) is R, and K(F) is in R. so the proof of the existence of K is proof that no such bijection exists.
Now, do you disagree with my reasoning so far (specifically, do you agree that if such a function K exists, then no bijection from between R and N exists, even if you believe that Cantor failed to properly demonstrate siad function K)?
It is sad to see so many fine mathematicians arguing with a fool. He know a lot of our words, true. But he uses them in unfamiliar ways. Like an aphasic.
Vorlath’s incorrectness does not harm us. Let us leave him be, with his happy little disproof of Cantor’s diagonalization argument. He will never publish it. The foundations of our mathematics are secure.
It does a disservice to our dignity to bicker with a child as if children ourselves.
@37, who said:
This can’t be true without another condition, can it? How can {26, Pi} be mapped onto [0,1]? For that matter, how can {26} be mapped onto {26, Pi}? I assume the missing condition is either that the subsets not have zero measure, or that the subsets have non-zero measure (which may not be equivalent conditions in the presence of AC, if I understand correctly?)?
There’s no valid Math in this region of lesser crackpotia.
This is, once again, a problem in Psychology. Or pair of linked problems:
(1) What is it about Euclid, Darwin, Cantor, and Einstein, that they have in common that attracts armies of the ignorant, over-confident, and deluded to attempt to kill them as father figures, or hated authority? There are so many other great thinkers who attract no loons, by comparison. Who’s trying to debunk Archimedes, or Fibonacci, or Euler?
(2) What drives the twisted minds and shattered psyches of those who, respectively, try to Square the Circle, Deny Evolution by Natural Selection, Squash Infinities into a finite box, or make Minkowski Space Euclidean?
This makes no sense. Each row is an infinite digit sequence. Each row has countably infinitely many digits. The digits in each sequence (i.e. the columns) are enumerable. The sequences (i.e. the rows) in a countably infinite set are enumerable by definition. Neither of these enumerations is “base 1,” whatever that means. The base used in the enumeration is completely irrelevant. The base of your digit sequences is completely irrelevant. In fact, you don’t even have to think of them as numbers. By the diagonal argument, a countable set of these infinite digit sequences will necessarily exclude at least one sequence, so the set of all infinite digit sequences (of any base) is larger than any countable subset. Notice that we haven’t even described any numbers yet.
NOW, if you wish, and if you are careful to exclude redundant digit expansions, you can create a one-to-one mapping between a set T of infinite digit sequences and the real numbers. Taking care again with the redundant digit expansions, you can still use the diagonal argument to show that any countable subset of T will necessarily exclude at least on sequence also in T, and so the set T is “larger” than any countable subset. Since T is a bijection with the reals, and each countable subset is, by the definition of countable, a bijection with the natural numbers, the reals are then a “larger” set than the naturals.
Disproving Cantor is easy: just assume the axiom of choice doesn’t hold. Or, you can just throw out the axiom of infinity and make all sets finite.
You might do some damage to the rest of mathematics, but no big deal, right?
Oh, it’s been a while. I forgot that Cantor–Bernstein–Schroeder shows you don’t need choice to prove the reals are larger than the naturals. Still, take enough axioms away, and we can make it not work. Clearly, it’s the only logical thing to do!
@56: “I know, but there is no contradiction. It only looks like one. The kth element uses base 2 digits while f(k) uses what is essentially base 1 like notches on a stick. Comparing different bases SHOULD result in one axis being able to represent more elements than the other when comparing finite digits. But the infinite case does not hold without using the fallacy of composition.”
Are you thinking f(k) is a number? f(k) is exactly the kth element, which is a string. There is no basis. I’m proving things about strings. You can think of them as having symbols A and B instead of 0 and 1. Whenever you give me an infinite enumerated list of strings, I can point to a string that is not there. It has got nothing to do with different representations of strings, whatever that is. I’m not even doing anything with the sets, you’re the one doing the work when you give me your bijection. I’m just pointing at an element that’s not included in the image of your map. Whether a string is an element of a set or not does not depend on where the set comes from.
1. Do you agree that a bijection between n and the set of infinite A,B-strings, is an enumerated list of all the A,B-strings?
2. Do you agree that if two strings differ at some position, then they are different?
3. Do you agree if an element is different from all elements on the list, then it is not in the list?
4. Do you agree that given a list, I can construct an element different from every element on the list and hence not in the list?
5. Do you agree that if any list is missing some element, then there is no comlete list?
Please be very specific about what you agree and do not agree with, otherwise we’ll just be talking past each other.
Here’s an example of how my construction works:
If the first ten elements of your list are
f(1) = A…
f(2) = BB…
f(3) = BBB…
f(4) = BABA…
f(5) = BAABA…
f(6) = BBBAAB…
f(7) = BBBBAAA…
f(8) = AABBABAA…
f(9) = ABABBABBB…
f(10) = ABBABABBBA…
then the first 10 letters in my counterstring will be:
BAABBABBAB…
Pelli, I’m not sure I understand how we know 4 is true. Could you explain?
@Blaise:
Yeah.
I agree this is what he’s trying to show. But he fails.
I’m not sure where to begin. You’re using the power set, but it’s the same issue.
So let me extract a few sections again and it might become clearer. What you’re doing is STATING that f is a bijection, but then you use f by setting it up as a mapping that is not one to one. When you use a mapping that is not one to one, elements are left out and it’s expected that you can find one of those left out elements. Hence, no contradiction.
So K(f) has two possibilities, correct? Either it IS in f(N) or it is NOT in f(N). That’s base 2.
But then you go through all N (or the other set, doesn’t matter since it’s assumed that a bijection exists, this is why you use f as an index I presume), correct? Since you can’t leave any of those out, it’s base 1.
So f(N) vs. N sets up a mapping between base 2 and base 1. This is not a mapping that is one to one. The result you got is an expected one, not a contradiction.
@64 Pelli:
You’re imposing a relationship as to how many f(k)’s there are relative to k through the use of finite digits. That means you’re using different bases. k indexes into a digit that uses base 2 while f(k) indexes into rows which is an enumeration (base 1). You can’t just handwave this away. Remove the relationship between finite digits in your “proof”, or use the same base.
Only with finite digits. Fallacy of composition when using infinite strings.
What you describe is an expected result for the specific mapping you are using which is not one to one. Use a one to one mapping like using the same base and your argument falls apart. You even state that you’re using different bases. An enumeration is base 1 since there is only ONE option to include each and every element in that set. But each digit has TWO options for the other set. It’s well known that you can’t compare bases and say that base X has higher cardinality than base Y.
The flaw in all these “proofs” is the same in that it’s mapping digits of different bases (or the equivalent version of it) one to one instead of mapping elements one to one. If you map digits, you must use the same base.
No. What you describe is a mapping that is not one to one and cannot ever be a bijection. It’s stated right in your definition. A,B strings use base 2 since there are two choices. And an enumeration as base 1 by definition. If you used base 2 vs. base 3, it would be obvious, but somehow, just because you use an enumeration, you think the base just disappears. Each axis or each set must be represented using a base. State what they are. In effect, everyone here is trying to convince me that base 2 has higher cardinality than base 1 (or the equivalent of base 3 having higher cardinality than base 2). So it’s not even MY argument. There is a contradiction between the conclusion of Cantor’s argument and what is known about infinite sets when comparing different bases. One of them has to be wrong. Pick one.
Yes.
Yes.
Not even close. The process you use to create this new element only works with finite digits. It does not extend to the case of infinite digits unless you use the fallacy of composition. Besides, it doesn’t even work in the finite case if you use the same base demonstrating that you’re using a mapping that is not one to one.
Yes.
@pjb:
The digits are base 2.
There’s your base 1.
So you’re mapping base 2 digits to base 1 rows. Fascinating that if it were base 3 compared to base 2, there would be no issue. But base 1 doesn’t need any specific digit for you to see. It can use anything at all and it uses the rows themselves as the vertical digits in this case (like notches).
So when you construct your diagonal, the row index can only use base 1 digits (notches). However, the string can use base 2 digits. If you map base 1 digits to base 2 digits in this manner, then base 2 will always be able to represent more elements than base 1 when using the same amount of digits. However, this does not hold up when using infinite sets. Otherwise, Cantor’s argument would mean that base 2 has higher cardinality than base 1 (or any base higher than the other would have higher cardinality).
Correction: “f(N) vs. N” should be “element of f(N) vs. enumeration of N (or f(N))”
Vorlath, thank you for your cooperation.
I think you’ve misunderstood the common definitions of what a set and a bijection are.
Also, reading through what you said to Blaise, I think you’ve misunderstood how the proof works. (“So let me extract a few sections again and it might become clearer. What you’re doing is STATING that f is a bijection, but then you use f by setting it up as a mapping that is not one to one.”)
What you say there is correct. We prove there is no bijection, by SUPPOSING (stating) there is one. Then we go on to show that it is not one-to-one. This is a contradiction, so the assumption that f existed was false. Note that our process of showing the failure DOES NOT ALTER f. We’re NOT taking a bijection f, changing it to make it fail, and then say it failed so it’s a contradiction – we ARE taking a bijection f, showing that it fails, and say that is a contradiction.
I still don’t understand what you mean by basis – do you mean that “base k” is k^N (infinite strings of k symbols)?. In that case what we’re trying to convince you of is that “base 1” = N is smaller than “base 2” = 2^n. However, this is not equivalent to “base 2” being smaller than “base 3” which is false. In fact k^N is the same size for all finite k > 1.
An infinitely-long conference is going to be held on disproofs of Cantor’s theorem. The conference begins Friday at noon, and each of the infinite number of lectures lasts one hour.
Vorlath approaches the conference organizer and asks to present a lecture. The organizer says, “I’m sorry, but the entire schedule is full.” Vorlath turns is about to leave, when the organizer says, “Wait, I think there’s something we can do.”
He reschedules the Friday noon talk to 1PM, the 1PM talk is rescheduled for 2PM, the 2PM talk is rescheduled for 3PM, and so on down the line, with Vorlath schedule to speak at noon. Thus Vorlath’s lecture can be accommodated in this infinitely-long anti-Cantor conference, despite the entire agenda being full already.
“That’s still no good,” says Vorlath. “You see, I have an infinite number of disproofs of Cantor, and I will need one hour to present each proof.” Vorlath regretfully turns to go, but the conference organizer stops him again. “I still think we can fit you in,” he says.
The talk that had been rescheduled for 1PM is now rescheduled for 2PM. But the talk that was scheduled for 2PM is now rescheduled until 4PM. The talk at 3PM is rescheduled to 6PM, 4PM to 8PM, 5PM to 10PM, 6PM rescheduled to midnight, 7PM rescheduled until 2AM the following morning, and so on down the line.
Thus, even though Vorlath has an infinite number of disproofs to present, and the conference schedule was already full to begin with, he can still present each of his infinitely-many lectures.
Isn’t infinity fun?
The value here, is in recognizing mania. Vorlath has latched on to a meaningless issue: an enumerated list is different from a number. This is true. And enumerated list is in fact, different from a number. All the nonsense about bases is obfuscative for no important reason.
None of it suggests, in any way, that we cannot make an enumerated list of numbers. Or that a diagonalization argument on that list does not produce an element previously not on that list.
The poor organizer of the infinitely-long anti-Cantor conference has another problem: After an infinite number of phone calls, he has discovered that ALL of the infinite number of conference participants each have an infinite number of proofs to present, each of which requires a one-hour lecture. The conference is postponed indefinitely while he tried to figure this out.
Suddenly, he has a eureka moment: Each of the conference participants is assigned a number, beginning with 1. At noon on the first day of the conference, presenter #1 may give his 1st lecture. At 1PM, presenter #1 gives his 2nd lecture. At 2PM, presenter #2 gives his 1st lecture. At 3PM, presenter #3 gives his 1st lecture. At 4PM, presenter #2 gives his 2nd lecture. At 5PM, presenter #1 gives his 3rd lecture. At 6PM, presenter #4 gives his 1st lecture. At 7PM, presenter #3 gives his 2nd lecture. At 8PM, presenter #2 gives his 3rd lecture. At 9PM, presenter #1 gives his 4th lecture. And so on in this fashion for ever and ever, amen.
Subsequently, the organizer realized that this wouldn’t work after all. All of his careful planning depended on one thing: being able to map each of the conference participants to a pre-assigned natural number. However, he discovered much to his chagrin that all of the participants presenting disproofs of Cantor were completely irrational. And everyone knows you can’t denumerate irrationals with the set of natural numbers….
Thanks, I’ll be here all night.
I think Vorlath’s trouble is even simpler than has been hypothesized: he doesn’t understand proof by contradiction. Cantor’s argument relies on assuming that something is a bijection and then discovering that it is not. (as pointed out by Pelli @68) This is, of course, a valid proof technique. I think Vorlath believes that our discovery of a contradiction invalidates the *entire* proof, not just the later assumption.
If that’s the case, Vorlath, I sympathize: It’s a pretty weird concept when first encountered. You should consult other examples of proof by contradiction to see how it’s done.
Vorlath,
which, if any, of the following propositions do you consider to be true:
1. the cardinality of the set of natural numbers is greater than the cardinality of the set of reals.
2. the cardinality of the set of natural numbers is less than the cardinality of the set of reals.
3. the cardinality of the set of natural numbers is equal to the cardinality of the set of reals.
If it’s anything but 2, please describe why.
As another exercise, please answer the same question, except that instead of “reals,” substitute “integers,” and describe any answer other than 3. Are the set of integers and the set of natural numbers independent? If they are independent, then what if I define the integers as {floor(n/2)*((1-2)^n) | n is a natural number}? Are the integers suddenly transformed into a dependent set, or have I just made an invalid dependency because -1 is not a natural number?
I still think that this is really about Psychology, rather than Math. I’ve spent HUNDREDS of hours arguing about people with “idées fixes” about Euclid, Darwin, Cantor, and Einstein. Most of the time, evidence does not change their mind. Logic does not change their mind. One in a LONG while, I do get to see the light go on over their head. I’ve dropped out of some email groups I’d been in for years, because I just burned out on suffering fools gladly. My bad.
I would like to quote the so-called ‘Myers’ Axiom’: ‘You can’t use reason to talk someone out of a position they didn’t use reason to arrive at.’
But anyway, allow me to attempt a derailing of the discussion at hand by proposing the following topic:
I have noticed, in my various encounters with persons of the crankish persuasion, that there appears to exist several levels of crank, each a little more educated than the next. For instance, one has the crank who does not believe in infinite sets, whose counterargument to any explanation is ‘[a given infinitary construction] would never finish.’ Then, further up along the ladder of education, one has cranks such as our present Mr. Vorlath (begging your pardon if you are a ‘Ms’), who (apparently) does not accept the existence of different ‘sizes’ of infinities (which we mathematicians know as ‘cardinalities’). And finally, at the boundary of academically acceptable mathematical activity, one has the fellow who, while possessing a doctoral degree in algebra (e.g.) occasionally shows up at the algebra seminar and asks the lecturer really braindead questions (about the group (Z/2)^2; ‘what scheme structure do you apply to this?’).
Have you, ladies & gentlemen, any thoughts on the topic?, do you know of any results or research on the classification of cranks?, and finally, do you have any amusing stories to share about encounters with such personalities?
There are various flavors of constructivists who are definitely not cranks in terms of mathematical ability. Some of them get real crankish about mathematics that does not follow their rules. Part of it is their views were extremely unfashionable for a time, as in, tenure and grants and mere publishability were made unfairly difficult for them. But part of it is they really do get crankish about things outside their philosophy.
As for math department cranks, UC Berkeley once admitted a seriously incompetent grad student who Did Not Get Anything. His presence in any class or lecture was usually a disaster, as he couldn’t help but ask psychobabble crackpot questions. The first year Prelim Exam study group that year deliberately held secret meetings just to avoid him.
But one question stands out, genius of a different order. Robert Griess had recently constructed the Monster, and when visiting, gave a general mathematics audience colloquium talk. Of course everyone went, what an event! Along the way, Griess mentioned various aspects of his construction, including how the known theory of the Monster had implied that if there was a 196883 dimensional representation, he could probably reduce it down to six parameters that had to be very carefully chosen. Which he did, and the rest was history.
Towards the end, he discussed the relationship of the Monster to the other sporadic simple groups, mentioned that the 26 sporadics split into 20 that were subquotients of the Monster, and 6 unrelated groups, which he was calling the “pariahs”. At the end, during the question and answer session, departmental crackpot got called upon (no one thought to run interference for Griess), and asked the immortal question: “is there a relationship between the six parameters and the six pariahs?” Despite the fact that very few people really followed Griess, everyone cracked up laughing, and Griess certainly was flabbergasted.
@Pelli:
No. You think that’s what you’re doing but you’re not. You are supposing that there is a bijection, but then DEFINE that bijection to not be a one to one mapping BEFORE the conclusion. Before the “contradiction”. Then you use this mapping that is NOT one to one to come to the conclusion that this mapping is not one to one. Circular logic.
You may also look at it another way. You assume there is a bijection and then assume a particular mapping for that bijection. At the end, you find out your mapping wasn’t actually one to one. However, it’s trivially obvious that the particular assumed, chosen and arbitrary mapping is not one to one. There’s no need to work through anything.
It doesn’t matter if the mapping you chose isn’t one to one. You have to prove that there is NO one to one mapping at all. Unfortunately, you believe this is what you have done.
It’s very difficult to show the flaw in circular reasoning because it goes round and round, especially when one doesn’t see that the bijection is defined to not be one to one. Then you come back and say “it’s assumed to be one to one”. Then I say “No, when you use the mapping, it is one particular mapping and NOT a bijection at all”. Then you say “This is what we show through the conclusion that it isn’t a one to one mapping”. Then I go, “no, BEFORE the conclusion. You actually define your own custom mapping. It may or may not end up being a bijection though it’s trivially obvious it doesn’t map one to one.” Then you say… on and on.
How do I break the cycle? And everybody reading this has already heard your side. They’ve seen it and are accustomed to it. But no one has yet seen what I’m describing. So I look crazy! That’s fine. I’ll keep trying.
Agreed.
Actually, this is exactly what you are doing. You’re assuming a bijection and then using it in a way that is not a bijection BEFORE the conclusion.
You’re essentially saying the following.
1. Assume X is 4.
2. Define X as 5 in a second assumption.
Then you show the contradiction that 4!=5 and thus X cannot be 4.
That’s what you’ve done. It’s circular logic.
No, you make it fail BEFORE the contradiction. You use f as a mapping that is not one to one when you construct (or define) K.
Also, the construction of K is using the fallacy of composition when using infinite sets.
I don’t think so. Base K is any string (infinite or otherwise) where the digits can use K symbols.
This is what your are “proving” though. The power set “bijunction” mapping you’re using is an equivalent setup. That’s why either |base 3| > |base 2| or your proof is wrong. It’s one or the other.
@AnyEdge:
Not if you use the list as notches that can be counted.
As an aside, please explain how you would select a particular row without using an index and where you cannot count anything (as that would create number as well).
@Clayton:
There is no discovery. The bijection “proof” has two assumptions.
1. Assume there is a bijection.
2. Define the bijection to be a mapping that is not one to one.
Then it goes on to show what appears to be a “contradiction”.
There is no discovery. Only circular reasoning.
I’m saying the contradiction is ASSUMED at the start by the way K is defined or the way the grid is defined depending on the version of the “proof” used.
@Shawn:
On this blog, I’m operating on the assumption that |R| > |N| for the sake of argument.
Also, my answer isn’t clear cut, but it’s definitely not 1.
As to the other two, it depends on how the elements are defined. If you only use independent elements in the set N, then |R| > |N|, but if you handle more esoteric definitions of naturals like X is the center of the set N, then |R| = |N|. When naturals are defined this way, they are actually reals. For example, all reals can be represented by their relative position along the set for [0,1.0). It’s simply a percentage. So each real is defined as a ratio between its position and the size of the set. If you define a natural as being located in the center of the set, then it too is defined relative to the size of the set. The two sets are then one and the same. You don’t even need to map them. But if you don’t use or allow those kinds of numbers, then |R| > |N|.
If you allow esoteric naturals (not sure what they’d be called), then you can do stuff like:
R = {X >> (log2(|Z|)/2) | X ∈ Z}
(>> is a binary shift, but the base isn’t important).
And you have a one to one mapping between naturals and reals.
From each other? Sure.
N is still independent, but your new set is dependent on N if you continue to use the mapping in the future. If you now throw away the definition, but keep the set, then it’s independent. You may also make them independent if you’re allowed to replace or update the mapping.
@Jonathan:
I know what you’re saying, but that’s not it at all. I can’t get anyone to see what I’m describing. If they saw it, that’d be one thing. But so far, I can’t even be right or wrong. No one has yet talked about what I’m talking about.
Mark is the one that came closest to seeing what I was talking about. But what normally happens in cases like this is that they explain it in a different way with the assumption that I don’t understand. But there isn’t a single thing in this thread I haven’t seen and understood a million times over.
So what’s one to do but appear crazy until the day comes when someone takes a chance and looks at what I’m describing instead of assuming I don’t understand.
BTW, I’m hoping I’m wrong. Just for the record. But I haven’t seen anything yet that indicates I’m wrong.
@78: Allow me to quote myself at #49.
Moreover: “BTW, I’m hoping I’m wrong. Just for the record. But I haven’t seen anything yet that indicates I’m wrong.”
No, you’re not, and yes you have.
Your ‘hope’ that you are wrong is perhaps the most transparent rhetorical device since the last time a Republican spoke publically. You do not ‘hope’ that you are wrong. You believe, with great conviction, that you are right, and bolster yourself with great fortitude against arguments to the contrary, whether they be right or not.
You have been presented with multiple very good explanations as to why you are wrong, but you steadfastly refuse to accept them, for reasons which are entirely related to your lack of understanding of set theory. You say ‘you haven’t seen them’, but you have, only you do not understand what it is you see.
There are people who try to disprove Cantor? The world never ceases to amaze me.
A couple years ago I had an amusing discussion with someone who tried to dissuade me from Cantor’s diagonal argument arguing that it was disproven by Marx’s philosophy. Yes, really.
“You are supposing that there is a bijection, but then DEFINE that bijection to not be a one to one mapping BEFORE the conclusion.”
“You may also look at it another way. You assume there is a bijection and then assume a particular mapping for that bijection.”
“You’re assuming a bijection and then using it in a way that is not a bijection BEFORE the conclusion.”
No. When I say we are given a bijection, then the bijection has been defined. You give me an infinite sheet of paper saying “f(1) = …., f(2) = …., f(3) = …., etc”. That is specifying f uniquely and at that point it is already decided whether f is a bijection (every element appears exactly once on your paper) or not (do you agree?). Then I will just say “hey, I’ve got an infinite slip of paper where I’ve written an element that’s not on your paper”. This does not alter f, as you agree, and there is no ‘redefining’, ‘reassuming’ or ‘wrong using’ of f going on.
“No, when you use the mapping, it is one particular mapping and NOT a bijection at all”
This is the point. A bijection is a function. It is a specific function. If I show this specific function misses an element, then it is not a bijection. You seem to think that a bijection is some magic entity that can change according to what I do.
“You’re essentially saying the following.
1. Assume X is 4.
2. Define X as 5 in a second assumption.
Then you show the contradiction that 4!=5 and thus X cannot be 4.”
No, it’s more like this:
Proof that no even odd number exists: Assume X is an even odd number. Since it is even, it is divisible by 2. Then it is not not divisible by 2, so it is not odd. Contradiction. There is no such X.
What you’re saying sounds to me like “You are assuming X is even and odd number, and then you show it is not odd. That’s a circular argument.”
“Base K is any string (infinite or otherwise) where the digits can use K symbols.”
OK, that’s a clear enough definition for me.
Here’s the reason the proof cannot show that base 3 is bigger than base 2: Suppose we have f mapping from base 2 to base 3. We want to show it is not onto (some element in base 3 is missed). So we try to do the usual thing, starting by putting down base 2 along the vertical axis. Unfortunately, since I have shown base 2 is larger than base 1, we cannot put them down one by one. We have to draw a solid line (real axis), and use every point on it. Now our grid isn’t a lattice anymore, and there is no diagonal, so we can’t do the diagonalization.
Basically, when we compared base 1 to base 2, the key thing that made it work was that the “length” of a base 2 string “is” base 1. So every letter in my counterexample could correspond to exactly one base 1 element, which in turn was supposed to correspond to a base 2 element. By choosing each letter to ensure it differs from that corresponding base 2 element, I made a string different from every base 2 element that was in the correspondence.
The length of base 3 elements is also base 1, and I have shown that it is smaller than base 2. Hence there are more base 2 elements than you have letters in your base 3 string, so you can’t use this idea to avoid them all.
If you really think base 3 > base 2, could you please write out a detailed proof?
Not quite on-topic, but here’s a nifty proof that the rationals have the same cardinality as the naturals:
I will prove that the set of (positive) rational numbers can be associated one-to-one with a subset of the natural numbers. Since it is easy to associate the natural numbers with a subset of the rationals (the reciprocal function will do), the demonstration below completes the proof.
By definition, each positive rational number can be expressed in a unique manner as p/q, where p and q are natural numbers with no common factors. Consider the string of symbols composed of (digits of p)/(digits of q), with a slash between the strings of digits. Now read that string (which is unique for every rational) as an integer in base 11, with the slash being the symbol for 10. There’s your integer associated with that rational number. QED.
Whenever someone says a concept is counterintuitive, what they are really saying is that their intuition is so lousy that it fails with this concept. That is why when my intuition doesn’t produce the right answer I change my intuition so that it doesn’t fail the next time I need it.
This is how you make your intuition better. When you have an intuitive idea, you test the idea with an algorithm, and then if the algorithm (i.e. a proof) is correct, then you can change your intuition to accommodate the correct idea.
I see intuition as a non-algorithmic method of arriving at an approximate answer to something. It might be correct; it might not be correct, but it is a lot faster than an algorithm. Of course there are many ideas that cannot be tested with an algorithm.
Why assume bijection? Any function is not surjective.
Holy cow! Here I thought this thread was going to stay on the lighter side; maybe score this goofball using John Baez’ crackpot index or something. Instead, you’re all blinding me with your formal logic and stuff. Too heavy for me, man.
@Pelli:
By using what could be called a sub-element of f(i), you are creating a new mapping that is not one to one. There is no reason to expect a mapping that is not one to one to be a bijection. Producing a new element (or set) K should be expected. No contradiction.
This is not what you are doing with K. What you are doing is like trying to figure out if X is 4. So you assume X is 4. Then you define X as 5. By showing that 4!=5, you’ve demonstrated a contradiction.
Do you at least agree that what I’ve just describe cannot be used in a proof by contradiction? If so, then this is the very flaw I see in your proof.
I think you mean that you have an enumeration of digits (which can be used as base 1) and are thus mapping digits of both axis one to one (I’ve agreed to this from the beginning). But this is not a requirement. It’s a personal choice and is a mapping that is not one to one on the elements.
How is base 2 larger than base 1? You mean one can represent more elements in base 2 with the same amount of digits, sure. But it has fewer digits. You can still list them one by one. Why would this no longer possible exactly?
Do you agree that taking the diagonal of base 1 and altering it in some fashion will not give a new number? And that since you can create a new number from the list of base 2 digits, then one set MUST have more elements than the other?
Good so far?
But consider what happens when you go to infinity with base 1. You can take the diagonal and you will create a new number. Not sure if I’m using this correctly, but doesn’t Dedekind’s theorem says that a proper subset MUST map to the set in order to be infinite?
Out of curiosity, when you do go to infinity, what is the ratio of digits in your diagonal vs. the number of rows?
I didn’t catch that last part. Avoid what?
@Vorlath,
“By using what could be called a sub-element of f(i), you are creating a new mapping that is not one to one. There is no reason to expect a mapping that is not one to one to be a bijection. Producing a new element (or set) K should be expected. No contradiction.”
What do you mean by sub-element? I am not creating a new map. I am pointing at the same unaltered f, except I have constructed an ELEMENT, a string S, such that S is not equal to any f(i). Hence f was not onto. I don’t understand what you mean by “producing … should be expected”.
“This is not what you are doing with K. What you are doing is like trying to figure out if X is 4. So you assume X is 4. Then you define X as 5. By showing that 4!=5, you’ve demonstrated a contradiction.”
No, I’m trying to prove X cannot be 4. Hence I assume the opposite, that X = 4. I then show this leads to X = 5. Obviously this is a contradiction, and since my logic is correct, the only thing that can be wrong is the assumption, which must be wrong. Hence X is not 4.
One realistic setting for this would be to prove X=4 is not a solution for X = 2X-3.
You could also consider the equation X = X+1. A proof that no such X exists could go along the lines of: Suppose there is such an X. Then X = X+1. This is a contradiction, so no such X existed.
“Do you at least agree that what I’ve just describe cannot be used in a proof by contradiction? If so, then this is the very flaw I see in your proof.”
Yes, what you described was not a proof by contradiction. But that doesn’t prove your point. Apart from what I just said, another objection is that “trying to figure out if X is 4” and “proving X is not 4” are different things. Only for the latter can you assume the opposite and prove it false.
“I think you mean that you have an enumeration of digits (which can be used as base 1) and are thus mapping digits of both axis one to one (I’ve agreed to this from the beginning). But this is not a requirement. It’s a personal choice and is a mapping that is not one to one on the elements.”
I don’t quite follow. I was questioning your claim that my proof for (base) 2 > 1 will also prove 3 > 2, by showing the key point where the argument would fail. If you want to prove 3 > 2, you’ll have to fix that somehow.
“How is base 2 larger than base 1? You mean one can represent more elements in base 2 with the same amount of digits, sure. But it has fewer digits. You can still list them one by one. Why would this no longer possible exactly?”
No, whether or not base 2 is larger than base 1 is what we are discussing, i.e. if there is a bijection between the infinite set of 1-letter strings (which is clearly equivalent to the set of natural numbers), and the set of 2-letter strings (which is clearly equivalent to the power set of the natural numbers and unclearly equivalent to the set of real numbers. We are not talking about the number of digits/letters either, since the strings are allowed to be infinite. What I’m saying is you can’t match up all 1-letter strings with all 2-letter strings (both of which there are infinitely many of) – there will always be at least one 2-letter string left over.
“Do you agree that taking the diagonal of base 1 and altering it in some fashion will not give a new number? And that since you can create a new number from the list of base 2 digits, then one set MUST have more elements than the other?”
I don’t know what you mean by the diagonal of base 1, or altering the diagonal. I agree that there are more (finite or infinite) 2-letter strings than 1-letter strings, in the sense that if you try to match them up there will always be 2-letter strings left over.
“But consider what happens when you go to infinity with base 1. You can take the diagonal and you will create a new number. Not sure if I’m using this correctly, but doesn’t Dedekind’s theorem says that a proper subset MUST map to the set in order to be infinite?”
When I try to do the “standard” diagonal argument with base 1, I will fail because I can’t pick a letter to make a string different from another given string at a given position – there is just one letter! Dedekind’s theorem says that if a set is infinite, then there EXISTS a proper subset that maps to the whole set. And if there exists such a set then the set is infinite.
“Out of curiosity, when you do go to infinity, what is the ratio of digits in your diagonal vs. the number of rows?”
In my diagonlisation proof that 2^n is bigger than n, I am making a construction which is not a process. My construction says “The kth letter of my string is the opposite of the kth letter in the string f(k)”. Although it is practical to think of it as choosing the first letter, then the second, then the third, etc., this actually does everything at once. Many misconceptions about infinite limits come from thinking that infinity is what you get if you do a finite thing at a time forever. As for your question – what I can say is that the first n letters in my string will only depend on the first n strings (rows) f(1), f(2), …, f(n).
” The length of base 3 elements is also base 1, and I have shown that it is smaller than base 2. Hence there are more base 2 elements than you have letters in your base 3 string, so you can’t use this idea to avoid them all.
I didn’t catch that last part. Avoid what?”
My construction of a counterexample avoids all the strings in the list by avoiding the kth string in the kth position. If you have more strings than positions, then you can’t do that. There will need to be a new idea introduced in order to prove that base 3 > base 2 (which is actually false).
To aid your understanding, here are some examples of sets that have bijections between them:
N (positive integers) and Z (integers): Map odd numbers 2k-1 to -k and even numbers 2k to k.
N (positive integers) and Q (rational numbers).
The reason Cantor’s diagonalisation fails is that the counterexample number you construct will inevitably be irrational and hence not a problem.
N (positive integers) and finite subsets of N.
Diagonalisation fails because the counterexample subset you construct will inevitably be infinite and hence not a problem.
By the way, I was reading the post on your blog and it struck me you are only talking about finite strings, or equivalently strings that begin with an infinite string of H’s. Those are indeed in bijection with N, as in the case of finite subsets of N.
Vorlath, I have a simple question. Does a bijective mapping exist between the set of natural numbers and the “independent” set of reals?
I’ve always understood cantor’s proof as follows
1) Assume there is a One-to-one mapping from the natural numbers to the reals
2) if it exists therefore you can write it out
example: 1->0.1000…
2->0.01000000…
etc. etc.
3) however, Cantor then goes, using the diagnalisation method (described well enough in the comments above for me to go over it again) to show that there is a real number that is not on that list at all, and therefore the mapping can’t have been complete
4) Since one-to-one mapping is how we define things being the same cardinality, since no one-to-one mapping exists (as shown above) then the cardinality of the Reals must be different to the cardinality of the Naturals
And since the mapping wasn’t specified
it could be any possible mapping
and therefore |R| =/= |N|
Which part of his proof do you disagree with, Vorlath?
@4 — Didn’t Dembski and Marks just publish something about that? 😉
“There is no discovery. The bijection “proof” has two assumptions.
1. Assume there is a bijection.
2. Define the bijection to be a mapping that is not one to one.
Then it goes on to show what appears to be a “contradiction”.
There is no discovery. Only circular reasoning.”
Assume that f:N –> R is one-to-one. List the values of f: f(1), f(2), etc. Use the diagonalization process to construct a number x so that x is not equal to f(n) for any n. Then f is not onto. Therefore any one-to-one function from N to R is not onto, so no bijection exists.
Does this clear up the issue?
@87 Pelli:
You use the notation for a power set, so I assumed the bijection was between an infinite set and its power set. Did I read that incorrectly?
If I read that correctly, then sub-element is when you say that n is only in K when n is not in f(n). I just said n is (or is not) a sub-element of f(n). I didn’t know what word to use because f(i) is both an element and a set depending on how you look at it. So I said sub-element.
But you are creating a new map. You’re checking if n is found (or not found) in f(n). That’s base 2 since you have two choices. And you check all f(i) leaving only one choice, base 1. This is a mapping that is not one to one. So when you construct K, f(i) cannot be a bijection even though you tried to assume it was. Then you go on to show the expected result how a mapping that is not one to one generates K that is not in f(i).
Yeah, sorry about that.
Actually, you define X as 5. It doesn’t actually come from anywhere. When you check n in f(n), nobody is forcing you to do that. You can use a different mapping.
Not trying to prove a point just yet. Taking it one step at a time.
So if it can be shown that your “proof” suffers from the same flaw, then it too would be flawed, correct?
Wait a sec. You actually agree that you’re proving |base 2| > |base 1|? And you can show how this does not imply |base 3| > |base 2|? If you can show this, I’d be satisfied. Oh wait, you’re talking about infinite base 2 digits used as a power set. Never mind. I already know the arguments.
That’s what I’m asking. What is the ratio of digits when you take the whole thing into account at once?
—
As far as base 1 and base 2, you see this as mapping |N| vertically to |N^2| horizontally, right? This would be equivalent to the power set, correct? So because you can create a new string not found in the list, then |N^2| > |N|. I’m good so far?
|N^2| is dependent on |N| through the digits. This is a very specific mapping. It’s certainly not a one to one mapping. This is known from the beginning. Use a different mapping and you might get better results. Just because you “prove” that one particular mapping isn’t a bijection doesn’t mean that no bijection can exist.
@88 Pelli: I understand bijection.
Does this really hold up past the fallacy of composition though? If you actually could build a diagonal using infinite digits, would you not produce infinitely many diagonals? If so, then these would not map to a single natural with finite digits, but to a proper subset of N which requires |N| digits. So we would not be able to conclude that any one of them is irrational by the mere fact that infinite digits are in use.
@89 Afgncaap:
Short answer is no. Don’t ask me to prove it 😉
@90 Michael:
I only disagree with:
@92 tux:
Nope.
The setup that the diagonalization process uses imposes a mapping that is not one to one. So your “proof” can stop before you even do anything. No need for a diagonal. Assuming that a mapping (known to not be one to one) to be a bijection is where the faux contradiction comes from.
@93, Vorlath, who wrote:
So, you reject Cantor’s method, but you do accept his result?
Truly this is a new and fascinating kind of crackpottery.
My intuitive feeling (definately nowhere near a proof, or even usefull in teh construction of one) of Cantor’s different infinities is that if you were able to enumerate the reals, you should be able to take a point on the real numer line, and then go on to the NEXT point. Since the real number line is a continuous line, this is mind bogglingly counter-intuitive, therefor my intuition is that Cantor is right.
Of course, my intuition has been mind bogglingly wrong before, so I’ve read and understood the proof and now I know for certain.
(Of course, my intuition assumes some kind of ‘nice’ probably monotone enumeration. Cantor proved that some kind of monstrously complicated enumeration which jumps back and forth and so fills the line will also fail.)
@96,
Sadly, the intuition is not quite true. Consider that the Real Line, R, is separable. The rationals are enumerable, but there is no ‘next’ rational point on the line.
@93 Vorlath,
“You use the notation for a power set, so I assumed the bijection was between an infinite set and its power set. Did I read that incorrectly?”
I’m trying to prove there is no bijection between the set of 1-letter strings and the set of 2-letter strings, which is roughly equivalent to both that there is no bijection between N and PN and that there is no bijection between N and R.
“If I read that correctly, then sub-element is when you say that n is only in K when n is not in f(n). I just said n is (or is not) a sub-element of f(n). I didn’t know what word to use because f(i) is both an element and a set depending on how you look at it. So I said sub-element.”
So in the proof for N vs PN, you do indeed construct a set K, which is an element of PN, such that n lies in K iff n does not lie in the set f(n), which is an element of PN. Hence K is different from all f(n)’s, which contradicts that f hits every element in PN. I’d prefer to talk about 1-letter and 2-letter strings though, since that way you don’t have sets of sets.
“But you are creating a new map. You’re checking if n is found (or not found) in f(n). That’s base 2 since you have two choices. And you check all f(i) leaving only one choice, base 1. ”
Apart from some of your reasoning, this is basically the reason that there is no bijection f between N and PN. It is not based on the fact that 2 choices is more than 1, because the analogy that 3 choices is more than 2 fails to produce an analogous proof for 3-letter strings vs 2-letter strings.
“This is a mapping that is not one to one. So when you construct K, f(i) cannot be a bijection even though you tried to assume it was.”
Exactly! You give me an f and claim it is a bijection, i.e. every element of PN, or equivalently every subset of N, is equal to f(i) for some i. I then say “look at K, you fail”.
“Then you go on to show the expected result how a mapping that is not one to one generates K that is not in f(i).”
No, then I go on to show that any mapping that is claimed to be a bijection has a counterelement K that is not equal to any f(i). So no bijective mapping exists.
“Actually, you define X as 5. It doesn’t actually come from anywhere.”
In my equation example, this is what goes on:
Proof that X=4 does not satisfy X=X+1. 1) Suppose that X=4 indeed satisfies X=X+1. 2) Since X=X+1, it follows that X=5. 3) X cannot be 4 and 5 at the same time, contradiction. 4) Hence our assumption was false.
The corresponding steps for me are: 1) Suppose there is an f that indeed is a bijection. 2) Since it is a bijection, we can list the elements and walk down the diagonal to get a counterexample. This is not hit by f, so f is not onto. 3) f cannot be both a bijection and not onto, contradiction. 4) Hence our assumption was false.
“When you check n in f(n), nobody is forcing you to do that. You can use a different mapping.”
f could be any mapping, but as I said f is not magic. When I assume there exists a bijection f, then f becomes a specific mapping. Put another way, do you agree that if you give me a SPECIFIC map f, I can use the diagonal argument to find a counterelement for that specific map? If so, wouldn’t you agree that no map f is a bijection, since every map has a counterelement?
“So if it can be shown that your “proof” suffers from the same flaw, then it too would be flawed, correct?”
If you can show me my proof suffers from a flaw, then it would be flawed. If you manage to point out a flaw in a proof for something else that I agree applies to an analogous point in my proof, then I will accept my proof is flawed.
“Wait a sec. You actually agree that you’re proving |base 2| > |base 1|? And you can show how this does not imply |base 3| > |base 2|? If you can show this, I’d be satisfied. Oh wait, you’re talking about infinite base 2 digits used as a power set. Never mind. I already know the arguments.”
In this line of argument, I’m claiming the following:
1. You CANNOT pair up 1-letter strings with 2-letter strings without there being 2-letter strings left over.
(2. You CAN pair up 2-letter strings with 3-letter strings without there being any strings left over.)
“That’s what I’m asking. What is the ratio of digits when you take the whole thing into account at once?”
The ratio between infinities is too complicated to discuss before we agree on what sets have the same size. It is easy to see that “intuitively”, the following ought to be true: inf + inf = inf and inf*inf = inf whereas inf/inf and inf-inf can be anything.
“Just because you “prove” that one particular mapping isn’t a bijection doesn’t mean that no bijection can exist.”
True. But if I prove that all mappings are not bijections, then indeed no bijections exist.
“Does this really hold up past the fallacy of composition though? If you actually could build a diagonal using infinite digits, would you not produce infinitely many diagonals? If so, then these would not map to a single natural with finite digits, but to a proper subset of N which requires |N| digits. So we would not be able to conclude that any one of them is irrational by the mere fact that infinite digits are in use.”
I’m sorry but I don’t understand what you are saying. The reason I can conclude that the number must be irrational is because I know the function is a bijection: I have something I know is a bijection between natural numbers and decimal expansions of rational numbers. You walk down the diagonal to find a decimal expansion for a number not hit by my function. Since I know my function hits all rationals, your number must be irrational.
Vorlath:
Are you in fact saying that R and N are NOT bijectable, and yet Cantor is STILL WRONG?!
Vorlath asks: “If you actually could build a diagonal using infinite digits, would you not produce infinitely many diagonals? ”
No.
You produce one diagonal. It’s the diagonal.
Similarly, you’re wrong about the proof involving “a bijection that’s not one to one”. It doesn’t. It shows that, if you attempt to define _any_ bijection- nature unspecified- between the rationals and the reals, you can always (by diagonal argument) define a real number that’s not covered by your bijection; so you can’t count the reals using rationals.
“@92 tux:
Does this clear up the issue?
Nope.
The setup that the diagonalization process uses imposes a mapping that is not one to one. So your “proof” can stop before you even do anything. No need for a diagonal. Assuming that a mapping (known to not be one to one) to be a bijection is where the faux contradiction comes from.”
No it doesn’t. For example, take a particular mapping, say f(n)=0…01000…., where 1 appears in the nth position. This is clearly one to one, and diagonalization will produce a string that was not on the original list. The process doesn’t force the map to not be one to one, but it shows that the map can’t be onto.
@95 Douglas:
It serves two purposes.
1. It avoids the crazies from coming out and asking for a one to one mapping.
2. It’s funny seeing how people who call others crackpot don’t understand (or never even think) how a proof can have the correct conclusion and still be bogus.
Oh and thanks for that reaction! Looks like I’m in good company here.
@98 Pelli:
But K uses a different mapping that f for its construction. All you’d showing is how this different mapping is not the same as f. You wouldn’t be showing that f is not a bijection.
K is built from ONE specific mapping. I want to know if ALL mappings can’t be f.
1. You assume that f is the bijection.
2. You then use a mapping where you take n from f(n). Call this mapping g. This cannot possibly be f because you’re using f in that very mapping. So we know ahead of time that g is not f.
3. g != f (this is a known fact)
4. You assume g = f.
5. You construct K from g.
6. K cannot exist in f
At this point, you say that f cannot exist, but there is no contradiction on f (existing). The only contradiction is between statement 3 and 4. The rest is a consequence of this.
You’ve proven that g!=f. But g is ONE specific mapping that is known to not be f.
So you know what it is even though you believe it doesn’t exist? WOW!
Not even close. The diagonal would require the use of a different mapping than f. So all you’d be showing is that this different mapping is not f.
You can ALWAYS show that your own mapping is not one to one. So the diagonal is POINTLESS.
But you don’t do that. You only prove that your custom mapping is not a bijection.
Suppose I do give you a mapping that I claim is f. Then you want to create a diagonal, but in order to create this diagonal, you need to use a custom mapping that USES f (so mapping g USES f). This is YOUR mapping. It is custom made. And can’t be f if it also uses f. So you take a DIFFERENT mapping than what I gave you and then say “look, it fails” Well, DUH! You always go back to a mapping that is known to not be f.
Only if you can create a SINGLE diagonal with infinite digits. I haven’t seen any proof of what you claim. I still don’t see how you get around the fallacy of composition.
@99 AnyEdge:
SHOCKER!!! C’mon. Seriously? WTF?
“But K uses a different mapping that f for its construction. All you’d showing is how this different mapping is not the same as f. You wouldn’t be showing that f is not a bijection.”
Let’s get things straight here: Let A = N and B = PN. I want to show there is no bijection f : A -> B. If you give me a function f, then I will exhibit an element b in B such that there is no element a in A for which f(a) = b. This will prove the function f is not onto and hence not a bijection. Agree?
Note how b is not a function. b is an element. f is still the same function as before.
“K is built from ONE specific mapping. I want to know if ALL mappings can’t be f.”
Yes, K is built from one mapping. WHICHEVER map f you give me, I can construct a counterelement for that specific map f.
“1. You assume that f is the bijection.”
Yes. I want to show there is a contradiction if f is a bijection. Hence I assume it is and show something goes wrong.
“2. You then use a mapping where you take n from f(n).”
No. There are no more functions flying around than f itself. I then define K = {n : n is not in f(n)}. This is a set. Not a function.
“Call this mapping g.”
There is no other map.
“This cannot possibly be f because you’re using f in that very mapping.”
I am not defining a new map. I would be wrong to define f in terms of f, but I’m not. I am assuming f is already defined, by some adversary trying to give me a counterexample.
“So we know ahead of time that g is not f.”
3. g != f (this is a known fact)”
4. You assume g = f.”
There is no g.
“5. You construct K from g.”
I construct K from f.
“6. K cannot exist in f”
K is not an element in the IMAGE of f, i.e. there is no n such that f(n) = K.
“So you know what it is even though you believe it doesn’t exist? WOW!”
Yes, I assume the adversary is correct and that there is such a map f. Then I will show that its properties make a contradiction. It’s similar to the argument “Suppose an omnipotent and benevolent god exists. Then there would be no suffering. Yet there is, so we have a contradiction. Hence there is no such god.” (Please don’t go into details about where this argument goes wrong.) Even if I don’t believe in a god, I can “show” that the claim “there is an omnipotent and benevolent god” is false by assuming god exists.
“Not even close. The diagonal would require the use of a different mapping than f. So all you’d be showing is that this different mapping is not f.”
No, the diagonal constructs an element not in the image of f.
” But if I prove that all mappings are not bijections, then indeed no bijections exist.
But you don’t do that. You only prove that your custom mapping is not a bijection.”
I prove that any mapping you give me is not a bijection.
“Suppose I do give you a mapping that I claim is f. Then you want to create a diagonal, but in order to create this diagonal, you need to use a custom mapping that USES f (so mapping g USES f).”
No, I create a set (or in my case, a string) directly from f.
“Only if you can create a SINGLE diagonal with infinite digits. I haven’t seen any proof of what you claim. I still don’t see how you get around the fallacy of composition.”
I don’t get this. You put all expansions down row by row. Then you draw a line down the diagonal. Now you have an infinite line with numbers on it. Pick a new expansion by making sure it is different from this line at every position.
I don’t like talking about sets and power sets and bijections, because there is lots of mathematical terminology that we may or may not agree on. Why don’t we talk about this instead:
Proof that you cannot write down all infinite A,B-strings row by row on an infinite sheet of paper: Suppose you can. Then I let you do it. I take your infinite sheet of paper, that looks like
ABBAAB..
ABABBB..
BBABAB..
BABABA..
……..
……..
and I take another infinite slip of paper, writing down the following A,B-string: In the kth position, I’ll write down an A if the string in the kth row contains a B in the kth position, otherwise I write a B. This string is clearly not equal to the string in any row, so it is not on the list. Thus your list is not complete.
Could you please point out where exactly my proof goes wrong?
@103. Pelli, my intuition says that ANY combination of ABs will be found on the first page, since it is infinite. Help me understand WHY your constructed string’s not there.
Molly the not-so-mathy-one
@104: This is where intuition fails. You think that since there are infinitely many rows and infinitely many A,B-strings, then they should match up. This is not the case though because there are many different infinite cardinalities (“set sizes”). (Colloquially, two sets are the same size if you can match up their elements. One set is bigger than the other if however you try to match up the elements there are always elements from the bigger set left over. This works as you’d expect for finite sets and extends to infinite sets without introducing any notion of infinite numbers, whatever that is.)
To get a string that’s not in the list, I do not use counting. Instead, I construct it to make it different from all the strings on the list: The nth letter in my string is chosen to be the OPPOSITE of the nth letter in the nth string.
So if the list looks like this:
A…
*A…
**B…
***A…
****B…
…
(where * denotes A or B)
my string will look like this:
BBABA…
It differs from the 1st string in the first letter, the 2nd string in the 2nd, etc. Hence it differs from all elements, and is therefore not on the list.
@104:
The reason why it isn’t there is because you’re going down the list row by row and systematically making the constructed string different than the string in each row in such a way that it is guaranteed to also be different than the strings in all the prior rows.
Put more long-windedly, your job is to make a string that is *not* already on the list. The way to do that is to start with the first string in the list and make your string different than that one. So you start with row 1. Making the first character of the constructed string not equal to the first character of the row 1 string is sufficient to ensure that the constructed string doesn’t match it. So far, so good. Now proceed to row 2. You need to do the same thing, but the catch is that you have to do it in such a way that the constructed string is now guaranteed to be different than the row 1 string *and* the row 2 string. In other words, you can’t go back and change the first character of the constructed string because you might be changing it *back* to what it was in the row 1 string. So instead you change the *second* character of the constructed string to be different than the *second* character of the row 2 string. Now the constructed string is guaranteed to be different than both the row 1 and row 2 strings because the first character in the constructed string doesn’t match the first character in the row 1 string and the second character in the constructed string doesn’t match the second character in the row 2 string. Imagine going through the same process for each row and it should be at least relatively plain (provided I explained it well at all) that the constructed string *must* be different than all the strings in the list.
…and Pelli beats me to it. Curses!
@Rilke’s Granddaughter #104,
If the strings were all finite size, then your intuition would be correct. However, all the strings are infinitely long. The key thing to know is that when it comes to infinity, our intuition doesn’t do a very good job describing what is actually happening. Infinities are just plain weird. When it comes to sets with an infinite number of elements, you can have two sets, and it can look like one of them is obviously smaller, like the counting numbers (positive integers) and all the integers (positive, negative, and 0) and they still have the same cardinality, which is kind of like saying they have the number of elements.
Pelli’s constructed string is different because no matter which string you point to on the first sheet of paper, Pelli’s string on the second sheet will be different from it. If Pelli’s string is different than every string on the first sheet, then it can’t be on it. The main property that allows that to happen is that all the strings are infinitely long. If it helps your intuition, maybe you can justify it by saying that that infinitely long string gives an infinite amount of chances to get a different string. Maybe that won’t be enough for your intuition to justify it, but no one said that set theory (and infinities, specifically) has to match anyone’s intuition.
Re-reading #104, it might be useful to her for us to explicitly state that just because you have an infinite list of some “Thing” doesn’t mean your list automatically includes every possible “Thing.” I think making that assumption is how her intuition failed.
For example, think about sets of integers. The set of all integers except “3” is still an infinite set of integers even though it’s missing one.
In fact, there are some things that are actually impossible to list (or “enumerate” as we nerds like to call it), which is precisely what Cantor’s Diagonalization proves and Pelli’s string example demonstrates.
Thanks, thanks, thanks! Makes much more sense now… except @109. But if the “infinity” is meant to be an “exhaustive list”‘; i.e. it is supposed to include all permutations of something, my intuition says that an infinite list of all permutations should include, well, all permutations. I see now how my intuition fails….
And I can see at least one order of infinity. But how the heck do you get to the next one? What on earth does it MEAN to have the multiple orders of infinity? Are they useful for anything?
But if the “infinity” is meant to be an “exhaustive list”‘; i.e. it is supposed to include all permutations of something, my intuition says that an infinite list of all permutations should include, well, all permutations.
That’s just it, infinity is not necessarily an exhaustive list. Cantor’s Theorem is a proof by contradiction that says “for certain infinite sets (specifically the “uncountable” ones), if you think you’ve got a complete list, you’re wrong and I can prove it by generating an element of the set that isn’t on your list (the Diagonalization) at will.”
And I can see at least one order of infinity. But how the heck do you get to the next one? What on earth does it MEAN to have the multiple orders of infinity? Are they useful for anything?
If by “order of an infinite set” you mean “number of elements in an infinite set,” then your intuition is correct. All infinite sets have the same order. “Infinity plus one” really is a meaningless phrase. The Reals and the Integers, for example, are the same size (note that this is true even though the Integers are in fact a proper subset of the Reals).
What we’re talking about in this thread is something different than Order called Cardinality. Two sets are said to have the same cardinality if and only if there exists a bijection (a one-to-one and onto mapping) between them. Cardinality doesn’t say anything at all about the relative size of the two sets (unless the sets are finite, of course). The Reals and the Integers, for example, do not have the same cardinality while the Integers and the Rationals do (note that the Integers are a proper subset of both the Reals and the Rationals).
People often-times mistake different cardinalities of infinite sets for different sizes because, frankly, of sloppy language. We have a habit of saying that an infinite set A is “bigger” than an infinite set B if the cardinality of A is larger than the cardinality of B (largely because in the case of finite sets, that’s actually how it works), but that’s not really what it means. The problem is that the very idea of “size” breaks down when you’re dealing with infinite sets. There is a sense in which, say, the Rationals are “bigger” than the Integers; namely that the Integers are a proper subset of the Rationals, but again, that notion doesn’t apply to the actual size of the two sets, which is still just infinity.
As for practical uses, I’m a computer scientist and all of this stuff bears directly on the question of computability (what computers can and cannot do), so I think it’s very useful indeed. I cannot write a program that enumerates the Reals, but I can write one that enumerates the Integers, just to pick a trivial example. I’m sure it’s relevant to other stuff as well, but someone else will have to step in and fill in those blanks.
Wikipedia, on Georg Ferdinand Ludwig Phillip Cantor, gives a hint of the counter-intuitive psychology in the History of this branch of Mathematics.
Cantor’s theory of transfinite numbers was originally regarded as so counter-intuitive—even shocking—that it encountered resistance from mathematical contemporaries such as Leopold Kronecker and Henri Poincaré [Dauben 2004, p. 1] and later from Hermann Weyl and L. E. J. Brouwer, while Ludwig Wittgenstein raised philosophical objections. Some Christian theologians (particularly neo-Scholastics) saw Cantor’s work as a challenge to the uniqueness of the absolute infinity in the nature of God,[Dauben, 1977, p. 86; Dauben, 1979, pp. 120 & 143] on one occasion equating the theory of transfinite numbers with pantheism.[Dauben, 1977, p. 102] The objections to his work were occasionally fierce: Poincaré referred to Cantor’s ideas as a “grave disease” infecting the discipline of mathematics,[Dauben 1979, p. 266] and Kronecker’s public opposition and personal attacks included describing Cantor as a “scientific charlatan”, a “renegade” and a “corrupter of youth.”[ Dauben 2004, p. 1. See also Dauben 1977, p. 89 15n] Writing decades after Cantor’s death, Wittgenstein lamented that mathematics is “ridden through and through with the pernicious idioms of set theory,” which he dismissed as “utter nonsense” that is “laughable” and “wrong”.[Rodych 2007] Cantor’s recurring bouts of depression from 1884 to the end of his life were once blamed on the hostile attitude of many of his contemporaries,[Dauben 1979, p. 280:”…the tradition made popular by [Arthur Moritz Schönflies] blamed Kronecker’s persistent criticism and Cantor’s inability to confirm his continuum hypothesis” for Cantor’s recurring bouts of depression] but these episodes can now be seen as probable manifestations of a bipolar disorder.[Dauben 2004, p. 1. Text includes a 1964 quote from psychiatrist Karl Pollitt, one of Cantor’s examining physicians at Halle Nervenklinik, referring to Cantor’s mental illness as “cyclic manic-depression”].
# Aczel, Amir D. (2000). The mystery of the Aleph: Mathematics, the Kabbala, and the Human Mind. New York: Four Walls Eight Windows Publishing. ISBN 0760777780. A popular treatment of infinity, in which Cantor is frequently mentioned.
# Dauben, Joseph W. (1977). Georg Cantor and Pope Leo XIII: Mathematics, Theology, and the Infinite. Journal of the History of Ideas 38.1.
# Dauben, Joseph W. (1979). Georg Cantor: his mathematics and philosophy of the infinite. Boston: Harvard University Press. The definitive biography to date. ISBN 978-0-691-02447-9
# Dauben, Joseph W. (1983). Georg Cantor and the Origins of Transfinite Set Theory. Scientific American 248.6:122-131
# Dauben, Joseph (1993, 2004). “Georg Cantor and the Battle for Transfinite Set Theory” in Proceedings of the 9th ACMS Conference (Westmont College, Santa Barbara, CA) (pp. 1–22). Internet version published in Journal of the ACMS 2004.
Vorlath,@92
I certainly do understand how a proof can have a correct conclusion and still be bogus. I was merely observing that it is new-to-me to see an anti-Cantor crackpot who accepts Cantor’s conclusion but rejects his argument. There is no logical inconsistency inherent in such a position, and I never claimed there was.
I will again call you a crackpot, because that is what you are. Just, as I said, a new (to me) kind of crackpot.
I said @92, I meant @102. Oops.
@96 Robert,
Assuming the axiom of choice, one can in fact choose a well-ordering of the real numbers, where each real number has a successor.
This of course doesn’t contradict Cantor’s diagonal argument, because ordinal numbers come in all cardinalities (a well-ordering of a set X being essentially an isomorphism between X and an ordinal number).
@111: As for practical uses, I’m a computer scientist and all of this stuff bears directly on the question of computability (what computers can and cannot do), so I think it’s very useful indeed. I cannot write a program that enumerates the Reals, but I can write one that enumerates the Integers, just to pick a trivial example. I’m sure it’s relevant to other stuff as well, but someone else will have to step in and fill in those blanks.
Here’s a pretty nifty trick: Seemingly impossible functional programs and a more general treatment, A Haskell monad for infinite search in finite time.
Using the fact that Cantor space is uniformly continuous, we can do searches of “infinite” sets (i.e. implictly defined infinities) in finite time. Just about all the work is done by the type system, which exploits the fact that Cantor space is topologically compact, so that we can decide propositions including the type (Cantor -> y) where y is a decidable type, but not (Integer->Integer) which is excluded due to the Halting Problem.
Very cool, trippy stuff. I’ve got a strong feeling that such techniques will pay off in correctness proofs of programs and related applications, as these searches don’t need access to the “guts” of a function, only relying on its type for proofs.
The fact that such techniques work is evidence for Cantor’s view of infinities: we can use finitistic programs to deal handily with implicitly defined infinities.
Or, to put things very simplistically, while the type (Integer->Integer) is undecidable, we can do a surprising amount of work with the fact that (Integer->Bool) is decidable.
@102: K is built from ONE specific mapping. I want to know if ALL mappings can’t be f.
f is defined very generically, to such an extent that most mathematicians find the proof valid.
If you could provide a mapping g that is not commensurable with or reducible to f, it would be very strong evidence for your argument. Otherwise, you will be left with the option of declaring that such a g exists with no evidence backing your assertion.
In Cantor’s proof, it is not necessary to assume that there is a bijection from N onto R. You need only let f be any arbitrary function with domain N. You can enumerate f(x) because the domain is N. Then using the enumeration you can find an element of R that is not in the image of f (using diagonalization if you like). So f is not onto R. (Indeed, the codomain need not be restricted to R, not even restricted at all except to the universe of discourse.)
This is not about finding a contradiction.
There is no reason to use a reductio ad absurdum method in this proof.
I can see Vorlath has been harping on the reductio aspect of Cantor’s proof. But there is no reductio aspect to his proof. (Actually I don’t want to bother looking for the original, but I just explained that the reductio is not needed.)
So the only criticism left would be directed toward diagonalization. The construction used is explicit and constructive. The constructed number is a real number. It is not in the enumeration of f(x) (i.e. it is not in the image of f).
On topic: some of these misunderstandings arise from incomplete or informal proofs given in classes (even at the college level). For the proof in question, there are a lot of bad illustrations used to make the point quickly in a class that really only wants to use the result. Specifically in entry level computer science, math, and philosophy classes. Even psychology classes do it.
One bit of evidence that someone has received an informal proof is that they talk about the diagonalization as if it had something to do with a grid. The grid is an illustration of an enumeration. Also, if someone thinks that the diagonalization is a way of discovering a “new real”, most likely they have been shown a proof that uses reductio ad absurdem.
One reason to avoid the reductio style proof, is that the end of the proof goes like this:
“If f is a bijection, then f is not a bijection.
…
Therefore, f is not a bijection.”
If you avoid the assumption that f is a bijection, and let f be any function, the end of the proof is more straight forward:
“If f is a function, then f is not a bijection.
Therefore, f is not a bijection.”
Christopher: You’re right. So our claims are: “If f is a function from N to R, then there is an element in R that is not hit by f” and “Given a(n enumerated) list of A,B-strings, there is an A,B-string not on the list.”
@103 Pelli:
Only by ditching f and using your own custom mapping that is known to not be f. Big deal. Doesn’t prove a thing.
Not even close. It will show that your custom mapping is not a bijection. But it says nothing about the bijection itself.
HAHAHA! What? You don’t use f, but rather digits of f. This imposes a specific mapping that is different from f.
Let’s say set P is the set of ALL mappings. We want to know if F (a bijection) exists in P. All other mappings are mutually exclusive with F since all other mappings are not one to one.
You want to tell me that by USING F in your own custom mapping G, making it a different mapping than F, you are showing how F is not a bijection? That’s not even wrong. All you’re showing is how G != F.
1. Assume there exists a function F that produces naturals other than 0 or 1.
2. If F exists, then I can take F/F and get 1 every time. Note that I’m ONLY USING F.
3. 1 cannot be any other natural number, so contradiction.
4. Conclusion: F cannot exist.
Do you accept that proof? No. This is what you are doing, so why should I accept your proof? F/F is a new function different from F and so is taking digits from F in base 2 with respect to base 1 digits in i.
Yes there is. If there wasn’t, you wouldn’t be able to construct K.
Not exactly. You are constructing K from g which uses f. That makes g!=f. If you used f, you would use it DIRECTLY. You would not be taking a digit from f which alters the mapping.
Saying so doesn’t make it so.
No you don’t. You create it from the DIGITS of f. That’s a different mapping since it retains the original mapping used when defining the power set which is known to not be one to one.
I will tell you that this is no longer the mapping I gave you and you are cheating.
@118 p:
g is the mapping used to define the power set.
That’s what is being used to form K. This mapping cannot be f by definition. Really, can you show how taking digits of f(i) is any different than the mapping used to defined the power set? It’s identical.
The mapping of f isn’t really being used, but rather the proof is using one side of f (as all f(i)) as a substitution for N^2 in order to falsely claim that only f is used, but then it takes base 2 digits from N^2 and maps them to base 1 digits (enumeration) from i to form K. Are we supposed to KNOW that this (original mapping used to define the power set) is the only mapping that can exist for f?
If there is a mapping f, it won’t use a base 2 to base 1 relationship as this is g used when defining the power set (except that the mapping is used from N^2 to N instead of N to N^2). So by taking digits of f(i), you are re-introducing mapping g used when defining the power set.
Suppose I give you a mapping where I tell you that it only works if you don’t map different bases (because this would re-introduce a mapping that is mutually exclusive with the mapping that I’m giving you). So you can’t take digits of f(i) unless you also take digits of i in the SAME base.
How good is your proof now?
I see four things.
1. The mapping used to define the power set is assumed to be a bijection.
2. I don’t see the proof where taking digits does not create a new mapping.
3. How do you create K without a very specific mapping?
4. When you take digits of f(i), how do you know that f uses it this way? If it doesn’t, then the proof is meaningless as this would mean that f(i) isn’t actually being used, but rather that f is used as a placeholder for N^2 (and not actually the mapping) where you then map N^2’s digits in your own way to N thereby eliminating f completely from the proof. IOW, there is nothing stating that the mapping of digits in base 2 from N^2 to digits in base 1 in N is what f uses.
Vorlath, for the nth time: for any proposed 1:1 mapping from the integers to the reals, the diagonalisation produces a real not mapped to any integer. Therefore there is no such mapping. How can this be problematic, and why are you talking about “G” and “N^2”?
Vorlath, I am not looking at the digits of the function f, whatever that is – I am looking at the digits of the elements!
” Suppose you can. Then I let you do it. I take your infinite sheet of paper, that looks like
I will tell you that this is no longer the mapping I gave you and you are cheating.”
Do you not agree that if you have a function f that maps from naturals to strings, then you can write it down uniquely likes this:
1: ABABBBABAB….
2: ABBBABAB….
…
etc?
(Just like the function f(x) = x^2 on naturals can be written
1:1
2:4
3:9
…)
If I’m not allowed to write down the values taken by your function, then what can I do?
And this time I wasn’t even talking about a function. I wanted to prove “that you cannot write down all infinite A,B-strings row by row on an infinite sheet of paper”. The adversary claims he can do it and does it, but as soon as I touch the paper I’m cheating?!
Vorlath,
In your allegedly analogous “proof”, you wrote:
What, exactly, is 3 supposed to contradict? None of your premises claims that F(x) / F(x) won’t equal 1 for any or all x, your premise is only that F(x) won’t equal 1 for any x. This, I’m sure you’ll agree, is not the same thing.
Here’s another (rather contrived) example of a similar proof:
Proof that there is no bijection between {0,1} and {0,1,2}:
Let any f from {0,1} to {0,1,2} be given. Consider the number k = 3-f(0)-f(1). We check it lies in {0,1,2} and that f(0) = k or f(1) = k both lead to f being not a bijection.
Vorlath, do you think your argument that we’re ‘using some other map’ instead of f applies here too? What would that map be in this case?
@122 Stephen:
For any proposed 1:1 mapping, you can ditch said mapping and use the power set mapping to show that you can create a new number. However, it does not mean that this new number doesn’t have a mapping in f.
@123 Pelli:
A million times no. This is the power set mapping. It’s not f by definition.
Yeah, but you’re using the same base here.
Take two sets where all elements are represented by infinite digits. Pretend we’re mapping R to R or something like that.
We know for certain that base 2 R maps one to one with base 3 R.
Now have the left side use base 2 and the right side use base 3. Write exactly the same digits on both side. No matter what, you can always create a new number on the right side by switching any digit to 2. All digits on the right have covered all combinations possible on the left. So this means you can always have more numbers on the right that aren’t mapped.
I can also ask people for their own custom mappings. I will swap out all numbers on the right that uses 2 in a digit with a number that does not use a 2. There should be no issue here as I can cover the exact same amount of numbers as on the left using only two symbols per digit (as that is all the left side uses). When I’m done, I will again have only numbers on the right that uses digits 0 and 1. This will leave all numbers with 2 as a digit being unmapped.
Does this mean that |R| > |R|. No. But it does prove my point that using different bases creates a different mapping that is not f. In my proof, I showed the one to one mapping and then proceeded to show a contradiction where one side did not map completely to the other side.
How did this happen? Where was the flaw? Whatever you answer is exactly how Cantor’s argument is flawed. The snag is that people get sideswiped by the use of naturals.
You can take the values (on both sides) as long as you don’t change the mapping f (and retain such a mapping). Make sure that f stays f without introducing an arbitrary mapping. If you don’t change f and through existing properties of such a mapping it ends up being in contradiction with each other, then that would be a valid proof.
Right now, f is not used directly. Instead, a new mapping g is constructed which uses the output of f and changes how it maps the indexes to the elements of N^2 via digits.
Prove that the ONLY mapping that f can have, if it exists, is g (the power set mapping). If you did that, then you would also have a valid proof.
You’re cheating if you change the mapping I’m giving you. And all the proofs mentioned so far do in fact change the mapping. I can even tell you exactly what mapping you’re using. It’s the original power set mapping that you’re asking if there exists ANOTHER mapping which is one to one. Of all the ironies, I find it amazing that all the proofs go ahead and use the original power set mapping when they’re trying to find something different and are then up in arms when it’s discovered that f != power set mapping.
You do realize that a one to one mapping, if it exits, will be inconsistent with the power set mapping? You do understand that, right?
Vorlath, the construction of a number which is not covered by f is exactly and precisely a demonstration that the “new number” does not have a mapping in f. We construct a number which differs, from every number covered by f, in at least digit. Ergo it’s not covered by f, and you are wrong.
We didn’t “ditch” f, we didn’t use a “power set mapping”, we didn’t switch from base 2 to 3 or n or anything. Try to grasp this before responding.
Incidentally, Vorlath, your argument about base 2/base 3 proves only that if you construct something that isn’t a bijection, it isn’t a bijection. Cantor’s proof does something entirely different by showing that for _any_ claimed bijection between integers and reals, you can make a real that doesn’t match any integer. Is this the source of your problem?
@123 Douglas:
You, my friend, have just entered the crackpot zone because this is 100% my argument. This is precisely the flaw in Cantor’s argument.
F(x) != F(x)/F(x)
We agree, right?
We know that g is the power set mapping, so f cannot be g just like F(x) cannot be F(x)/F(x).
I would have to prove that F(x) is the same as F(x)/F(x). In the same manner, you must prove that f and the power set mapping are one and the same.
@128 Stephen:
YES!!!
NO!!! It does no such thing. You only think it does.
Cantor’s argument uses a mapping that isn’t a bijection and then goes on to show that it isn’t a bijection.
Vorlath, how do you represent an A,B-string if not by what it is, mainly e.g. “ABABBABBA….”? It is true that the A,B-strings can be put in bijective correspondence with the subsets of N, but that is no problem.
You’re talking about different bases, but functions don’t care about bases. If one of my sets is {cat, dog, horse} that does not mean a bijection between that and the set {1,2,3} has to be written “cat one, horse two, dog three” rather than “cat 1, horse 2, dog 3”.
“This is the power set mapping. It’s not f by definition.”
As I said, an infinite string written down does not transform it into a power set and change a function.
“Take two sets where all elements are represented by infinite digits. Pretend we’re mapping R to R or something like that.”
OK
“We know for certain that base 2 R maps one to one with base 3 R.”
Yes.
“Now have the left side use base 2 and the right side use base 3. Write exactly the same digits on both side. No matter what, you can always create a new number on the right side by switching any digit to 2. All digits on the right have covered all combinations possible on the left.
So this means you can always have more numbers on the right that aren’t mapped.”
Yes to all. What you are saying can be generalized to “if you write down a function that maps reals in base 2 to the numbers in base 3 with no 2s, then there are reals (on the right) left over.” The proof fails because there are reals not in the form “base 3 without 2s”.
The corresponding argument against our proof would be: “You have only shown that any function from N to 2^N that maps numbers to strings of the form 010111…, then there are elements in 2^N left over.” This is not a problem since every element in 2^N is exactly of the form 0101011…. Hence any function f from N to 2^N will indeed map numbers to strings of the form 01101…
Is this your objection? That we haven’t proven all elements of 2^N are of the form 0100101…? That’s true almost by definition!
” The adversary claims he can do it and does it, but as soon as I touch the paper I’m cheating?!
You’re cheating if you change the mapping I’m giving you.”
If I claim you cannot write down all A,B-strings row by row, then can I not safely assume if you do it your paper will contain rows and rows of ABABABAB….?
“You do realize that a one to one mapping, if it exits, will be inconsistent with the power set mapping? You do understand that, right?”
I don’t know what you mean by “the power set mapping”. What I can tell you is that if you find a bijection, it will be inconsistent with my definition of a function.
@128
Vorlath clearly has many problems. Your problem is that you’re trying to understand his problems as though they were merely mathematical in nature.
@130 Pelli:
You can do that as long as the other side of the mapping is expressed in a similar manner.
So why are you using different bases if they don’t matter? Use the same base and prove me wrong. In all these discussions, no one is ever willing to use the same base.
We all know that bases matter to functions when said functions maps via digits. You’re mapping base 1 digits to base 2 digits. That makes all the difference in the world.
You’re matching by element, not digits.
Of course it does otherwise I can write infinite strings in base 2 and the same strings in base 3 and then match them by digits and you’ll get a different mapping. I proved it in my comment above.
Exactly right.
With your proof, there are reals not in the form “base 2 without 1s”.
no no. Not that. I’m saying you haven’t proven that all elements of 2^N are of the form 11111111…. (base 1).
The power set mapping is what you used to define N^2 from N.
“The power set mapping is what you used to define N^2 from N.”
N^2 is the set of integer pairs. Do you mean 2^N, the set of infinite strings 0110.., which is in bijection with PN, the power set of N? How do I use any map to define PN from N? I define PN = {A : A is a subset of N}. There is no function.
” Vorlath, how do you represent an A,B-string if not by what it is, mainly e.g. “ABABBABBA….”?
You can do that as long as the other side of the mapping is expressed in a similar manner.”
When there is no function at all, and you are just looking at strings, don’t you agree A,B-strings are exactly the things that are “BABABA…”?
” You’re talking about different bases, but functions don’t care about bases.
So why are you using different bases if they don’t matter? Use the same base and prove me wrong. In all these discussions, no one is ever willing to use the same base.”
Because there is as little reason for there to exist a common basis (whatever that is) for N and 2^N as there should exist a common basis for {1,2,3} and {cat, dog, horse}.
“We all know that bases matter to functions when said functions maps via digits. You’re mapping base 1 digits to base 2 digits. That makes all the difference in the world.”
No. You can define functions by specifying what they do to digits, e.g. let f : N -> N be given by reversing the digits in base 10. The function doesn’t care about what bases you think of when you look at its elements though, so for this f we have f(10000_binary) = f(16) = 61 = 111101_binary.
” If one of my sets is {cat, dog, horse} that does not mean a bijection between that and the set {1,2,3} has to be written “cat one, horse two, dog three” rather than “cat 1, horse 2, dog 3″.
You’re matching by element, not digits.”
Huh? I am matching naturals numbers n with strings of the form ABAB… . Forcing them to be represented in the same way is like forcing cat and 1 to be represented in the same way when matched up.
” As I said, an infinite string written down does not transform it into a power set and change a function.
Of course it does otherwise I can write infinite strings in base 2 and the same strings in base 3 and then match them by digits and you’ll get a different mapping. I proved it in my comment above.”
No. What you proved is you can define _A_ function from R to R by mapping x to the real whose base 3 rep is the base 2 rep of x. An example of another function from R to R is f(x) = x^2. And as I said above, feeding the function numbers that you in your mind consider to be in some other basis does not change what the function does.
” The proof fails because there are reals not in the form “base 3 without 2s”.
Exactly right. With your proof, there are reals not in the form “base 2 without 1s”.”
No, “base 3 without 2s” is on the RIGHT side, not on the LEFT side (base 2). My right side is “ABABA….”, not the left side “natural numbers / base 1”.
“I’m saying you haven’t proven that all elements of 2^N are of the form 11111111…. (base 1).”
Wrong side.
Vorlath,
By the way, a “basis” says what number a string is, right? E.g. in base 2, we know “ab.cde” is 2a+b+c/2+d/4+e/8, whereas in base 3 it is 3a+b+c/3+d/9+e/27. Lo and behold, a basis maps strings of digits to real numbers! If you demand a basis to exist before you talk about functions between strings and numbers, then you will get in trouble because a basis is exactly a function between strings and numbers.
You need to realise a function f is just something that takes elements x of a set to elements f(x) of another set, which is formalised by saying a function is a set of pairs (x,f(x)). Since elements don’t care about bases (the number 2 is the same even if you denote it by “cow”), functions don’t care about bases. A function mapping integers to their base 10 reversed forms is just a collection of pairs {(cow,cat), (dog, horse), (horse, dog), (lamb, lamb), …} where I have denoted the numbers 13 by cow, 31 by cat, 597 by dog, 795 by horse, 11 by lamb, etc. No basis is required for the function to exist, and no basis will affect this specific function. If you replace base 10 in the definition of f by base 11, you get ANOTHER function, just as replacing base 2 by base 3 in the definition of “101 in base 2” (= 5) will result in the different number “101 in base 3” (= 10).
Vorlath wrote:
I agree that F(x) may not necessarily equal F(x)/F(x) (for many choices of F and x).
I have no idea what you are claiming that this has to do with anything. Or what g is. Or how we know it to be the power set mapping. Or why it is “just like” how F(x) can’t be F(x)/F(x) (there are plenty of other problems with your claimed analogy).
You’re wrong, Vorlath. It’s really simple. Ignore the reals and answer Pelli’s questions about the binary strings. All your ramblings about bases and how defining this or that construction “changes” some other sets is just that, nonsensical rambling.
@133 Pelli:
Yeah.
Not fully, but since you mention that A is a subset, then we know that an element from N is either included or not included. That’s base 2. So we know that that this is not one to one with base 1 when restricted to the same amount of digits.
Sure there is. If you don’t then you get a different mapping as I’ve proven in my earlier comment.
I agree, but you’re using a single base, 10. My point is that when you use different bases, then you get things like 011 in binary is not the same as 011 in octal.
Here, you are either mapping the same base (base 2 or base 10) or you are allowing the different bases to have different amounts of digits. Again, I agree with your examples, but they reinforce the point I was making.
Illusion only. You don’t have enough symbols to cover the full range and it amounts to one digit with three symbols in all cases.
Same base just means same number of symbols per digit. Each set can use its own set of symbols as long as the amount is the same per digit. If aliens were to use 10 hieroglyphs per digit, it’s still base 10.
YES!!! THIS is the flaw in Cantor’s argument. Right there. Your argument, apply it to Cantor’s argument.
You can map them with the proper base 3 rep and I can swap those elements one for one with elements that don’t have 2’s for digits. So your argument doesn’t hold water. Besides, do you not agree that if the base 3 rep doesn’t use any 2’s, that it can map to all elements with base 2 rep when matching digit by digit? So there’s no problem swapping out all the elements that use 2’s.
With Cantor’s grid, I can do the same thing. I can swap out any element that doesn’t have the form 111111000… (all ones at the start and all zeros at the end) with an element that does (and is not already in the list). This means we can reorder the list so that the 1 count of any entry will match the row count. However, there are elements that are not in the form “11111000…” just as you’ve said earlier.
How come this makes my proof invalid, but makes Cantor’s valid?
f(x) = x^2 doesn’t use digits. So it’s not a valid example.
@135 Douglas:
Not necessarily? What number divided by itself and is not 0 will give an answer that is not 1?
A list of infinite binary strings is the same as the list of elements in a power set, no?
We know that F(x) is not F(x)/F(x) just like we know that mapping g which is a list of infinite binary digits that is known to not map one to one with a list of infinite singular digits when using the same amount of digits. This means we know that g != f. So Cantor uses _A_ mapping that is not f. Just like I was using _A_ function F(x)/F(x) that is not F(x).
Does anybody have any clear idea what Vorlath means when he talks about ‘bases’? They don’t appear to have [i]anything[/i] to do with the discussion.
Vorlath, you made a strange comment:
Pelli: I define PN = {A : A is a subset of N}. There is no function.
Vorlath: Not fully, but since you mention that A is a subset, then we know that an element from N is either included or not included. That’s base 2. So we know that that this is not one to one with base 1 when restricted to the same amount of digits.
That’s silly. He’s not defining a function; therefore there is no function. To claim that it’s a case of “not fully” makes no sense. Are you somehow claiming that every definition of a set is “not fully” a function?
Vorlath,
The reason I said “not necessarily” is because you didn’t universally quantify over both F and x. For example, let F be the function that always returns 1. Then, for all x, F(x) = F(x)/F(x) = 1.
None of this has ANYTHING to do with the topic, because your analogy isn’t an analogy.
You also wrote:
Light dawning? You’re absolutely right, there is a bijection between naturals and binary strings of the form “some number of 1s followed by infinite 0s”. As you noted, there are lots of binary strings that aren’t included. It doesn’t invalidate Cantor’s proof because he is TRYING to prove that some binary strings aren’t included!
@139 Douglas:
You didn’t answer the question. Why is it ok to say |base 2| > |base 1| but it’s not ok to say |base 3| > |base 2| when exactly the same technique is used? There are lots of base 3 strings that aren’t included that “proof” too.
Pelli said earlier that my proof was flawed because there were numbers not in the form of not using 2’s. Here you have numbers not in the form “111110000….”. Where is the difference? How can you use the same statement to validate one proof and dismiss the other?
@138 Rilke’s Granddaughter:
But we can determine some features of the function even if it’s not stated directly. For example, allowing an element of N to either be included or not included tells us this is base 2. So if you try to enumerate this list using the same binary digits, you will have a mapping between base 1 and base 2. This is known to not be a one to one mapping when using equal amounts of digits, but it’s this very mapping that is used in the “proof”.
Vorlath:
There IS NO FUNCTION. There is a set, and a definition of a set.
Answer this question: are you claiming that every definition of a set is “not fully” a function, but is some kind of function?
@141:
I don’t know what those other definitions would be.
All I’m saying is that when you enumerate your set and you use base 2, then you create _A_ mapping when you match digits. There is enough there to know certain properties that this mapping has. Such as not being a one to one mapping.
Vorlath,
“Pelli said earlier that my proof was flawed because there were numbers not in the form of not using 2’s. Here you have numbers not in the form “111110000….”. Where is the difference? How can you use the same statement to validate one proof and dismiss the other?”
Where your 3 > 2 proof flaws is that you say f : A -> B, and then you assume f maps from A to elements that do not fill B. Your argument against my proof is that I don’t care that the elements of B do not fit nicely into A. That is not the same thing. Do you agree?
(Your maps is from base 2 to base 3 without 2s. You fail because base 3 without 2s is not base 3. My map is from n to ABAB… strings. I do not fail, since ABAB… strings are just ABAB… strings. There is no reason for ABAB… strings on the right to have the same basis as n on the left, just as a map between animals and numbers does not force the numbers to be expressed as animals.
“Not fully, but since you mention that A is a subset, then we know that an element from N is either included or not included. That’s base 2. So we know that that this is not one to one with base 1 when restricted to the same amount of digits.”
True. The set of finite A-strings of length n is greater than the set of finite A,B-strings of length n. Assuming this argument can be taken to infinity is fallacy of composition.
” No. You can define functions by specifying what they do to digits, e.g. let f : N -> N be given by reversing the digits in base 10.
I agree, but you’re using a single base, 10. My point is that when you use different bases, then you get things like 011 in binary is not the same as 011 in octal.”
There is a difference between defining a function in terms of bases and looking at what a function’s elements are in different bases. Suppose you say “f(x) = y, where y is obtained by reading the base 2 expansion of x as base 3″. Then the function is defined in terms of a basis. Changing the bases in the definition will probably change the function. Changing what basis you think about when you give the function a number will not affect it, just as f(x) = x^2 does not care about bases.
” so for this f we have f(10000_binary) = f(16) = 61 = 111101_binary.
Here, you are either mapping the same base (base 2 or base 10) or you are allowing the different bases to have different amounts of digits. Again, I agree with your examples, but they reinforce the point I was making.”
The number of digits is irrelevant. A number is the same no matter what string of digits or other symbols you use to denote it.
” Huh? I am matching naturals numbers n with strings of the form ABAB… .
Illusion only. You don’t have enough symbols to cover the full range and it amounts to one digit with three symbols in all cases.”
Are you talking about my bijection between the set {1,2,3} and three animals? Talking about symbol representation here is just stupid! The function is the same even if I write the numbers in some alien language and the animals in Hindi!
” Forcing them to be represented in the same way is like forcing cat and 1 to be represented in the same way when matched up.
Same base just means same number of symbols per digit. Each set can use its own set of symbols as long as the amount is the same per digit.”
OK. But isn’t f(1) = cat, etc a bijection, even though I haven’t written 1,2,3 in a basis with 26 symbols or “cat”, etc in a basis with 10 symbols?
“If aliens were to use 10 hieroglyphs per digit, it’s still base 10.”
Yes.
” What you proved is you can define _A_ function from R to R by mapping x to the real whose base 3 rep is the base 2 rep of x.
YES!!! THIS is the flaw in Cantor’s argument. Right there. Your argument, apply it to Cantor’s argument.”
No. You assume every element from R is an element in R base 3 without 2, which is false. Cantor’s assumption that every element in 2^N is of the form 010101.. is true.
“You can map them with the proper base 3 rep and I can swap those elements one for one with elements that don’t have 2’s for digits. So your argument doesn’t hold water. Besides, do you not agree that if the base 3 rep doesn’t use any 2’s, that it can map to all elements with base 2 rep when matching digit by digit? So there’s no problem swapping out all the elements that use 2’s.”
I don’t understand what you’re trying to say. There is indeed almost (because base 2 expansion is not unique) a bijection between reals and reals that have no 2 in base 3, by defining f(x) to be x in base 2 read as base 3.
“With Cantor’s grid, I can do the same thing. I can swap out any element that doesn’t have the form 111111000… (all ones at the start and all zeros at the end) with an element that does (and is not already in the list).”
No. Here’s a list where you can’t (unless you swap rows around, in which case all you’re saying is “I can replace the first element by 1000.., the second element by 1100.., etc which is clearly true):
1: 1010101010….
2. 1111111111…. (just in case that’s a valid 111000… string)
3: 000…
4: 1000….
5: 11000…
6: 111000…
7: 1111000…
etc
“This means we can reorder the list so that the 1 count of any entry will match the row count.”
OK.
“However, there are elements that are not in the form “11111000…” just as you’ve said earlier.”
Do you mean there are elements in 2^N missed by your list? Then yes.
“How come this makes my proof invalid, but makes Cantor’s valid?”
Because you’re swapping around elements. Cantor is just saying “look at the 0101.. representation of f(k)”. That does not alter f.
If you can swap elements, then you get things like “There is no bijection from N to N. Given any such, replacing every f(k) by f(k)+1 won’t change bijectiveness, but then no f(n) is equal to 1. Cantor is saying “Writing all the elements of 2^N as 0101… does not change bijectiveness”, and indeed it doesn’t, because functions don’t care about bases.
“f(x) = x^2 doesn’t use digits. So it’s not a valid example.”
Sure it is. The function f(x)=x^2 cares about the basis of your input just as much as the read base 2 as base 3 function. If it helps, think of the function as “translate x to base 2. then read as base 3.” No matter what basis you give the number in, it will be translated to base 2 in the first step.
Vorlath,
A little clarification. My argument against the generality of the map read base 2 in base 3 is not that there are base 3 strings not in base 2. It is that the image of your map is still numbers with only 0s and 1s.
Similarly, suppose you take base 2, double each digit, and read as base 3. Then exactly the same argument says you’ll miss base 3 numbers with 1s.
Or if you take base 2, and replace every other 1 with a 2, you will miss all numbers whose base 3 rep does not have 1 and 2 alternating.
If you take base 3, and replace all the 2s (and 1s) with 1 and read as base 3, you’ll once again miss the numbers with 2s in their base 3 rep.
Do the same with base 10 in the domain, and you’ll still miss the same numbers, even though 10 has more than enough digits.
Take base 2 and insert 0s between every digit and read as base 2. You still miss things, and this map is injective. (If you try to say you get double the number of digitsand take that to infinity then you’re compositioning again.)
Conclusion: My argument has nothing to do about the basis of the domain of the function not working well with the image.
Sorry for the multiple posts, but:
A fallacious argument for base 3 > base 2 would go like this:
Let f : base 2 -> base 3 be given. Then f maps to numbers whose base 3 rep contains only 0s and 2s (no, base 3 contains more than that). Considering 1, f is not a bijection. (I picked 2s instead of 1s to show there is no link to the basis of the domain.)
The Cantor argument says:
Let f : N -> 2^N be given. Then f maps to string of the form 0101… (true, 2^N contains exactly these strings). Diagonal, contradiction.
Vorlath, you so nearly got it in your post 129! You complain that “Cantor’s proof uses a function that isn’t a bijection and then shows that it isn’t a bijection”. That’s exactly what the proof does; it shows that for f which somebody comes up to you and claims is a bijection, you can show (using the diagonal argument) that f is NOT a bijection by defining a real which isn’t covered by f. We didn’t have to know anything about the specifics of f, so it’s valid for all proposed f.
THIS IS A FEATURE, NOT A BUG. Capisce?
Your complaints about base 2/base 3 representations are a red herring; all you’ve shown is that ONE proposed G, of your own devising, is not a bijection. That proves nothing about different cardinalities. If I propose to map rationals to reals by associating every rational P with the real (Q=P), I miss some reals, in a very similar way to the way that your proposed (real base 2/real base 3) mapping misses some reals in base 3. But there are OTHER ways of mapping (real, base 2) to (real, base 3) which ARE bijections, so your argument about base2/base 3 fails. There is no way, however subtle, of mapping rationals to reals with a bijection, which is waht Cantor proved.
Ho hum.
What I think some people fail te realize (perhaps this has been mentioned before in of the hundreds of post above though) is that a digital (binary, tertiary, octal, whatever) representation of a number is not necesarily unique.
In decimal:
0.09999…. = 0.100000
This non uniqueness occurs only for those numbers which have a finite representation in a certain base. The infinite string of zeros can also be seen seen as in infinite string of 9’s (base – 1). Cantor’s diagnolisation works around this problem by creating a number of only 4’s and 5’s. Doing this, you know that the created number has a unique digital representation, and that this representation can not be found in your enumeration of reals. In base two you cannot choose a digit between 0 and 1 and the process doesn’t work (although there are ways to work around this.)
Given an enumeration, and using base 10, you find one number not in your enumeration. Using base 8 you would find another, etc… In fact there are infinitely many numbers not in your enumeration, Cantor’s proof just gives you a specific way of finding one. He does not claim, that given any enumeration f there is a unique number which is not in the enumeration, he shows there is at least one.
The argument has degenerated into “Cantor is trying to show that numbers are missing” while the argument against base 2 vs. base 3 is “You have numbers missing.” Or in the alternate, but equivalent is that I’ve use _A_ particular mapping when Cantor did not, yet I used HIS technique. It’s identical.
If none of you can explain why the exact same argument validates one proof, but not the other, this discussion is over.
Vorlath, as I have said, it’s different if the numbers that should be on the right side are missing from the RIGHT side (in the case you are supposed to map to all of base 3 but only use base 3 without 2) or “missing” from the LEFT side (in the case I map to strings of the form ABAB… and all I assume is that the strings I map to are of the form ABAB…, without bothering about what basis the integers on the left side use since that is irrelevant).
Vorlath, it’s quite simple. You brought to the table _one specific_ proposed mapping between reals base 2 and reals base 3. We have established that this mapping is not a bijection. This, incidentally, shows that the reals can be mapped to a subset of the reals, which we knew, so yay consistency.
Cantor’s diagonal argument shows that for ANY proposed mapping between the rationals and the reals there is at least one real which isn’t mapped to any rational. The argument is completely general and does not rely on any detail about any one particular proposed mapping.
It’s the difference between “This car is not working” and “no car can drive to the moon”.
So no, your arguments about bases and Cantor’s argument about cardinality are not remotely identical.
Get it?
Vorlath, I think this discussion has become a bit bogged down in side-issues. Let’s briefly try again from scratch and try to understand exactly where the divergence between your view and the mainstream begins. I’ll go through the steps in Cantor’s proof, subdividing as finely as seems reasonable (so what follows is long; sorry), and I’d like to know at what point you think I first say something false, and exactly why it’s false given that everything before it is true.
(I understand that your objection is a “high-level” one to the effect that it’s some kind of category error to combine “base-1-ish” and “base-something-else” things, or that somehow Cantor is treating infinite sets as finite, or that the proof doesn’t take into account how some sets are “dependent” on one another. But if there’s such a high-level error in the argument then it must show up as a false statement in the sequence that follows; I think it will be easier to understand your objection when we have a concrete example of an inference that you think is broken.)
1. Cantor claims: There is no bijection between the positive integers and the real numbers.
2. This will be true provided there is no *surjection* from the positive integers to the real numbers.
3. In other words, provided that there is no function f from N to R such that everything in R is f(n) for some n. (I am defining N to be the set of positive integers, and R to be the set of real numbers.)
4. So it suffices to do the following. (a) Let f be any function from N to R. (b) Describe a procedure that, given such a function f, produces a real number. (c) Show that, whatever f was, this number is not equal to f(n) for any n. (In other words, whatever f was, it was not in fact a surjection, let alone a bijection.)
5. OK, so let’s assume there is a function f from N to R such that everything in R is f(n) for some n.
6. For each n, f(n) is a real number, and can be written in decimal notation. Some numbers have more than one decimal representation (e.g., 0.3 = 0.29999…); when f(n) is one of these, choose the one that ends with an infinite string of 0s rather than an infinite string of 1s. Define d(n,k) to be the k’th digit of f(n) when written out in this way.
7. (For clarification: let’s say that d(n,0) is the units digit, d(n,1) the 0.1 digit, etc. Of course k can be negative too, though it happens that we won’t bother looking at any d(n,k) for k0, then look at d(k,k), the k’th digit of f(k). If this is any of 0,1,2,3,4 then digit k of x will be 7. Otherwise, digit k of x will be 2.
11. So I have described a number x. All its digits before the decimal point are 0. All its digits after the decimal point are 2 or 7.
12. In particular, it doesn’t end with an infinite string of 0s or 9s, so its decimal representation is not ambiguous.
13. So if for any n it equals f(n), then its decimal digits are given by d(n,k).
14. But digit n of x differs from d(n,n) by at least 3, by the construction in step 10. In particular, it does not equal d(n,n), the n’th digit of f(n).
15. Therefore, x has only one decimal representation (by step 12) which doesn’t equal that of f(n) (by step 14).
16. Therefore, x is not equal to f(n).
17. Steps 13-16 apply for all n, so x does not equal any f(n).
18. (Note that the definition of x doesn’t depend on what n is. First, we defined all the digits of x; then, we said “choose any n and look at the n’th digit”.)
19. Since x does not equal any f(n), f was not in fact a surjection.
20. Note that the above construction applies no matter what f was; whatever f might be, we can define x using steps 8-11 above, and then by steps 12-17 we find that x is not equal to f(n) for any n.
21. So *every* f from N to R turns out not to be a surjection.
22. In other words, there is no surjection from N to R.
23. In particular, there is no bijection from N to R (since every bijection is a surjection).
24. Therefore N and R are not of equal cardinality.
I know you think statement 24 is wrong. What’s the first statement in that list that you think is wrong?
* * * * * * * * * *
Incidentally, although Cantor’s argument is usually expressed in terms of digits (in binary, base 2, or whatever), one can do essentially the same thing without any mention of digits. Like this, for instance:
1. As above, we’ll let f be any function from N to R, describe a real number x in terms of f, and show that x doesn’t equal any f(n).
2. The first step in defining x is to construct a sequence of intervals on the real number line. We start with I(0), which we define to be [0,1], the closed interval whose endpoints are 0 and 1.
3. Now for n=1,2,3,… in turn, we construct intervals I(n). The idea is to make sure that I(n) (a) is contained in I(n-1) and (b) stays away from f(n).
4. So. Suppose the length of I(n) is L(n). (Note that L(0) is positive; I shall define later intervals so as to make sure that L(n) is always positive.) Let J(n) be an interval of length L(n-1)/4, centred on f(n).
5. The difference I(n-1) J(n) — that is, all numbers that are in I(n-1) but not in J(n) — consists of either one interval or two, of total length at least 3/4 L(n-1).
6. In particular, it contains an interval of length at least 3/8 L(n-1). (The whole thing, if it’s a single interval; or the larger half; let’s choose the left half if they are of equal length.)
7. So it contains a *closed* interval — one that includes its endpoints — of length at least 1/4 L(n-1). (Move each endpoint in by 1/16 L(n-1).
8. This interval is what we shall call I(n).
9. I(n) is a closed interval of positive length.
10. I(n) is contained in I(n-1).
11. I(n) does not contain f(n).
12. As n runs through the positive integers, the left-hand endpoints of the I(n) never decrease and the right-hand endpoints never increase. (By 10 above.)
13. The left-hand and right-hand endpoints never meet or cross over. (By 9 above. Their limits as n->oo may coincide, though.)
14. Therefore, there is at least one number that is >= all the left-hand endpoints and = all the left-hand endpoints will do.)
15. This number does not equal any f(n), because it’s in all the I(n) and f(n) is not contained in any I(n).
16. Therefore, whatever f was, there is a number that doesn’t equal any f(n).
17. Therefore, whatever f was, it wasn’t a surjection, hence not a bijection; hence N and R are not of equal cardinality. (As before.)
@150 Stephen:
I used Cantor’s argument, but used base 2 and base 3 instead of base 2 and base 1. It’s the exact same proof so anything you say against one must also be against the other. You can’t play on both sides of the fence. If you say I built a custom mapping, then so did Cantor. It’s the EXACT same proof with the exact same construction. Only thing that’s different is how I build the new number, but I’ve shown how you can build a new number using the exact same method using Cantor’s setup.
@151 g:
I’ve seen all that a million times over. You’re comparing base 10 to base 1 here. Doesn’t change the fact that this is _A_ particular mapping. You can’t do that. It’s just a difference in base. Things start going wrong at point 6 where you fail to indicate the row number in base 10 as well.
Cantor’s first proof is even more asinine than the diagonal argument. He’s specifically using dependent sets when he says that between any two members exists another. What makes this possible is remapping and hence the use of dependent sets. This has to do with the way that reals are defined. Naturals are not defined in the same manner, so this proof fails automatically. Really, this is idiotic.
Like I said before, if you create a division at 0.5 and call the section from 0 to 0.5 as S, then |R| > |S|. It has to be since all elements in S are the exact same elements in R for that same range. However, once you remove the original mapping, S can now map to R, |R| = |S| and this is how you obtain a new number in between existing numbers. You can even use this technique on R by using R as a subset of itself so that you can always find a new number between two other numbers.
All Cantor is doing is using
1. |R| > |S| of dependent sets;
2. |R| = |S| of independent sets;
as a contradiction when there is no such thing.
What Cantor does is define two sequences A and B that are assumed to map to the entire range of R and then maps two subsets N1 and N2 of N that map to each range. Cantor then says that there is an element c between A and B, but that there is no element in between of N1 and N2 to map to c since it would already be included in either N1 or N2.
What you can do is create two dependent and proper subsets N1 and N2 of N that are complements of each other. Then map N1 and N2 to A and B of the reals. When you obtain c, remap N1 and N2 to a different pair of proper subsets of N and you will have no problem finding a natural to map to c while mapping N1 and N2 to A and B. And Cantor’s first proof falls apart, not to mention that he again uses _A_ specific mapping.
In any case, as I said earlier this discussion has devolved to three tactics.
1. Saying I’m wrong just because.
2. Playing on both sides of the fence where Cantor’s argument applies to base 1 vs base 2, but not to base 2 vs. base 3 when it’s the exact same proof.
3. Re-explaining Cantor’s argument in countless ways thereby changing the topic. Why do people do this?
I want to know why Cantor’s proof applies to base 1 vs base 2, but not to base 2 vs. base 3. That’s it. I agree with everyone else on pretty much everything else.
I won’t reply to anything that qualifies as one of the three points I’ve mentioned in my list because it’s a waste of time. I’ve already responded in enough detail to cover those areas, not to mention that I’ve gotten enough evidence that people will agree that Cantor’s argument is flawed just as long as you use the same proof, but change the representation used. That’s the last issue remaining and if anyone wants to tackle it, fine. Otherwise, I’m more than satisfied that Cantor’s argument is trivially flawed.
Vorlath, I still don’t understand how and why you’re using “base” in this context. So far as I can see there is no point at which cantor is showing a mapping from some set expressed in base 1 and some set expressed in base 10. Can you explain?
“I want to know why Cantor’s proof applies to base 1 vs base 2, but not to base 2 vs. base 3.”
First, let’s standardize the notation:
base 1 = set of all {1} strings (finite or infinite)
base 2 = set of all {0,1} strings (finite or infinite)
base 3 = set of all {0,1,2} strings (finite or infinite)
Also, let finite base n = set of all finite base n strings. I think we agree that |finite base 1|=|finite base n| for any natural number n.
What Cantor’s proof shows is that |finite base n|<|base 2| for any n. The argument relies on the FINITE part. You list every element of “finite base n” in the “left-hand list”, and the argument requires any given element from the set “finite base n” can be found in this list after finitely many steps.
The argument does not show that |base 2|<|base 3| because we don’t have the finiteness here. If we attempted to list every element of base 2 in the “left-hand list” we could try something like
…000000
…000001
…000010
…000011
…000100
… etc.
But we won’t be able to find any given element of base 2 in this list after finitely many steps – that’s the difference.
Vorlath, do you seriously imagine that anything which is true about one proof (which happens to use a diagonal argument) must also be true of all other proof that happen to use a diagonal argument? Wow. Apparently you _don’t_ see the difference between “this car is broken” and “no car can drive to the moon”.
Your argument about bases proposes ONE SPECIFIC mapping between two ways of writing the reals. You say specifically: my mapping is such that every real in base 2 is mapped to the real in base 3 that has the same digits.
We prove that this isn’t a bijection by finding any real in base 3 which your mapping doesn’t match to any real in base 2. That’s trivial. Fine. Your mapping is not a bijection.
This proves nothing about the cardinalities of “real base 2” and “real base 3” because you only considered one proposed mapping. You specified it yourself.
Cantor’s argument does not involve specifying any particular mapping between the integers and the reals. f(i) stands for _any_ proposed mapping such that a real n is given by f(i). The only property that we know _any_ proposed mapping must have is that 1 is associated to a real f(1) and 2 is associated to f(2) and so on, so we can make a list of reals f(1), f(2), f(3) etc.
The application of the diagonal argument then generates a real R which is not f(i) for any i.
This proof is valid for _any_ proposed mapping f because we did not appeal to any property of f except that for every i there’s a real f(i)- which must be true of any proposed mapping.
So your argument about the property of one mapping is not the same as Cantor’s proof about the property of any mapping.
A proof that Paul has two legs is not the same as a proof that nobody has 27 legs.
Guys, reasoning cannot cure his neurological problems.
Vorlath, I still don’t understand how and why you’re using “base” in this context. So far as I can see there is no point at which cantor is showing a mapping from some set expressed in base 1 and some set expressed in base 10. Can you explain?
Rilke’s granddaughter, apparently Vorlath thinks that a list of the integers is “base 1” (because you could represent them by tickmarks or something) and so the mapping in Cantor’s proof is “a mapping between base 1 and base 10”.
There are no words.
I’m wondering if the confusion is in the whole tickmarks thing. The fun part of a list of the rationals (Or integers, of course) is that every element on the list is finitely large. You can write a finite number of tickmarks. But Cantor’s demonstrating primarily that you cannot create a list that can be enumerated using only finitely large ticklengths. I THINK that may be where some of the confusion is?
Then he rambles on about base 3, and I have no gorram clue what he’s going on about. Base 3 is not larger than base 2. There is no inequality relation defined on bases. I don’t think even size is defined.
Vorlath, I wasn’t purporting to show you something you haven’t seen before; I was trying to arrive at some common understanding of where your disagreement with the mainstream actually begins.
When you say things start to go wrong at step 6, do you mean that in step 6 I have said something false? (In which case: what false thing have I said?) Or that in step 6 I have committed some other error (e.g., not writing something in base 10 that you would like me to write in base 10) that makes a later statement false? (In which case: what later statement is false?) Or that in step 6 I have said “now do X” where X cannot be done? (In which case: what specific thing have I said to do that cannot be done?) Or something else? (In which case: what?)
I appreciate that you would prefer to have a discussion about “base 1 versus base 2”, etc., but unfortunately I am unable to make much sense of what you’ve said about bases at present and I therefore don’t think having such a discussion will help us until I’ve understood as concrete as possible what specific step in the reasoning you think is wrong and how it fails.
I am not “re-explaining” Cantor’s argument in order to change the subject (the subject *is* Cantor’s argument, after all), nor because I think a different or more detailed explanation will convince you; I am splitting it up into tiny steps because I want to find exactly where the disagreement begins. Do you think there is something wrong with this procedure?
I am not attempting to diagnose what, if anything, is wrong in (e.g.) your arguments about “independent sets” because, again, it is not yet clear to me exactly what you are saying. Let’s first understand exactly where you think Cantor’s argument breaks — where there is a step from something true to something false or meaningless. If we can do that, then perhaps we can make some progress.
@158
But that’s insane. Base one would be something with only 1 digit: 0 (or 1, I supposed). You could only represent one number.
Base 1 has nothing to do with Cantor’s problem. And Cantor’s problem doesn’t even have anything to do with bases.
And god only knows what he thinks he means by “fails to indicate the row number in base 10”. The row number is an integer. You could write it in base 537 and it wouldn’t make the slightest difference.
Long ago, in my point-set topology course (there was a lot of tennis), our instructor, a well regarded fellow at Washington University in St. Louis, used “Base 1” to describe a series of tick marks the way Vorlath is. But he made it a point to say that it was merely an ancient way of representing a number, it was not part of formal rigour, and had no place in a formal proof in Point-Set Topology.
It was useful for things like keeping score at sports that score by ones.
Base 1 is a perfectly good base for representing the integers, and it’s actually very useful when thinking about Turing machines. (Mark recently had a post in which he talked about base 1, too, if you’d like to know more.)
Like the rest of you, though, I don’t quite understand what use Vorlath is making of the term ‘base’. Though perhaps it is the following. There are denumerably many base 1 strings–strings of the character ‘1’. (This is so even when we throw in the the infinite base 1 strings, since, of course, there’s only one of them). One way to view the Cantor proof is as showing that there are more base two strings–strings composed of ‘0’ and ‘1’–than base 1 strings. This might be what Vorlath means when he talks about base 1 being larger than base 2.
With base 1 you mean simply ticking, 1, 11, 111, etc… This is fundamentally different from the other bases for two reasons. There is no zero, and you can’t do fractions. This is possible in all other bases.
While ‘base 1’ can be usefull for certain number theoretic purposes, or for turing machines, in this context talking about base 1 is only confusing the issue since it is not really a base.
I suspect Vorlath is confused by the fact that a number can have different representations in different bases. Perhaps he doesn’t realize that a number exists independantly of any base. It is however possible to write down a unique representation of a number in any given base by writing a (possibly infinite) string of digits. Cantor’s proof doesn’t rely on a base, only on the fact that it is always possible to write down a representation of a number (in any base) in a unique way.
V,
Let’s run through Cantor’s proof your way:
You give me a function, f, claiming that it is a bijective mapping between two specific sets.
Now, it is my job to show that f does not map to every element in the image by pointing out an element that f does not map to, and I may ONLY use your description of f, nothing more; I cannot restrict f or use a different function. To recap, the description of f is ‘a bijective mapping between two specific sets.’
If I am successful, I will show that f is not bijective. If my method can be used for not just f but any bijective mapping between two specific sets, then I will have shown that there does not exist a bijective mapping between the two sets.
Is this acceptable? If so, let’s begin!
All we know about f is that it is a bijective mapping. This means that every element of the domain maps to an element of the codomain because f is a mapping. Take an element of the domain and find its image in the codomain. Can you find another element of the codomain that is not this image? If yes, then take another element in the domain of f and find its image. Can you find another element in the codomain that is neither of these two images? If yes, then continue, can you find an element in the codomain that is not the image of any element of the domain? If yes, then the element you found is the element I want to point out which shows f is not bijective.
Acceptable so far? That would prove that f is not bijective. Also, because f is only defined as a bijective mapping and we have not added to that definition or changed f, it would work for any bijective mapping. That would mean the sets have no bijective mapping, i.e. the sets have unequal cardinality.
So far, I have not defined the domain and codomain of f. I wish to prove that the cardinality of N, the set of natural numbers, is unequal to the cardinality of R, the set of real numbers. Naturally I will have f map from N to R. The function f is still just a bijective mapping between two specific sets. Now the sets are named.
The question is “Can you find an element in the codomain that is not the image of any element of the domain?” If yes, then f is not bijective and the cardinality of N is unequal to the cardinality of R.
I must come up with a number that is not the image of any element of the domain in order to say ‘yes.’ I must describe my number without ambiguity so that you know exactly what my number is. I must clearly state what is in every decimal place of my number so that everyone can see that it is distinctly different from any of the images in the codomain. In order to do this I will simply describe my number one digit at a time to be different from each image in the codomain. This is possible because each image in the codomain is mapped from an element in the domain. An element of the domain is a natural number. My digits will correspond to the natural numbers.
Acceptable so far?
We must check whether my number matches any of the images. Choose an image, being an image it is mapped from a natural number, which corresponds to one of my digits. I defined that digit to be different of the one from that image, so my number does not match the chosen image, nor any other image for that matter by the same reasoning.
My number checks out.
Function f is not a bijection.
There does not exist a bijection between N and R.
The cardinality of N is different from the cardinality of R.
Two infinite sets may have different cardinalities.
One twist to this is that Cantor’s proof has been formalized in absolutely rigorous detail, and is theorem “ruc” in Metamath.
The proof is not all that difficult to follow, and I have fairly high confidence in the underlying system (having written a verifier for it from scratch, and various other things). I’m curious what exactly the cranks would find in this proof to disagree with. It’s hard to believe it’s an individual step, as those are, as mentioned before, rigorous. My personal guess would be definitions, but again, I’d love to know which one(s) in particular.
In this instance, I think Vorlath is thinking that what functions there are from one set to another depend on how you happen to be describing the sets at any given time. (So, e.g., he thinks that if you talk about “[0,1/2], a subset of [0,1]” then you’re somehow committing to using {x->x} to map the one to the other, which means that *in that context* the former set has smaller cardinality than the latter; and that once you start talking about base-whatever digits, you’re constraining what functions you’re allowed to use, which again will make N look smaller than R even if it really isn’t.
In other words, I think he’s thinking of set theory as being rather like software development using a statically-typed language: the operations you’re allowed to perform on a given bit pattern depend on whether you’re thinking of that bit pattern as an integer, a floating-point number, a pointer, a string, etc.
At least, I *think* that’s roughly what’s motivating his complaints. I could, of course, have misunderstood.
g,
I think I’ve identified two good stumbling points. First, I think Vorlath doubts the existence or characteristics of sets when we define them in terms of other sets. Vorlath defined such sets as “dependent” because they seem to intuitively ‘depend’ on other sets for their definition and maybe even existence. Of course this is silly, the elements of a powerset of an infinite set are just as well defined as any infinite set; yes, we might refer to the definition of another set to determine whether something is an element of a powerset but we also refer to that very definition to determine whether something is an element of the original set. Furthermore we could have alternatively defined a powerset of A without referring to A by including the definition of A in our definition of the powerset.
Also, Vorlath might not be familiar with most popular constructions of number sets because he described N as ‘independent’ of R, which, based on his definition of “dependent”, doesn’t seem right.
Secondly I think Vorlath has a problem with logical quantifiers when talking about diagonalization in that he interprets our proof as saying ‘for every’ bijective function, ‘there exists’ function f which meets standards of diagonalization (which may not represent bijective functions). What we are really saying is that ‘for every’ bijective function f, f meets the standards of diagonalization. There is no loss of generality during the diagonalization.
Mark C. Chu-Carroll:
I applaud your patience in trying to explain the obvious to people who, simply, can’t get it. Like the religious ones, it doesn’t matter what you prove to them. If it goes against their hard-wired, pre-existing, beliefs and “intuition”, your argument will, in their opinion, be wrong. Try as much as you can, they’ll remain unmoved.
This comment and the ensuing, erm, noise, suggest that the problems lie rather deeper or earlier than the details of terminology in (the usual portrayal of) Cantor’s proof.
I wonder if Mark C^3 was getting flashbacks…
Another hallmark of crackpottery: suing people who criticize you.
@168:
Most of what you said is correct. Cantor’s argument won’t let go of that specific mapping.
Yes, Cantor is doing exactly what you said here. That’s the contradiction he’s using. He’s not allowing the remapping of [0,0.5] to [0,1] to happen. So no matter how many list I give you, you will map my list to [0,0.5] as proper subsets are wont to do and you will show how I’m missing an element.
@169 mike:
What if the way you use your definition of the powerset to verify the list is incompatible with the one to one mapping?
You are using _A_ mapping that is known to be different from f when you do the verification.
And there are more base 3 strings than base 2 strings. Explain why Cantor can use base 2 vs. base 1, but when we use the exact same proof on base 3 vs. base 2, the proof fails?
When you have infinite digits, there is another way to represent base 1. Simply have one and only one digit that is 1. All other digits are 0. For Cantor’s argument to work, it must be possible to produce ALL base 2 strings regardless if it’s countable or not. We do not concern ourselves with N or any of that. If you believe you need more than |N| rows (and digits), then use that. Right now, we simply want to make sure ALL infinite strings are there.
But no matter what the cardinality is of this set, I can only produce |base 1| strings. I can do this by placing all 1’s on the diagonal and 0’s everywhere else.
I’ve just proven that using Cantor’s diagonal, we can never use more than |base 1| strings as there are no free spots for strings of any other format. No matter how many infinite strings you use, this setup does not allow us to list more than |base 1| strings. This is true regardless of the cardinality of S.
So it does not matter what list I give you. You will always be able to produce more strings because you can swap out one to one any string that is in base 2 format with one that is in base 1 format (not already in the list) producing an equivalent situation.
So Cantor’s proof amounts to restricting the list to only use base 1 strings. We are not in fact free to use whatever strings we want. It’s an illusion only. And since we know it’s 100% trivially obvious that we can map infinite digits base 1 strings to base 2 strings since they’re just different representations of the same set (not to mention that’s how I defined them), something is out of whack with Cantor’s proof in that it can’t even map one to one S to S regardless of what S is or what the cardinality of S is.
Note that I did not go into N or R or whatever else. It doesn’t matter what the set is.
Vorlath,
You probably won’t read this, since your last comment is two days old, but you are really right on the verge of accepting Cantor’s proof.
Step 1. We can make a nice infinite list of all the base 1 strings. We can show that all the base 1 strings are accounted for in this list. You cannot create a base 1 string that is not on this list. Give me a base 1 string, I’ll tell you where it is on the list.
Step 2. *If* we can map all the base 1 strings to all the base 2 strings, then we can create a second list of base 2 strings and line it up with our list of base 1 strings. You are utterly convinced that we cannot construct such a list of base 2 strings, because we will always have to leave some out. You are correct. So, one list is complete, and the other list cannot be complete. This is how Cantor proves that the base 2 strings have a higher cardinality than base 1.
Cantor’s proof cannot work the same way comparing base 2 and base 3, because we already know that we cannot make an infinite list of all the base 2 strings. Similarly, we cannot make an infinite list of all the base 3 strings. With stuff missing from both lists, we can’t decide whether there is a complete mapping or not by comparing lists.
We can, however, treat the base 2 strings as co-efficients C_i in SUM_i(C_i/2^i) which will construct all the real numbers between 0 and 1. We can treat base 3 strings as coefficients D_i in SUM_i(D_i/3^i), and also construct distinct real numbers between 0 and 1. We can create an algorithm that will translate between base 2 strings and base 3 strings by making them construct the same real number. If every base 2 string corresponds to a unique real between 0 and 1, and every base 3 string corresponds to a unique real between 0 and 1, and we can define the algorithm to translate between them, we have a successful mapping between base 2 and base 3.
Once we have that mapping, then we can redefine the math such that the base 2 strings define reals between 0.0 and 50.0, or between 0 and 0.000001. The previous base 2 to base 3 mapping still holds, therefore the real numbers in a smaller or larger range than 0.0 to 1.0 are still the same cardinality as the 0.0 to 1.0 range.
I am a bit comfused about the discussion about base 1. While I can imagine how you would express an integer in base 1 (3 in base 10 = 111 in base 1) how would you express a rational number (or an approximation of a real number) in base 1?
How do you write one third in base one?
The way I understand it, Cantor’s proof uses a base (generally base 10) to construct a counterexample. This number is a counterexample whether you write it in base 2 or base 10, however it’s easiest to show it’s not in the image of f using the base the number was constructed in.
Robert,
The difficulty of translating base 1 strings to real numbers is kind of the point of Cantor’s proof, really. There’s an obvious mapping from base 1 strings to integers, and any higher base string can map to the reals, and those sets are not the same size.
I think Vorlath implied that there was some trickery involving matching base 10 integers with base 10 reals, and so wanted to discuss base 1 strings and base 2 strings. It ultimately works out the same way, IMO.
Vorlath is still wrong. Cantor is considering a mapping between the _positive integers_ from 1 upwards and the reals, and he shows that for any such mapping, we can create a real that isn’t mapped by any integer. The base in which the integers are written is irrelevant.
As others have pointed out, “base 1” isn’t even a meaningful concept for the reals. You can write the integers as tickmark counts and call that “base 1”. So what?
One thing Vorlath is claiming is that when you have a enumeration, then you’re required to state the base of it, (even though you may never write it down, and represent it only with an index ‘i’ for example), and furthermore that that base is required to be base 1.
I looked around and you can find him stating this in a blog post from a few months ago ( http://my.opera.com/Vorlath/blog/2009/06/22/cantors-theorem )
He doesn’t just say it CAN be represented that way, he says you HAVE TO do that.
I thought it was unusual when he introduced axes on the grid diagram and claimed you have to specify their base. The above quote shows that he thinks an expression of more than base 1 will be more numerous or more expressive (his intuitive take on cardinality I think) than an index of (only) base 1. Thus he thinks a false comparison was made.
Also interesting is his take on what he calls dependant and independant sets, and the indications from above of “allowed” to map something, (paraphrasing) that a set is ‘claimed’ by map, of that something is tied to something else and can’t be used for something beyond that, etc. Interesting because his other writings indicate that he has a lot of background in software writing. He seems to have take some concerns from software into his ideas about math proofs: the software ideas of memory ownership (ie responsibility to free an alloc), the notion of resources pointed-to or held-onto, generally the time-wise concerns behind software, and translated these into worries in math that a set is ‘held’ by a mapping, for example, and can’t be the domain or range of another function then, until it’s “freed” (time-wise again) and then you would be “allowed” to use it.
In other words, his definition of “number” (real or integer) is not our definition, and his definition of “set” is not ours?
Well… I can imagine that if you redefine number and set to mean different things, Cantor’s proof might not work. But if he redefines things to be different from what they’re generally accepted to be, he’s just talking gibberish.
@173 Vorlath,
“What if the way you use your definition of the powerset to verify the list is incompatible with the one to one mapping?”
1. You need to show how that’s even possible. 2. If it is possible, then we could define the same set differently in the manner I described. 3. I did not use the definition of powerset in my proof. I was careful to avoid the parts of math you are uneasy about.
“You are using _A_ mapping that is known to be different from f when you do the verification.”
No, I’m not. Prove it.
In my proof, f represents any bijective function from N to R and I only used that definition to describe what f could do.
@178:
Only if you match by digits (infinite or otherwise). So if the cardinality of digits for base 1 is the same as the cardinality of digits for base 2, then yes, base 2 will be more expressive because base 1 can only be expressed by finite consecutive 1’s or a single 1. All other combinations are not allowed.
So it’s not just base 1 and base 2 by themselves. It’s when they are matched by digit as is the case in Cantor’s argument.
You keep mucking around with this digit nonsense.
How would you even compare base-2 with base-3 using diagonalization? Show that comparing base-2 and base-3 produces a contradiction. You can’t.
@12 (yes, I know this was a long time ago), don’t you mean that Math Journals get multiple submissions a month?
@Vorlath, I am going to try to define what the standard definition of size/cardinality is into your terms.
Two sets have the same cardinality if it is possible, once removing all dependencies, to create a complete mapping between the two sets. This mapping cannot leave out elements in any set (injective mapping), and cannot have elements mapped to twice (surjective mapping)
An injective surjective mapping (an injection that is also a surjection) is called bijective or a bijection.
It does not mean that all mappings
So Cantor’s proof goes like:
1. If there is a bijection between the natural numbers and the real numbers between 0 and 1, it is possible to (given infinite time) to write the real numbers in a list. Let’s just call those numbers ai.
Do you agree with this?
2. If the digit function (in some base) is d(a,i), defined as the ith digit after the decimal point of a, then it is possible to find all the d(ai,i). Let’s call those numbers bi
Agree?
Note that bi is between 0 and the base, inclusive on 0, not on the base.
3. There is a digit other than b1. There is a digit other that b2. Etc.
Agree?
4. Construct a real number given by the lowest possible other digit than the bi.
Do you agree that this is possible?
Is this real number on the list?
NO
Thus, we find that one of the steps or one of the assumptions are false.
Most people believe that all the steps are sound, showing that there are multiple infinities.
My question to Vorlath is, which step was wrong?
This is just so I can understand what you are saying.
Other note: All bases other than base 1 can be mapped to the interval [0,1].
Cantor shows it is not possible to map base 1 into [0,1].