pageok
pageok
pageok
Beyond Infinity:

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.

John (mail):
All well and good. But which infinity is the number of handguns in D.C.?
11.21.2007 7:35pm
Eugene Volokh (www):
Compared to infinity, even very large finite numbers are very small.
11.21.2007 7:38pm
chrismn (mail):
Not to be too pedantic. (OK. Precisely in order to be pedantic): Infinity is not a number. It is a description of a set, as in, the set of integers has infinitely many elements. So, not all sets with an infinitely many elements are the same size. Some are bigger than others.
11.21.2007 7:44pm
Anonymous Coward #39841:
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.)
11.21.2007 8:10pm
Armen (mail) (www):
And stay tuned tomorrow for an explanation of the set of all sets that contain themselves. Or a turkey containing something.
11.21.2007 8:14pm
Edward Lee (www):
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.
11.21.2007 8:26pm
Oren:

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 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).
11.21.2007 8:28pm
Zathras (mail):
I can't believe I missed this set of posts earlier.

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 are isomorphic the set of binary functions on the integers (i.e., the set of functions which assign either 0 or 1 to every integer).
11.21.2007 8:40pm
An MIT Graduate:
This reminds me of a shirt the Undergraduate Math Association made at the Institute. It said:

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.
11.21.2007 8:41pm
Anonymous Coward #39841:
Oren said:


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 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).

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 can write a (finite) computer program that, given enough time and memory, can produce a decimal approximation of pi to any arbitrary precision. You cannot write such a program for a real number that requires an actually infinite representation (by definition).
11.21.2007 9:00pm
Anonymous Coward #39841:
Edward Lee said:

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

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.
11.21.2007 9:08pm
Math_Mage (mail):
Oopsie. Just posted this in the comments section of the rational-numbers post.

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.
11.21.2007 9:10pm
Some Mathematician (mail):
Edward Lee, in response to:
>>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.
11.21.2007 9:14pm
Ian Argent (www):

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



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.
11.21.2007 9:24pm
Shane (mail):
Anonymous Coward (I feel like I'm starting a flame war when I address you by that name),

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."
11.21.2007 9:42pm
A Berman (mail):

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.

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?
11.21.2007 9:47pm
billb:
AC #39841: The numbers you describe (in your first post) cannot be put in a one-to-one correspondence with the natural numbers because they lack a constructive definition. At best, to construct them you would need a (countably) infinite dimensional space of possible statement classes each containing a countably infinite number of statements, and N^N, which is the same size (it's of size \aleph_0^{\aleph_0}, in fact), can't be put in one-to-one correspondence with N.

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....)
11.21.2007 9:50pm
mobathome:
Anonymous Coward #39841: I see a flaw with your idea. You say you deal only with finite descriptions, but you don't put any limitations on the collection of "words" you use to make up your descriptions. Unless you can show that you only need at most a countable number of words to express in finite descriptions all that we expect of the real numbers*, you may have sneaked in something uncountable. Then your criticism of Cantor's proof is invalid.

* By "real number" I mean an ordered field with the least-upper-bound property that contains the rationals as a subfield.
11.21.2007 9:58pm
Anonymous Coward #39841:
billb said:

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.

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.
11.21.2007 10:06pm
Anonymous Coward #39841:
A Berman wrote:

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

Indeed. I would tend to doubt that such a number exists, in the absence of any proof to the contrary.
11.21.2007 10:14pm
devin chalmers (mail):
A nifty fact about real numbers (what a misnomer!) is found in Khinchin's Constant.

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).
11.21.2007 10:41pm
Anonymous Coward #39841:
mobathome said:

Unless you can show that you only need at most a countable number of words to express in finite descriptions all that we expect of the real numbers*, you may have sneaked in something uncountable. ...
* By "real number" I mean an ordered field with the least-upper-bound property that contains the rationals as a subfield.


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.
11.21.2007 10:47pm
Sean M:
As the individual in the thread with his B.A. in Philosophy, can we go back into posts whose comment threads dissolve into partisan sniping?

I think my head would hurt less...
11.21.2007 10:57pm
Henry T:
Anonymous Coward: Given a countable enumeration of the real numbers, the real number constructed by Cantor's argument is as constructive as anyone could want (and, for example, acceptable even by Brouwerian standards). Given an algorithm for enumerating the real numbers, the Cantor argument gives a sequence of rationals approximating the desired real, with the property that, after n steps, we know the value of the real to within 1/10^n. This is precisely the standard constructive definition of a real (a computable Cauchy sequence of rationals with an a priori given rate of convergence).

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.
11.21.2007 10:59pm
Dave N (mail):
My head hurts--and this series of posts reaffirm that I was right to enter the law and not mathematics as my chosen profession.
11.21.2007 10:59pm
Javert:
"All infinite sets are infinite and therefore equal in size?" "All infinite numbers are infinite, but some are more infinite than others."

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.
11.21.2007 11:25pm
Maniakes (mail):
The definition of real numbers Anonymous Coward #39841 is proposing is better known as Computable Real Numbers.

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.
11.21.2007 11:46pm
Kovarsky (mail):
the newish david foster wallace book on infinity has a nice discussion of this proof, and cantor generally.
11.21.2007 11:59pm
Anonymous Coward #39841:
Maniakes said:

... 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.
11.22.2007 12:36am
egn (mail):
IANAM -- Can someone explain why the 8 has to be changed to a 0 and not a 9?
11.22.2007 12:39am
TonyH:
If you allow for 9s you can get a decimal terminating in an infinite string of 9s, which would destroy the uniqueness of the new decimal expansion (for example 0.999999 repeating is equal to 1). So you wouldn't necessarily have a new element that wasn't already enumerated in the list. It's sort of a trivial point, but necessary for rigor.
11.22.2007 12:57am
Mike Keenan:
"IANAM -- Can someone explain why the 8 has to be changed to a 0 and not a 9?"

I assume it is to avoid the fact that 1 = 0.999... and such. Using base 2 numbers can avoid that.
11.22.2007 1:00am
pierre menard (mail):
Anonymous Coward:

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.
11.22.2007 1:02am
ReaderY:
There's another elegant proof that uses Russell's paradox.

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.
11.22.2007 1:14am
Maniakes (mail):
Anonymous Coward #39841, you're right -- my claim doesn't work. Math isn't my field, and it's been a few years since college.

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.
11.22.2007 1:30am
Lior:
egn: It really doesn't matter. All you need is a rule for changing the digits to make sure the "diagonal" number you make is different from all the numbers in the list. You could use the rule "change all digits to 3 except 3 which gets changed to 7", the one "add 1 to all digits except 9, which becomes 0" or "add 1 to all digits except 8,9 which become 0". The all work equally well.


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 the completeness of 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?
11.22.2007 1:33am
Lior:
Sorry for the runaway bold tag.
11.22.2007 1:37am
Gil (mail) (www):
Lior had two unmatched bold tags. He closed one of them, and I've closed the other (I hope).
11.22.2007 1:50am
Eli Rabett (www):
Stick to your day job.
11.22.2007 2:20am
John Armstrong (mail) (www):
Those running off about constructivists have a rosy view of constructivism. Those saying that calculus falls apart are right.

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 must be 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't have 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, all functions 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 more counterintuitive. 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.
11.22.2007 2:21am
Watzilaus Wondratschek (mail):
For those of you interested in a more literary description of the paradoxa of set theory, I would suggest the book "White Light" by Rudy Rucker. You find more in http://en.wikipedia.org/wiki/White_Light_%28novel%29
11.22.2007 3:46am
Frater Plotter:
The problem with restricting to the set of finitely describable numbers is that this set embodies a Russell paradox.

Consider the subset of all real numbers that are finitely describable. This set has a complement: the set of all real numbers that are not finitely 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 any indescribable reals on the number line above 1/3, then there must be 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.
11.22.2007 5:25am
Arkady:
"It is the business of philosophy, not to resolve a contradiction by means of a mathematical or logico-mathematical discovery, but to make it possible for us to get a clear view of the state of mathematics that troubles us: the state of affairs before the 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 meaning something. 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.
11.22.2007 6:40am
Zathras (mail):
For a bit more technical exploration of the problems in set theory with Russell's paradox, the book Vicious Circles is very good.
11.22.2007 7:07am
Paul Dietz (mail):
An amusing theorem that relates to all this is that any 'reasonable' (technical details omitted) collection of axioms for set theory admits a countable model. So, all the sets in that model are countable. This is not actually a contradiction, since the bijections with the natural numbers needed to prove countability do not all exist within the model itself.
11.22.2007 9:50am
seadrive:
I'm glad Prof. Armstrong is here to keep order.

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.
11.22.2007 1:38pm
Bill Poser (mail) (www):
So, are there any legal decisions that rest either on mathematical reasoning beyond trivial arithmetic or on false assumptions (e.g. that there is only one order of infinity)? The closest example that I can think of is the attempt of fundamentalist Christians to legislate an incorrect value of pi.
11.22.2007 2:39pm
seadrive:

So, are there any legal decisions that rest either on mathematical reasoning beyond trivial arithmetic or on false assumptions.


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.
11.22.2007 3:05pm
Mike Keenan:

Does the method would work for base 2?



Yes, and the couple of real analysis text books I have (such as the one by Rudin) present it using base 2.
11.22.2007 3:37pm
Eugene Volokh (www):
Bill Poser: I'd heard stories about the attempts to set pi at some other number; the Straight Dope account of it is here. Can you point me, though, to sources that report that it was "Christian fundamentalists" who were trying to do it?
11.22.2007 7:41pm
Bill Poser (mail) (www):
Eugene,

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.
11.22.2007 8:38pm
Bill Poser (mail) (www):


So, are there any legal decisions that rest either on mathematical reasoning beyond trivial arithmetic or on false assumptions.

es. 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.


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.
11.22.2007 8:42pm
Anonymous Coward #39841:
I realize now that I've been a bit vague on why I object to Cantor's method, so I'm going to give an argument on why I think it leads to contradiction. I'm going to argue, by 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 the nth name in the enumeration. But this obviously leads to contradiction: By construction of the diagonal, the nth 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!
11.22.2007 10:18pm
roystgnr (mail):
"If there are any indescribable reals on the number line above 1/3, then there must be a lowest indescribable real above 1/3 (because reals are totally ordered)"

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".
11.22.2007 11:19pm
seadrive:

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.


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?
11.23.2007 8:47am
Henry T:
AC: Your argument refutes the claim that you can write down a single list of all nameable real numbers, not the diagonalization method. As soon as you declare that you have a fixed listing of all numbers, that listing can itself be used to name a new one. (There are connections to Godelian incompleteness here.)

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.)
11.23.2007 11:10am
Henry T:
That should say "which isn't really even a coherent claim constructively". Many people, myself included, find it to be a perfectly coherent assertion.
11.23.2007 11:26am
Brian Macker (mail) (www):
"I assume it is to avoid the fact that 1 = 0.999... and such. Using base 2 numbers can avoid that."

Guess what, 1 = .111... in base 2 (binary)
11.23.2007 4:25pm
Mike Keenan:

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.
11.23.2007 4:52pm
Smokey:
11.23.2007 5:20pm
Choy (mail):
Hmmm... Just ran across this and it seems overly complicated to me. Wouldn't it be more easily understood to say:

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?
11.26.2007 1:49am
heedless (mail):
Choy,


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 no such 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.
11.26.2007 11:48am
Kent G. Budge (mail) (www):
"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."

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.
11.26.2007 12:14pm