4 ms·

The Diagonalization Proof Without Infinite Sets

• j2kun 12y ago
  in Python: # assume every generator produces integers and is unbounded from above def diagonalize(generatorOfGenerators): currentMax = 0 for G in generatorOfGenerators: for x in G: if x > currentMax: yield x + 1 currentMax = x + 1 break
• tel 12y ago
  Introducing these generators as objects feels like new technology perhaps not so available in Gauss' time: codata/corecursion! The idea of a finite datum (ie a finitely specified program) which produces infinite "unfoldings" or operations is pretty formalized today, but not exactly amenable to standard set theory (or anything available in Gauss' time). For instance, usually in order to formulate these things in a set-theoretic method you need to reject the foundation axiom and replace it with the (aptly named) "anti-foundation axiom" which basically says that we can define "sets" which uniquely satisfy any recursive set of equations satisfying some properties. From here you get generator "objects", bisimilarity, and enough mechanism to formalize this proof nicely.
  • tel 12y ago
    I just wrote up a post describing this idea in Haskell http://tel.github.io/2014/08/04/codata_diagonalization/ http://tel.github.io/2014/08/04/codata_diagonalization/
• ArkyBeagle 12y ago
  FTA: "Suppose that we reject the actual infinite. But we allow a process that goes on forever. " Er... some infinities are more equal than others?
  • Filligree 12y ago
    Sounds like the difference between "this never happens" and "no matter how long you search, you won't see this happening". There is a difference. Honest. I'm not making it up... Sometimes I wonder.
    • ArkyBeagle 12y ago
      I guess we just use four-dimensional spacetime only when it's necessary and treat it as good old time-that-marches-on when we don't have to.
  • ot 12y ago
    No, it is just saying that the process is unbounded, not infinite. This subtle difference can be very confusing. Unbounded means: for every n, the computation can generate more than n values. Infinite means: the computation generates infinite values. Talking about infinity is usually very tricky because it is easy to run into paradoxes without a good knowledge of set theory. So many mathematicians are more comfortable using finitary arguments like the unboundedness argument above. One prominent example is calculus: despite logicians have laid down solid foundations for non-standard calculus using actual infinitesimals/infinites, most analysts prefer to use the Weierstrass epsilon-delta-like arguments, for example: lim x->0 f(x) = 0 is defined as for every epsilon there exist a delta such that |x| < delta implies |f(x)| < epsilon while with infinitesimals you can just write f(csi) is infinitesimal for every infinitesimal csi Notice how the epsilon-delta argument is similar to the unboundedness argument for the integer generator.
    • ArkyBeagle 12y ago
      But the infinitesimals invite treating them as "quantities" in an algebraic "game". That's a drill-lesson in abstraction when they're teaching you ( usually pre)Calculus, before you learn the dF(x)/dt transforms in derivative and integral tables. They also turn up in engineering contexts, which is pretty cool when it happens - it's not all just slide rule and look-up - you get to play with first principles some times when you're lucky... Wasn't me, but I got to watch. I still suspect the generators are infinite sets in the Cantor sense, just stated more politely. We're more of a habit to think in terms of ... series in that way. I recall being exhilarated by the sheer ... hubris of Cantor's approach. So I am probably biased. And as strange as it may sound, if I use infinite sets to derive the Diagonalization, then use that to assist in Godel's Theorem, it feels less like there's a tangled hierarchy when reasoning about Turing machines. That could easily be an elegance that I'm am stubborn about missing.
  • phkahler 12y ago
    >> Er... some infinities are more equal than others? That's the whole point of the diagonal argument. To prove that.
    • ArkyBeagle 12y ago
      That is absolutely true. :)
      • phkahler 12y ago
        This should not become a thing. Absolutely not ;-)