Are The Specifiable Reals Well Defined

Subargument broken off UnknowableNumbers

Thesis:

Consider all finite-length programs that specify a single real number. Call each such program a "specification". Call the number produced by such a program a "specifiable real" or "knowable number". There is a countably infinite number of such programs. Since there are uncountably infinite number of real numbers, there are uncountably many reals that we cannot specify, even in principle. Call these "other" real numbers "unspecifiable reals" or "unknowable numbers".

One such specification is: "Print the real number specified by 'diagonalization' on the set of specifiable reals."

(Diagonalization of a set generates a real number *different* from any other real number in that set.)

This specification leads to a contradiction, and so needs to be deemed invalid (ie., not in the set). However, excluding it from the set avoids the contradiction, making it a valid (albeit 'excluded'!) definition of a real not in the supposedly all-inclusive set.

Conclusion:

A 'satisfactory' definition for the above set is impossible, since it needs to exclude diagonalization over the reals defined by the set, which generates a further real.

-- VickiKerr

Actually, the conclusion is that "Print the real number specified by 'diagonalization' on the set of specifiable reals." is not a specification. It is never demonstrated that there is a finite-length program which will produce that number. Without it (and I don't see how to produce one), the "paradox" resolves into a proof of that such a program doesn't exists.

The original discussion of the above point is below.

Response: What does it mean to be a definable/specifiable real? Can someone remind us what the definition of a real number is?

A finite-length program (which can be expressed as a finite-length string) can specify a particular real number. For example,

    print("0.125") -- same as print(1/8);

    print("0."); while(1){ print("3"); }; -- similar to print(1/3);

    print("0."); n=0; while(1){ print(n); n=n+1 }; -- an irrational number.

Any real number that can be specified by at least one finite-length program is "specifiable" or "definable".

The precise definition of a real shouldn't matter. Roughly, a real is an integer or an integer plus a limiting value such as 0.13259749... (where any sequence of digits is allowed, each giving a different real, except that the sequence should not be all 9's or all 0's from some point onwards (if infinite), and ends in a non-zero digit if finite).

See UnknowableNumbers for examples.

Response 1: The countable set of all (?) specifiable reals yields another one (using diagonalization)

Unfortunately, there seems to be a flaw in Michael's reasoning. The method of diagonalization can be applied to the countable set of definable numbers to "define" a new number - a contradiction. -- VickiKerr

To clarify, the situation is a form of BerrysParadox.

Bearing the above in mind, let's return to considering the "knowable" reals. If we can find suitable rules as to which finite definitions are valid, the set of knowable reals exists, and is countable. A new real can be formed from this set by diagonalization, but to avoid contradiction, the rules must make this real unknowable.

In other words, we need rules to define the set of knowable reals, but whatever rules we choose, an unknowable number (as categorized by those rules) is found by simply using diagonalization (which necessarily is not applicable to that set in any finite definition which is valid under those rules).

It has been suggested that a valid definition using diagonalization is flawed for the knowable reals because one cannot specify a unique ordering of the knowable reals. However, this seems to be just an attempt to avoid Berry's paradox. Anyway, a unique ordering is probably achievable by using alphabetical ordering of the corresponding definitions.

No it is not. It was explained that producing a specifiable alphabetical ordering requires solving the HaltingProblem for all Turing Machines. In producing an ordering you cannot make use of any prior knowledge as to which specifications correspond to reals. You may order all specifications but you may not order all valid specifications. And if you try to use all specifications in the diagonalization then the diagonalization itself becomes unspecifiable (either because it assigns no number to the digits corresponding to invalid specs or because it again tries to solve the Halting Problem in determining whether a spec is valid). If you can't order the specifiable reals by themselves and you can't order them by their specifications then you can't order them at all.

I accept you need to solve the HaltingProblem if you want to claim an actual construction of the ordering, but I did not claim that. The ordering I stated was intended to be well-defined, but not constructive. -- VickiKerr

The unfortunate situation is reached that although unknowable reals exist, one needs rules for describing them which are to some extent arbitrary. This is just what Michael was trying to avoid.

Warning: there are numerous internet pages attempting to resolve Berry's paradox, many of which are hard to follow and probably resort to faulty reasoning. Perhaps this is one of them now!

Where do we go from here?

-- VickiKerr [with apologies for removing the original text of the comments by JoshuaGrosse and others]

AlistairCockburn: Sorry, Vicki, I can't get into BerrysParadox, so you certainly have cut me off there. However,... while I am willing to agree that there is another real formed by diagonalizing, I am not yet willing to agree that that number is well specified, given the rules for specification we started with. That new number exists, but may not be a Knowable Number. E.g., it is not actually specifiable, exactly as "the smallest positive real" isn't. Do you see what I'm after?

I regret that Berry's paradox is fundamental here. The smallest positive real simply doesn't exist, so that's a different type of failure. -- vk

The real formed by diagonalization can't be knowable as it differs from every knowable real. -- vk

Arguments should be rehearsed on the original Berry's paradox before being extended to the case of knowable real numbers.

It seems to me that Berry's paradox just means you can't use definability in that particular way, but doesn't break the concept, just like BertrandRussell's paradox does for sets. What am I missing here, Vicki? -- JoshuaGrosse

[Possibly nothing, although I wasn't trying to break the concept completely, but rather the rules-independent aspect which MC was originally aiming for. I notice you don't define 'that particular way', but that may not matter much.]

My instinct is to define specifiability in terms of ChurchNumerals and to avoid paradoxes by using a paraconsistent successor function (or just paraconsistent lambda application, whatever that might mean). You'd no longer be working on R, though, then. If you know more about paraconsistent arithmetics please get in touch! -- DanSheppard

I thought I could build a simpler paradox involving just 2 or 3 specifications, rather than "the set of all specifiable reals". Drawing an analogy from the HaltingProblem, the specifications would examine the string representations of each other, and one would try to predict the other's output, while the other would try to contradict the first one (say, emit a number 1 greater than the other, or having 1 more decimal place, or ...).

I think I need to sleep on it.

The Real numbers are a combination of the rational numbers (ratio of two whole numbers), and the irrational numbers (think pi, e, etc). There is a proof (which I will not repeat here), that the rational numbers are countable (infinite, aleph-null), while adding the irrational numbers makes the reals uncountable (uncountably infinite, aleph-one). -- ChuckCottrill

The Real numbers are