Dedekind, Cantor, Conway, & Hewitt (w/ some Chomsky)

Here, I will attempt to cool down controversy on LtU over Hewitt's construction of Real by explaining it in more familiar terms. I think this will help to shed some light on Direct Logic and begin to hint why it is interesting in a PLT context.

I will borrow conceptually from John H. Conway who wrote, in "On numbers and games":

Let us see how those were good at constructing numbers have approached this problem in the past.

Dedekind (and before him the author -- thought to be Eudoxus -- of the fifth book of Euclid) constructed the real numbers from the rationals. His method was to divide the rationals into two sets L and R in such a way that no number of L was greater than any number of R, and use this "section" to define a new number {L|R} in the case that neither L nor R had an extremal point.

His method produces a logically sound collection of real numbers (if we ignore some objections on the grounds of ineffectivity, etc.), but has been criticised on several counts. Perhaps the most important is that the rationals are supposed to have been already constructed in some other way, and yet are "reconstructed" as certain real numbers. The distinction between the "old" and "new" rationals seems artificial but essential.

Cantor constructed the infinite ordinal numbers. Supposing the integers 1,2,3... given he observed that their order-type ω was a nwe (and infinite) number greater than all of them. Then the order-type of {1,2,3...,ω} is a still greater number ω + 1, and so on, and on, and on. The similar objections to Cantor's procedure have already been met by von Neumann, who observes that it unnecessary to suppose 1,2,3,... given and that it is natural to start at 0 rather than 1. He also takes each ordinal as the set (rather than the order-type) of all previous ones. Thus for von Neumann, 0 is the empty set, 1 the set {0}, 2, the set {0, 1}, ..., ω the set {0, 1, 2, ...} and so on.

In this chapter [Conway teases] we intend to show that these two methods are in reality part of a simpler and more general method by which we can construct a very large Class No of numbers, including at the same time the real numbers and the ordinal numbers, and others such as those mentioned above [e.g. infinitessimals] [....]

Hewitt can be read as constructing Real by specifying a set of 3-way partitions of the dyadic fractions between 0 and 1.

Every Real in [0..1] corresponds to three sets: {L | M | R}

The sets are ordered so that no member of L is greater than or equal to any member of M or R, no member of M is greater than or equal to any member of R.

  Zero:

  0 ≡ {{} | {} | Dyad} 
  where Dyad is the set of all dyadic fractions between 0 and 1

  One:
  1 ≡ {Dyad | {} | {}} 

Hopefully the dyadic fractions are themselves members of Real and we can memorialize that fact in a manner similar to Dedekind:

  ∀d ∈ Dyad, {dl | { d } | dr } ∈ ℝ

  where dl ≡ { x ∈ Dyad | x < d }
    and dr ≡ { x ∈ Dyad | x > d }

  Note: the Real {dl | { d } | dr } is called d.

The rationals in general correspond to regular languages as follows:

  Let Rat be the set of of sets of finite strings of 0 and 1 such that:

  ∀r in Rat, r is a regular language
    r is well ordered by a prefix relation
    ∀s in r, s is finite length and ends with 1

    rl ≡ { d ∈ Dyad | ∃x ∈ r, x > d }
    rm ≡ { d ∈ r | ∀x ∈ r, x <= d }
    rr ≡ { d ∈ Dyad | ∃x ∈ r, x < d }

   Note: the Real { rl, rm, rr } is called r }

As you can see, the subset of Real given by Rat is the set of all rational fractions between 0 and 1.

The rationals are given by certain regular languages over the alphabet {0,1}. Similarly, the constructible reals are given by certain recursivvely enumerable languages.

  Let Tructable be the set of all recursively enumerable sets of finite 
  strings of 0s and 1s, each string ending with a 1, such that each member
  of Tructable is well ordered by a prefix relation.

  By analogous construction to the rationals:

  ∀ t ∈ Tructable, { tl, tm, tr } is in Real

All rationals (dyadic and otherwise) are Tructable.

Finally, we consider a set of languages of finite strings for which the generator functions are non-deterministic.

  Let Fracs be the set of all sets of finite strings of 0s and 1s, 
  each string ending with a 1, such that each member of Fracs is
  well ordered by a prefix relation.

  By analogous construction, 

  ∀ f ∈ Fracs, { fl, fm, fr } is in Real

Note that if a member f of Fracs has a maximal element, then f is also a dyadic rational.

Note that if a member f is a regular language over {0,1}, then it is a rational.

Note that if a member of f is a recursively enumerable set, then it is a tructable real.

There are other possibilities. By a diagonalization argument, we know that Fracs contains members f which are not recursively enumerable. Those f are the unconstructible reals.

Let's suppose that the real world contains fair randomness. For example, there is a coin flip or some other kind of measurement we can repeat that will produce random outcomes. Neither heads or tails will be permanently starved. A sequence of coinflips on a given world-line will eventually produce both a 0 and a 1. Furthermore, on some world-lines, the sequence of coin flips is not described by any recursively enumerable function (at least assuming that there is no upper bound on the number of times we get to flip the coin).

The number of possible world-lines on which coin flips might be recorded is uncountable and, indeed, corresponds nicely to the members of Fracs.

In other words, a machine can enumerate the members of any f in Fracs, from shortest to longest. Such a machine, on a particular world-line, is pretty much what Hewitt means by an "Actor address".

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I think I got what that his reals are a limit

bounded by binary digits.

What confused me is that "actor" means a computer program at an address, but apparently it also means "any object that Hewitt can think up" (?at the very same time and for the very same object?)

And it also confused me that considers actors a model of computation, but now he's treating the completed and infinite result of infinite computations as not only concrete objects but as addresses...

And if the result of any infinite computation is treated as a concrete object, then you have a lot of infinite proofs to make, because I'm not so sure that hypercomputing is on a firm basis. Just because we have proofs about limits doesn't mean that you can treat general infinite computation as a single step with a concrete output all of the time.

I don't understand Hewitt's level of discourse, but it worries me that he can't jump down to my level for an overview.

I don't even understand the rest but I suspect that John Shutt is right and that this system is full of unfinished homework.

Now I suspect that Conway's numbers are interesting, carefully constructed, and maybe there's a whole bunch of fascinating math hidden in them. I have no idea if the same is true here.

josh: rigor?

I don't know what "a limit bounded by binary digits" could possibly mean.

I don't understand Hewitt's level of discourse, but it worries me that he can't jump down to my level for an overview.

It is not easy to see. It takes some effort. You can do it.

Forget Hewitt for a bit and wrestle with my (i claim isomorphic) definition of Real above. Where do you get lost?

Look

any way of squeezing a real between two converging sequences is a legitimate way to specify a real.

I think Hewitt probably mentioned spitting out digits, and you made some last page post saying that this could specify a real with a sequence one end closed, one end open line segements. That's perfectly reasonable.

If you want recast that sort of thing as sets, uhm fine. That works too?

Reasoning is finite

Let's suppose that the real world contains fair randomness. [...]

I claim that whatever you are ever able to comprehend about this world, it will be presented to you in a finite form. Even if you are able to reason about a physical process that examines infinitely many possibilities in finite time, your understanding of that process will be finite. You will assign a name to process, and will reason with finite propositions, using computable inferences that capture your understanding of physical principles, to reach conclusions. Your understanding of those physical processes will also be finite. When you learn the result of an experiment conducted using the process, you will incorporate the result into your reasoning by those same finite means.

Is it possible to analogize the mechanisms of our reasoning to infinite modes of reasoning? Yes, but it is far from clear to me that there is any point in doing so. Because the only way you'll ever get a handle on such abstract reasoning is through ordinary finite reasoning. And do you know what's harder than reasoning about real numbers? Reasoning about abstract sentences and proofs that contain real numbers as literals. So where's the value added by this extra level of indirection? It looks like nothing but a burden to me.

So for me, the first 90% of what you've written above is great stuff but well known. But as far as I can tell, fuzzy thinking is involved in the step where we should skip the finite reasoning (aka reasoning) and somehow directly work with abstract sentences that embed infinite mathematical objects. And claims about provability that only apply to this abstract reasoning system fall into the "not even wrong" category for me.

re reasoning is finite

I claim that whatever you are ever able to comprehend about this world, it will be presented to you in a finite form.

I agree that's true but I disagree I have written anything to the contrary, if that's what you mean to suggest.

You will assign a name to process,

The name of a process can be identified with a relativistic world-line. (A more detailed elaboration of this view can be found in a famous couple of papers by Leslie Lamport, "The mutual exclusion problem: parts I and II" found in the JACM, April 1986, Vol 33 No 2.)

So for me, the first 90% of what you've written above is great stuff but well known.

Yes, I am only trying to demystify Direct Logic a bit.

skip the finite reasoning (aka reasoning) and somehow directly work with abstract sentences that embed infinite mathematical objects.

A physical intuition is to picture a syntax tree for a logical Sentence reified as a data structure that includes a live computation as leaf-node terms.

also (re reasoning is finite) it's frame-dependent

A piece of hardware can decide that two bitstreams are the same because it is hard-wired with knowledge that they the streams are a single signal duplicated on two pins.

An abstract program running on that piece of hardware doesn't have the same built-in knowledge and relies on the hardware implementation of "=".

From the perspective of the abstract program, "=" can sometimes effectively compare an infinite number of bits while from the perspective of the hardware, "=" can return true in some cases without being strict in the full list of bits.

But why?

A physical intuition is to picture a syntax tree for a logical Sentence reified as a data structure that includes a live computation as leaf-node terms.

What does this simplify? What does this enable?

re What does this simplify? What does this enable?

A physical intuition is to picture a syntax tree for a logical Sentence reified as a data structure that includes a live computation as leaf-node terms.

What does this simplify? What does this enable?

That's a very open (and challengingly fun) question. For example, it enables the abstract and effective algebraic manipulation of actor programs over the type Real in a way that can be compiled straightforwardly.

the Real.[] example

This actor program describes all the partions of the dyadic fractions between 0 and 1:

  (define real () 
    (cons (either 0 1) (delay (real))))

It describes (in made-up but hopefully very clear notation) an uncountable number of lazily constructed lists of 0s and 1s.

We have some choices about the semantics of "either".

It could allow a call to "real" to produce nothing but 0s or nothing but 1s.

On the other hand, "either" could be "fair" in the sense that every call to "real" produces only finitely many 0s followed by a 1 and only finitely many 1s followed by a 0.

If we are going to define equivalence and an order relationship among calls to real, the exact definition depends on how we choose to define "either".

Either way, we still get the reals.

I don't see any good reason not to allow the value returned by a call to "real" to appear as a term in a tree that reifies some expression representing a Sentence in some logic. That's just keeping clear a distinction between the logical structure of a Sentence and a surface syntax for Sentences that can be parsed from a String.

I can see some advantage for allowing sentences to be constructed without having to parse a string. One type of example is that it would allow a program to construct first-class logical propositions that include terms such as "the stream of bits available on the standard input channel".

On another page

He and Hewitt are claiming that the fact that they have a program that spits out an infinite, unfinished sequence of random 1s and 0s that they interpret as binary digits past the binary point (ie one number in [0, 1) ) somehow shows that the number of actors is uncountable.

As if a finished infinite result of a single actor is somehow an actor and not only an actor but a continuum of actors.

I'm sorry, but this sounds like confusion to me.

They're not actors they're the potential infinite results of one actor.

Real.[ ] is *one* Actor: may be nonelement of countable set

Real.[ ] is one indeterminate Actor that may not be an element any particular countable set of reals.