Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Reals in different fields
Replies: 3   Last Post: Apr 24, 2013 8:17 AM

 Messages: [ Previous | Next ]
 DBatchelo1 Posts: 236 Registered: 12/12/04
Reals in different fields
Posted: Apr 6, 2013 10:16 AM

There has been a great deal of discussion about real numbers; what they are, and how many of them are there. I would like to approach this from a different direction; given a particular field, how many of the theorems of classical Real Analysis are valid for it?

First, consider the classical real number field. This has the property that it is complete; every set of real numbers has a least upper bound (LUB) that is itself a real number. All the theorems of real analysis are true (of course). Many of the proofs depend on the completeness property.

There are philosophical problems with this set. Almost all of its members are undescribable. They will never turn up as the result of a computation or as the end result of any proof. Suppose you think of a real number, x. Is it meaningful to say that this x is one of the undescribable numbers? If I think of such an x, is it meaningful for me to ask you to think of the same number? (For describable numbers, such as computable numbers, this is certainly meaningful; if my choice is, say sqrt(2), I can ask you to think of the same number. If a third party asks us questions about or number, he can expect to get the same answers from each of us. This is not true if the number is undescribable.)

Let us consider a much smaller field; the field, C, of computable numbers. This field is bound up with the theory of Turing Machines (TM). If a TM is total (stops whenever it is started with a single integer on its tape) it can be associated with a Computable Real.
How much of classical Real Analysis is valid for this field?
First, note that C does not have the completeness property. There are recursively-enumerable sets of computable numbers that do not have a computable LUB.. However, many of the theorems are still true.
I believe that the properties of C have been carefully studied. I believe that Constructive Mathematics cna be regarded as the study of this field. A Constructivist does not consider a proof to be valid unless there is a possible procedure that can be executed. Constructism is therefore equivalent to the study of TMs (perhaps this is only strictly true for the Russian branch of Consructivism).
How many of the theorems of Real Analysis are provable constructively? This is complicated. Some are; some are not. A simple classical proof may divide into many constructive subcases, in some of which the theorem is true, in others it is not. The proofs are complicated. Constructivism is very difficult.

How about a larger field than the computable numbers? Sippose we include ALL the LUBs of recursively-enumerable sets of computable numbers? Alas, this does not solve the problem; there are recursively-enumerable sets of these numbers which do not have a LUB (that is one of these numbers). Try again, but the problem persists.

Change the approach a little and consider Turing Machines. Any book on Turing Machines will tell you that ~K, the set of TMs that do not stop on their own Godel number, is not recursively-enumerable. Imagine an oracle that will tell you if a particular TM is a member of ~K or not, and that Turing Machines can use this oracle. This set of TMs is larger than the original set (simple TMs).This set is called (~K)?, the jump of ~K. The jump operation can be repeated without limit. This is called the Kleene Hierarchy.
Call the oracle that generates level n of the Kleene Hierarcy oracle-n. The Tms that are total can be associated with real numbers. Call them level-n real numbers. Note:=
A) The level-n real numbers are not recursivly-enumerable. (In fact they cannot be written in a list, even with the aid of oracle-n. (If they could be, then Cantor?s Diagonalization procedure would create a paradox.. Diagonalization would create a level-n real that was not in the list that contains all level-n reals.)
B) The level-n reals can be written in a list with the aid of a level-(n+1) oracle.

The Kleene Hierarchy has no largest member. For any n, there is always a higher level, level-(n+1). In fact, the hierarchy does not stop at infinity. One can easily imagine a real number whoe n-th digit depends on an oracle-n to compute it. No problem. There is an oracle level omega that will compute this. Nor does the hierarchy stop at omega. There is a level for omega+1, omega^2 etc; through the whole set of constructable ordinals..

The set of all such members of every level of the Kleene hierarchy forms the Hyperarithemetic Set.

If a member of the Hyperarithmetic Set is total, it can be associated with a real number. Call these the Hyperarithmetic Reals.

The Hyperarithmetic Reals are (effectively) complete:-
If S is any recursively-enumerable set of Hyperarithmetc Reals the LUB of S exists and is a Hyperarithmetic Real.( In addition, the LUB is Hyperarithmetic even if S requires a level-n oracle to evaluate it.)

The Hyperarithmetic Reals cannot be written in a list. If there were an oracle that would allow you to form such a list. it would be the largest in the Kleene Hiererchy. There is no such thing. Assuming there is leads to paradox.

The set of ALL members of ALL levels of the Kleene Hierarchy is called the Hyperarithmetic Set.

If a member of the Hyperarithmetic Set is total, it can be associated with a real number. Call this set the Hyperarithmetic Numbers.

If S is a recursively-enumerable set of Hyperarithmetic Numbers its LUB is also a Hyperarithmetic Number. In fact, I believe that this is still true if the recursively-enumerable condition is relaxed to allow any kind of Hyperarithmetic process. This means that the field of Hyperarithmec Numbers is, for all practical purposes, complete. The theorems of classical Real Analysis will be true for the Hyperarithmetic Numbers. Are there any exceptions?

What does Cantor?s Diagonalization procedure prove in each of these environments.

For the Computable numbers, it shows that they are not recursively-enumerable. If there were a recursively-enumerable set containing all Computable numbers, diagonalization would produce a new Computable real that is not in the set - the well known contradiction.
In fact, the Computable numbers are a Productive Set. A Productive Set has the property that, given any recursively-enumerable subset of it there is a recursive function, the Productive Function that will produce a member of the original set that is not in the recursively-enumerable subset. For the Computable numbers, diagonalization is the Productive Function.

For the Hyperarithmetic numbers, it shows tht there is no oracle which will list them. Since the Hyperarithmetic set is the set of all numbers procuced by oracles, the numbers such an oracle produced would themselves be members of the Hyperarithmetic set. This produces a paradox; there can be no such oracle.

For the set of Classical Real numbers the procedure does not produce any very interesting results. It shows they are not listable - but so are the Hyperarithmetics.. It does NOT prove they are uncountable (mappable into the integers); any such proof would also apply to the Hyperarithmetics and each of these has an associared integer (the combination of a notation for its level in the hierarchy and the Godel number of the associated Turing Machine.) Of course, the Classical reals are uncountable; they are the powerset of an infinite set, and Cantor proved that any powerset has a larger cardinal than the original set.

Dick

Date Subject Author
4/6/13 DBatchelo1
4/6/13 fom
4/7/13 Bill Taylor
4/24/13 DBatchelo1