free categories viewed from a constructivist viewpoint
Hello, Let G be a directed graph that either has an infinite # of nodes or has edges which are loops. Would a constructist recognize the existence of G's free category? Thank you, Bill Halchin
Galchin Vasili wrote:
Hello,
Let G be a directed graph that either has an infinite # of nodes or has edges which are loops.
Would a constructist recognize the existence of G's free category?
<disclaimer> IAMNOT ="constructivist, logician", BUT </disclaimer> The free category consists of finite sequences of choices from an infinite set of edges; this does not require the axiom of choice, assuming the edges of the graph themselves to be constructively well-defined. Constructivists would have trouble with the "opposite" case in which infinitely many independent choices were required, even if each choice was between only finitely many options (but more than one). -Robert Dawson
At 14:00 -0700 6/6/05, Galchin Vasili wrote:
Hello,
Let G be a directed graph that either has an infinite # of nodes or has edges which are loops.
Would a constructist recognize the existence of G's free category?
Bill, In general, constructionists would have trouble with any completed infinite set. In this context, completed means that we have a list of all the elements. This is different that the situation wherein I can generate as many elements as I want (Peano axioms) but they must be built on one another. I can't speak to the "loops" part. -- best, steve Dr. D. E. Stevenson Director, Institute for Modeling and Simulation Applications Clemson University Clemson,SC 29634-0974
Galchin Vasili wrote:
Let G be a directed graph that either has an infinite # of nodes or has edges which are loops.
Would a constructist recognize the existence of G's free category?
I'm no expert on the various schools of constructivism, but every one that I know would accept this free category (at least assuming that they already accept the infinite graph G). Note that the free category on a graph with 1 node and 1 loop is the monoid of natural numbers. Although philosophers talk about finitism (even ultra-intuitionism = ultra-finitism), everybody interested in doing mathematics itself (rather than simply the philosophy of mathematics) seems to believe in the monoid of natural numbers. Conversely, once you have the set of natural numbers, an explicit description of the free category on any graph is easy. For example, a morphism from x to y (where x and y are nodes in G) consists of a natural number n and a function from {1,...,n} to the set of edges that satisfies certain equations about endpoints. So if you believe in the set of natural numbers and you believe in G, then you ought to believe in the set of morphisms; and the rest is yet easier. Even a finitist can ~talk~ about this, even if they don't ~believe~ in it, in much the same way that a ZFC dogmatist, who believes only in small sets, can nevertheless talk about large categories with no difficulty. So only an ultra-finitist should have any problems; but ultra-finitism is a pretty ill developed approach anyway. -- Toby
The free category on the 1-vertex 1-edge graph is just the monoid (N,+,0) of natural numbers. Although it was somewhat fashionable in the 19th century to distinguish actual existence of numbers from the potential existence of the set of all numbers, the actual-potential distinction has since faded in importance for most constructivists. A more modern constructive concern would be with the existence of a well-ordering of the continuum. That aside, the odds are good that anyone who did not recognize the existence of the natural numbers is likely to doubt that you could produce a graph having an infinite number of nodes. If you're prepared to produce the latter, why would it bother you to have someone produce the former? Vaughan Pratt ----------- Galchin Vasili wrote:
Hello,
Let G be a directed graph that either has an infinite # of nodes or has edges which are loops.
Would a constructist recognize the existence of G's free category?
Thank you, Bill Halchin
Dear Bill, Most constructivists would not have problems with this, despite the fact that at any finite stage of the construction you have only a finite approximation to the infinite category. Eventually (in finite time) you can get any finite part of the category, including the knowledge of any finite set of the equalities between objects or morphisms, and that is normally considered good enough. Computationally, a programming language such as Haskell is happy to deal with infinite objects. The computations never terminate, but every finite approximation to the object is obtained in finite time. For instance, one function might generate the decimal expansion of pi and another function may take that as input and calculate its square. In topos-valid constructivism the way it works is this. In an arbitrary elementary topos you can't always construct the free categories over graphs. But as soon as you admit a natural numbers object other free algebra constructions, such as the free category, come along with it. Regards, Steve Vickers. Galchin Vasili wrote:
Hello,
Let G be a directed graph that either has an infinite # of nodes or has edges which are loops.
Would a constructist recognize the existence of G's free category?
Thank you, Bill Halchin
I don't have any problem with the general idea expressed below and my objection doesn't apply at all to the free category construction, but I just wanted to point out that seeing constructible numbers as infinite decimals just does not work. Bishop in his book Constructive Analysis, gives an example of two numbers with constructible decimal expansion of which no single digit of the sum is (currently) constructible. I don't think this problem would arise in pi^2, but who knows. At any rate, for him a constructible is given by a sequence of rationals q_1,q_2,..., whose numerators and denominators are recursively enumerable sequences of integers and for which |q_n - q_m| < 1/n + 1/m. When you add two such sequences, you have to take every second term of the sum and multiplication involves more drastic trimming. Moreover, division is possible only if you can prove that eventually |q_n| > 1/N for some fixed N. So what you get is a local ring, not a field. On Thu, 9 Jun 2005, Steve Vickers wrote:
Dear Bill,
Most constructivists would not have problems with this, despite the fact that at any finite stage of the construction you have only a finite approximation to the infinite category. Eventually (in finite time) you can get any finite part of the category, including the knowledge of any finite set of the equalities between objects or morphisms, and that is normally considered good enough.
Computationally, a programming language such as Haskell is happy to deal with infinite objects. The computations never terminate, but every finite approximation to the object is obtained in finite time. For instance, one function might generate the decimal expansion of pi and another function may take that as input and calculate its square.
In topos-valid constructivism the way it works is this. In an arbitrary elementary topos you can't always construct the free categories over graphs. But as soon as you admit a natural numbers object other free algebra constructions, such as the free category, come along with it.
Regards,
Steve Vickers.
Galchin Vasili wrote:
Hello,
Let G be a directed graph that either has an infinite # of nodes or has edges which are loops.
Would a constructist recognize the existence of G's free category?
Thank you, Bill Halchin
10-Jun-2005 11:54:26 -0300,6270;000000000000-0000000e
What Mike says is correct. I oversimplified for the sake of keeping the story short. The core truth of what I said is that real programming languages (such as Haskell) can deal with infinite structures that represent real numbers exactly, and can do arithmetic on them. But, for the reasons Mike referred to, they do not use decimal (or binary) expansions. One simple alternative is to use infinite sequence of signed binary digits +1, 0 or -1. This is highly redundant - there may be many representations of any given real. But the redundancy has the effect that output can always proceed and doesn't get blocked. Example: In ordinary binary fractions, 1/4 can be either .0100000 ... or .0011111 ... If you add these together, you can never get even a single digit. At any given finite stage, for all you know the answer may be very slightly less than 1/2, in which case the first digit would have to be 0, or very slightly more, in which case the first digit would have to be 1. With the added flexibility of negative digits, you can safely output +1 for the first digit since negative digits later can take the answer back below 1/2. Sorry if anyone was misled, Steve Vickers. On 9 Jun 2005, at 20:39, Michael Barr wrote:
I don't have any problem with the general idea expressed below and my objection doesn't apply at all to the free category construction, but I just wanted to point out that seeing constructible numbers as infinite decimals just does not work. Bishop in his book Constructive Analysis, gives an example of two numbers with constructible decimal expansion of which no single digit of the sum is (currently) constructible. I don't think this problem would arise in pi^2, but who knows. At any rate, for him a constructible is given by a sequence of rationals q_1,q_2,..., whose numerators and denominators are recursively enumerable sequences of integers and for which |q_n - q_m| < 1/n + 1/m. When you add two such sequences, you have to take every second term of the sum and multiplication involves more drastic trimming. Moreover, division is possible only if you can prove that eventually |q_n| > 1/N for some fixed N. So what you get is a local ring, not a field.
10-Jun-2005 11:54:26 -0300,3729;000000000000-0000000c
participants (7)
-
Galchin Vasili -
Michael Barr -
Robert J. MacG. Dawson -
Steve Stevenson -
Steve Vickers -
Toby Bartels -
Vaughan Pratt