Re: How to do magic with infinity

From: Eray Ozkural exa (examachine_at_gmail.com)
Date: 10/25/04 

Date: 25 Oct 2004 03:48:24 -0700

"Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message news:<A5Med.34142$QJ3.25542@newssvr21.news.prodigy.com>...
> "Category theory is a relatively young branch of mathematics, stemming from
> alge­braic topology, and designed to describe various structural concepts
> from different mathematical fields in a uniform way. Indeed, category theory
> provides a bag of concepts (and theorems about those concepts) that form an
> abstraction of many concrete concepts in diverse branches of mathematics,
> including computing science.
> Hence it will come as no surprise that the concepts of category theory form
> an
> abstraction of many concepts that play a role in algorithmics."
>
> http://wwwhome.cs.utwente.nl/~fokkinga/algorithmics.html
> In algorithmics, also known as the mathematics of program construction, one
> looks at formal methods to construct programs. The most important question
> is not so much how a program can be derived from a specification, but rather
> how that can be done effectively and efficiently (and elegantly).
>
> Looking at international research on this subject, there appears to be much
> attention for the method of program transformation: derive a program in a
> step-by-step way through a series of "transformations" that preserve the
> meaning and hence the correctness. A significant practical problem is that
> very many steps seem needed: the individual steps are too small. In
> algorithmics a solution to this problem is searched for: formalisms and
> theories are developed with which a whole series of little steps can be
> combined into one single step at a higher level. Compare this with the
> development of higher programming languages: these make it possible to
> express compactly what needs many instructions in an assembler language. It
> also resembles the way mathematics is built up with concepts, notations, and
> theorems that are used in later proofs.
>
> An important source of inspiration for the research are concrete algorithms,
> or rather classes of algorithms. For instance, what is the essence of
> parsing methods, or of shortest path methods? How can we express the
> derivation of these algorithms in a clear and succinct way? What systematic
> theory can be set up? In this research quite fundamental questions pop up,
> that can be well studied with tools like category theory and type theory.
> And besides theory formation, there is also an important more practical
> aspect: the development of tools that support this formal method of program
> construction, like ``incremental proof editors''.

Thanks for these remarks, indeed these are quite relevant for my
inquiry.

I cannot decide which one should come first: category theory or set
theory. Both give formalizations of "collection", so it would seem
that they may lead to different foundations of mathematics, although I
cannot clearly see how category theory could replace set theory in so
many theorems. At any rate, I have a great like for category theory,
and I would like to read a bit about the above mentioned automatic
program synthesis work using category theory.

Category theory could be fruitful for another reason: its theorems and
proofs are short, e.g. its statements seem to be more compact. There
was a famous category theoretical proof of Godel's first
incompleteness theorem in a few sentences. Since that is possible,
perhaps if we adopted the language of category theory, it would be a
lot easier to express some of the ideas running
here, such as formalizing Han's approach.

My method had to do with programs that generated these sets. You look
at how much space-time they consume in relation to each other, you
measure infinite sets in terms of computational costs, so a hierarchy
of countable infinite (magnitudes) becomes sensible. The algorithmics
research could be the solution here, because these explanations need
rigor, and without using set theory.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: How to do magic with infinity
    ... > "Category theory is a relatively young branch of mathematics, ... > In algorithmics, also known as the mathematics of program construction, one ... > algorithmics a solution to this problem is searched for: formalisms and ... > theorems that are used in later proofs. ...
    (sci.math)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... formalisms, and when I ask for an example of it actually doing ... theorems then you get variations of those theorems (including the ... if "that's a standard result that appears in standard texts" is ... you show a commonality between different branches of Mathematics - all ...
    (sci.logic)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... formalisms, and when I ask for an example of it actually doing ... theorems then you get variations of those theorems (including the ... if "that's a standard result that appears in standard texts" is ... you show a commonality between different branches of Mathematics - all ...
    (sci.logic)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ...  It's the *axioms* ... If no more theorems to generate, ... bastardizing the notion of an axiomatic system to the point that it ... The program was to be able to rewrite all mathematics starting using ...
    (sci.logic)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... It's the *axioms* ... If no more theorems to generate, ... Otherwise it's not an axiomatic system. ... The program was to be able to rewrite all mathematics starting using ...
    (sci.logic)