So we've seen that there are as many squares as there are positive integers, and as many rational numbers as there are positive integers. That's because infinity is infinity, right? All infinite sets are infinite and therefore equal in size?

The answer, it turns out, is no. Georg Cantor, in fact, provided a simple and elegant proof that there are more real numbers even just between 0 and 1 (not counting 1) than there are integers, which is to say that there's no one-to-one mapping of real numbers and integers, though there is of rational numbers and integers.

Here's the proof. Let's assume that there is such a mapping, so that, for instance,

1 maps to 0.62584146011243...

2 maps to 0.43256984161433...

3 maps to 0.46543618463411...

4 maps to 0.68905671314112...

5 maps to 0.23348521001518...

...

Then let's construct a number based on the digits along the diagonal, with its first digit after the decimal point being 1 more than the first digit of the first number, the second digit being 1 more than the second digit of the second number, and so on (those are the underlined digits); but if some digit in the original mapping is an 8 or 9, we change it to a 0 instead of adding 1. The diagonal number for the mapping above, for instance, is 0.63508..., and the constructed number is 0.74610....

This constructed number is *not within the mapping*; it can't correspond to any integer n, because the nth digit of the constructed number is guaranteed to differ from the nth digit of the nth number in the mapping.

What's more, this is true of any mapping you can come up with. No matter how you try to map the real numbers between 0 and 1 to the positive integers, there will always be a real number between 0 and 1 that one can construct using Cantor's algorithm that will be guaranteed to be outside the mapping. Therefore, no such mapping can exist: It's not possible to map the real numbers between 0 and 1 to the positive integers. Cool, no? All infinite numbers are infinite, but some are more infinite than others.

Related Posts (on one page):

requirean actually infinite representation.If we restrict ourselves to numbers that can be definitively described by a finite description (such as "3 divided by 7" or "the ratio of a circle's circumference to its diameter"), then the proof fails. (The set of definite descriptions can be put in a one-to-one correspondence with the positive integers by ordering them lexicographically.)

I've studied Cantor's diagonalization method quite a bit, but I've never been convinced by it. My beef with it: Cantor assumes (without proof) the existence of real numbers that require an actually infinite representation.If we restrict ourselves to numbers that can be definitively described by a finite description (such as "3 divided by 7" or "the ratio of a circle's circumference to its diameter"), then the proof fails. (The set of definite descriptions can be put in a one-to-one correspondence with the positive integers by ordering them lexicographically.)

By this definition of real numbers, calculus doesn't exist.

The ratio of a circle's circumference to its diameter is indeed a transcendental number - it cannot be represented by any finite number of digits (or bits, for that matter).

In comparing the reals and the integers, while the integers are not isomorphic (has the same number as) to the reals, or [0,1]], it is interesting to note that the reals

areisomorphic the set of binary functions on the integers (i.e., the set of functions which assign either 0 or 1 to every integer).A Complete List of Real Numbers

1. 1.00000000000000

2. 0.00000000000000

3. 3.141592...

4 2.71......

and so on. The point is that we divide infinite sets into those that are countable which can be mapped onto the integers, and therefore listable, and those that are not which are referred to as uncountable.

Yes, the ratio of a circle's circumference to its diameter cannot be represented as the ratio of two integers or even as the root of a (rational) polynomial. But you

canwrite a (finite) computer program that, given enough time and memory, can produce a decimal approximation of pi to any arbitrary precision. Youcannotwrite such a program for a real number that requires an actually infinite representation (by definition).Why? I don't think any idea of intergral or differential calculus requires the use of numbers that cannot be named by a finite description. Perhaps the standard set-theoretic formalization of calculus uses such devices, but that does not mean that calculus cannot be suitably formalized under a different system.

Anonymous Coward: Where do you get this definition of real numbers from? My recipe is "Given an infinite number of placeholders, drop numbers in all the placeholders, then add a decimal point somewhere. Done." Most of these numbers can't be described finitely.

>>If we restrict ourselves to numbers that can be definitively described by a finite description (such as "3 divided by 7" or "the ratio of a circle's circumference to its diameter"), then the proof fails.

>By this definition of real numbers, calculus doesn't exist.

Sure it does, we just need to have slightly more quantitative assumptions. For instance, if we replace continuity by Holder continuity, we can keep most results about continuous functions. Keeping derivatives is more work, but we can still survive.

Weird numbers are necessary for logicians, but no one else.

And there are any number of freshmen in college who would be overjoyed were this to be the case. OTOH; a good many engineers and physicists would be quite pissed.

I think there is an infinite set of numbers with infinite non-repeating digits "that can be definitively described by a finite description." I could describe a set of numbers as "all the negative powers of pi" - each term in that definition has its own finite definition. Take that set, and you can say that it is an infinitely large set, but that it's even easier than the cantor diagonal method to prove that it doesn't include say, 1/e^3. Or even the number 1/2, for that matter.

Obviously, you could create more complex definitions of a set of numbers, and still find numbers not in that set. It is only when you define a set as an infinitely large set of numbers between 0 and 1 that all have infinitely long strings of random digits after the decimal point, when Cantor's diagonal method is even required to prove that such a set does not contain every number imaginable. Basically, Cantor's proof assumes the existence of these numbers because the definition of the set assumes the existence of these numbers - otherwise his method would not be required, and we could intuitively look at the definition of the set and choose a counterexample to the idea that "this set has all real numbers between 0 and 1 in it."

That's because the number of numbers that can be described by a finite description is countably infinite:

Proof-- You can map each description to the integers by changing each letter/number/space/punctuation to a different integer (such as ASCII) and considering the whole description as a number. Each of those is an integer and the number of integers is countably infinite.

Anyway, it's an interesting philosophical question-- does an unnameable number exist in any meaningful sense.

Here's another question- Let 'R' represent the smallest indescribable number. Did I just describe it?

Your second post (about computer programs and approximation to arbitrary precision) clearly implicates the Computable Numbers, but there are certainly useful, necessary real numbers outside this set (e.g. supremums of certain sets).

There are plenty of constructivists out there who don't accept the diagonalization argument or the Axiom of Choice or whatever, but they at least tend to reject any further math that relies on such arguments. You seem to be arguing that we can do everything we already do with Cantor's argument, without it, which is quite an extraordinary claim. (And you know what they say about extraordinary claims....)

* By "real number" I mean an ordered field with the least-upper-bound property that contains the rationals as a subfield.

I'm sorry if I gave that impression. I do not make that extraordinary claim; instead, I side with the constructivists in remaining doubtful of any results that depend on Cantor's diagonalization argument.

Indeed. I would tend to doubt that such a number exists, in the absence of any proof to the contrary.

In a nutshell: the geometric mean of the terms in the continued fraction expansion of almost every real number tends towards a constant K ~= 2.68545..., a value utterly independent of the value of the number.

(By "almost every" it is meant that the set of real numbers this is not true of have measure 0--it is true across the whole uncountable universe of reals, except at a number of isolated points.)

The funny thing is that we are utterly unable to construct a single real number for which we can actually demonstrate Khinchin's constant. For pi, e, the square root of two, etc., or any real number yet named, the proposition is false.

"Real" numbers, indeed! They are ontologically unnecessary and unjustified (though admittedly fascinating).

I do not claim that the set of all finitely-describable numbers will have exactly the same properties as the set of all real numbers.

However, I think that there is a major problem with all considerations of numbers that lack finite descriptions: There is no good reason to believe that such numbers even 'exist'. Recall that the first attempt at axiomatizing set theory, which naively assumed the existence of certain infinite sets, suffered from contradiction. In fact, I think there is good reason to remain suspicious of anything that depends on the existence of actual infinities, as it is far from clear that the notion of actual infinity is not conceptually incoherent.

I think my head would hurt less...

This doesn't require a proof that such reals existâ€”it provides one explicitly. It's true that constructivists reject the result (really, the statement itself) as meaningless, but the proof itself is still constructively valid, but with a different meaning (it can only show that there is no enumeration of the reals), since constructivists reject as meaningless or incoherent notions like a preexisting set of all the reals which could have an infinite cardinality.

This commits a fallacy answered by Aristotle. "Infinity" is a potential, not an actual. As a corollary, there cannot be "equal," "more," or "less" infinity.

The reason Calculus requires classical Reals instead of Computable Reals is the continuous nature of classical Reals. The delta-epsilon proofs of limits, and indeed the fundamental theorem of calculus, all rely on the assumption that for any real numbers A and B, there exists a real number C such that A < C < B or A > C > B (depending, of course on whether A > B). If Reals were countable (and Turing proved Computable Reals to be countable), then this property would not hold -- you could sort the list of reals, and then there would be no real number between the 42nd positive real number and the 43rd positive real number.

Umm, I think this property holds even for the set of rational numbers. Let A and B be rational numbers such that A > B. Then (A+B)/2 is also a rational number, and A > (A+B)/2 > B.

If the rationals are enumerated as in Volokh's previous post, then it is NOT necessarily the case that the nth number is less than the (n+1)th number.

I assume it is to avoid the fact that 1 = 0.999... and such. Using base 2 numbers can avoid that.

It depends on what you mean by "real number." This proof works with the definition that a real number between 0 and 1 is a sequence

0.a1 a2 a3 a4 a5 ...

where a1,a2,a3,a4... are all integers, and that two real numbers are equal if the sequences are equal element by element*.

Starting with this definition, the Cantor proofs works fine: given a list of real numbers, it produces a different real number not in the list.

The fact that the number of real number with finite description is countable then becomes a proof that numbers without a finite description do indeed exist.

*with an exception in place for numbers ending in a string of 9s, to which different rules apply, e.g. 0.99999...=1.

First, observe that we can put the set of reals between 0 and 1 into a 1-1 correspondence with the set of all sets of natural numbers by representing each real number in binary and corresponding it with the set of naturals that has the integer i whenever the ith digit is a 1. (Example: 3/8 is .011 in binary, which corresponds to {2, 3}, the set containing the integers 2 and 3). (Wrinkle: for purposes of this discussion, we'll treat 0.1000... and 0.0111... as different numbers; a more complicated proof would address this detail).

Given this, if there are the same number of natural numbers as reals between 0 and 1, there is also the same number of naturals as the number of sets of natural numbers. Now can we construct a 1-1 correspondence between the set of natural numbers and the set of sets of natural numbers? Let's suppose we can. If we assume this, then the set N of natural numbers itself (which corresponds to 0.1111...) must correspond to some natural number x. Further, the set {x} (the set containing only the number x) must correspond to some natural number y. We know y does not equal x, because x already has a set of naturals corresponding to it (the set N itself), and we've assumed the correspondence is 1-1 (so each number has one and only one set, and there can be no other).

So we've just shown that if a 1-1 correspondence between the natural numbers and the sets of natural numbers exists, then there must exist a natural number y which has the peculiar property that the set it corresponds to does not contain it. Let us call the set of all numbers with this property the "belonger set", the set of all naturals whose corresponding set does not contain them. Since the belonger set contains y, we've just shown it is non-empty.

Since the belonger set is a set of natural numbers, if the hypothetical 1-1 correspondence exists this set too must correspond to some natural number z. So it's natural to ask, does the belonger set contain the number it corresponds to? This is where Russell's Paradox comes in.

Let's suppose the belonger set does contain its corresponding integer z. Then since z is in the belonger set, by definition it is not a member of the set it corresponds to, so it can't be in the belonger set. Similarly, if z is not in the belonger set, then it is not in the set it corresponds to, so it meets the belonger set membership criteria and must be a member. In other words, the existence of a 1-1 correspondence between the set of naturals and the set of sets of naturals results in a logical contradiction. It therefore follows that no such 1-1 correspondence exists. It's easy to show that there are at least as many sets of naturals as there are naturals (in particular {1}, {2}, ...{n},.... are all sets of naturals.). So it follows that there are more sets of whole numbers then there are whole numbers. Therefore there are more reals between 0 and 1 then there are natural numbers. QED. This type of proof, where we assume what we are trying to disprove and show that it leads to a logical contradiction, is called a reductio ad absurdum proof.

Note: Another way of formulating Russell's Paradox is the army barber, who shaves everyone who doesn't shave himself.

After a bit of poking around on google, I believe the property I was thinking of that delta-epsilon proofs requires that countably infinite sets don't have is the least upper bound property. Hopefully, someone who has not only taken Real Analysis but also remembers it will jump in and rescue me at this point...

My googling also turned up a reformulation of calculus that works over computable numbers rather than real numbers.

mobathome: every ordered field contains the rationals (as its prime subfield). The reals are a complete, ordered field.

AC 39841: The field of computable numbers is interesting, but it is

countable. It's thecompletenessof the reals that makes them really useful (but uncountable). You may be suspicious of infinite constructions like completion, but they certainly don't require the full force of ZF -- you won't need to go beyond $\beth_2 = \aleph ^ \aleph$ for most mathematics.

The notion of "actual infinity" is quite cohorent. We understand it well, and the fact that you can't have "the set of all sets" only shows that you have the wrong approach to sets. The "algebraic" approach of the usual axiom system (you make sets from existing ones) won't get you in such troubles, and as mentioned above for most of mathematics you need much weaker assumptions.

You cannot do mathematics without actual infinity, especially the mathematics we use to describe the world around us. That mathematics has been vindicated whenever compared to experimental results -- or perhaps you think that this was an accident?

The fundamental point that makes the real numbers what they are is that they are complete, in the sense that all Cauchy sequences (where the points get closer to each other) converge (have a point they all get closer to). And such a continuum

mustbe uncountable. On the other hand, some of you are groping towards a definition of "computable" numbers, which are well-known to be countable, since they correspond to the outputs of Turing machines and Turing machines are easily shown to be countable.The upshot is that you just

can'thave a solid notion of continuity without uncountably infinite sets, and without throwing in numbers that you can't compute. Sure, constructivists do without them, but there are side effects you're completely glossing over here. For one,allfunctions are continuous to a constructivist. Of course, that seems counterintuitive as well, but once you throw out certain axioms a lot of things change.Look: no matter what counterintuitive result mathematicians come up with, you'll usually find that the alternative is actually

morecounterintuitive. Infinities behave weirdly, sure. But without them we don't have good notions of convergence to work with and calculus goes screwey. The Axiom of Choice implies the Banach-Tarksi theorem, but without AC we can take an infinite product of a bunch of sets and end up with nothing. Sure, you can hack something together, or say, "I don't like that", but you haven't really understood what the alternative is.Consider the subset of all real numbers that are finitely describable. This set has a complement: the set of all real numbers that are

notfinitely describable. (Call these "the indescribable reals," which would make a good name for a nerdcore band.)But once we've constructed that set, we can choose elements from it and generate descriptions therefrom. "The lowest indescribable real above 1/3", for instance. If there are

anyindescribable reals on the number line above 1/3, then theremustbe a lowest indescribable real above 1/3 (because reals are totally ordered) ... but if there is, then it has a finite description, and thus is not an indescribable real.The notion of finite descriptions of real numbers, in other words, is self-contradictory.

beforethe contradiction is resolved. (And this does not mean that one is side-stepping a difficulty.)"The fundamental fact here is that we lay down rules, a technique, for a game, and that then when we follow the rules, things do not turn out as we had assumed. That we are therefore as it were entangled in our own rules.

"This entanglement in our own rules is what we want to understand (i.e. get a clear view of).

"It throws light on our concept of

meaningsomething. For in those cases things turn out otherwise than we had meant, foreseen. That is just what we say when, for example, a contradiction appears: 'I didn't mean it like that.'"The civil status of a contradiction, or its status in our civil life: there is the philosophical problem."

Wittgenstein,

Philosophical Investigations, para 125.The explanation of Cantor's Diagonalization Theorem as presented here may look fine, but it's not the actual proof which has to discuss the fine points of the number representation scheme. (Does the method would work for base 2?) That leads to the the business of both 8 and 9 being replaced by zero. To mathematicians, the Reals are not just "all decimal numbers." They are defined in other ways.

Still Anonymous Coward has it backward. It's not whether there are a lot of numbers with infinite decimals, but whether "diagonal" sequence constructed represents a number in the set of reals.

Yes. Lots. Interactions between tax rates. Voting schemes. Congressional districts. Apportionment of congressmen between the states. Interest rates set by the Fed. Naive reliance on statistical criteria, e.g. No Child Left Behind. Probability interpretation of evidence, e.g. DNA testing. FDA testing of drug tests for safety and efficacy.

Yes, and the couple of real analysis text books I have (such as the one by Rudin) present it using base 2.

I know that the idea that pi=3 is supposed to be based on a literal interpretation of 2 Chronicles 4:2 "Also he made a molten sea of ten cubits from brim to brim, round in compass, and five cubits the height thereof; and a line of thirty cubits did compass it round about." and the very similar passage in 1 Kings 7. I don't know the connection of this to attempts at legislation. It apparently was not the motivation for the Indiana bill. It is possible that this is a conflation of the real Indiana bill and the Alabama hoax.

I should have been more precise. Obviously many issues that come before courts depend on mathematics, but in most such cases the mathematics is dealt with by expert witnesses and not directly addressed by the court. That is probably a good thing, given the extremely limited mathematical competence of most people, including judges and jurors. I was wondering about cases in which the mathematical issues were directly dealt with by the court.

reductio ad absurdum, that Cantor's diagonalization technique actually fails to construct a number. (It fails in the same way that the 14-syllable phrase "The least number not named in less than 15 syllables" fails to name a number. Cf. Frater Plotter's above post, which brings up a similar idea but reaches IMHO the wrong conclusion.)Let's consider the set of real numbers, between 0 and 1, that are (finitely) nameable -- i.e., those that can be identified by a finite description. This set can be enumerated by ordering the names in lexicographical order. Now, consider this question: does the phrase

"Cantor's diagonal for the set of nameable reals"name a real number? Suppose it does, and that it is thenth name in the enumeration. But this obviously leads to contradiction: By construction of the diagonal, thenth digit of the named number must be different from itself, a contradiction. So, the phrase must not name a number.Now, it may be argued that we aren't allowed to use the phrase "Cantor's diagonal for the set of nameable reals" when constructing the set of nameable reals, but that we are allowed to use it when we're done. But this seems too

ad hoc: it should come as no surprise that we can't map to a real number that we are forbidden to name!There's no theorem which states this. The reals are totally ordered, as are the rational reals, the irrational reals, etc, and none of these sets has a lowest member above 1/3. The Berry Paradox only applies to more discrete sets like the integers.

I'd say you're right to be suspicious, though. The "describable numbers" ironically doesn't seem like a well-defined set: who's to say what number future mathematicians might one day refer to as "Calo's Constant"? You've got to fix your language more precisely before you get to anything like what Wikipedia is calling the "definable numbers".

You might want to restrict yourself to this set, but I don't think Cantor did.

Here's a question: if we restrict ourselves to a finite description, do we have a choice about which numbers we identify, i.e. are any two such sets the same?

Constructively, Cantor's argument can't prove that there are uncountably many reals (which isn't really even a coherent claim), but it's a perfectly valid way to prove that there is no enumeration of all real numbers. The number he constructs (given a computable would-be-enumeration of the reals) is given in a very definite form--a rapidly converging sequence of rationals--which is exactly the requirement to be a real in constructive analysis.

(To those skeptics of constructive analysis, while it's true that it has some significant differences from ordinary analysis, like the lack of discontinuous functions, there is a well-developed theory which not only preserves many results from ordinary analysis, but has been used to prove new ones.)

constructively". Many people, myself included, find it to be a perfectly coherent assertion.Guess what, 1 = .111... in base 2 (binary)

Yeah, you are right. But, doesn't this work:

1 maps to 0.10100001011010...

2 maps to 0.00101000111110...

3 maps to 0.11010111010110...

4 maps to 0.10010000101010...

5 maps to 0.11110001010101...

...

Then let's construct a number based on the digits along the diagonal, with its first digit after the decimal point being a 0 if a 1 or a 1 if a 0 and so forth. Then, the constructed number is not in the list.

Could be I am wrong. Haven't taken the analysis course in 25 years.

For each integer n where 1 < n <= infinity there exists a number 1/n in the range 0 < 1/n < 1. This maps each positive integer to a decimal equivalent. You can then state that for each n > 2 there exists a number 1/n + 1/2 that exists in the range 0.5 < 1/n+0.5 < 1. This means there are at least twice as many real numbers from 0 to 1 as there are positive integers > 1.

Basically for n=2, 1/n=0.5 every future n yields a 1/n in the range 0 < 1/n < 0.5 so there are no n's mapped in the range 0.5 to 1 (exclusive). So we can add 0.5 to the 1/n's < 0.5 to map them into the empty space.

If you just want to show one set is bigger than the other, isn't that a simpler way?

What you've described is a map from the set of positive integers to the set of rationals that is not bijective. You need to prove that

nosuch mapping exists.This is not as simple as providing one counterexample. For instance the set of even numbers {2,4,6,8,...} is the same size as the set of positive integers {1,2,3,4,...} even though it's quite easy to see that there are twice as many positive integers as even numbers. When it comes to infinity (technically aleph-null) the two statements aren't mutually exclusive. This is what makes the study of infinite sets so fascinating, and what makes it so difficult to grasp.

Maybe someone said this already -- I skimmed -- but the cardinality of the set of definable numbers is indeed aleph-null, the same as the cardinality of the integers. So, yeah.