- The Naturals. These consist of non-negative integers (negative integers are unnatural). We can define the naturals inductively. 0 is a natural number, and for every natural number x, (x+1) is also natural.
- The Rationals. These consist of numbers that can be written "as fractions" (Postulating the existence of any other sort of number would be irrational). We can define the rationals: for every two integers x and y, x/y is in the set of rationals.
- The Reals. These consist of numbers that can be written as (infinite) decimal expansions (Any other kind of number must be imaginary). We can define the reals as the limits of sequences of binary expansions (i.e. 3, 3.1, 3.14, 3.141, 3.1415,...). In this view, real numbers are actually functions from the naturals to the rationals: A real number f corresponds to the sequence whose i'th term is f(i).
In each case, we can perhaps ascribe the disparaging labels of these class of numbers to the closed-mindedness of the namers. After all, there have been times in history when negative numbers were considered unnatural, and the square root of 2 was actually thought of as not rational. But have we gone too far? Are real numbers really real?
Real numbers pose a problem for people with a computational world view -- those that believe that in principle physical phenomena can be simulated. If quantities in the universe such as position, mass, velocity, temperature, etc. are represented by (continuous) real values, then they can't be perfectly simulated.
The first and most obvious problem we encounter is representation size -- most reals can't be finitely represented. So in any simulation with finite memory, even barring any other problems, we're just not going to have the space to keep track of even a single value.
A second and more insidious problem is even worse -- most real numbers aren't computable. That is, there is no finitely representable procedure for calculating most real numbers, even if we were to avoid the first problem by granting our simulation infinite memory, and even if we were to allow your procedure an infinite amount of time. This is because, no matter what representation you choose for writing down your finite procedure (Turing Machines are popular), the set of such procedures is only countably infinite, whereas there are uncountably many reals.
A third (related) problem is that most anything we would want to do with our real values would be undecidable. Even the problem of comparing two reals is undecidable -- consider the process of comparing the real x_T to pi, where x_T is defined to be the real with the i'th digit of pi in its i'th decimal place for all i less than T_h, where T_h is the step at which Turing machine T halts, and with the i'th digit of e in its i'th decimal place for all i greater than or equal to T_h.
So is anything in our universe actually represented by "variables" defined over the reals? Believing this seems to entail believing that the universe is inherently non-computational, regularly resolves undecidable problems and maintains information to infinite precision.
P.S. Many people object to the axiom of choice, because although it is consistent with (and independent of) other mathematical axioms, it allows for things that go counter to our intuition. For example, the Banach-Tarski Paradox: One may partition a solid 3-dimensional sphere into finitely many non-overlapping pieces, and then with only rotations and translations can reassemble the pieces into two identical copies of the original ball. But maybe it isn't the axiom of choice that challenges our intuition ("we can choose an element from any nonempty set"), which after all, seems reasonable -- maybe it is the existence of the reals and other uncountably infinite sets. It is really only these sets that require the axiom of choice -- we can choose elements from countably infinite sets without resorting to the axiom (We can define a choice function by first putting the elements of our countable set in one to one correspondence with the integers. Then we may choose the smallest element in each nonempty set.)
Can we really choose an element from an uncountable set? It seems less reasonable. Consider the reals - an uncountable set. Remove from this set all reals that can be named (or defined) - a countable set. Now choose an element!
7 comments:
"We can define a choice function by first putting the elements of our countable set in one to one correspondence with the integers." - Aren't you going to need a correspondence to the natural numbers in order to be able to get a smallest element?
Good point. Fortunately the integers can be placed in 1-1 correspondence with the naturals. :-) Actually, I suspect that the entire postscript is nonsensical.
Can we really choose an element from an uncountable set?
I don't think that the Banach-Tarski paradox is a problem, because any physical object is made of a countable set of "things" (virtual particles notwithstanding).
But here's a related problem: In probability theory, we can't choose an element from a countably infinite set in such a way that each element has the same chance of being chosen.
(To see why, suppose we pick two naturaly at random, say, x and y. There are a finite number of numbers less than x, and an infinite number greater. If each number has the same chance of being chosen, then with probability 1, y is greater than x. But by the same argument, with probability 1, x is greater than y.)
However, we can (and routinely do, at least theoretically) choose an element from an uncountably infinite set such as [0,1), such that each number has equal chance of being chosen.
How does that work?
Woah, I just noticed that you covered the "can't pick a natural number at random with equal probability" in the two envelope paradox. There you go. :-)
The version of the two-envelope paradox I describe actually doesn't rely on the ability to pick two elements from a countable set with equal probability -- I had always thought that the non-existence of a uniform distribution over the integers was the "solution" to the two-envelope paradox, but apprantly it is not.
"If quantities in the universe such as position, mass, velocity, temperature, etc. are represented by (continuous) real values, then they can't be perfectly simulated."
You've convinced me that the Reals cannot be perfectly simulated. But you haven't convinced me that physical quantities can be perfectly simulated. So why should I question whether or not pi is physically real?
Anyway, imperfect simulations are quite valuable!
This is maybe alluded to above, but I want to be more explicit: A single choice from an uncountable set (or any set) does not require the axiom of choice. If you want to avoid the ability to choose a single element from an uncountable set, you need to avoid allowing uncountable sets to exist... for that, I guess you need to get rid of the power set axiom or the axiom of infinity. (Avoid having infinite sets at all, or avoid having power sets.)
Post a Comment