Post by email@example.com Post by Dick Post by firstname.lastname@example.org
On the margin of another thread.
Let's take the set of Turing's machines with halting property.
This set is countable. There is a simple construction that will list it'
But the other half of Turing machines set still has
And how about R? Cantor has proven no bijection exists.
Cantor hasn't proven no injection exists. Or has he?
Let us make a distinction between a "surjection" and an "injection"
A "surjection" means the set can be written in a list. Cantor's construction proves that for R no surjection exists.
However, Cantor's construction does not prove that no injection exists. If there is no way to tell whether an integer object is in the list or not, there is no way to convert the injection to a surjection; the problem is then open.
This must seem unclear. To clarify, consider the set of all Computavble Real Numbers (REC). Each has an associated TM that computes it. This TM has a Gödel number. an integer. Thus there is an injection between REC and the integers. Each member of REC has an associated integer. Thus, in this sense REC is countable
However, REC cannot be arranged as a list by ANY recursive function. If it could, then the diagonalization of REC would be a computable number and would belong in REC. Contradiction!
If you want to arrange REC as a list, you must have access to the Characteristic Function or REC (This returns TRUE if n is in REC, FALSE otherwise.)
With this you can form the list. However, this is NOT a recursive function.)
Thus REC is countable (injection) but uncountable (no recursive surjection)
There are richer sets of Real numbers than REC. They have more and more of the properties of Classical Real Numbers.
In REC not every recursively enumerable sequence has a LUB.
In the next level up, this property is true. And so on.
The study of these fields is called "Reverse Mathematica."
For detrails, se Wikepedis.